[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