Невозможность определить гарантированно
Ошибка.
Попробуйте повторить позже
На столе лежат 28 конфет. Петя считает некоторые из них вкусными. Вася за один ход может указать любой набор конфет и спросить Петю, сколько из них вкусных. Как Васе гарантированно найти все вкусные конфеты (a) за 21 ход, (б) за 20 ходов?
Источники:
Пункт а, подсказка 1
Кажется, что если узнавать про большие наборы, то сложновато следить за конфетами. Может попробовать поработать с каким-то маленьким набором конфет, например с 4...
Пункт а, подсказка 2
Попробуем за несколько ходов определить каждую конфету из множества {a, b, c, d}. Что нам могут дать вопросы о наборах {b, c, d} и {a, c, d}?
Пункт а, подсказка 3
Если ответы на них разные, то мы однозначно определим конфеты a и b, а из этого и конфеты c и d. Интереснее будет, если ответы на эти вопросы одинаковые: тогда мы понимаем, что a и b либо обе вкусные, либо обе невкусные. Как нам тогда определить остальные конфеты, если задать вопрос про набор {a,b,c}?
Пункт а, подсказка 4
Если предположить, что конфеты a и b вкусные, то ответ на вопрос про набор {a,b,c} должен быть хотя бы 2. Если ответ ровно 2, то c- невкусная, а если 3, то с- вкусная. Если же конфеты a и b обе невкусные, то ответ будет 1 или 0, тогда c будет вкусная или невкусная соответственно. Тогда, зная a, b и с, мы из вопроса про набор {a, c, d} восстанавливаем d. Итак, мы справились за не более чем 3 хода. А сколько групп по 4 можно выделить из 28 конфет...
Пункт б, подсказка 1
А вот и пункт б... Полезно будет подумать над тем, как можно увеличить количество известных конфет, и при этом не сильно увеличить количество вопросов, если у нас уже есть способ узнать все про n конфет за m вопросов...
Пункт б, подсказка 2
Пускай у нас есть способ узнать все про n конфет за m вопросов. Попробуем добавить к известным нам еще 3 конфеты за 3 вопроса. Пусть самый первый вопрос мы задавали про множество конфет X. Попробуйте подумать, что нам могут дать вопросы про наборы {a, c, X} и {b, c, X} ...
Пункт б, подсказка 3
Если ответы разные, то мы однозначно определим конфеты a и b, тогда останется лишь задать вопрос про набор {a, b, c} и узнать c. Если ответы на эти вопросы одинаковые, то мы понимаем, что a и b либо обе вкусные, либо обе невкусные. Тогда задав вопрос про набор {a, b, c} мы также узнаем про с, ведь если они обе вкусные, то ответ будет хотя бы 2 и мы узнаем про с, а если обе невкусные, то ответ меньше 2 и мы также узнаем про с. Итак, мы смогли узнать про a, b, c. А мы как-то пользовались тем, что мы знаем количество вкусных конфет в множестве X?
Пункт б, подсказка 4
На самом деле нет. А вот узнав все про a, b, c мы попутно узнали и про количество вкусных конфет в множестве X. Тогда в способе узнать все про n конфет за m вопросов мы могли не задавать вопрос про множество X. Значит мы смогли узнать про n+3 конфет за m+2 вопроса. Как нам теперь завершить решение, если про 1 конфету можно узнать какая она за 1 вопрос?
Пункт б, подсказка 5
Если про 1 конфету можно узнать какая она за 1 вопрос, то про 4 конфеты можно узнать за 3 вопроса, про 7 конфет за 5 вопросов, ... про 28 конфет за 19 вопросов. А это даже лучше, чем за 20 вопросов!!!
а)
Разобьём конфеты на 
групп по 
штуки. За 
хода можно узнать всё про данные конфеты 
спросив, например, про наборы
Если на первые два вопросы ответы будут разными, то мы узнаем, каковы конфеты 
и 
а из
третьего вопроса поймём, какова 
Вернувшись к первому вопросу, узнаем и про 
Если же ответы на первые два вопроса
совпадают, значит, 
и 
одинаковы. Если ответ на третий вопрос меньше 
то 
и 
невкусные, а если 
или более, то
вкусные; вкусная ли 
определим по четности этого ответа. И вновь, вернувшись к первому вопросу, определим, какова 
Замечание.
Подойдёт и другой набор вопросов, например, 
______________________________________________________________________________________________________________________________________________________
б)
Возможны различные решения этого пункта. Приведём решение, позволяющее найти все конфеты даже за 
ходов. Докажем
следующее утверждение: "Если для 
конфет задача решается за 
вопросов, то для 
конфет ее можно решить за 
вопроса"(Поскольку для одной конфеты достаточно одного вопроса, то для 
конфет хватит 
вопросов).
Действительно, пусть есть способ узнать про 
конфет за 
вопросов, и пусть первый из этих вопросов задаётся про некоторое
множество X. Добавим три конфеты 
а к списку вопросов добавим три вопроса про множества 
, 
и 
и
уберём вопрос про 
По ответам на эти вопросы можно узнать, каковы конфеты 
и сколько сладких конфет в 
(точно так же,
как в пункте а, только 
заменяется на 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
