Impossible problem? -- Bisecting and combining stacks of coins

115 Views Asked by At

I encounter this problem about dividing and combining stacks of coins. Now, the problem uses coins because it's easier to visualize, but it need not to be, it is in fact misleading because real coins can't be infinitely subdivided. So, for the purpose of the problems, imagine that there are as many coins as is needed.

Problem:

There are three stacks of coins with equal heights. You are allowed to divide any stack into two stacks of equal height, and you are allowed to combine any two stacks into one new stack. How would you divide the three stacks of coins into three new stacks such that their heights have the ratio of $1 : 2 :4$ ?

My hunch is that this is not possible, because the final outcome essentially requires $7$ stacks of equal height, given a $3$ stacks to begin with, this would not be possible and have something to do with prime numbers. However, I am at a lose as to why it is impossible, if indeed it is.

2

There are 2 best solutions below

0
On BEST ANSWER

Hint: if $h$ is the height of the initial three stacks, then all stacks created by these two operations have a height of the form $hm/2^n$, where $m$ and $n$ are integers. (You can prove this by induction.)

But you want to create stacks of height $3h/7,6h/7$, and $12h/7$.

0
On

I think your hunch is right. Let's use weights instead of coins, and suppose each stack weighs 1 (unit) so the total weight of the three equal stacks is 3. You must produce a stack with weight 3/7. Clearly each operation produces stacks with rational weights. Since the only way to decrease a stack is to halve it, the only denominators you can reach are multiples of 2 (in fact, powers of 2).