there are chests were we have some coins prove that someday the number of coins in every chest will be the same after some operations

Question

The avaricious knight holds money in several chests. Initially, each chest contains several coins. On the first day, the knight adds 1 coin to each chest. On the second day, he adds a coin to all chests where the number of coins is even. And then, on day $k$, he adds 1 coin to those chests where the number of coins is divisible by $k$. Prove that someday all the chests will contain equal coins.

I actually don't know what to do. on 3rd day in all chests there were odd numbers of coins.Then he does thhe same operation and then there's no chest with 3m coins so how I can prove that someday numbers will be the same using this?

Answer 1

Here's a sketch of a proof – you'll enjoy working out the details.

Consider two chests, where the number of coins differs by some nonzero amount. Show that the difference between those two chests never increases, and that eventually it goes down by one. Then use that to show that eventually the two chests have the same number of coins. Then use that to show that given any finite number of chests, eventually they all have the same number of coins.

Answer 2

Another method is to consider just one chest, containing $c$ coins. If $k$, the number of days that have passed is equal to $c$, then from that day forward $c$ is increased every day, in step with $k$.

If you can prove that $k$ will always eventually catch up to $c$, regardless of the starting value of $c$, then this will happen to all the chests, and so eventually all the chests will be equal to $k$ and equal to each other.

So all you have to do is prove that when $k<c$, eventually $k$ will always catch up to $c$. The only way for this to NOT happen, is if eventually $c$ is increased every day without fail. Note that $c$ is allowed to reduce its lead a bit, but to stay ahead indefinitely there would have to be some day after which it is increased every single day. That would mean that $c+d$ is divisible by $k+d$ for every possible number of days $d$ in the future. I'll leave the final step of proving this cannot be the case for you to finish off.

Answer 3

Notice that if on day $n$, the number of coins in a chest is $n$ before the king adding a coin, then on day $n+k$, the number of coins in that chest will be $n+k$ before the king adding a coin.

Now, as others have said before, if $c$ denotes the number of coins in a chest at the start, then we show that there is a positive integer $d$ such that $c+a = d$ before the king adds a coin on the $d$-th day, where $a$ is the number of coins added to $c$ in the previous $d-1$ days.

Let's argue by contradiction. If there is no such $d$, then for any $n$, we have $c + a(n) > n$, where $a(n)$ denotes the number of coins added to $c$ in the previous $n-1$ days. This means we can find a natural number $m$ for which $c + a(m)$ is a prime, since the set $\{c + a(n) : n\in N\} = \{c, c+1, c+2, ...\}$. This means after the number of coins in the chest is $c + a(m)$, the king will only add a coin to that chest on the $c + a(m)$-th day, thereby contradicting our assumption.