пятница, 18 сентября 2015 г.

Три коробка спичек

Давно ли вы ходили в походы? Если не очень, то должны помнить, что в походе бывают нужны спички. Нормальные сухие спички. И вот по этому поводу вспомнилась задачка. (Впрочем, деталей оригинальной задачки я все равно не помню, так что додумывал сам.)

У вас есть три коробка по 20 спичек в каждом. Однако известно, что какой-то один из них полностью состоит из хороших спичек, а в двух других половина (10 штук) спичек бракованные и непригодны для использования. Однако на ощупь брак никак не опознается, поэтому различать коробки вы не умеете.
Вы можете попытаться поджечь любую из спичек. С бракованной спичкой, естественно, ничего не случится, а хорошая загорится. Беда в том, что после этого ее уже нельзя будет взять в поход. Такую операцию назовём тестированием спички. Вы можете тестировать столько спичек, сколько захотите. 

1. Какое (в худшем случае) количество хороших спичек вам удастся взять в поход? (Брать в поход бракованные спички ни в коем случае нельзя.)

2. Попробуйте придумать алгоритм, который позволяет отобрать это количество, затратив при этом наименьшее (в среднем) число тестирований. 

2 комментария:

  1. в худшем случае у нас в руках окажется хороший коробок и на проверку этого мы потратим 11 спичек, останется всего 9
    если же у нас сначала в руках окажется бракованный коробок, то в худшем случае мы потратим все его 10 хороших спичек на проверку, после чего у нас останется два непротестированных коробка

    ОтветитьУдалить
  2. Если жечь по одной спички из каждого коробка (round-robin) и отбрасывать коробок если одна спичка не зажжётся - в худшем случае мы сожжём 31 спичку (11 из хорошего коробка и по 10 из плохих) и 9 спичек останется.

    ОтветитьУдалить