In three piles there are $51, 49$, and $5$ stones, respectively. You can combine any two piles into one pile or divide a pile consisting of an even number of stones into two equal piles. Is it possible to get $105$ piles with one stone in each?
Problem
Source: ToT - 2001 Spring Junior A-Level #2
Tags: number theory, greatest common divisor, number theory unsolved
professordad
17.08.2011 22:36
If we combine the 51 and 49, we get two piles of 100 and 5 stones. Here, no matter what, we will have to end up with a number of stones divisible by 5 at a point (when you combine, that ensures 0 mod 5, and when you divide by 2, that doesn't change it mod 5) so we cannot end with 105 piles of one stone each. Similarly, if we combine the 51 and 5, we get two piles of 56 and 49, whose gcd is 7, and if we combine the 49 and 5, we get two piles of 51 and 54, whose gcd is 3. None of them have gcd of 1, so the result is impossible.
IceWolf10
09.04.2021 21:30
Notice that only when a number is a power of $2$, it can be divided in half repeatedly until we are left with $1$. So only piles with the number of stones being a power of $2$ can be split into some number of $1$-stone piles. It follows that it is impossible to get a $1$-stone pile from a pile that isn't a power of $2$. So since it is impossible to express $105$ as a sum of $2$'s raised to a positive power, it is also not possible to get $105$ piles with one stone in each.
oolite
10.04.2021 01:26
IceWolf10 wrote: So since it is impossible to express 105 as a sum of 2's raised to a positive power, it is also not possible to get 105 piles with one stone in each. Unfortunately, this doesn't work. Consider the problem with 105 = 51 + 31 + 23. Add 51+31=82 then split to make 41,41,23; add 41+23=64 then split into 41,1,1,1,...,1; add some 1's back into 41 to make 64,1,1,1,...,1; then split all the way to 1,1,1,....,1. Your proof needs to use more than the fact that the total is 105; the starting piles are important too.