6. There are 28 candies on the table. Petya considers some of them to be delicious. Vasya can, in one move, point to any set of candies and ask Petya how many of them are delicious. How can Vasya guaranteedly find all the delicious candies... (a) in 21 moves; (b) in 20 moves?

(A. A. Tselery, E. Yu. Voronechik)

#
# Solution.

a) Let's divide the candies into 7 groups of 4 each. In 3 moves, we can learn everything about these 4 candies $a, b, c, d$, by asking, for example, about the sets $\{a, c, d\}, \{b, c, d\}, \{a, b, c\}$.

If the answers to the first two questions are different, we will learn about candies $a$ and $b$, and from the third question, we will understand $c$. Returning to the first question, we will learn about $d$. If the answers to the first two questions are the same, then $a$ and $b$ are the same. If the answer to the third question is less than 2, then $a$ and $b$ are not tasty, and if it is 2 or more, then they are tasty; whether $c$ is tasty can be determined by the parity of this answer. And again, returning to the first question, we will determine $d$.

Note. Another set of questions would also work, for example, $\{a, c\}, \{b, c\}, \{a, b, d\}$.

b) There are various solutions to this part. We will provide a solution that allows finding all the candies even in 19 moves. We will prove the following statement: "If the problem for $n>0$ candies can be solved in $m$ questions, then for $n+3$ candies it can be solved in $m+2$ questions." (Since for one candy it takes one question, for $28=1+9 \cdot 3$ candies, 19 questions will suffice, i.e., $1+9 \cdot 2=19$ questions.)

Indeed, suppose there is a way to find out about $n$ candies in $m$ questions, and the first of these questions is about some set $X$. Add three candies $a, b, c$, and to the list of questions, add three questions about the sets $\{a, c\} \cup X, \{b, c\} \cup X, \{a, b, c\}$, and remove the question about $X$. From the answers to these questions, we can learn about the candies $a, b, c$ and how many sweet candies are in $X$ (just like in part (a), only $d$ is replaced by $X$).

Grading criteria. 2 points for part (a) and 5 points for part (b).