Problem - 02 - National Math Camp 2021 Combinatorics Test - "The result is invariant"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 02 - National Math Camp 2021 Combinatorics Test - "The result is invariant"

Unread post by Anindya Biswas » Fri Apr 30, 2021 5:22 pm

There are $2021$ stones in a pile. At each step, Lazim chooses a pile with at least two stones, splits it into two piles, and multiplies the sizes of the resulting two piles. He keeps doing this until there are $2021$ piles each containing exactly one stone. Finally, he adds up all the products he obtains during the process and ends up with the number $N$. Find, with proof, all the possible values of $N$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 02 - National Math Camp 2021 Combinatorics Test - "The result is invariant"

Unread post by Mehrab4226 » Fri Apr 30, 2021 10:23 pm

You actually gave the main idea of the solution.
Claim:
Whatever number of stones in the initial pile Lazim starts with there is always a single value of $N$ and $N=\frac{n(n-1)}{2}$ if the initial pile has $n$ stones.

Base case:
This is very trivial for 1, 2, and 3.

Inductive Hypothesis:
Let all the number of initial stones from $1$ to $k$ obey our claim.

Inductive step:
Now let us take a pile that has $k+1$ stones. Now let Lazim divides the first pile into 2 such that one pile has $k+1-l$ stones and the other has $l$. Now no matter how Lazim divides the first pile with $k+1-l$ stones the sum o the multiplied values for only that pile is $N_1 = \frac{(k+1-l)(k-l)}{2}=\frac{k^2+k-2kl-l+l^2}{2}$
The same for the pile with $l$ stones is $N_2=\frac{l(l-1)}{2}=\frac{l^2-l}{2}$

$\therefore N=(k+1-l)l+N_1+N_2=\frac{(k+1)k}{2}$
So for our $2021$ case, $N=\frac{2021\times 2020}{2} = \boxed{2041210}$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply