20
$\begingroup$

An even number of nuts is divided into three nonempty piles. In each step, we are allowed to take half the nuts from a pile with an even number of nuts, and put them on another pile. Can we always reach a point where exactly half of the nuts belong to one pile?

For example, if we start with $(3,5,6)$, we can transform as $(3,5,6)\rightarrow (3,8,3)\rightarrow (3,4,7)$, and now the last pile has half of the nuts.

Note that in each step, some pile of nuts must be even, so we can keep moving. Moreover, we will never empty a pile.

$\endgroup$
  • $\begingroup$ Say we have an even number k of nuts, if k is divisible by 3, if we can make three piles of nuts that all have an even number of nuts. Then, we can take half of the nuts from one pile and keep moving them from pile to pile and we will continuously arrive at our original arrangement of three even piles of k/3 nuts, but then we don't have half of the nuts in one pile. For the case that the total number is not divisible by 3 it is harder. $\endgroup$ – wesssg May 26 '16 at 2:07
  • 1
    $\begingroup$ @wesssg - huh? Can you explain how your process works when k = 6? $\endgroup$ – mathguy May 26 '16 at 2:12
  • $\begingroup$ I guess i'm thinking that if we have for example 12 total nuts, we can make 3 piles of 4 nuts. Then, we can keep shifting 2 nuts around the circle, but we will end up getting back to that original arrangement, you know what I mean ? I'm not sure if this is a valid point though $\endgroup$ – wesssg May 26 '16 at 2:12
  • 4
    $\begingroup$ Made a program to check all starting combinations for a given even number of nuts $n \ge 4$. No counterexamples for $n$ up to $100$. $\endgroup$ – Jens May 28 '16 at 13:24
  • 4
    $\begingroup$ Noticed 2 things: One cannot move from odd, odd, even (in some order) to even, even, even (in some order) But the opposite is possible. Also, it is easy to see that any step just before a solution will look like x, x, 2n -2x And will necessarily have 2 same counts. $\endgroup$ – Shooter Jun 9 '16 at 5:16
4
$\begingroup$

The answer is yes and here is how (I got the idea from Shooter's comment above):

Step 1: If you are given three even piles of nuts (otherwise go to step 2): Choose one pile and take nuts from it as long as you can (until the number of nuts is odd). Put them wherever you like.

Step 2: You now are in the situation even (pile A), odd (pile B), odd (pile C) (up to changing the order). Now, you cut pile A into half as often as you can. Put all of the nuts on pile C except in the last step in which you put them one pile B. So that now pile B is the only one with an even number of nuts.

Step 3: Go back to Step 2 (with A and B reversed) unless pile B has precisely double the size of pile A. In that case go to Step 4.

Step 4: You arrived at numbers of the form (x,2x,sum-3x). Cut B and put it on C, then cut C and put it on A to get (sum/2,x,sum/2-x).

For this algorithm to work, we have to argue, why indeed we get to step 4 at all: If we look at our loop, it is clear that the sum of the nuts in piles A and B is non-increasing and so there comes a point where it will be constant for all eternity (nothing goes to C any longer). If the loop never ends the numbers would then behave like this:

$$(m,2n) \to (m+n,n) \to (\frac{1}{2}m+\frac{1}{2}n,\frac{1}{2}m+\frac{3}{2}n) \to (\frac{3}{4}m+\frac{5}{4}n,\frac{1}{4}m+\frac{3}{4}n)\to ...$$

In this sequence it is easy to see that the difference between one entry and the same entry two steps later is always of the form $\pm 2^{-k}(m-n)$ with $k$ increasing with each step (it is a geometric sum). But all the numbers are integers so that $2^{-k}(m-n)$ must be an integer for all $k$. Therefore, $m=n$!

I hope I did not miss anything and this is correct.

$\endgroup$
  • $\begingroup$ I'm afraid that there is a flaw here: "if the loop never ends the numbers would then behave like this". There is no reason for the endless loop to necessarily consist in alternating A and B at each step. You might have two halvings of A followed by two halvings of B bringing the situation at the initial condition. Start at $(m,4n)$ and you see that you need $m=n$. For example $(3,12,C)\rightarrow(9,6,C)\rightarrow(12,3,C)\rightarrow(6,9,C)\rightarrow(3,12,C)$ $\endgroup$ – lesath82 May 19 '17 at 19:38
  • $\begingroup$ In cases like this one has to follow a different strategy to the goal. Since Jens verified the absence of counterexamples up to $100$, up to there this is certainly possible, but it could be necessary to choose a different one case by case. @Karo $\endgroup$ – lesath82 May 19 '17 at 19:47
  • $\begingroup$ sorry lesath82, but you should read step 2 again. Everything except the last 'halving' goes to C. In your example, we would have (12,3,C)→(6,3,C+6)→(3,6,C)→step 4 $\endgroup$ – Julian Braun May 21 '17 at 15:22
  • $\begingroup$ meant to write: (12,3,C)→(6,3,C+6)→(3,6,C+6)→step 4 or in all detail: (12,3,C)→(6,3,C+6)→(3,6,C+6)→(3,3,C+9)→((C+15)/2,3,(C+9)/2) $\endgroup$ – Julian Braun May 21 '17 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.