У оракула в саду живут четыре черепашки. Посетитель может за ход выбирать любое подмножество черепашек и спрашивать оракула, сколько среди этих черепашек самцов (ответы оракула всегда правдивы). За какое наименьшее количество ходов можно узнать про всех черепах, какого они пола?
5
1
3
Ответы
Ответ:
3
Пошаговое объяснение:
а три вопроса можно получить ответ следующим образом. Первые два вопроса про черепах 1 и 2, про 2 и 3. Если хотя бы
один из ответов 0 или 2, про соответствующую пару знаем, кто они, про
оставшуюся из трёх знаем из другого вопроса, остался 1 вопрос на 4-ю
черепашку. Если оба ответа 1, то черепашки 1 и 3 одного пола. Тогда
спросим про 1, 3, 4. Мы услышим ответ не меньше 2, если черепашки 1
и 3 были самцами, и ответ не больше 1 иначе. При этом пол черепашки 4 также однозначно восстанавливается, и остается одним вопросом
выяснить пол черепашки 2.
Докажем, что двух вопросов недостаточно. Прежде всего заметим,
что: а) за один вопрос, не зная общего числа самцов, мы не сможем
разобраться даже с двумя черепашками; б) зная общее число самцов,
мы сможем разобраться с двумя, но не сможем разобраться с тремя черепашками. Поэтому в ситуации четырёх черепашек и двух вопросов задавать первый вопрос про всех черепашек сразу или про одну черепашку
бессмысленно. Поскольку при вопросе про группу из трёх или двух черепашек мы можем услышать ответ 1, такой вопрос также не приведёт
к успех