There are three piles of coins, with $a,b$ and $c$ coins respectively, where $a,b,c\geq2015$ are positive integers. The following operations are allowed: (1) Choose a pile with an even number of coins and remove all coins from this pile. Add coins to each of the remaining two piles with amount equal to half of that removed; or (2) Choose a pile with an odd number of coins and at least 2017 coins. Remove 2017 coins from this pile. Add 1009 coins to each of the remaining two piles. Suppose there are sufficiently many spare coins. Find all ordered triples $(a,b,c)$ such that after some finite sequence of allowed operations. There exists a pile with at least $2017^{2017}$ coins.
Problem
Source: 2018HKTST2P2
Tags: combinatorics
HKIS200543
21.10.2017 17:06
I believe the answer is any $(a,b,c)$ except $(2015, 2015, 2015)$.
ThE-dArK-lOrD
21.10.2017 20:41
First, it's easy to see that if $(a,b,c)=(2015,2015,2015)$, no operation is allowed and so there won't exist any pile with at least $2017^{2017}$ coins. Note that the operations will cease if and only if $x,y,z$ are all odd number less than $2017$ where $x,y,z$ are the number of coins in three piles. So, as long as the total number of coins in three piles is at least $1+(2015+2015+2015)$, the operation can continue. Also, note that, after any choice of operation, the total number of coins in three piles is the same or increase by one. This gives us, if $(a,b,c)\neq (2015,2015,2015)$, the operation can continue forever. If operation (2) occurs infinitely many times, after some finite times, the total number of coins in three piles will greater than $3\times 2017^{2017}$. Then there will be a pile with at least $2017^{2017}$ coins. If operation (2) occurs only finite times, after some finite times, the only operation used after that is operation (1). Now we'll consider only the number coins in three piles after that time. Let $(0,p,q)$ be the number of coins in three piles after operation (1) occurs once. Then note that each time operation (1) occurs, the absolute value of the number of coins in two piles which is not empty will increase. This can't continue for more than $p+q$ times since, after that, there will be a pile which contains more than $p+q$ coins, but the total number of coins must be $p+q$. So we get the contradiction in this case, and so there will be a pile with at least $2017^{2017}$ coins. Finally, we conclude that the answer is all $(a,b,c)$ except $(2015,2015,2015)$.
ltf0501
06.11.2017 14:28
ThE-dArK-lOrD wrote: Then note that each time operation (1) occurs, the absolute value of the number of coins in two piles which is not empty will increase. Why can this happen? (0,p,q)->(p/2,0,q+p/2)->(q/2+3p/4,q/2+p/4,0) I think it's false.
ltf0501
06.11.2017 14:35
But actually, we can perform operation (2) iff one of them is odd and larger than 2015. So, we can prove that we can ensure if both a,b,c are even, we can perform (1) finitely such that one of them will eventually become odd. Just consider power of 2.