To open the magic chest, one needs to say a magic code of length $n$ consisting of digits $0, 1, 2, 3, 4, 5, 6, 7, 8, 9.$ Each time Griphook tells the chest a code it thinks up, the chest's talkative guardian responds by saying the number of digits in that code that match the magic code. (For example, if the magic code is $0423$ and Griphook says $3442,$ the chest's talkative guard will say $1$). Prove that there exists a number $k$ such that for any natural number $n \geq k,$ Griphook can find the magic code by checking at most $4n-2023$ times, regardless of what the magic code of the box is.
Problem
Source: Azerbaijan NMO 2023. Senior P4
Tags: combinatorics, AZE SENIOR NATIONAL MO
Steven.Cai
06.10.2023 18:51
First try 000...000 (all zeros) , 111...111(all ones) , ... , and 999...999(all nines). That will take 10 tries, but that doesn't matter, because with these ten tries, we exactly know how many zeros, ones, twos, ... , nines are there in the code. The next step is to find out where they are. Let a(k) be the times that the number k appears in the code. WLOG a(0)>=a(1)>=...>=a(9),then a(0)+a(1)>=a(2)+a(3)>=a(4)+a(5)>=a(6)+a(7)>=a(8)+a(9), so a(0)+a(1)>=0.2*[a(0)+a(1)+...+a(9)]=0.2n>=a(8)+a(9), then a(0)+a(1)+...+a(7)>=0.8n. Now, we try 000...000(all zeros) for our first trial (we try it again but it still doesn't matter). And we'll get the answer from the guardian about how many numbers are in their correct place. Let the number he answers be t(0). Now, we switch the first zero to one, and ask him again, then we may get three answers:(let the answer he gives this time is x(1)) Case 1:if x(1)=t(0), then neither 0 or 1 is the correct number on this place. Case 2:if x(1)=t(0)-1, then 0 should be the correct number on this place. Case 3:if x(1)=t(0)+1,then it means that 1 is the correct number on this place. if the first two cases happens, then let t(1)=t(0), and switch the number 1 back to 0; if the last case happens, then let t(1)=t(0)+1, and keep the 1 in the code. After these moves, do the same things to the second number of code, switch the second 0 to 1, and compare x(2) with t(1)... Keep doing these to every place of code. And after all of these, with n+1 moves, we can know exactly if the number on some place of the code is 0, or 1, or neither of them. Then we can start the second round of trial. Set the code to all twos, and for each try, switch one of them to 3. However, as we have confirmed where all the 0s and 1s exactly are, so we don't need to give these places(with 0 or 1 correctly in its place) a try. So we only need n+1-a(0)-a(1) tries in this round. Then in the third round, it will only take n+1-a(0)-a(1)-a(2)-a(3) tries, for 4 and 5, and n+1-a(0)-...-a(5) tries for 6 and 7, and finally n+1-a(0)-...-a(7) tries for 8 and 9. And after all of these above, we used S=10+5n+5-[a(0)+a(1)]-[a(0)+a(1)+a(2)+a(3)]-[a(0)+...+a(5)]-[a(0)+...+a(7)] tries to find out what the number on every place is, which means we get the exact code. However, since a(0)+...+a(5)>=a(0)+...+a(3)>=a(0)+a(1)>=0.2n, and a(0)+...+a(7)>=0.8n (these have been proved above),then S<=5n+15-3*0.2n-0.8n=3.6n+15 Obviously, there exist a number k, for all the number n>=k, 3.6n+15<=4n-2023, as we desired.