I was given this puzzle earlier today by a colleague who in turn heard it from a friend who got the problem from a math professor at UCSB.
Suppose Alice has $753$ coins of some denomination. She offers to give the coins to her friend Bob if Bob wins the following game; if he loses, he must pay Alice the equivalent value. The game is played as follows:
At the beginning of the game, all of Alice's coins are in one pile. Bob can repeatedly do the following as many times as he likes: from any pile that contains at least $3$ coins, Bob can remove exactly one coin (which is then no longer "in play") and divide the remaining coins in that pile into two separate piles. These two piles do not have to be the same size, though each pile must have at least one coin. Bob wins if he can make it so that every pile has exactly three coins. He loses if he cannot win.
Should Bob take Alice's wager?
My attempted solution is as follows:
After each operation, the number of piles increases by one and the number of coins in play decreases by one. Suppose it is possible for Bob to win, i.e. there exists some number of operations $n$ such that, after $n$ operations, Bob wins. Importantly, there must be $n+1$ piles of coins after these $n$ operations, each of which has $3$ coins. If this is right, then the following equation should hold $$753 = 3(n+1) + n.$$
Simplifying this equation, I get $$750 = 4n.$$
I think this is a contradiction, since the implication is that $n=187.5$. This can't be right since it would mean Bob would have to perform half of an operation. Thus, Bob cannot win and he should not take this wager.
Does my solution work? Are there better solutions?
Best Answer
Your solution works; a variant more couched in the concepts of combinatorial game theory follows. Call a single pile winnable if it is possible to reduce it to piles of $3$ coins by the rules of the game. Every winnable pile's coin count is $3\bmod4$, since the reverse of the splitting operation (on two winnable piles, combining them and adding one coin back) preserves this invariant: $3+3+1\equiv3\bmod4$. But $753\equiv1\bmod4$, so Bob cannot win. (Conversely, Bob can always win from piles with coin count $3\bmod4$).