From:mathwft@math.canterbury.ac.nz (Bill Taylor)Date:29 Jul 1997 02:57:37 GMTNewsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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 +0000Newsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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 GMTNewsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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 -0400Newsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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 -0700Newsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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 -0400Newsgroups:rec.games.abstract,sci.math,rec.puzzlesSubject: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.