8
$\begingroup$

My eldest came home with some interesting maths homework.

We have three bowls containing peas.

Distribute the peas evenly across the bowls, by moving peas from one bowl to another. The only move allowed, is doubling the amount of peas in one bowl by taking them from one other bowl.

For example:
$\begin{array}{rlrlrl} A & & B & & C & \\ \hline 11 & & 6 & & 7 \\ 4 & (-7) & 6 & & 14 & (+7) \\ 4 & & 12 & (+6) & 8 & (-6) \\ 8 & (+4) & 8 & (-4) & 8 \end{array}$

We had some fun with this. We quickly decided that the order of the bowls doesn't matter, so we can just sort them by the number of peas they contain.
Then, there are just three moves possible:

  1. Double the amount of peas in the first bowl (containing the fewest peas) by taking them from the third bowl (containing the most peas)
  2. Double the amount of peas in the first bowl containing the fewest by taking them from the second bowl (containing the neither the most nor the fewest peas)
  3. Double the amount of peas in the second bowl by taking them from the third bowl

From that, we made state diagrams and found our solutions. We also found out that for one of the problems, we could never reach an end state (with all bowls containing the same amount of peas).


But of course I couldn't leave it alone. So I tried to formalise what we did.

The amount of peas in each bowl at any time is of course a positive integer (or possibly 0):
$a_i \le b_i \le c_i \,|\,a_i, b_i, c_i \in \mathbb Z_{\ge 0}$

A solution has the peas distributed equally across the bowls:
$a_i = b_i = c_i$

The total amount of peas at any time is a multiple of 3:
$a_i + b_i + c_i = 3n \,|\,n \in \mathbb Z_{\ge 0}$

The three possible moves:
$\left\{a_{i+1}, b_{i+1}, c_{i+1}\right\} \in \begin{Bmatrix} \left\{2\cdot a_i, b_i, c_i-a_i\right\} \\ \left\{2\cdot a_i, b_i-a_i, c_i\right\} \\ \left\{a_i, 2\cdot b_i, c_i-b_i\right\} \end{Bmatrix}$

The set of possible moves brings us to the conclusion that for each state after the first, at least one bowl contains an even amount of peas. Since in the end state, all bowls contain the same amount of peas, they all contain the same even amount of peas and thus the total number of peas must be even.
If we combine this with the requirement that the total number of peas is a multiple of 3 as well, we see that the total number of peas must be a multiple of 6:
$a_i + b_i + c_i = 6n \,|\,n \in \mathbb Z_{\ge 0}$

(Ignoring the very trivial case where we start with a solved state).


But these conditions aren't sufficient to guarantee a solvable puzzle. For instance, $\left\{a_0, b_0, c_0\right\} = \left\{6,12,24\right\}$ is not solvable. The only reachable states are $$\begin{Bmatrix} \left\{ 6, 12, 24 \right\} \\ \left\{12, 12, 18 \right\} \\ \left\{ 0, 18, 24 \right\} \\ \left\{ 0, 6, 36 \right\} \\ \left\{ 0, 12, 30 \right\} \\ \end{Bmatrix}$$ neither of which is an end state.

So what additional conditions do we need to define to make such a puzzle sovable?


Problems can have multiple solutions. See for instance this example, with two possible paths to a solution:

$\begin{array}{rlrlrl} A & & B & & C & \\ \hline 11 & & 6 & & 7 \\ 4 & (-7) & 6 & & 14 & (+7) \\ 4 & & 12 & (+6) & 8 & (-6) \\ 8 & (+4) & 8 & (-4) & 8 \end{array}$

and

$\begin{array}{rlrlrl} A & & B & & C & \\ \hline 11 & & 6 & & 7 \\ 5 & (-6) & 12 & (+6) & 7 & \\ 10 & (+5) & 12 & & 2 & (-5) \\ 8 & (-2) & 12 & & 4 & (+2) \\ 8 & & 8 & (-4) & 8 & (+4) \end{array}$

The only way to solve a problem that I've come up so far, is drawing a state diagram and determining the shortest path to the end state. But while state diagrams work fine for small numbers of peas, the number of possible states may well explode for higher numbers.

So is there another way to solve these problems?

What is a good strategy to arrive at a solution?


Yes, I'm asking two questions in one, but I don't want to repeat the explanation for a second question. Also, I feel both questions are closely related, since what I'm really looking for is an analysis of this type of problem, if possible even with a variable number of bowls.

$\endgroup$
  • 2
    $\begingroup$ I think your definition of the three possible moves how you present it is not entirely correct because it doesn't account for reordering the bowls again when they are not in ascending order any more $\endgroup$ – Ivo Beckers Oct 13 '15 at 14:20
  • 1
    $\begingroup$ Some observation: If one of the bowls ends up empty at some point you are in an unsolvable state because double zero is still zero. $\endgroup$ – Ivo Beckers Oct 13 '15 at 14:35
  • $\begingroup$ If the number of peas in each bowl share a common divisor, they will always share that same divisor. So in fact the total number of peas must be a multiple of $6$ times the greatest common divisor of the initial numbers of peas in the bowls. $\endgroup$ – Julian Rosen Oct 13 '15 at 15:40
  • $\begingroup$ @IvoBeckers Yes, it's true that my representation of the moves doesn't take the reordering into account, but that doesn't seem to be an important factor. And we indeed encountered the states where one bowl was empty. We continued and found loops, as was to be expected. $\endgroup$ – SQB Oct 13 '15 at 17:05
  • 1
    $\begingroup$ On a whim, I pronounced the puzzle title and was surprised by my pun detector going off! $\endgroup$ – Oliphaunt Feb 27 '16 at 11:55
6
$\begingroup$

If $a_0$, $b_0$, and $c_0$ are positive integers, the puzzle is solvable from an initial state $\{a_0,b_0,c_0\}$ if and only if $$a_0+b_0+c_0=3\cdot 2^m\cdot \gcd(a_0,b_0,c_0)$$ for some $m\geq 0$, where $\gcd(a_0,b_0,c_0)$ denotes the greatest common divisor of $a_0$, $b_0$, and $c_0$.

For $k\geq 3$ an odd number, one can check that if there is a bowl whose pea number is not divisible by $k$, then after making a move there will still be a bowl whose pea number is not divisible by $k$.

Suppose the initial state is $\{a_0,b_0,c_0\}$ is solvable, and let $n=\frac{a_0+b_0+c_0}{3}$ be the desired number of peas in each bowl.
If $k\geq 3$ is an odd number dividing $n$, then in the final state every pea number is divisible by $k$, so the argument above implies that $k$ divides $a_0$, $b_0$, and $c_0$. Every odd divisor of $n$ is a common divisor of $a_0$, $b_0$, and $c_0$, so it must be the case that $n=2^m\cdot \gcd(a_0,b_0,c_0)$, or equivalently $a_0+b_0+c_0=3\cdot 2^m\cdot \gcd(a_0,b_0,c_0)$.

Conversely, suppose $n=2^m\cdot \gcd(a_0,b_0,c_0)$. We can solve the puzzle as follows. If the current state is $\{a,b,c\}$, write $a=2^x a'$, $b=2^y b'$, $c=2^z c'$, where $a'$, $b'$, and $c'$ are odd. The condition on $n$ implies that either $a=b=c$, or that of the three numbers $x$, $y$, and $z$, two will be equal and the third will be larger.
Reordering if necessary, we can assume $x=y<z$ and that $a\leq b$. If $a< b$, replace $\{a,b,c\}$ by $\{2a,b-a,c\}$ and repeat the process. If $a=b$, replace $\{a,b,c\}$ by $\{2a,b,c-a\}$ (if $a<c$) or $\{a-c,b,2c\}$ (if $a>c$) and repeat the process. This will eventually terminate with all three bowls having the same number of peas. The reason this terminates is that if $\{a,b,c\}$ is replaced by $\{2a,b-a,c\}$, then the values of $x$ and $y$ increase by at least one. The replacement with $\{2a,b,c-a\}$ or $\{a-c,b,2c\}$ cannot happen twice in a row, and the size of $x$, $y$, and $z$ must remain bounded.

$\endgroup$

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.