Shortest loop?
ptane...@hotmail.com
Is there a short sequence of dice rolls that could
reproduce the starting position? Also, is it possible to
prove a lower bound on the length of such a sequence?
Of course, we assume that the players will conspire
to achieve this result.
Paul T.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
Stephen Turner
other person on roll) allowed? If so, I can manage 7:
63: 24/15 33: 13/10*/1*
11: b/24(2) 6/5 8/7 54: b/20*/16
56: b/14 21: 16/13
61: 14/8 7/6
I don't immediately have a proof that this is shortest, though it must be at
least close.
--
Stephen Turner sr...@cam.ac.uk http://www.statslab.cam.ac.uk/~sret1/
Normally: Statistical Laboratory, 16 Mill Lane, Cambridge CB2 1SB, England
Until 12/98: Dept of Math & Stats, 585 King Edward Ave, Ottawa K1N 6N5, Canada
"Ad infinitum, if not ad nauseam." (Interviewee, BBC Radio 4)
JDPeh
> Is there a short sequence of dice rolls that could
>reproduce the starting position? Also, is it possible to
>prove a lower bound on the length of such a sequence?
> Of course, we assume that the players will conspire
>to achieve this result.
My initial crack at it gives a short, but not quite
according to the rules, answer.
The sequence of rolls, and moves of X and O
using 1..24 point movement:
The english summary:
Bring one down and in to the five point.
Hit it and escape.
Enter, to the bar point.
Run the escapee.
Hit it back, and restore half the position.
Enter with a one, and stop.
11 dice are needed. The last one is
not.
62 (13-5) 54 (1-5* 5-10)
43 ( 18 ) 32 ( 10-15 )
32 ( 18-15*-13 ) 1x enter, take a picture, play x.
So, momentarily, in a very short sequence, the original
position repeats. There are minor variations.
-Dan
Gary Wong
> Nice puzzle. Are ones that get back in an odd number of moves (i.e., with the
> other person on roll) allowed? If so, I can manage 7:
>
> 63: 24/15 33: 13/10*/1*
> 11: b/24(2) 6/5 8/7 54: b/20*/16
> 56: b/14 21: 16/13
> 61: 14/8 7/6
>
> I don't immediately have a proof that this is shortest, though it must be at
> least close.
That's pretty good, but it can be done in less... Tom Keith and Ole Jensen
posted (independent, but similar) five roll solutions in the thread "silly
backgammon puzzle" in November '96 (articles <327FAB...@io.org> and
<yvtlocg...@iris.cl.cam.ac.uk> respectively). Ole also gives some nice
reasoning showing it appears to be impossible to achieve in fewer rolls.
If you don't like odd numbers of rolld, Peter Bell and Alexander Nitschke
posted solutions in 6 (ie. 3 moves each).
Tom Keith
31: 13/9 44: 24/16*, 13/5
32: bar/20* 31: bar/24, 16/13
43: 20/13
Ole Jensen
41: 13/9 24/23 44: 24/16* 13/5
31: bar/24 23/20* 11: bar/24 16/13
52: 20/13
Silly me, playing an opening 31 as 8/5 6/5 all this time -- it turns out to
be better to play 13/9 so that you have the potential to return to the start
in 4 more moves. Naturally, it's then not the first roll of the game any
more, so you're free to roll 66 -- a much better number than that hopeless
31 opener :-)
Cheers,
Gary.
--
Gary Wong, Department of Computer Science, University of Arizona
ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/
Murat Kalinyaprak
>Nice puzzle. Are ones that get back in an odd number
>of moves (i.e., with the other person on roll) allowed?
>If so, I can manage 7:
> 63: 24/15 33: 13/10*/1*
> 11: b/24(2) 6/5 8/7 54: b/20*/16
> 56: b/14 21: 16/13
> 61: 14/8 7/6
>I don't immediately have a proof that this is shortest,
>though it must be at least close.
Here is one with 5 rolls and no moves left unplayed:
44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
51: 25/24 25/20* 31: 25/24 16/13
61: 20/14 14/13
The last roll/moves could also be "52: 20/15 15/13"
or "43: 20/16 16/13". Actually, after the 44's, there
can be a variety of 3 rolls which can accomplish the
same in a total of 5 rolls, with all moves completed,
like:
44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
54: 25/20* 20/16 31: 25/24 16/13
31: 25/24 16/13
44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
54: 25/20* 20/16 11: 25/1 16/15 15/14 14/13
11: 25/1 16/15 15/14 14/13
44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
52: 25/20* 20/18 31: 25/24 16/13
51: 25/24 18/13
Etc... Can it be done in less than 5 rolls, whether
the last roll completely played or not?
MK
Murat Kalinyaprak
>That's pretty good, but it can be done in less... Tom Keith
>and Ole Jensen posted (independent, but similar) five roll
>solutions in the thread "silly backgammon puzzle" in November
>'96... Ole also gives some nice reasoning showing it appears
>to be impossible to achieve in fewer rolls. If you don't like
>odd numbers of rolld, Peter Bell and Alexander Nitschke
>posted solutions in 6 (ie. 3 moves each).
>Tom Keith
>31: 13/9 44: 24/16*, 13/5
>32: bar/20* 31: bar/24, 16/13
>43: 20/13
>Ole Jensen
>41: 13/9 24/23 44: 24/16* 13/5
>31: bar/24 23/20* 11: bar/24 16/13
>52: 20/13
I also posted several 5-roll possibilities a few
days ago, but my solutions allowed doubles in the
first roll (as would be in traditional playing).
In fact, if doubles are allowed, there are many
more 5-roll solutions that I later discovered
with double 3's instead of double 4's, etc.
I also came up with this 4-roll solution (which
allows an initial double):
44: 24/16 13/5 22: 24/22 22/20* 20/18 13/11
11: bar/24 16/15 15/14* 14/13 15: bar/24 18/13
Even for the ones who may want to stick with the
rule that the first roll cannot be a double, it
should still qualify as a valid solution at least
for a "second iteration" of the loop.
MK
BTW: Does anyone know how/when/where this rule of
the player rolling the high number having to play
the combination resulting while deciding who will
go first came about?
Stephen Turner
>
>
> Here is one with 5 rolls and no moves left unplayed:
>
> 44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
> 51: 25/24 25/20* 31: 25/24 16/13
> 61: 20/14 14/13
>
Oh, I was only thinking of sequences that could be the opening of a game,
i.e., not starting with a double. Can anyone beat 7 on this basis?
> 44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
> 54: 25/20* 20/16 31: 25/24 16/13
> 31: 25/24 16/13
No, this doesn't work because the third half-move is illegal.
Murat Kalinyaprak
MK
the resulting combination while deciding who will
go first came about?
Murat Kalinyaprak
>Murat Kalinyaprak wrote:
>> Here is one with 5 rolls and no moves left unplayed:
>> 44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
>> 51: 25/24 25/20* 31: 25/24 16/13
>> 61: 20/14 14/13
>Oh, I was only thinking of sequences that could be the
>opening of a game, i.e., not starting with a double.
Being of Middle-East background, I have difficulty
keeping this variation of rule always in mind. It
occurred to me after I posted the above and specified
it when I posted a subsequent 4-roll solution (also
valid only if doubles are allowed at the opening of
a game or as a second iteration of the loop).
I'm not sure if all articles posted are disseminated
regularly, so I'll include it here again:
44: 24/16 13/5 22: 24/22 22/20* 20/18 13/11
11: bar/24 16/15 15/14* 14/13 15: bar/24 18/13
>Can anyone beat 7 on this basis?
Apparently so. Somebody has posted 5-roll solutions
beginning with non-doubles.
>> 44: 24/20 20/16 13/9 9/5 44: 24/20* 20/16 13/9* 9/5
>> 54: 25/20* 20/16 31: 25/24 16/13
>> 31: 25/24 16/13
>No, this doesn't work because the third half-move is illegal.
You're right. Thanks for paying attention to details
and correcting me.
MK