На столе лежат 28 конфет. Петя считает некоторые из них вкусными. Вася за один ход может указать любой набор конфет и спросить Петю, сколько из них вкусных. Как Васе гарантированно найти все вкусные конфеты (а) за 21 ход; (б) за 20 ходов?

Решение

a) Разобьём конфеты на 7 групп по 4 штуки. За 3 хода можно узнать всё про данные 4 конфеты \(a, b, c, d\), спросив, например, про наборы \(\{a, c, d\},\{b, c, d\},\{a, b, c\}\).

Если на первые два вопроса ответы будут разными, то мы узнаем, каковы конфеты \(a\) и \(b\), а из третьего вопроса поймём, какова \(c\). Вернувшись к первому вопросу, узнаем и про \(d\). Если же ответы на первые два вопроса совпадают, значит, \(a\) и \(b\) одинаковы. Если ответ на третий вопрос меньше 2, то \(a\) и \(b\) невкусные, а если 2 или более, то вкусные; вкусная ли \(c\), определим по чётности этого ответа. И вновь, вернувшись к первому вопросу, определим, какова \(d\).

Замечание. Подойдёт и другой набор вопросов, например, \(\{a, c\},\{b, c\},\{a, b, d\}\).

б) Возможны различные решения этого пункта. Приведём решение, позволяющее найти все конфеты даже за 19 ходов. Докажем следующее утверждение: «Если для \(n>0\) конфет задача решается за \(m\) вопросов, то для \(n+3\) конфет её можно решить за \(m+2\) вопроса». (Поскольку для одной конфеты достаточно одного вопроса, то для \(28=1+9 \cdot 3\) конфет хватит \(1+9 \cdot 2=19\) вопросов.)

Действительно, пусть есть способ узнать про \(n\) конфет за \(m\) вопросов, и пусть первый из этих вопросов задаётся про некое множество \(X\). Добавим три конфеты \(a, b, c\), а к списку вопросов добавим три вопроса про множества \(\{a, c\} \cup X,\{b, c\} \cup X,\{a, b, c\}\) и уберём вопрос про \(X\). По ответам на эти вопросы можно узнать, каковы конфеты \(a, b, c\) и сколько сладких конфет в \(X\) (точно так же, как в пункте а, только \(d\) заменяется на \(X\) ).

Ответ: ответ в решении.