[seqfan] Re: Glass worst worms

Jacques Tramu jacques.tramu at echolalie.com
Mon Mar 9 23:36:14 CET 2009


We could also consider the worst worms case :
What is the starting configuration which leads to the larger number of 
moves,
before detecting a cycle ?

I found the following (not exhaustive search)
sequence for glasses = 1 to 11 :

number of glasses , {start config}  , max moves to cycle detection

1 {0} 1
2  { 0, 1} 2
3 { 1, 0, 1}      4
4 { 0, 1, 1, 1}   7
5 { 0, 1, 0, 2, 1}        10
6 { 3, 0, 0, 0, 0, 2}     13
7 { 2, 0, 0, 5, 4, 4, 1}  20
8 { 0, 0, 0, 2, 2, 2, 0, 1}       22
9 { 1, 5, 1, 1, 1, 2, 0, 0, 3}    42 (!)
10 { 3, 0, 4, 2, 1, 0, 0, 1, 0, 3} 43
11 { 0, 3, 0, 1, 4, 0, 5, 10, 1, 1, 3}     63

Example :
{ 1, 0, 1}
{ 1, 1,0}  move 1
{ 2,0,0}  move 2
{ 0,2,0} move 3
{ 2,0,0} move 4  <-- cycle detection



Regards,
JT

>> Take a finite row of glasses, each one containing an
>> integer number of liquid-units (zero = empty glass)
>>
>> Procedure:
>>
>> - take the leftmost glass,
>> - consider the number k of liquid-units it contains,
>> - empty the glass in the k-th glass on it's right,
>> - put the now empty glass at the right end of the row;
>> - start the procedure again.
>
> Isn't it obvious that they all end in a cycle? Or do you expect to encode 
> a
> TM-like thing?
> (they all have to loop eventually, because you have a finite amount of
> liquid so the # of glasses is finite).
>
> Mitch

-----------------------------------------
http://www.echolalie.com/gbnums
-----------------------------------------------





More information about the SeqFan mailing list