Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 9.2 IMO level Prove it Taiwan

Dexter's Laboratory has 20242024 robots, each with a program setup by Dexter. One day, his naughty sister Dee Dee intrudes and writes an integer in {1,2,,113}\{1, 2, \dots, 113\} on each of the robot's forehead. Each robot detects the numbers on all other robots' foreheads, and guess its own number base on its program, individually and simultaneously.
Find the largest positive integer kk such that Dexter can setup the programs so that, no matter how the numbers distribute, there are always at least kk robots who guess their numbers right.

Solution

k=2024/113=17k = \lfloor 2024/113 \rfloor = 17. In general, for nn robots and mm numbers, k=n/mk = \lfloor n/m \rfloor.

Upper bound estimate: Number the robots 11 through nn, let the set of numbers be C={0,1,,m1}C = \{0, 1, \dots, m-1\}, the number worn by robot ii be xiCx_i \in C, and the program be
fi(x1,x2,,xi1,xi+1,,xn):CnC. f_i(x_1, x_2, \dots, x_{i-1}, x_{i+1}, \dots, x_n) : C^n \to C.
Suppose Dee Dee randomly writes XiX_i on robot ii, where XiX_i follows a uniform distribution on CC, independent of the other XjX_j. Then by independence, it is easy to see that
E[1{fi=Xi}]=P{fi(X1,X2,,Xi1,Xi+1,,Xn)=Xi}=1m. E[1_{\{f_i=X_i\}}] = P\{f_i(X_1, X_2, \dots, X_{i-1}, X_{i+1}, \dots, X_n) = X_i\} = \frac{1}{m}.
This means the expected number of robots who guess correctly =E[1{fi=Xi}]=n/m= \sum E[1_{\{f_i=X_i\}}] = n/m, and this also implies that Dee Dee must have a way of writing the numbers such that the number of robots who guess correctly is at most n/m\lfloor n/m \rfloor.

Construction: Consider
fi=ijixjmodm f_i = i - \sum_{j \neq i} x_j \quad \bmod m
Note that robot ii guesses correctly if and only if
xiijixjmodmjxjimodm,(1) x_i \equiv i - \sum_{j \neq i} x_j \quad \bmod m \Leftrightarrow \sum_j x_j \equiv i \quad \bmod m, \quad (1)
and there must be at least n/m\lfloor n/m \rfloor values of ii for which the last expression of (1) holds, so the result follows.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.