From: mathwft@math.canterbury.ac.nz (Bill Taylor)
Date: 29 Jul 1997 02:57:37 GMT
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Yann's MANCALA problem - solved!
Some while ago, and again a fortnight ago, David Yann posted a very
interesting problem based on the Mancala group of games.
Here again is his mathematically abstracted variant of the games.
####################################################################
Consider a (finite) circular list of boxes and a (finite) set of
tokens. At any time the tokens are distributed between the boxes;
a box may contain any number of tokens (including none at all).
A move consists in taking all the tokens from one of the nonempty
boxes and redistributing them clockwise, one token at a time,
into the boxes, starting with the one following the emptied box -
and without omitting that box.
The question is: given two distributions A and B of the tokens, is
there ALWAYS a series of moves which can bring the game from A to B ?
####################################################################
This is a fascinating problem, to gamers and mathematicians alike,
and if you want to give it a try yourself, do not read any further yet!
David Yann goes on to note:-
>>>
The apparent, "practical" answer is yes: I haven't been able to
come up with a counter-example yet, and I strongly doubt there is
any; on the other hand, I cannot figure any proof of that property
- except in the obvious subcase in which there are less tokens
than boxes. Also, it is very easy to bring all of the tokens
into any of the boxes.
Of course that problem is not extraordinarily general or even
useful, but it has a world of variants; and even the subproblem
with only two boxes is difficult enough, in my opinion.
<<<
All of this is very true.
[SPOILER]
v
v
v
v
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
v
v
I believe I have a complete solution to the problem, which I write
up informally here.
Firstly - the solution is YES:- it is possible to get from any position
to any other position.
Secondly - I too, like David, tried various ways to get a construcvtive
solution, (his second post contains some heroic efforts in this direction),
but finally achieved it with some simple-ish graph theory.
The position-tree is a classic example of a directed graph with both
multiple arcs, and loops; (as is quite common with abstract games).
And for that reason alone is a fun scenario for graph theory teachers.
It is possible to regard positions as being defined only up to
rotational isomorphism, or as completely distinct. i.e. regarding
(1,2,3) and (2,3,1) as the same, or different, respectively. I adopt
the former view, though either is quite convenient; the proof is the
same either way.
Note that it *is* possible for loops to exist:- (2,3,1)-->(3,1,2) by
unloading the 3; and multiple arcs:- (2,2,1)-->(3,2,0) by unloading the
left-hand 2, or the 1. (Taking the sowing direction as left to right).
Now for the proof.
-------------------
Firstly note it is possible to pile up all the tokens into one box;
(into *any* box in the nonisomorphic treatment). Just keep emptying
any loaded boxes *except* your target box - and eventually all will
come to rest there. So (N,0,0,0,...,0,0) is a "universal target".
Now, we note this crucial phenomenon:- For any position, there are
always the *same number* of arcs in as there are arcs out.
--->
Look at a "typical" position... say (4,3,5,4,6). Clearly there are
5 arcs out of it. There are also 5 arcs in:- the 3 box is the only one
that could have been unloaded, and it could have had 15,16,17,18 or 19
tokens in it - depending on where the last token landed. So 5 different
positions are all that could have led to this.
If there are repeated smallest boxes, it is just a little more complex:
position (2,4,2,3,6) could have been entered by emptying the first 2,
with either 10 or 11 tokens in it; or the 2nd 2, with 10,11 or 12 tokens.
Similarly for any number of equal minimum boxes.
If some boxes are zero, this merely reduces both possibilities.
Position (0,4,0,2,7) has only 3 arcs out; but also 3 in, from 1 token
on the first 0-cell, or 1 or 2 on the second. Similarly for any others.
Finally - we have proceeded as if rotated positions were being counted
as different, (easiest to do); but if not, it merely divides both
in-arcs and out-arcs by the same index. e.g. (2,2,2,2,2) has 5
isomorphic out-arcs, only 1 distinct; but also 5 in-arcs (from above),
which must be isomorphic (by symmetry). Similarly, (2,4,2,4,2,4)
has 6 out-arcs, only 2 roto-distinct; and 6 in-arcs, only 2 distinct.
<---
So then - we know that any box, and thus (easily) any group of boxes,
has the same number of ins and outs. Informally, this means there are
no groups acting as sources or sinks anywhere. More precisely, look
at I = the set of positions inaccessible from the Universal Target
(N,0,0,0,...,0). Thus the complementary set has all positions accessible
from UT. But I has some exits to co-I (as anything can get to UT), thus
I must have some *entries* from co-I. But this is impossible, else we
could get from UT into I ! So I = empty; and we are done.
-------------------
Phew! What a mouthful. But it is (EIIDSSM) a rather elegant proof.
More interestingly, it is utterly non-constructive. Of course, any
theorem about finitely checkable procedures cannot be non-constructive
in the *logical* sense, (one can just proceed by exhaustion); but as
we know (e.g. the game "chomp", or any strategy-stealing argument),
there are "psychologically" nonconstructive prooofs.
My guess is that they correspond to solution by non-polynomial methods,
(e.g. by exhaustion). If anyone has more to say on that particular
subject I'd be pleased to hear it.
AFAIK this is an original proof.
Anyone else know? Another little deja news milestone!
------------------
A few further remarks.
Question:- is it possible to obtain either loops or multiple arcs even
when regarding rotated positions as distinct? (No, I'm sure.)
Observation:- it is not always possible to find a Hamiltonian directed
cycle through the position digraph, but it does always
seem to be if there are enough tokens compared to boxes.
(But try e.g. 6 tokens and 2 boxes.)
Can anyone find a result concerning HCs?
Cheers, Bill.
---------------------------------------------------------------------------
The sole purpose of the present appears to be to generate the future.
---------------------------------------------------------------------------
Bill Taylor W.Taylor@math.canterbury.ac.nz
---------------------------------------------------------------------------
Life is a strange attractor in the chaos of the universe.
---------------------------------------------------------------------------
From: Const Razinsky <const@cimatron.co.il>
Date: Wed, 30 Jul 1997 17:37:53 +0000
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Re: Yann's MANCALA problem - solved!
Bill Taylor wrote:
>> --->
> Look at a "typical" position... say (4,3,5,4,6). Clearly there are
> 5 arcs out of it. There are also 5 arcs in:- the 3 box is the only one
> that could have been unloaded, and it could have had 15,16,17,18 or 19
> tokens in it - depending on where the last token landed. So 5 different
> positions are all that could have led to this.
>
> If there are repeated smallest boxes, it is just a little more complex:
> position (2,4,2,3,6) could have been entered by emptying the first 2,
> with either 10 or 11 tokens in it; or the 2nd 2, with 10,11 or 12 tokens.
> Similarly for any number of equal minimum boxes.
>
> If some boxes are zero, this merely reduces both possibilities.
> Position (0,4,0,2,7) has only 3 arcs out; but also 3 in, from 1 token
> on the first 0-cell, or 1 or 2 on the second. Similarly for any others.
>
> Finally - we have proceeded as if rotated positions were being counted
> as different, (easiest to do); but if not, it merely divides both
> in-arcs and out-arcs by the same index. e.g. (2,2,2,2,2) has 5
> isomorphic out-arcs, only 1 distinct; but also 5 in-arcs (from above),
> which must be isomorphic (by symmetry). Similarly, (2,4,2,4,2,4)
> has 6 out-arcs, only 2 roto-distinct; and 6 in-arcs, only 2 distinct.
> <---
>
> So then - we know that any box, and thus (easily) any group of boxes,
> has the same number of ins and outs.
However, position (1,1,1) produces three ones :
(0,2,1) (1,0,2) & (2,1,0)
but has six "in-arcs"
(3,0,0) (0,3,0) (0,0,3) (2,0,1) (1,2,0) & (0,1,2).
--
Cheers,
Const Razinsky
Cimatron Ltd. Israel
From: dahm@informatik.uni-koblenz.de (Peter Dahm)
Date: 30 Jul 1997 15:50:47 GMT
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Re: Yann's MANCALA problem - solved!
In article <33DF7BF1.469B@cimatron.co.il>,
Const Razinsky <const@cimatron.co.il> writes:
>However, position (1,1,1) produces three ones :
>(0,2,1) (1,0,2) & (2,1,0)
>but has six "in-arcs"
>(3,0,0) (0,3,0) (0,0,3) (2,0,1) (1,2,0) & (0,1,2).
The last produce (0,1,2), (2,0,1), (1,2,0), if you unload the 2.
But a more formal proof of indegree = outdegree would be interesting.
--
Peter Dahm
Universitaet Koblenz-Landau, e-mail: dahm@informatik.uni-koblenz.de
Institut fuer Softwaretechnik voice : +49 261 9119-409
Rheinau 1, D-56075 Koblenz, Germany fax : +49 261 9119-499
Was wuerde Rudi Altig dazu sagen?
From: sethb@panix.com (Seth Breidbart)
Date: 30 Jul 1997 13:32:28 -0400
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Re: Yann's MANCALA problem - solved!
In article <5rnnsn$k1c$1@newshost.uni-koblenz.de>,
Peter Dahm <dahm@informatik.uni-koblenz.de> wrote:
>In article <33DF7BF1.469B@cimatron.co.il>,
> Const Razinsky <const@cimatron.co.il> writes:
>
>>However, position (1,1,1) produces three ones :
>>(0,2,1) (1,0,2) & (2,1,0)
>>but has six "in-arcs"
>>(3,0,0) (0,3,0) (0,0,3) (2,0,1) (1,2,0) & (0,1,2).
>The last produce (0,1,2), (2,0,1), (1,2,0), if you unload the 2.
>But a more formal proof of indegree = outdegree would be interesting.
Out-degree is the number of non-zero entries. For in-degree, note
that there's precisely one predecessor that drops its last token into
any non-empty bucket (run the move backwards, picking up tokens as you
go and then dropping all the ones you're holding into the next bucket,
which must be empty, and you can't pick up a token from an empty
bucket so that must be where the move started).
Seth
From: Don Woods <don@clari.net>
Date: 01 Aug 1997 12:46:17 -0700
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Re: Yann's MANCALA problem - solved!
> In article <33DFD2A4.41C6@mail.lns.cornell.edu>,
> Elliot Lipeles <lipeles@mail.lns.cornell.edu> wrote:
> >It has already been shown that you can get from any
> >position to (N,0,0,...,0) using the normal operation.
> >
> >You can also get to this position by operating with
> >the reverse operation: Just keep running the reverse
> >operation on every space except the first. Since you
> >everytime you pass over the first space you deposit
> >one token and you can go until all the space are depleted,
> >the first space will end up with all the tokens.
This is bogus. This is not the "reverse" operation. All you're
doing is running the normal operation counterclockwise instead of
clockwise.
The reverse operation, as someone else posted, is as follows: start
at any non-empty space. Pick up one token from it, then proceed
counterclockwise picking up one token from each space until you come
to a space which (by that time) is empty. Drop all the collected
tokens there.
As the earlier poster noted, this move is unique given the choice of
starting space, so it is an elegant way to prove that indegree equals
outdegree. (I.e., from any position, the number of normal moves and
the number of reverse moves each equals the number of non-empty spaces.)
But it is not obvious how to reach (N,0,0,...,0) from an arbitrary
position using the reverse operation.
Try making the _normal_ (forward) move from (N,0,0,...,0). This takes
you to position X, which is either (k-1,k,k,...,k,k-1,...,k-1) or
(k,k,k,...,k), depending on whether N is a multiple of the number of
spaces. The ONLY way to reach (N,0,0,...,0) from ANY other position via
reverse moves, has to get to this "evenly spread" position first. And
how to do that seems far from obvious.
-- Don.
-------------------------------------------------------------------------------
--
-- Don Woods (don@clari.net) ClariNet provides on-line news.
-- http://www.clari.net/~don I provide personal opinions.
--
From: Elliot Lipeles <lipeles@mail.lns.cornell.edu>
Date: Tue, 05 Aug 1997 19:10:16 -0400
Newsgroups: rec.games.abstract,sci.math,rec.puzzles
Subject: Re: Yann's MANCALA problem - solved!
Bill Taylor wrote:
>
> |> You can also get to this position by operating with
> |> the reverse operation: Just keep running the reverse
> |> operation on every space except the first. Since you
> |> everytime you pass over the first space you deposit
> |> one token and you can go until all the space are depleted,
> |> the first space will end up with all the tokens.
>
> What's all this nonsense?
Okay, Okay
I made a mistake
here is a real proof that you can go from any state to (N,O,O...0)
using the reverse operation
It has already been shown for the forward operation.
-------------------------------------------------------------
Given an arbitrary state consider the set of all states that
you can get to via any sequence of reverse operations. This
set is "closed" under the reverse operationm, so the "in" degree
for the entire set is zero.
out degree set = out degree states - "out"'s give elements of the set
in degree set = in degree states - "in"'s give members of the set
Note that every out that gives and element of the set is an in
that gives an element of the set and
out degree states = in degree states
has already been seen.
so out degree set = in degree set = 0
So the out degree of the set is zero and any state can be sent
to (N,0,0...0) via forward (out) operations so (N,0,0,..,0)
must be in the set of states that can be reached by the reverse
operation.
----------------------------------------------------------------
The rest of the proof is the same as the erroneous previous version.
This of course now hinges on the same details as the original
proof by another poster and is now longer an constructive proof.