All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Leave no stone unturned (Posted on 2017-03-19)
There are three virtual piles of stones. In one operation one may add to, or remove from, one of the piles the number of stones equivalent to the quantity in the other two piles combined, leaving the numbers in those two piles unchanged.
Thus, e.g., (12,3,5) can become (12,20,5) by adding 12+5=17 stones to the second pile, or (12,3,5) can become (4,3,5) by removing 3+5=8 stones from the first pile.

Assume a starting state (1111,111,11).
Is it possible, by a sequence of such operations, reach a state where one of the piles is empty?

 See The Solution Submitted by Ady TZIDON Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Other cases | Comment 2 of 5 |
Charlie's parity argument proves that zero can never be reached if all three piles start with an odd number.

I believe that there are many other cases in which zero cannot be reached.  For instance, start with piles of (1110,110,10).  The issue is that if at any point we want to reduce stones, we are not allowed to go negative.  So there is only one way to reduce the stones at any given step, namely by subtracting the two smallest piles if their sum is not greater than the largest pile.  Repeatedly applying this process gets us to (30, 30, 10), after which no further reduction is possible.  And it does no good to add stones at any step, because the path down necessarily reverses any additions.  This is because the pile to which stones is added is necessarily the new largest pile.  Whenever we decide to reduce stones we are forced to undo the last add.  If we reduce further, we are forced to undo the add before that.

Of course, some initial piles will allow us to get to zero.  For instance, (1110, 112, 10) can be reduced to (0, 2, 10) and then to (0, 2, 2) and then to either (0,0,2) or (0,2,0).

Interesting problem, Ady.

 Posted by Steve Herman on 2017-03-19 14:13:27
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information