There are $33!$ empty boxes labeled from $1$ to $33!$. In every move, we find the empty box with the smallest label, then we transfer $1$ ball from every box with a smaller label and we add an additional $1$ ball to that box. Find the smallest labeled non-empty box and the number of the balls in it after $33!$ moves.
Problem
Source: Turkey EGMO TST P3
Tags: combinatorics
07.02.2020 07:37
Denote $33!$ by $n$. It's easy to show that after the $i$th move (when $i\leqslant 2^n-1$), the numbers of balls from box $1$ to $n$ are $a_1,a_2,\dotsc ,a_n$ that satisfy $$i=\overline{a_na_{n-1}\dotsc a_1}_2\text{ and }a_1,a_2,\dotsc ,a_n\in \{ 0,1\}.$$So, the answer is box number $\nu_2(33!)+1=32$, with one ball in it.
07.02.2020 09:12
You're wrong answer is 36
07.02.2020 09:49
ThE-dArK-lOrD wrote: Denote $33!$ by $n$. It's easy to show that after the $i$th move (when $i\leqslant 2^n-1$), the numbers of balls from box $1$ to $n$ are $a_1,a_2,\dotsc ,a_n$ that satisfy $$i=\overline{a_na_{n-1}\dotsc a_1}_2\text{ and }a_1,a_2,\dotsc ,a_n\in \{ 0,1\}.$$So, the answer is box number $\nu_2(33!)+1=32$, with one ball in it. Check with smaller numbers and you will see you are mistaken
07.02.2020 11:17
inmemories wrote: ThE-dArK-lOrD wrote: Denote $33!$ by $n$. It's easy to show that after the $i$th move (when $i\leqslant 2^n-1$), the numbers of balls from box $1$ to $n$ are $a_1,a_2,\dotsc ,a_n$ that satisfy $$i=\overline{a_na_{n-1}\dotsc a_1}_2\text{ and }a_1,a_2,\dotsc ,a_n\in \{ 0,1\}.$$So, the answer is box number $\nu_2(33!)+1=32$, with one ball in it. Check with smaller numbers and you will see you are mistaken İn memories you 're absolutely right bro
07.02.2020 11:20
Kyolcu22 wrote: inmemories wrote: ThE-dArK-lOrD wrote: Denote $33!$ by $n$. It's easy to show that after the $i$th move (when $i\leqslant 2^n-1$), the numbers of balls from box $1$ to $n$ are $a_1,a_2,\dotsc ,a_n$ that satisfy $$i=\overline{a_na_{n-1}\dotsc a_1}_2\text{ and }a_1,a_2,\dotsc ,a_n\in \{ 0,1\}.$$So, the answer is box number $\nu_2(33!)+1=32$, with one ball in it. Check with smaller numbers and you will see you are mistaken İn memories you 're absolutely right bro You're also absolutely right dude. Cheers.
26.07.2020 13:01
I get 36, because the period of the kth box is lcm(1,2,...k+1) but I can't find how many balls are there in the 36th box.
02.06.2022 15:03
Answer: The box labeled with $36$ with $31$ balls in it. Claim.1: When $n-th$ box is filled for the first time, exactly $n$ balls will be placed in it. And after any moves the number of balls in n-th box cannot be greater than n. Proof: It's easy to see when n-th box filled for the first time, all other smaller numbered boxes must contain at least one ball each. And in any move if n-th box isnt empty we cannot increase the number of balls in it. Thus we can easily reach claim.1 . Claim.2: After any move, the total number of balls in boxes with numbers greater than n and n-th box is divisible by n. (For example, after any move the sum of the ball numbers in the $7$th to $33!$-rd box is divisible by $7$.) Proof: If that sum has changed after our move that means we have filled some box with labeled some number which is greater than n. So we increased the sum by exactly $(n-1)+1=n.$ The sum remains $0$ modulo n. Now we are ready to finish. By using $claim.2$ it is easy to show the period of first $35$ box getting empty is $lcm(1,2,...,36)$ which is a divisor of $33!$ but the period of first $36$ box is $lcm(1,2,...,37)$ which is not a divisor of $33!$ $\implies 36-th$ box gonna be the first non-empty box after $33!$ moves. By wilsons theorem, we know that $33!=\frac{1}{6} =31 (mod 37)$. That implies the number of the balls in $36-th$ box must be $31$ by claim.1.