diumenge, 16 d’octubre del 2005

Cadena més llarga

El problema de la setmana passada va portar una mica de polèmica, perquè jo vaig llegir per sobre com era la solució, i al final va resultar que ho havia llegit una mica malament.

Abans de començar amb la cadena de tres símbols, es comença amb una cadena de dos símbols, anomenada sèrie de Thue. Es comença per 01 i a cada pas es substitueix cada 0 per 01 i cada 1 per 10. Així, s'obtenen cadenes, cada cop del doble de longitud de l'anterior:

01
0110
01101001
0110100110010110

Com es pot observar, cada cadena té el doble de longitud que la anterior i, a més, la primera meitat de cada cadena és exactament la cadena anterior.

Aquestes cadenes compleixen (faig un acte de fe i m'ho crec) que cap bloc d'un o més dígits es repeteix 3 vegades consecutives. Es poden repetir dos cops, però mai tres.

Com que aquest pas de canviar els 0 per 01 i els 1 per 10 es pot fer tantes vegades com es vulgui, aquesta sèrie es pot aconseguir amb el nombre de dígits que es vulgui.

Aleshores, per aconseguir la sèrie desitjada, només cal substituir els 00 i 11 per 1, els 10 per 2 i els 01 per 3. Així, la sèrie que surt compleix la propietat (segons el llibre, jo faig un acte de fe). I com que la sèrie de Thue és infinita, aquesta també ho serà.

En el cas de l'exemple, la sèrie seria:

312321312132312

I així se'n pot construir una tan llarga com es vulgui.