Jelly beans join the clean plate club

[bonanova]

On a table are three plates, containing a, b and c jelly beans, in some order, where a < b < c. At any time you may double the number of jelly beans on a plate, by transferring beans to it from a fuller (or equally populated) plate. After one such move, for example, the plates could have 2a, b-a,  and c beans. Using a series of these moves, Is it possible to remove all the jelly beans from one of the plates?

 

Edited January 17, 2018 by bonanova
Clarified the conditions for transferring beans

[flamebirde]

23 hours ago, bonanova said:

On a table are three plates, containing a, b and c jelly beans, in some order, where a < b < c. At any time you may double the number of jelly beans on a plate, by transferring beans to it from a fuller plate. After one such move, for example, the plates could have 2a, b-a,  and c beans. Using a series of these moves, Is it possible to remove all the jelly beans from one of the plates?

 

Spoiler

No.

In order to get a plate with no beans on it, one must transfer all the beans on it to a different plate. In order to do that, the number of beans on that plate must be greater than the number of beans on the other. Since you can only transfer from "fuller" to "less full", you can't transfer beans if the amount of beans from one equals the amount of beans on the other. (This also has the side effect of potentially "locking" the plates if all three have the same # of beans.)

The only way to get rid of all the beans on a plate with n beans would be to transfer n beans to a different plate.  However, this violates the transfer condition, since this means another plate has exactly n beans on it as well (since the other plate must double in beans), which means neither plate is "fuller" when compared with the other. Hence, there is no way to get an empty plate.

Alternative solution: let me eat all of them.

 

[Molly Mae]

37 minutes ago, flamebirde said:

  Hide contents

No.

In order to get a plate with no beans on it, one must transfer all the beans on it to a different plate. In order to do that, the number of beans on that plate must be greater than the number of beans on the other. Since you can only transfer from "fuller" to "less full", you can't transfer beans if the amount of beans from one equals the amount of beans on the other. (This also has the side effect of potentially "locking" the plates if all three have the same # of beans.)

The only way to get rid of all the beans on a plate with n beans would be to transfer n beans to a different plate.  However, this violates the transfer condition, since this means another plate has exactly n beans on it as well (since the other plate must double in beans), which means neither plate is "fuller" when compared with the other. Hence, there is no way to get an empty plate.

Alternative solution: let me eat all of them.

 

Thank you!  This was driving me mad, because I thought it was trivially easy for the case of 1-2-3 jellybeans.  I figured there was something I had overlooked.  You have proven me to be incorrect, as I obviously violated that rule.

[Slashpuzzler]

I have a doubt to confirm.

Spoiler

Lets say we were transferring from plate B to A . When you said fuller plate , do you mean that the (no of beans on  A)<( no of beans on B)  , or do you mean (no of beans on A)<=(no of beans on B)? My final answer will depend on this condition.

 

[rocdocmac]

Spoiler

If you cannot transfer from "fuller" to "less full" by creating equal amounts on two plates, the answer is No. If it is allowed to have equal numbers on two plates, the answer is Yes.

 

[bonanova]

Sorry guys, "fuller" should have read "at least as full." Examples always help, so here is an example.

 a   b   c
 7   9  12
  <-
14   2  12
  ----->
 2   2  24
  ->
 0   4  24

So { 7 9 12 } is a starting point where a plate can be emptied. Can any { a < b < c } lead to an empty plate?

A Yes answer needs proof; a No answer just needs a counter example.

[flamebirde]

Aw man, I was so confident I'd finally solved one of Bonanova's legendary puzzles.

A start on thinking:

Spoiler

I get this far:

a     b     c

2a     b-a    c

2a     2b-2a     c-b+a

but then I'm stumped, since it's not possible to definitively say that any one of these three values is larger than another. I would have to examine every possible case (where 2a is now the biggest, where 2b-2a is the biggest, and so on, for every branch) in order to determine whether or not beans can be moved, and even then my calculations would have to go to infinity in order to figure it all out. Thoughts?

 

[Molly Mae]

You definitely cannot rely on the subtractive relationship between two bins.  You do, however, have to state their relationship to prove that it can be done in every case.  I'm fairly certain it can be done in every case, and here's the foundation of my (currently) terrible (and incomplete) proof: somehow binding their binary parity and, if necessary, the parity of their average to the third bin.

For bins a, b, and c where 0<a<b<c, if the sum of a and b is divisible by 4,  heh.  Unless 2a=b.  Nevermind this.  Of course, it 2a=b, we can get 2a, b, c-a and have two identical bins.  

Perhaps showing that it can be done for certain a and b and that a and b can always be reduced to that state given c if necessary.

 

[flamebirde]

I think I've gotten closer.

Spoiler

If a+b is even, then probably continuously shifting beans between the two will eventually result in two identical bins, solving the question.

If b+c is even, then the case is identical to the one above.

If a+b is odd, and b+c is odd, then a+c is even, which means that the solution is identical to the one given above.

now the question is: can we prove that the function of doubling one bin by taking beans from the other converges to the average of the two? If so, then the question is solved.

 

[Molly Mae]

10 minutes ago, flamebirde said:

I think I've gotten closer.

  Hide contents

If a+b is even, then probably continuously shifting beans between the two will eventually result in two identical bins, solving the question.

If b+c is even, then the case is identical to the one above.

If a+b is odd, and b+c is odd, then a+c is even, which means that the solution is identical to the one given above.

now the question is: can we prove that the function of doubling one bin by taking beans from the other converges to the average of the two? If so, then the question is solved.

 

I can show you by counterexamples that they don't always land at the average (if, for example, their average is odd [say 4, 6], you'll never be able to double to the average).  That's why I considered evaluating the difference between two as being divisible by 4 (instead of 2).  Perhaps you'll succeed where I have failed.

[flamebirde]

21 hours ago, Molly Mae said:

I can show you by counterexamples that they don't always land at the average (if, for example, their average is odd [say 4, 6], you'll never be able to double to the average).  That's why I considered evaluating the difference between two as being divisible by 4 (instead of 2).  Perhaps you'll succeed where I have failed.

But no matter what you'll always have at least one pair whose average is even. Try it: pick any three numbers such that the average of any two is odd. I'm fairly sure it's impossible, since between a+b, b+c, and a+c at least one is guaranteed to be even. Do you have another counterexample of two numbers whose average is even but can't be reached via doubling?

Edited January 19, 2018 by flamebirde
clarification.

[CaptainEd]

Here’s a tiny observation about what the next to last step looks like.

Any one of the following three patterns results in the x,x,y pattern that leads to an empty plate.

(Z, 3z, anything)

(Half of the total, anything, anything)

(Z, 2z, z+ anything)

[flamebirde]

6 minutes ago, flamebirde said:

But no matter what you'll always have at least one pair whose average is even. Try it: pick any three numbers such that the average of any two is odd. I'm fairly sure it's impossible, since between a+b, b+c, and a+c at least one is guaranteed to be even. Do you have another counterexample of two numbers whose average is even but can't be reached via doubling?

Especially when you consider as well that at any point you've got an extra plate either to transfer to or to transfer from (although that does complicate things a bit, it also ensures that pairs such as {4,8} are solvable).

11 minutes ago, CaptainEd said:

Here’s a tiny observation about what the next to last step looks like.

 

  Hide contents

 

Any one of the following three patterns results in the x,x,y pattern that leads to an empty plate.

(Z, 3z, anything)

(Half of the total, anything, anything)

(Z, 2z, z+ anything)

 

 

Spoiler

Potentially the second one of these seems really useful... if we can ever get 1/2(a+b+c) on a plate then we can solve the entire thing. Although this won't always be possible if the sum of all the numbers is odd... hmm. I'm a little stumped, to be honest.

 

[Molly Mae]

1 hour ago, flamebirde said:

Do you have another counterexample of two numbers whose average is even but can't be reached via doubling?

I sure don't!  But I also couldn't find an easy way to express the relationship between (1) the average of two numbers being even and (2) the third plate.  That's when I disappeared down the rabbit hole of the difference between a and b being divisible by 4.

I think we're in the same boat, though.  We just can't come up with a way to express what's in our heads.

Whenever I'm in a situation like this (which happens pretty often), I sit back and watch the rest of you all solve where I have struggled.

Godspeed, my friends!  Should anything pop into my head, I will be certain to post it.

EDIT: What if we rename the plates to a, a+x, and a+y (or a+x+y)?

Edited January 19, 2018 by Molly Mae

[Molly Mae]

12 minutes ago, Molly Mae said:

I sure don't! 

I lied.  I can show you two numbers whose average is even that cannot be reduced to their average (and thus not reduced to 0) without a third plate.  The example of {4,8}.

These two alone cannot be reduced to 0.  As soon as you add in a third plate, regardless of the number on that plate, you can reduce one of them to 0.  That is the cornerstone of my reasoning, but I'm not certain I can express it.

[plasmid]

@Molly Mae maybe this'll help.

Q: How should you arrange all those plates of jelly beans?

A: Put them on a table.

Spoiler

Consider the following grid representing a table with seven jelly beans among the three plates. Each square on the grid represents the state where plate #1 has the number of jelly beans indicated by the column number, plate #2 has the number of jelly beans indicated by the row number, and plate #3 has the number of jelly beans that appears as a number in that square. So for example, the square in the upper left represents the situation where plate #1 has 1 jelly bean, plate #2 has 1 jelly bean, and plate #3 has 5 jelly beans.

Our goal will be to clear out plate #3, or in other words, to reach one of the cells along the diagonal with a zero in it. But instead of working forwards, I'm going to work backwards -- consider all of the cells where plate #3 is cleared out and see which states could lead to a cleared out plate #3.

For example, consider the state where plate #1 has 2 jelly beans, plate #2 has 5 jelly beans, and plate #3 has 0 jelly beans. (From now on I'm going to start writing states like that in shorthand with vectors, so like (2, 5, 0) for that thing I just said.) I'll color that cell yellow. Working backwards, what states could reach (2, 5, 0) in a single move? The only way to have reached that state is if you previously had one jelly bean on plate #1 and you moved one jelly bean from plate #3 onto plate #1, or in other words you went from (1, 5, 1) to (2, 5, 0). (I guess you could also argue that you could go from (1, 6, 0) to (2, 5, 0) but I'm not going to sweat that case because you would have already had plate #3 cleared out anyway.) Shown on the table, you could reach the yellow square by moving there from the orange square.

Now consider all of those squares where plate #3 is empty. Color them all yellow, and color each square that could get you to a yellow square in one move orange. That will give you the following figure.

It's probably worth stopping for a moment at this point and talking through the process of how you can work backward, and given a cell (x, y, z) find out which cells could get you there in one move. If x (on plate #1) is even, then you could have potentially moved x/2 jelly beans from plate #2 to plate #1 or from plate #3 to plate #1. On the figure, if you were to move jelly beans from plate #2 to plate #1 then that would be moving diagonally up and right, and if you were to move jelly beans from plate #3 to plate #1 then that would be moving straight right, and in either case you would be moving from column (x/2) to column (x) or in other words you would have come from the column halfway to the edge from point (x, y, z). Similarly if y is even then you could have moved jelly beans from plate #1 to plate #2 (moving diagonally down and left) or from plate #3 to plate #2 (moving straight down) from a point halfway to the top edge. And if z is even then you could have moved jelly beans from plate #1 to plate #3 (moving left) or from plate #2 to plate #3 (moving up) from a point halfway to the diagonal edge.

With that in mind, work through the next step: consider each of the orange squares and see which squares that are still uncolored could get you there in one step. In this case the squares (5, 1, 1) and (3, 1, 1) (and their symmetrical counterparts) can't be reached from any other state because none of them currently have an even number of jelly beans on a plate, but state (3, 2, 2) could be reached by moving from plate #1 to #2 [i.e. from (4, 1, 2) which is up and right from (3, 2, 2)], from plate #3 to #2 [from (3, 1, 3) which is straight up from (3, 2, 2)], from plate #1 to #3 [from (4, 2, 1) which is right from (3, 2, 2)], or from plate #2 to #3 [from (3, 3, 1) which is down from (3, 2, 2)]. Let's go ahead and color those red (except for (3, 3, 1) which is already colored and can therefore reach an empty plate #3) and the corresponding symmetrical squares that can reach (2, 3, 2) in one step.

Now you could reach those red squares with the following moves: (4, 1, 2) can be reached from (2, 1, 4) to its left, (4, 2, 1) can be reached from (2, 2, 3) to its left, and by symmetry (1, 4, 2) can be reached from (1, 2, 4) above it. Color those green.

And lastly square (1, 1, 5) could go to say square (2, 1, 4). So all squares have a path to the diagonal with zero jelly beans on plate #3.

I haven't developed a proof that it's possible to color the entire triangle like that for all numbers of jelly beans, but I did color this triangle with 15 jelly beans. Yellow <- orange <- red <- lime <- darkergreen <- blue <- purple <- violet.

 

[plasmid]

I wrote a perl program to do what I said earlier...

Spoiler

... and it said that it's possible to clear a plate from any state if you have up to at least 500 jelly beans. So I'm betting it's possible for any number of jelly beans. Proof still to be worked out. But I'll post a plot of the maximum number of moves it takes to clear a plate as a function of the number of jelly beans in play, and the perl code.

#!/usr/bin/perl
use strict;
use warnings;

my $beans = 5;
my @steps;

# Set up the output in a space-delimited spreadsheet format
# with number of jellybeans in the first column and the
# maximum number of moves it would take to clear a plate
# in the second column.
print "Jellybeans MovesToClear\n";

while ($beans <= 500) {
  # Increment and then print the number of jellybeans in the
  # first column of the output
  $beans++;
  print "$beans";
  
  # Make a two dimensional variable $steps where $steps[$x][$y] is the
  # number of steps it takes to reach an empty plate if you have $x
  # beans on plate 1 and $y beans on plate 2, plus one so states with
  # an empty plate will have value 1, states that can reach an empty
  # plate in one move will have value 2, states that can reach an
  # empty plate in two moves will have value 3, etc and states that
  # are still undetermined will have value 0.

  for (my $i=0; $i<=$beans; $i++) {
    for (my $j=0; $j<=$beans-$i; $j++) {
      $steps[$i][$j] = 0;
    }
  }
  
  # Mark all states with an empty plate with 1.
  for (my $i=0; $i<=$beans; $i++) {
    $steps[0][$i] = 1;
    $steps[$i][0] = 1;
    $steps[$i][$beans-$i] = 1;
  }
  
  # For the variable newstep, find all states marked with newstep-1,
  # find out which states could go to the newstep-1 states, and
  # give them a value of newstep.
  
  # Also make the moresteps variable and set it to zero. If any new
  # states are marked as accessible then set it to 1 and run through
  # this loop again. Otherwise, if no new states were added, you're
  # done handling this value of beans.
  my $newstep = 1;
  my $moresteps;
  do {
    $newstep++;
    $moresteps = 0;
    for (my $i=0; $i<=$beans; $i++) {
      for (my $j=0; $j<=$beans-$i; $j++) {
        if ($steps[$i][$j] == $newstep-1) {
          my $k = $beans-$i-$j;
          if ($i % 2 == 0) {
            if ($steps[$i/2][$j+$i/2] == 0) {
              $steps[$i/2][$j+$i/2] = $newstep;
              $moresteps = 1;
            }
            if ($steps[$i/2][$j] == 0) {
              $steps[$i/2][$j] = $newstep;
              $moresteps = 1;
            }
          }
          if ($j % 2 == 0) {
            if ($steps[$i+$j/2][$j/2] == 0) {
              $steps[$i+$j/2][$j/2] = $newstep;
              $moresteps = 1;
            }
            if ($steps[$i][$j/2] == 0) {
              $steps[$i][$j/2] = $newstep;
              $moresteps = 1;
            }
          }
          if ($k % 2 == 0) {
            if ($steps[$i+$k/2][$j] == 0) {
              $steps[$i+$k/2][$j] = $newstep;
              $moresteps = 1;
            }
            if ($steps[$i][$j+$k/2] == 0) {
              $steps[$i][$j+$k/2] = $newstep;
              $moresteps = 1;
            }
          }
        }
      }
    }
  } while ($moresteps);
  
  # See if all states were reached
  for (my $i=1; $i<$beans; $i++) {
    for (my $j=1; $j<$beans-$i; $j++) {
      if ($steps[$i][$j] == 0) {
        print "Could not clean a plate from state $i, $j, " . ($beans-$i-$j) . "\n";
        exit;
      }
    }
  }
  
  # If all states could be reached, print the maximum
  # number of moves to reach an empty plate in the
  # second column of the output. Remember that on the
  # last run through the loop, no new states were
  # numbered with the current value of $newstep, and
  # the states with empty plates were labeled with 1,
  # so the maximum number of steps will be the value
  # of $newstep minus 2.
  print " " . ($newstep - 2) . "\n";
}

Edited January 22, 2018 by plasmid
fixed the display of the perl code

[bonanova]

@plasmid Does the program imply a proof that it can always be done? Or is it a statement that no counterexample has yet been found?

A proof could be a repeated procedure which after each application reduces the smallest number of beans on a plate. Does your algorithm always reduce the number on place C?

[plasmid]

20 minutes ago, bonanova said:

@plasmid Does the program imply a proof that it can always be done? Or is it a statement that no counterexample has yet been found?

A proof could be a repeated procedure which after each application reduces the smallest number of beans on a plate. Does your algorithm always reduce the number on place C?

The program isn't a proof, it's just an application of a greedy algorithm that starts from states with an empty plate and works backwards to see whether every state could eventually reach one with an empty plate. It covered every possible state for up to 500 jelly beans, but it doesn't prove that a plate can always be cleared if you have something like 8x10¹² jelly beans.

Spoiler

I tried looking at the output of the matrix of how many moves it takes to reach an empty plate for the case of 500 jelly beans, and got the following image before my computer konked out colored in ROY G BIV from red = 1 move to blue = 10 moves. It's kind of neat, but doesn't clearly lend itself to coming up with an algorithm that's guaranteed to work.

 

[bonanova]

It must be symmetric about  the NW-SE diagonal, so your figure show all the cases you computed. Nice, btw.

Hint

Spoiler

If plates are labeled so that C > B > A, I'm aware of an algorithm that identifies a sequence of moves, each being either from B to A or from C to A, that reduces either plate B or plate C to (strictly) fewer beans than plate A had. You can then relabel the plates so that again C > B > A, repeat the procedure, and march on to zero. Finding such an algorithm then constitutes a proof.

Hint

Spoiler

The algorithm depends only on the number of beans in plates A and B.

 

 

[plasmid]

On 1/22/2018 at 11:17 AM, bonanova said:

It must be symmetric about  the NW-SE diagonal, so your figure show all the cases you computed. Nice, btw.

Hint

  Hide contents

If plates are labeled so that C > B > A, I'm aware of an algorithm that identifies a sequence of moves, each being either from B to A or from C to A, that reduces either plate B or plate C to (strictly) fewer beans than plate A had. You can then relabel the plates so that again C > B > A, repeat the procedure, and march on to zero. Finding such an algorithm then constitutes a proof.

Hint

  Hide contents

The algorithm depends only on the number of beans in plates A and B.

 

 

Ah, this is probably what you have in mind.

Spoiler

 

Suppose you have (A, B, C) where A < B < C and A=1.

B can be written in binary.

If the binary ones digit of B is 1 then transfer a bean from B to A, and if the binary ones digit of B is 0 then transfer a bean from C to A. Either way, A will now be 2 (or 10 in binary) and the ones unit of B in binary will be 0.

Repeat with each subsequent digit of B in binary, and you’ll eventually clear out B.

 

Suppose you have (A, B, C) where A < B < C, and A > 1.

Divide all the numbers by A, throwing out the remainder, and proceed with the algorithm above. B will be reduced to whatever remainder was left over after dividing by A, which will of course be less than A.

 

 

[bonanova]

16 hours ago, plasmid said:

Ah, this is probably what you have in mind.

  Hide contents

 

Suppose you have (A, B, C) where A < B < C and A=1.

B can be written in binary.

If the binary ones digit of B is 1 then transfer a bean from B to A, and if the binary ones digit of B is 0 then transfer a bean from C to A. Either way, A will now be 2 (or 10 in binary) and the ones unit of B in binary will be 0.

Repeat with each subsequent digit of B in binary, and you’ll eventually clear out B.

 

Suppose you have (A, B, C) where A < B < C, and A > 1.

Divide all the numbers by A, throwing out the remainder, and proceed with the algorithm above. B will be reduced to whatever remainder was left over after dividing by A, which will of course be less than A.

 

 

That's it. Binary representation of B/A indicates moves to make B smaller than A was. Rinse and repeat. Nice.