BdMO Online Forum

তোমার সামনে কয়েনের \(2020\)টা পাইল আছে। প্রথম পাইলে আছে \(1\)টা কয়েন, দ্বিতীয় পাইলে আছে \(2\)টা কয়েন, তৃতীয় পাইলে আছে \(3\)টা কয়েন। এভাবে \(2020\)তম পাইলে আছে \(2020\)টা কয়েন। এক চালে তুমি একটা ধনাত্মক পূর্ণসংখ্যা \(k\) বাছাই করো এবং যেসব পাইলে কমপক্ষে \(k\)টা কয়েন আছে, সেসব পাইলের প্রত্যেকটা থেকে ঠিক \(k\) সংখ্যক কয়েন সরিয়ে নাও। সবগুলো কয়েন সরিয়ে ফেলতে তোমার সর্বনিম্ন কয়টা চাল লাগবে?

You have \(2020\) piles of coins in front of you. The first pile contains \(1\) coin, the second pile contains \(2\) coins, the third pile contains \(3\) coins and so on. So, the \(2020\)th pile contains \(2020\) coins. A move consists of selected a positive integer \(k\) and removing exactly \(k\) coins from every pile that contains at least \(k\) coins. What is the minimum number of moves required to remove all the coins?

1010
.......
.

Naeem588 wrote: ↑

Sat Apr 03, 2021 7:15 pm

1010
Lol
Lol

Process? Here in the forum, we don't care that much about answer, we need proof. Which algorithm gives the answer $1010$? and what is the proof that this is the minimum?

For $k$ being the number chosen for elimination, we can denote the number of balls in the piles initially as $1,2,3,...,k,(k+1),...,(k+m)$. Therefore, after eliminating $k$ coins by the given rule we are left with $1,2,...,(k-1),0,1,2,...,n$ balls altogether.

Observation: In the ultimate step we are left with just a unique number in several piles which is cancelled. So, in each step, if we can have the lowest amount of distinct integers after removing the coins, we can ultimately remove all coins in the minimum number of moves.

For a system with n number of piles having $1,2,3,...n$ coins and choosing $k$ coins to remove, we are left with $(k-1)$ coins or $m$ coins (either of which is larger) and where $n = k + m$. Since $n = k + m$, $m >{\frac{n}{2}} \text{ when } k < \frac{n}{2}$ and in the second case, k is already greater than $\frac{n}{2}$. This implies that the smallest possible number of distinct integers after a step is $\frac{n}{2}$ which is possible only when $$k=\frac{n}{2}$$. This entire statement would apply for all integers n (including odd integers) if we consider the floor of $\frac{n}{2}$ (i.e. the largest integer less than $\frac{n}{2}$).

Therefore, the number of distinct numbers converges to its half in each step, and converges to $$\frac{1}{2^a}^{th}$$ in $a$ steps. Since $2^{10} < 2020 < 2^{11}$, we would have just a unique number in several piles after $10$ steps, ($1$ is the floor of $$\frac{2020}{2^{10}}$$). Thus we need a total of $11$ steps minimum to remove all the coins.