In a school, there are $1000$ students in each year level, from Year $1$ to Year $12$. The school has $12 000$ lockers, numbered from $1$ to $12 000$. The school principal requests that each student is assigned their own locker, so that the following condition is satisfied: For every pair of students in the same year level, the difference between their locker numbers must be divisible by their year-level number. Can the principal’s request be satisfied?
Problem
Source: Australia MO 2024 P6
Tags: combinatorics
vsamc
24.02.2024 20:50
wrong.....
squarc_rs3v2m
14.03.2024 13:15
above is wrong answer actually
pick any residue class mod 12. now there are 11000 lockers so pick the residue class mod 11 with the most lockers ($\geq 1000$). now there are 10000 lockers so pick the residue class mod 10 with the most lockers ($\geq 1000$). Induct down etc. etc.
ohiorizzler1434
14.03.2024 14:15
Hello W rizzlers! I present my fanumtastic solution!
If there are $n$ grades left, there are $1000n$ lockers to assign. Therefore, by the pigeonhole principle, at least one residue class mod $n$ holds at least $1000$ lockers. Therefore, I can always assign the grades.
D_S
14.03.2024 14:50
vsamc wrote:
No. Note that all the year 12's set of lockers are precisely the ones between $1$ and $12000$ which are $r\mod{12}$, for some $0\leq r\leq 11$, since we cannot have any spare $r\pmod{12}$'s since there are a total of $\frac{12000}{12} = 1000$ such $r\pmod{12}$'s. Now, suppose that the year 11's set of lockers are all of the form $s\pmod{11}$ for some $0\leq s\leq 11$. Then, note that by CRT, there are at least $\left \lfloor \frac{12000}{132}\right \rfloor = 90$ lockers of the form $s\pmod{11}$ that belong to someone in year $12$, and there are exactly $1000$ lockers of the form $s\pmod{11}$ that belong to someone in year $11$. Furthermore, there are at most $\left \lceil \frac{12000}{11}\right \rceil = 1091$ lockers that are of the form $s\pmod{11}$ for some $0\leq s\leq 11$. So there is at most $1091 - (1000+90) = 1$ locker that is $s\pmod{11}$ but not belonging to anyone in year $12$ and year $11$.
Now, suppose that year $10$'s set of lockers are all of the form $t\pmod{10}$, then there must be exactly $\frac{12000}{10} = 1200$ of them. Then, of the lockers which are of the form $t\pmod{10}$, we have by CRT that there are at least $\left \lfloor \frac{1200}{\frac{12}{\gcd(12, 10)}} \right \rfloor = 200$ lockers which are $r\pmod{12}$. Furthermore, there are at least $2$ lockers that are $s\pmod{11}, t\pmod{10}$, but not $r\pmod{12}$ by CRT as $\left \lfloor \frac{12000}{\text{lcm}(11, 10,12)}\right \rfloor = 18$. One of these lockers must be a year $11$ locker, since there is at most one locker which is $s\pmod{11}$ but not in year $11$ or $12$, and since it's not $r\pmod{12}$ it cannot be a year $12$ locker. Thus, of the lockers of the form $t\pmod{10}$, at least one of them is a year $11$ locker and at least $200$ of them are a year $12$ locker, so at least $201$ of them are not year $10$ lockers, so there are at most $1200-200-1 = 999$ year $10$ lockers which are $t\pmod{10}$. But all year $10$ lockers must be $t\pmod{10}$, so there are at most $999$ lockers which are year $10$, a contradiction. $\blacksquare$
Your argument that there are at least 200 lockers which are $r \pmod {12}$ among the tenth graders is false. Suppose $r = 3$, $t = 0$.