An ordered quadruple of numbers is called ten-esque if it is composed of 4 nonnegative integers whose sum is equal to $10$. Ana chooses a ten-esque quadruple $(a_1, a_2, a_3, a_4)$ and Banana tries to guess it. At each stage Banana offers a ten-esque quadtruple $(x_1,x_2,x_3,x_4)$ and Ana tells her the value of \[|a_1-x_1|+|a_2-x_2|+|a_3-x_3|+|a_4-x_4|\]How many guesses are needed for Banana to figure out the quadruple Ana chose?
Problem
Source: 2021 Israel TST 8 P1
Tags: combinatorics, games
01.06.2022 04:50
The answer is $3$. This can be obtained by asking $(10,0,0,0)$, $(0,10,0,0)$, $(0,0,10,0)$. The first time, Ana will tell her $|a_1-10|+|a_2-0|+|a_3-0|+|a_4-0|= 10-a_1+a_2+a_3+a_4 = 20-2a_1$, whence Banana can obtain $a_1$. Similarly, she can get $a_2$ and $a_3$, whence $a_4=10-a_1-a_2-a_3$. Now, we will show optimality. Suppose that Banana could guarantee to find the quadruple in two moves for the sake of contradiction. We know that each value Ana tells Banana must be even and from $0$ to $20$, inclusive: \[|a_1-x_1|+|a_2-x_2|+|a_3-x_3|+|a_4-x_4|\pmod 2 \equiv a_1+a_2+a_3+a_4-x_1-x_2-x_3-x_4\pmod 2 \equiv 0.\] If we view Banana's decision process as a "decision tree," then there are at most $11$ choices for how she could ask her second question (based on the result of the first question, since we assumed that such a strategy exists). Each of these questions could have at most $11$ different answers from Ana. Thus, the total number of possible cases that Banana could determine is at most $11^2$. However, there are $\binom{10+3}{3} = 286$ possible tuples for Ana to start with, so Banana cannot determine all of the tuples that Ana could have chosen, a contradiction.
12.06.2022 17:12
Quite similar to ISL 2002 C4; the bound part (checking the number of possibilities) is the same. https://artofproblemsolving.com/community/c6h17339p118715