14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Some testing indicates that if you start with a bowl of $n^2+1$ and a bowl of $n^2-1$, $n\in\mathbb{Z^+}$, you will cycle. $\endgroup$ – Tim Thayer Feb 19 '17 at 19:34
  • $\begingroup$ Unfortunately, it fails for the starting positions (7,9) and (6,10) which both cycle. $\endgroup$ – Ola Feb 19 '17 at 19:39
  • $\begingroup$ I was only offering some data I found. I am thinking through the problem... $\endgroup$ – Tim Thayer Feb 19 '17 at 19:44
  • 2
    $\begingroup$ It reminds me somehow to the Collatz conjecture, which is an unsolved problem. $\endgroup$ – Simon Marynissen Feb 19 '17 at 22:06
  • 1
    $\begingroup$ A small pattern that seems to hold is that if neither $m$ or $n$ are $1$ or powers of $2$ then $(m,n)$ and $(n,m)$ are cyclic when $m+n=2^k$ or $m+n=2^k-1$. E.g. if $m+n= 7$ or $8$, or $m+n= 15$ or $16$, or $m+n= 31$ or $32$, etc, then $(m,n)$ and $(n,m)$ are cyclic. $\endgroup$ – Jens Feb 23 '17 at 16:41
11
$\begingroup$

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:

plot of convergents

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.

$\endgroup$
  • 1
    $\begingroup$ Given the similarities between the Collatz conjecture, it would be nice if someone relates this with it. $\endgroup$ – Simon Marynissen Feb 22 '17 at 14:31
  • 1
    $\begingroup$ The plot looks great, thanks! It seems that the sets of states of the form $(i, T-i)$ for fixed T are interesting. If I can see well, it seems that for certain $T$ the corresponding set is all-black, whereas for other $T$ the corresponding set is all-white (except for $i=T/2$ and the $i$'s that are powers of $2$ of course). $\endgroup$ – Evangelos Bampas Feb 23 '17 at 8:54
  • $\begingroup$ You are a beutiful person. Besides the diagonal given by $(i,i)$, there are two diagonals protruding from the origin. On a side note, it would be interesting to see if $T^k(n,m)$ could be extended beyond positive integers. $\endgroup$ – Ola Feb 23 '17 at 15:26
  • $\begingroup$ For the exponent, this would be the same. The map $T$ can be extended to $\mathbb{Z} \times \mathbb{Z}$. I don't know if this map would be injective or surjective. $\endgroup$ – Simon Marynissen Feb 24 '17 at 11:52
  • 2
    $\begingroup$ @SimonMarynissen Isn't your research almost solved the question? $T^{-1}(n,n) = (2n, 0)$, $T^{-1}(2n,0) = (1, 2n-1)$ so $(n,n)$ is indeed in the orbit of $(1, 2n-1)$! $\endgroup$ – didgogns Feb 24 '17 at 15:39
3
$\begingroup$

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$.

$\endgroup$
3
+100
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I gave the bounty to your answer, since you first saw how to answer the $(n,n)$ case. $\endgroup$ – Simon Marynissen Feb 28 '17 at 18:11
1
$\begingroup$

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.

enter image description here

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

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Haha looks like the patterns on bus seats back in my hometown ! $\endgroup$ – G. Fougeron Feb 24 '17 at 16:33

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.