На одном крупном банкете произошел инцидент - какого-то гостя попытались отравить.
Всех сразу эвакуировали. Когда прибыли полицейские, они увидели на огромном столе стаканы с вином, и уже никто из свидетелей не помнил, где сидел потерпевший. Но было точно известно, что отравленный стакан - один, а всего стаканов было от сотни до двухсот.
Нужно было определить, какой стакан отравлен.
Эксперт сказал, что не имеет смысла проверять каждый стакан - это дорого и долго.
После того, как эксперт сосчитал стаканы , он сказал:
- Мы будем брать небольшое число жидкости из нескольких стаканов, и проверять смесь, таким образом, нам не понадобится и десяти проверок, чтобы выявить отравленный стакан!Но при этом, взяв один стакан, он заявил, что надо исследовать его первым - и это не будет растратой попыток впустую.
Свою оптимальную методику он наметил исходя из подсчитанного им числа стаканов.
Исходя из этих данных можно заключить, какое точное число стаканов стояло на столе.
Ответ: 129. 129-1 = 128 это единственная степень двойки больше ста и меньше двухсот. А оптимальный метод заключается в поэтапном отбросе половины количества оставшихся стаканов.
Комментарии
Кто понял, объясните пожадуйста..
Я тоже ничего не поняла
Не уловил.
Если их к примеру 200, с чего начали считать я, собственно.
1. 100 и 100
2. 50 и 50
3. 25 и 25
4. 12 и 13+
5. 6 и 7+
6. 3 и 4+
7. 2 и 2
8. 1 и 1
И тоже укладываюсь в менее чем 10 действий.
С помощью одной попытки можно определить лишь ту половину стаканов, в которой находится стакан с ядом. Всего 9 попыток. Со 100% результатом с помощью одной попытки можно определить лишь какой из двух стаканов отравлен. Далее со 100% результатом можно определить какие 2 стакана из 4 отравлены. Таким образом с помощью 8 попыток можно определить отравленный стакан лишь из 128 стаканов. Так как эксперт предложил проверить 1 из всех стаканов то всего получается что 129 стаканов
Раскладка с 200-ми стаканами тоже верна, да и вообще под условия задачи попадает любое количество стаканов и даже более, например: до 256 при 8 замерах и 512 стаканов! при 9 замерах. В задаче нет никакого пояснения о условиях формирования числа каждого замера, делить то можно не точно поровну, но и n/n+1.
Эксперт потратился впустую на 1 стакан, кстати))
Эксперт предложил следующий метод: сливать жидкость сразу из нескольких стаканов и брать пробу на яд. Допустим у нас 16 стаканов - берем 8 - сливаем из них жидкость и берем пробу - если яд обнаружен - значит отравлен один из этих восьми, если нет, то отравлен один из оставшихся. берем "подозреваемые" 8 стаканов, опять делим их пополам (по 4) и берем пробу из одной группы и т.д. пока не останется 2 стакана.
А неизвестное количество стаканов вычисляем обратным способом берем 2 и умножаем на 2. 2*2=4*2=8*2=16*2=32*2=64*2=128 (сказано что стаканов было между 100 и 200). и +1 стакан, который он исследовал в самом начале (для того чтоб было четное число). 128+1=129. надеюсь теперь понятно?
Спасибо! Доступно!
По сути определяющим является 3й снизу абзац "Мы будем брать небольшое число жидкости из нескольких стаканов..." Далее следует пояснить, чтобы найти 1 нужный стакан из 2х, конечно, зная, что он только один(в условии "...было точно известно, что отравленный стакан - один, а всего стаканов было от сотни до двухсот" ) понадобится 1 проверка (если даже один чист, значит отравлен другой, плюс, ко всему, используется принцип смешивания жидкостей*); далее - из 3х выявить один можно с помощью 2х проверок, так же, как и из 4х (нас интересует только максимальное число проверок по эт. правилу*). Т. о. можно составить таблицу:
2 стак. - 1 пров.
3-4 стак. - 2 пров.
5-8 стак. - 3 пров.
9-16 стак. - 4 пров.
17-32 стак. - 5 пров.
.....
Можно заметить ,что четные цифры, стоящие в 1м столбце, будут удваиваться (в правильности таблицы можно самим убедиться более наглядно). Дальше нас интересуют только 2 строчки:
65-128 стак. - 7 пров.
129-256 стак. - 8 пров.
Т.е чтобы найти только один нужный стакан из числа таких же в интервале от 129 до 256 нужно затратить всего 8 проверок. Теперь обратим внимание на фразу "... при этом, взяв один стакан, он заявил, что надо исследовать его первым - и это не будет растратой попыток впустую." Т.е., взяв любое число стаканов от 100 до 200 кроме 129 и отняв 1, мы затратим на проверку общего числа стаканов лишнюю попытку. Например, для того чтобы найти 1 стакан из 131-го понадобится 8 проверок,но если первоначально проверить 1, то останется 130 ст., выявить 1 из которых можно, также затратив 8 проверок, т.е. в сумме уже получится 9 проверок вместо восьми. С числом 129 этого не произойдет(т.к. на 128 ст. требуется 7 п., в итоге 7+1=8 попыток, как и в последней строке таблицы). Фактически эта фраза и нужна была для того, чтобы определить точное число проверок.
Следаку потребуется 8 попыток, для поиска отравленного стакана из 129. Легкая задача - 57 сек
возьмите 121,ничем не сложнее,по похожему принципу делается.тут любое число брать можно.
Я думаю, что 129 ответ неверный.
В случае (129-1) мы потратим 8 шагов на поиски стакана.
А в случае, если будем честно делить 129, то с большей долей вероятности сможем уложиться в 7 шагов.
Вариант 129 "честный":
Если мы будем делить пополам 129, получим 64 и 65.
Теперь в 50% случаев дойдем до нужного стакана за 6 шагов (всего будет 7), в 50% - за 7 шагов (всего будет 8).
Вариант 129-1:
Если же мы проверим сначала 1 стакан, то у нас уже одна попытка исчерпана.
Осталось 128 стаканов. Методом деления 128-и стаканов мы можем дойти до нужного стакана за 7 шагов (всего будет 8).
условие соблюдается, если каждая проверка будет выявлять яд с первого раза. а если нет? тогда ему потребуется гораздо большее число проверок
Смотрю никто не пояснил этого ...
очень важное условие: "взяв один стакан, он заявил, что надо исследовать его первым - и это не будет растратой попыток впустую" !
это условие соблюдается, только если при последовательном делении напополам в конце у нас остается 3 стакана (в этом случае можно сразу один из стаканов проверить первым, и это не будет растратой попыток впустую)
129 /2 = 65 и 64
65 / 2= 33 и 32
33 / 2 = 17 и 16
17 / 2 = 9 и 8
9 / 2 = 5 и 4
5 / 2 = 3 и 2
остается 3, из них 2 нужно проверить. Получается 8 проверок в любом случае.
Проверяя сперва 1 , а потом остальные
128 / 2 = 64 и 64
64 / 2 = 32 и 32
32 / 2 = 16 и 16
16 / 2 = 8 и 8
8 / 2 = 4 и 4
4 / 2 = 2 и 2
2 / 2 = 1 - все равно 8 проверок.
В других случаях есть вероятность, что проверка сразу же 1 стакана будет напрасной,
например, 121 стакан - 1 проверяем сразу , потом 120 = 60 и 60 - 2 попытки
или можно сразу поделить 121 = 61 и 60 - и при одной проверке выйти на ту же цифру 60. То есть изначально проверять при 121 стакане 1 стакан - пустая трата попыток.
Поэтому задача корректная, ребята.
твой ответ не корректный...если подключить логику то она приведёт по твоему ответу вот к чему.....если 1 стакан не проверить то мы тогда можем не определить тот стакан которым он отравился и за 129 попыток так как когда будем делить на пополам то надо будет смешивать половину в каком-то стакане.....а в этой половине окажется стакан с ядом .....тогда при смешивании у нас окажется уже 2 стакана с ядом.....так что проверка 1 стакана изначально она СТОПРОЦЕНТНО ПРАВИЛЬНАЯ.....
лучше делить остаток не на 2, а на 3 - меньше шагов
я и со ста стаканов сделал 100-1=99 99:3=33(2 попытки)33:3=11(2 попытки)6 стаканов проверить 3 стакана и 1 стакан 8 попыток
Я из 200 стаканов отравленый определю за 8 проверок (если вначале не проверять один).
Если проверять, то 9.
Хотя эта проверка только тогда не впустую, когда у эксперта нет другой посуды (колбы. И ему приходится использовать один из стаканов для смешивания жидкостей.
ну эксперт сказал не более 10 проб, а вы все в 8 упёрлись, гнались за производительностью, тут правда в том, что точно не вычислить, есть расхождение на 9 бокалов, даже на 8, чтоб считалось лучше, есть расхождение
Так же эксперт должен был учесть,что из начатых стаканов,в принципе, можно и не брать пробу,потому как из них пили и остались живы.А так как эта задача на логику,по-моему на это следует обратить внимание.
193 человека:
1. 1
2. 96
3. 48
4. 24
5. 12
6. 6
7. 3
8. 1
9. 1
193 cтакана при оптимальной методике можно проверить за 8 попыток. 9 попыток получилось именно потому, что первый стакан проверили отдельно. То есть проверка первого стакана привела к растрате попыток, что противоречит условию
Почему 129?задачана логику),--1--зачем тратить ход,веть в процентном соотношении цыфр при делении он бесмысленен и даже на оборот неверен,у эксперта страных ход мышления)--2-- не обязательно 129,невазможна точна сказать сколька было гостей,зацепок нет,ведь ходов не более 10)тоесть 9 он имеет виду)
По условию стаканов от 100 до 200.
Если стаканов от 100 до 128, то требуется 7 проверок для нахождения нужного.
Если стаканов от 129 до 200, то требуется 8 проверок для нахождения нужного.
Если стаканов от 100 до 128, проверка одного стакана в начале увеличит требуемое число проверок до 8.
Если стаканов от 130 до 200, проверка одного стакана в начале увеличит требуемое число проверок до 9.
Но по условию, проверка первого стакана не является растратой попыток. Значит число стаканов 129, а требуемое число проверок (8) не уменьшается после проверки первого стакана.
Было стаканов 66
1 проба 66-1
2. 32/33
3. 16/17
4. 8/9
5. 4/5
6. 2/3
7. 1/2
8. 1/1
Здесь, на сколько я понимаю, диапазон для данного случая будет от 66 до 129 стаканов.
Лишь только в случае со 129 стаканами лишняя проба одного стакана не будет лишней потому, что количество проб будет одинаковым. Т.е. количество проб 129 стаканов = количеству проб 128 стаканов + проба одного стакана. Во всех остальных случаях в диапазоне от 100 до 200 стаканов любая лишняя проба одного из стаканов будет как раз таки лишней, т.е. кол-во проб n стаканов < кол-ва проб n-1 стаканов на одну пробу.
А про конкретное количество проб в задаче ничего не говорится.