Distributing pebbles

Question

The rules to this "game" are simple, but after checking 120 starting positions, i can still not find a single pattern that consistantly holds. I am grateful for the smallest of suggestions.

---

Rules:

You have two bowls with pebbles in each of them.

Pick up the pebbles from one bowl and distribute them equally between both bowls. If the number of pebbles is odd, place the remaining pebble in the other bowl.

If the number of distributed pebbles was even, repeat the rule by picking up the pebbles from the same bowl. If the number of pebbles was odd, repeat the rule by picking up the pebbles from the other bowl.

Continue applying the previous rules until you have to pick up exactly 1 pebble from a bowl, at which point you win.

---

There are some starting positions, however, for which you will never be able to win. If the number of pebbles in the bowls are 5 and 3 respectively, you will cycle on forever.

---

Question:

Depending on the number of pebbles in each bowl at the starting position, can you easily predict if that position will be winnable/unwinnable?

Edit: Here is some python code i wrote to generate answers for given starting values: http://codepad.org/IC4pp2vH

Picking up $2^n$ pebbles will guarantee a win.

Edit:

As shown by didgogns, starting with n pebbles in both bowls always results in a win.

Answer 1

This is only a partial answer, but it's a bit too large to put in a comment. I will use $\mathbb{N}$ to be the set of positive integers, which includes zero.

We can represent the bowls as a couple of positive integers (can be zero) $(m, n)$. The first integer is the number of pebbles from the bowl you're picking from. The second integer is the number of pebbles in the other bowl. Now, if $m$ is even we go to $(m/2, n + m/2)$, where we are still going to pick from the first bowl. If $m$ is odd we go to $(n + (m+1)/2, (m-1)/2)$ (we swapped the two bowls, so we always pick pebbles from the first bowl. Abstractly we can model this as the following function: $$T:\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}:(m,n) \mapsto \begin{cases} \left(\frac{m}{2}, n + \frac{m}{2}\right) & \text{if }m\text{ is even} \\ \left(n+\frac{m+1}{2}, \frac{m-1}{2}\right) & \text{if }m\text{ is odd}\end{cases}$$ Your question can now be translated to the question: For which $(m, n)$ there exists a $k \in \mathbb{N}$ such that $T^k(m,n)=(1, m+n-1)$, where $T^k$ is $T$ applied $k$ times and $T^0(m,n)=(m,n)$.

Properties of $T$:

The map $T$ is surjective. Take $m,n \in \mathbb{N}$. If $n \geq m$, then $T(2m, n-m)=(m,n)$. If $n<m$, then $T(2n+1, m-n-1)=(m,n)$.

The map $T$ is injective. Let $m,n,k,l \in \mathbb{N}$ such that $T(m,n)=T(k,l)$. If both $m$ and $k$ are even, then $(m,n)=(k,l)$. If both $m$ and $k$ are odd, then $(m,n)=(k,l)$. Without loss of generality we now can assume that $m$ is even and $k$ is odd. Since $T(m,n)=T(k,l)$ we get that $$\begin{cases} \frac{m}{2}=l + \frac{k+1}{2} \\ n+\frac{m}{2}=\frac{k-1}{2}\end{cases}$$ Since $n \geq 0$ we get that $\frac{k-1}{2} =n +\frac{m}{2} \geq \frac{m}{2} = l + \frac{k+1}{2}$, hence $l \leq -1$, which is a contradiction. This proves that $T$ is injective, hence $T$ is bijective.

The orbit of $(m,n)$ is a subset of $\{(k,l) \in \mathbb{N} \times \mathbb{N} \mid k+l=m+n\}$, hence finite. This means that there is a $k \in \mathbb{N}$ such that $T^k(m, n)=(m,n)$. This $k$ is smaller or equal to the size of its orbit, hence $k \leq m+n+1$. This also means that if $T^k(m,n) = (1, m+n-1)$, then $k \leq m+n$. It is easy to see that

$T^k(m,n)=(1, m+n-1)$ for some $k \in \mathbb{N}$ if and only if $(1, m+n-1)$ is in the orbit of $(m,n)$.

We can calculate the orbit of $(1,m+n-1)$ by keep applying $T^{-1}$ ($T$ is also possible). In our proof of the surjectivity we basically found the inverse $$T^{-1}:\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}:(m,n) \mapsto \begin{cases} \left(2m, n -m\right) & \text{if }m \leq n \\ \left(2n+1, m-n-1\right) & \text{if }m > n\end{cases}$$ Let $k$ be an integer such that $2^k \leq n+m$, i.e. $2^{k-1} \leq n+m-2^{k-1}$, then $T^k(1, n+m-1)=T^{k-1}(2, n+m-2)=\cdots=(2^k, n+m-2^k)$. If $K$ is the biggest integer such that $2^K \leq n+m$, i.e. $2^K \leq n+m < 2^{K+1}$, then we get that $(2n+2m-2^{K+1} + 1, 2^{K+1}-n-m-1)$ is in the orbit of $(1, n+m-1)$.

To get to the computational side of this, you could start with $(1, m+n-1)$ and keep applying $T^{-1}$ (you can also use $T$) until you get $(1, m+n-1)$ back. All intermediate values are the pairs $(k,l)$ such that $k+l=m+n$ and $T^d(k,l)=(1, m+n-1)$ for some $d \in \mathbb{N}$.

I know it's just a partial answer, but I hope I've been able to help you.

---

Update

As suggested by Evangelos Bampas:

This is a plot such that a square at coordinate $(m,n)$ is coloured black if $T^k(m,n)=(1, m+n-1)$ for some $k \in \mathbb{N}$, and coloured white otherwise. You can see vertical lines corresponding to $(2^k, n)$.

---

Update 2

didgogns showed that $(n,n)$ (for $n > 0$) always results in win since $T^2(1, 2n-1) = (n,n)$. Now similar to this, we have that the tuples $(n, n+1)$ with $n>0$ always win. This is because $$T^2(1, 2n)=T(2n+1,0)=(n+1, n).$$

For every $n> 0$ and $\ell\geq k$ the tuple $(2^k n, (2^\ell-2^k)n)$ always wins since $$T^{\ell-k+1}(1, 2^\ell n-1) = T^{\ell-k}(2^\ell n, 0)=(2^kn, (2^\ell-2^k)n)$$ By taking $k=0$ we get the lines (starting from the origin) above the diagonal.

Answer 2

PARTIAL ANSWER

Let:

• the bowls be $A$ and $B$
• that we start by picking from bowl $A$
• the position with $a$ pebbles in bowl $A$ and $b$ pebbles in bowl $B$ be represented by $p(a,b)$
• the position with $a$ pebbles in bowl $A$ and $t-a$ pebbles in bowl $B$ be represented by $Pt(a)$, for example $P5(2)$
• the function $f$ map each possible position to its consequent
• the function $F$ be the inverse of $f$.

As has been shown by Simon,

$f(p(a,b))= \begin{cases} p(\frac a2,\frac a2+b), &\text{if $a$ is even}\\ p(b+\frac{a+1}2,\frac{a-1}2),&\text{if $a$ is odd.} \end{cases}$

In the $P$ notation,

$f(Pt(a))= \begin{cases} Pt(\frac a2), &\text{if $a$ is even}\\ Pt(t-\frac{a-1}2),&\text{if $a$ is odd.} \end{cases}$

It is easy to see that bowl $A$ will always contain between $1$ and $t$ pebbles inclusive, which is a finite number of possibilities, thus $f^n$ always cycles (there is always a natural number $n$ such that $f^n(Pt(a))=Pt(a)$).

Let the set of positions $f^n(Pt(x))$ cycles through be $Ct(x)$. Because $f$ is bijective, as has also been shown by Simon, $Pt(x)\in Ct(x)$.

It is clear that the position $Pt(x)$ is winnable if and only if $Pt(1)\in Ct(x)$. Now consider that it is the case. Because it is also the case that $Pt(x)\in Ct(x)$, $Pt(1)$ and $Pt(x)$ are in the same cycle, thus $Ct(x)=Ct(1)$. Therefore, we can conclude that $Pt(x)\in Ct(1)$.

Restating, $Pt(x)$ is winnable if and only if $Pt(x)\in Ct(1)$.

Consider that because $f$ is bijective, $F^{n}(Pt(x))$ also cycles through the positions in $Ct(x)$. As has also been shown by Simon,

$F(Pt(a))= \begin{cases} Pt(2a), &\text{if $a\le\frac t2$}\\ Pt(-2a+2t+1),&\text{if $a>\frac t2$} \end{cases}$

So, in checking whether $Pt(x)$ is a member of $Ct(x)$, we can iterate $F(Pt(1))$ and see if the iteration reaches $Pt(x)$.

Let the value of the number inside $Pt$'s parentheses in $F^i(Pt(1))$ be $k_i$. Consider that $k_0=1$ and $k_i$ is either $2k_{i-1}$ or $-(2k_{i-1}-(2t+1))$ for every positive integer $i$. Therefore, $k_i=\pm2^i\mp(2t+1)m$ for some non-negative integer $m$ (the signs being opposite can be easily proved). Rearranging the equation yields $$k_i=\pm(2^i-(2t+1)m)\text.$$ Now it's just an existence problem. $Pt(x)$ is winnable if and only if there exists non-negative integers $i$ and $m$ such that $x=2^i-(2t+1)m$ or $x=(2t+1)m-2^i$.

Answer 3

Here's another image (1000x1000), similar to that of Simon Marynissen. Here the red pixels correspond to the unwinnable states. The rest are painted dark or light according to its "normalized distance" $k/(n+m)$ to the final winner state - black pixels take (relatively) few moves to win, white pixels take many moves.

Not very illuminating, I'm afraid. Here's a zoom of the first 100x100 values.

Answer 4

By the result of Simon, $T^k(n,n)=(1,2n−1)$ for some $k∈N$ if and only if $(1,2n−1)$ is in the orbit of $(n,n)$.

$(1,2n−1)$ is in the orbit of $(n,n)$ if and only if $(n,n)$ is in the orbit of $(1,2n−1)$.

Indeed, $$T^2(1,2n-1)=T(2n,0)=(n,n)$$ and it is obvious that there exist $a$ such that $T^a(1,2n-1)=(1,2n-1)$. $T^{a-2}(1,2n-1)=(n,n)$ because T is bijective and you always win the game at $(n,n)$.