From ray_sitf@yahoo.co.uk Mon Nov 29 20:35:32 CST 2004 Article: 342470 of sci.math Path: news!news.niu.edu!arclight.uoregon.edu!wn13feed!worldnet.att.net!199.45.49.37!cyclone1.gnilink.net!gnilink.net!news.glorb.com!postnews.google.com!not-for-mail From: ray_sitf@yahoo.co.uk (ray) Newsgroups: alt.math.recreational,sci.math Subject: Problem arising from a board game. (Mancala.) Date: 26 Nov 2004 10:23:16 -0800 Organization: http://groups.google.com Lines: 32 Message-ID: NNTP-Posting-Host: 81.174.213.110 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1101493396 9996 127.0.0.1 (26 Nov 2004 18:23:16 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Fri, 26 Nov 2004 18:23:16 +0000 (UTC) Xref: news sci.math:342470 We have a string of bowls b_0, b_1, b_2, b_3, and so on. Counters are placed into bowls b_1, b_2, b_3,... All the counters have to finish in bowl 0 (b_0) according to the following rule. If there are 3 counters in bowl 3 (b_3) then we can move them by putting one of them in bowl 2, one in bowl 1 and then one in bowl 0. We can only move counters >from bowl j by taking all the counters from bowl j and by putting one counter in every bowl k, where k is less than j, and putting a final counter in bowl 0. Clearly, a move can only take place if we are moving j counters from bowl j. A winning position is an allocation of counters to bowls so that it is possible to clear all the bowls b_1, b_2, b_3,... For example, b_5 = 5, b_4 = 3, b_3 = 1, b_2 = 1, b_1 = 1 i.e. using an obvious notation, (5,3,1,1,1) is a winning position, by the sequence of moves 5,3,1,1,1 5,3,1,1,0 0,4,2,2,1 0,4,2,2,0 0,4,2,0,1 0,4,2,0,0 0,0,3,1,1 0,0,3,1,0 0,0,0,2,1 0,0,0,2,0 0,0,0,0,1 0,0,0,0,0 Note that on each move one more counter is placed in bowl 0, so there are as many moves as there are counters. Let G(n) be the greatest nbr of counters that one can start with that is a winning position with n bowls. Then by my reckoning the values of G(n) for n from 1 to 15 are 1,3,5,9,11,17,21,29,33,41,47,57,59,77,81. But I don't seem to get anything resembling a pattern except that these nbrs are all odd. Is anybody acquainted with this problem that might be able to throw some light? Thanks in advance. From israel@math.ubc.ca Mon Nov 29 20:35:38 CST 2004 Article: 342500 of sci.math Path: news!news.niu.edu!arclight.uoregon.edu!wn14feed!worldnet.att.net!199.218.7.141!news.glorb.com!cyclone.bc.net!nntp.itservices.ubc.ca!not-for-mail From: israel@math.ubc.ca (Robert Israel) Newsgroups: alt.math.recreational,sci.math Subject: Re: Problem arising from a board game. (Mancala.) Date: 26 Nov 2004 19:47:51 GMT Organization: ITServices, University of British Columbia Lines: 18 Message-ID: References: X-Trace: nntp.itservices.ubc.ca 1101498471 27936 137.82.36.63 (26 Nov 2004 19:47:51 GMT) X-Complaints-To: abuse@interchange.ubc.ca X-Newsreader: trn 4.0-test72 (19 April 1999) Xref: news sci.math:342500 In article , ray wrote: >Let G(n) be the greatest nbr of counters that one can start with that >is a winning position with n bowls. Then by my reckoning the values of >G(n) for n from 1 to 15 are >1,3,5,9,11,17,21,29,33,41,47,57,59,77,81. But I don't seem to get >anything resembling a pattern except that these nbrs are all odd. This is sequence A007952 in the online Encyclopedia of Integer Sequences. See and the references given there (especially, I guess, the link to a paper of Broline and Loeb that has Mancala in the title). Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada From lewis@SPYDER.MITRE.ORG Mon Nov 29 20:36:01 CST 2004 Article: 342536 of sci.math Path: news!news.niu.edu!arclight.uoregon.edu!news.tufts.edu!newstransit.mitre.org!news.mitre.org!not-for-mail From: lewis@SPYDER.MITRE.ORG (Keith A. Lewis) Newsgroups: alt.math.recreational,sci.math Subject: Re: Problem arising from a board game. (Mancala.) Date: Fri, 26 Nov 2004 21:04:14 +0000 (UTC) Organization: The MITRE Organization Lines: 53 Message-ID: References: NNTP-Posting-Host: spyder.mitre.org X-Trace: newslocal.mitre.org 1101503054 1352 128.29.35.27 (26 Nov 2004 21:04:14 GMT) X-Complaints-To: news@mitre.org NNTP-Posting-Date: Fri, 26 Nov 2004 21:04:14 +0000 (UTC) Xref: news sci.math:342536 ray_sitf@yahoo.co.uk (ray) writes in article dated 26 Nov 2004 10:23:16 -0800: >We have a string of bowls b_0, b_1, b_2, b_3, and so on. Counters are >placed into bowls b_1, b_2, b_3,... All the counters have to finish in >bowl 0 (b_0) according to the following rule. If there are 3 counters >in bowl 3 (b_3) then we can move them by putting one of them in bowl >2, one in bowl 1 and then one in bowl 0. We can only move counters >from bowl j by taking all the counters from bowl j and by putting one >counter in every bowl k, where k is less than j, and putting a final >counter in bowl 0. Clearly, a move can only take place if we are >moving j counters from bowl j. > >A winning position is an allocation of counters to bowls so that it is >possible to clear all the bowls b_1, b_2, b_3,... > >For example, b_5 = 5, b_4 = 3, b_3 = 1, b_2 = 1, b_1 = 1 i.e. using >an obvious notation, (5,3,1,1,1) is a winning position, by the >sequence of moves > >5,3,1,1,1 5,3,1,1,0 0,4,2,2,1 0,4,2,2,0 >0,4,2,0,1 0,4,2,0,0 0,0,3,1,1 0,0,3,1,0 >0,0,0,2,1 0,0,0,2,0 0,0,0,0,1 0,0,0,0,0 > >Note that on each move one more counter is placed in bowl 0, so there >are as many moves as there are counters. > >Let G(n) be the greatest nbr of counters that one can start with that >is a winning position with n bowls. Then by my reckoning the values of >G(n) for n from 1 to 15 are >1,3,5,9,11,17,21,29,33,41,47,57,59,77,81. But I don't seem to get >anything resembling a pattern except that these nbrs are all odd. The number of counters in bowl k at the beginning, plus the number of moves >from greater bowls, must be 0 mod k. Calculation is pretty straightforward. The only time you have a choice is when the options for bowl k are 0 and k, and for the maximum you clearly want to choose k. Take n=10... Max for b_10 is 10, which represents 1 move at that level. b_9 + 1 = 0 mod 9; b_9 = 8, 2 moves. b_8 + 2 = 0 mod 8; b_8 = 6, 3 moves. b_7 + 3 = 0 mod 7; b_7 = 4, 4 moves. b_6 + 4 = 0 mod 6; b_6 = 2, 5 moves. b_5 + 5 = 0 mod 5; b_5 = 5 (high option), 7 moves. b_4 + 7 = 0 mod 4; b_4 = 1, 9 moves. b_3 + 9 = 0 mod 3; b_3 = 3 (high option), 13 moves. b_2 + 13 = 0 mod 2; b_2 = 1, 20 moves. b_1 = 1 (high option); 41 moves total. The oddness property comes from b_2 forcing an even total and then b_1=1. --Keith Lewis klewis {at} mitre.org The above may not (yet) represent the opinions of my employer.