mathematical game

[Michael Verschaeve]

In Plato's heaven, there exist an infinite number of bowls in a straight
line. Each either contains some or none of a finite number of kidney beans.
A peculiar woman plays a game, which allows only one kind of move: removing
two kidney beans from any bowl, and putting one in each of the two adjacent
bowls. The game ends when each bowl contains either one or no kidney beans.
Prove that, given an initial arrangement of beans, the game terminates at
the same final position after the same number of moves, no matter how she
plays.

This one was posted a long time ago on the recreational mathematics
delphi-forum, the poster never provided a solution and no one at that forum
did either. Over the years (it was posted about three years ago) it has come
back several times in my mind to haunt me. I can prove that the game ends in
a finite number of moves and that if the game indeed ends in a final state
that the number of moves is constant (I actually can calculate the number of
moves). Can anyone solve the problem completely?

Yours sincerely

Michael Verschaeve

[Hace]

> Prove that, given an initial arrangement of beans, the game terminates at
> the same final position after the same number of moves, no matter how she
> plays.

Well I can't prove anything but at least I found out that for a given
random _initial_ arrangement, there always exists one and only one
'parent' initial arrangement that is also the ultimate 'pivot' of that
arrangement.

An example of what I mean:

Suppose you have the initial arrangement:

A B C D E F G H
0 0 1 2 2 1 0 0

Than the ultimate 'pivot' arrangement is:

A B C D E F G H
0 0 0 3 3 0 0 0

So with 'parent pivot' I have moved 'backward' and searched the pivot
of the bowls, which is at bowls D and E.

For another more difficult example:
A B C D E F G H
0 5 3 6 0 2 5 0

Has the pivot parent:

A B C D E F G H
0 0 0 15 6 0 0 0

Which, if you play the game the lady is playing, will have the same
outcome.

> that the number of moves is constant (I actually can calculate the number of
> moves). Can anyone solve the problem completely?

My addition is that the 'pivot parent' has the most number of moves to
get to the same outcome.

Cheers,
Hace
http://hace.dyndns.org/

[Revoklaw]

This was a great puzzle. I think I've finally cracked it though!

Let's define a 'move on pot p' to be the process of taking two beans from p
and putting one in each of the neighbors.
Let's say I watch the woman play out a game. Surely only a finite number of
pots were used, so let's call these 1,2,...,m, with 1 a neighbor of 2 a
neighbor of 3, etc. Then I construct a function f so that f(i) is the number
of times over the course of the game the lady made a move on pot i. There's
also a function g so that g(i) is the number of beans that started in pot i.
Let h(i) denote the number of beans that finish in pot i.

What we are asked to show is that g uniquely determines h. Before we
consider that, though - will you believe that f and g together uniquely
determine h? A moments thought will show that h(i) =
g(i)+f(i-1)+f(i+1)-2f(i), so the answer is yes. (Take the undefined f(0) and
f(m+1) to equal 0.) Which means that as long as we know how many times made
a move on each pot, we do not need to know what order the moves were made
in - that information is totally irrelevant, and does not influence the
value of h in the least.

Let me define a 'game sequence' i_1, i_2,..., i_n as a game the lady plays
in which she fist makes a move on pot i_1, then on i_2, and so on until
after she makes a move on pot i_n, at which point she finishes with at most
one bean in each pot. The above argument shows that since the order of moves
isn't important, the game sequence i_1, i_2,..., i_n has the same final
result (in terms of which pots have beans) as any permutation of those
moves, assuming the permutation still defines a valid game. (i.e., no pot
ever has negative beans in it).

Now for our proof.
Let's say that there is some initial configuration of beans in pots so that
there are two different games the lady could play which lead to different
final arrangements. Denote these two games by gane sequence A, i_1,
i_2,...i_n, and game sequence B, j_1, j_2,....j_n', and assume n <= n'.
Since the games have different final outcomes, the sequences are not
identical, so let k be the smallest index such that i_k doesn't equal j_k.
(Possibly, k = 1.)

So the games were identical up to the kth move. Since it was legal to do a
move on pot i_k with that configuration of beans, pot i_k must have had two
or more beans in it at that point. There's no way to decrease the number of
beans in a pot unless you actually move with that pot, right? But each pot
will have at most one bean at the end, right? Which means there must be some
index k' > k so that j_k' = i_k. (Meaning that even though in game B we
didn't make a move on pot i_k at the kth stage, we must have eventually make
a move on it.)

However, as already argued, the order in which the moves are made doesn't
matter. So, we can change the game sequence B into B', which is
j_1, j_2,...,j_(k-1), j_k', j_k, j_(k+1),...,j_(k'-1), j_(k'+1),....j_n'
In words, just perform the move j_k', which we know must eventually be
played, earlier on - at the same time as we play it in the first game.

This modified second game is still a valid game, since the only thing that's
not the same as before was that we performed j_k' earlier, and we know that
that pot had at least two beans in it, so we're alright. Since B' is just a
permutation of B, it still has the same final result as the second game.
However, it now has the first k moves in common with game A instead of just
the first k-1 moves. Inductively apply this procedure now, and before long
we will have a valid game which is a permutation of B which has the first n
moves in common with game A. But game A ended after those very n moves, so
there are no more legal moves. The second game must therefore end at that
stage as well, and thus the games have the same final output.

This establishes that all games have the same final configuration of beans,
and all games take the same number of turns. It relies on the facts that any
game uses only a finite number of pots and a finite number of moves, both of
which are fairly easy to show.

-Asher Walkover
(To reply via email, my address is a hotmail account, not an aol one.)

Michael Verschaeve <Michael.V...@rug.ac.be> wrote in message
news:Oawr9.165918$8o4....@afrodite.telenet-ops.be...

[Michael Verschaeve]

"Revoklaw" <revo...@aol.com> schreef in bericht
news:aov7ku$pbo$1...@news01.cit.cornell.edu...

> This was a great puzzle. I think I've finally cracked it though!
>

Congratulations, I can find no flaw in your proof.
Before I've read your post, I solved the problem myself in more or less the
same way and posted my solution on a dutch newsgroup: nl.hobby.puzzel
Your (in my opinion succesfull) attack is however a way more formal proof.

You did a very good job !

Michael Verschaeve

[Geert-Jan van Opdorp]

Does the following short reasoning hold?

Because a chosen move never disables other possible moves, and because
all possible moves must eventually be made, the final configuration
cannot depend on the order of moves.

--
Geert-Jan van Opdorp
Diff Automatisering
Amsterdam

[Michael Verschaeve]

"Geert-Jan van Opdorp" <ge...@diff.nl> schreef in bericht
news:m24rbfu...@diff.nl...

>
>
> Does the following short reasoning hold?
>
> Because a chosen move never disables other possible moves, and because
> all possible moves must eventually be made, the final configuration
> cannot depend on the order of moves.
>

Your short reasoning doesn't take in account that new possible moves are
created while playing. However, ever new possible move will be created
eventually and made eventually.

Not every permutation of the moves is a valid game, every valid game is
however a permutation of the moves. For the happy few, given an initial
configuration, how many different ways are there to play a game ? With
different ways being the number of permutations of a game that give a valid
game.

Yours sincerely,

Michael Verschaeve

[Hace]

Geert-Jan van Opdorp schreef:

>Does the following short reasoning hold?
>
>Because a chosen move never disables other possible moves, and because
>all possible moves must eventually be made, the final configuration
>cannot depend on the order of moves.

Sounds reasonable but moves will also create new moves while playing,
just as Michael said.

If you want to play around with this game, I've created a windows
program for it:
http://hace.dyndns.org/Plato.zip

Cheers,

--
anti-rsi software at: http://hace.dyndns.org/files/rsibreakreminder/
Learning to quote with outlook express:
http://home.in.tum.de/~jain/software/quotefix.php

[mathguy]

Not to be nitpicking Revoklaw's proof, but I see a slight necessary
modification.

At one point you write "Which means there must be some index k' > k so
that j_k' = i_k."
Need to add "let k' be the first index > k so that j_k' = i_k."
Here's why.
With m=6 pots, suppose the starting distribution, g(i), is g(1)=0,
g(2)=1, g(3)=3, g(4)=0, g(5)=2, g(6)=0. Let game sequence A be
3,5,4,3,2 and let game sequence B be 5,3,2,3,4. The first moves are
different, i_1 = 3 and j_4 = 3 (instead of j_2). Now B' becomes
3,5,3,2,4. Now the 3rd move is illegal.