Maths Olympiad Prep

Library / /30 of 73

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it Turkey

There are nn students and 2929 boards. Each student writes one of the numbers 11, 22 or 33 to each board (a student can write different numbers to different boards). It is observed that any two students wrote different numbers to at least one board and any three students wrote the same number to at least one board. Find the largest possible value of nn.

Solution

Answer: 3283^{28}.
Let us numerate boards by 11, 22, \ldots, 2929 and for each student define a vector (a1,a2,,a29)(a_1, a_2, \ldots, a_{29}), where aia_i is a number written by this student to the board number ii. Since any two students wrote different numbers to at least one board, we get a set VV of nn different vectors each having 2929 components. For each given vector v=(a1,a2,,a29)v = (a_1, a_2, \ldots, a_{29}) let us define v1=(a1+1,a2+1,,a29+1)v_1 = (a_1+1, a_2+1, \ldots, a_{29}+1) and v2=(a1+2,a2+2,,a29+2)v_2 = (a_1+2, a_2+2, \ldots, a_{29}+2) where all entries are considered in (mod 3)(\bmod\ 3). Since any three students wrote the same number to at least one board, at most one of three vectors vv, v1v_1 and v2v_2 can be present in the set VV. Therefore, VV contains at most
3293=328 \frac{3^{29}}{3} = 3^{28}
vectors. Now note that if first entries of all vectors of VV coincide and the remaining components span all possible 3283^{28} combinations, problem conditions are satisfied. Thus, the maximal value of nn is 3283^{28}.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.