Each of the $n$ students writes one of the numbers $1,2$ or $3$ on each of the $29$ boards. If any two students wrote different numbers on at least one of the boards and any three students wrote the same number on at least one of the boards, what is the maximum possible value of $n$?
Problem
Source: 2022 Turkey JBMO TST P5
Tags: combinatorics
BarisKoyuncu
15.03.2022 23:38
The answer is $3^{28}$.
Instead of writing a number in each board, assume that each student chooses a $29$ digit number where each digit is either $1,2$ or $3$.
Constructing an example is not hard. Assume that the students wrote every $29$ digit number starting with $1$. This gives a total of $3^{28}$ students and clearly satisfies the condition.
Let's consider all the numbers that could have been chosen. Group some numbers if we can derive one of them by adding the same number to each digit of another number (we consider the digits in modulo $3$ so $2+2=1$). For example, one of the group is $$11\cdots 1, 22\cdots 2, 33\cdots 3$$It is easy to check that each group is consist of $3$ numbers. Hence, there are $3^{28}$ groups in total. Now, just see that two students cannot choose their numbers from the same group. Therefore, there are at most $3^{28}$ students, done.