diumenge, 9 d’octubre del 2005

El problema de la setmana - Cadena més llarga

Es tracta de trobar la cadena més llarga que es pot aconseguir amb el 1, 2 i 3 sense que es repeteixi cap seqüència de símbols seguits.

Si només es fes amb l'1 i el 2, la seqüència més llarga tindria 3 símbols: 121 (o 212). Després de l'1 no es pot posar un altre 1 perquè es repetiria la seqüència d'uns. Per tant, després de l'1 hi va un 2. Després del 2 no es pot posar un altre 2, perquè es repetiria la seqüència 2. Així que s'ha de posar un 1: 121. I després d'aquest 1 no es pot posar un 1 perquè es repetiria la seqüència d'1 seguida, ni tampoc es pot posar un 2 perquè es repetiria la seqüència 12.

Un cop vist l'exemple de l'1 i el 2, es tracta de fer el mateix amb el 1, el 2 i el 3. Donaré el punt a qui posi la seqüència més llarga, i en cas de que no sigui la seqüència més llarga, donaré un exemple de la seqüència més llarga.

Exemples correctes: 12312
121312
Exemples incorrectes: 123123
1231212
12321321

(Espero que s'hagi entès bé).


Setmana anterior

Setmana següent

11 comentaris:

Anònim ha dit...

A veure, un intent. No crec que sigui màxim, però a mi m'ha semblat etern:

12312132123121312313

Matgala ha dit...

Hi ha d'haver un error, perquè una cadena tan llarga no és possible. Però no veig la cadena repetida, i en aquests moments tampoc tinc el cap clar per pensar. Ja m'ho tornaré a mirar...

Matgala ha dit...

Mea culpa...

Vaig mirar-me la solució i vaig veure que hi havia una solució que tenia com a màxim 11 xifres. Però ho vaig mirar massa ràpid... En tot cas, ara he vist que es pot aconseguir una sèrie de dígits infinita que ho compleix. Mea culpa. La sèrie anterior està bé (crec). Així que si ningú troba una sèrie més llarga, els punts seran per l'escaquejant.

Anònim ha dit...

Infinita? Amb el que m'ha costat a mi treure aquesta! Bé, repto als visitants a treure'n una de més llarga...

Anònim ha dit...

Estem parlant de variacions,sense repetició de tres elements amb grups de 3,per lo tant seran 3x2x1;6 combinacions
123 132 213 231 312 321;ará bé sense fer cas a no poder seguir el mateix número a l´altre,seríen variacions amb repetició de estos sis elements 6 elevat a 6;6x6x6x6x6x6;46656 formes de combinarlos,si les posem totes seguides no vec l´infinit per cap de costat no???? o no entenc bé el problema

Matgala ha dit...

El problema és que sí que els pots repetir, si no els repeteixes seguits... però tinc el cap una mica espès. M'ho miraré i ja diré alguna cosa un dia d'aquests...

Anònim ha dit...

Bé encara que es pugues repetir variacions amb repetició de 3;son 3x3x3=27:i 27 elevat a 27 tampoc es infinit;torne sense entendre l´infinit;sense tindre en compte el tema de no poder repetir seguits.

Anònim ha dit...

pacopat,
el teu argument consisteix en analitzar les possibles repeticions en blocs de 3, però jo entenc de l'enunciat que s'han d'impedir les repeticions per a qualsevol magnitud de bloc. És a dir, que la seqüència

12131231213123

no és vàlida per ser una repetició d'un bloc de 7. De tota manera, per la dificultat que he tingut en trobar l'exemple que he postejat abans, em costa de veure un infinit, però tampoc no trobo cap raó que pugui forçar una cota.

M'ha picat la curiositat: provaré de fer un programet que cerqui números sense repeticions, a veure si a partir de certa longitud s'estanca...

Anònim ha dit...

Bé, ja he fet el programet. L'he fet treballar una mica i diria que confirma l'infinit que diu la matgala.
Concretament, l'he fet parar quan em donava el següent número:
12131231321231213123132131213212312131231321231213212313213121321231213123132
12321312132123121312313213121321231213123212312132123132131213212312131231321
23121321231321312132123121312321231213212313213121321231213231232123121312313
21231213123212312131

He buscat repeticions i no n'he trobat cap, tot i que evidentment no he estat exhaustiu en la revisió.

Anònim ha dit...

Bé jo no entre en lo llarga que puguem fer la cadena,però del enunciat(no és poden repetir seguits)de les 27 combinacions sols son válides 12;121 131 123 132 212 232 231 213 313 323 312 321;i estos 12 amb repeticions;12 elevat a 12 donaría 8916100448000;tot aixó de posibilitats ;vora nou billons;sense entrar en que la primera que jo he escrit ja no es válida;i en hi haurán altres més;que deuríem calcular;torne sense entendre l ínfinit;a no ser que matgala ens diga algo nou sobre l´enunciat del problema

Matgala ha dit...

Bé, dono el punt a l'escaquejant, que per alguna cosa ha tret la cadena més llarga. El problema de la setmana que ve serà molt més fàcil i no tindrà solució que es pugui discutir...

D'aquí a una estona escriuré en un post la solució que dóna al llibre.