Blog d’en Xavi

L’altre dia vos proposava un problema de tassons. He reflexionat un poc en aquest problema…. la meva modelització aniria sobre reticles i el nombre mínim de moviments per passar d’un conjunt determinat d’un reticle a un altre conjunt determinat dins el mateix reticle (amb l’única condició de que aquests conjunts han de tenir el mateix cardinal).

He pensat que la solució general a aquest problema per mi és bastant difícil, i la he intentat simplificar eliminant una variable (el conjunt d’arribada). Tot seguit vos oferesc el problema simplificat:

Tenim un conjunt de tassons disposats de la següent manera:

[]T[]T

T[]TT

[]T[]T

i volem saber el nombre mínim de moviments (només són permesos els moviments dels tassons a buits adjacents al lloc que ocupen) necessaris per a què els tassons estiguin tots apinyats (sense buits), de qualsevol forma.

La meva modelització seria amb reticles:

Sigui A un subconjunt de . Hauríem de definir què és ser apinyat i què no. I després hauríem de definir un moviment natural com aquell que passa un element d’un conjunt a un espai adjacent all lloc que ocupa aquest element. I després definir s(A) com el nombre mínim de moviments per passar de A a A* un conjunt apinyat.

Les definicions són difícils de formalitzar però tothom té la intuïció sobre els conceptes. Per això, tothom pot deduir que si A i B són disjunts, aleshores . Tenint en compte que si A té dos punts , on , llavors (una fita molt grollera)

Algú s’atreveix a trobar la fórmula exacta de s(A)?

PS: Al conjunt de l’exemple s(A) = 3 (els punts aïllats, tots a la dreta) i la meva fita dóna (!)

Actualització (16/03/08): El ser un conjunt apinyat es podria definir com que cada element està a distància mínima possible de tots els altres elements. Per exemple, el conjunt:

[][]A[]

[][][][]

[]B[]C

no seria apinyat

ni el conjunt

[][]A[]

[][]B[]

[][][]C

tampoc (C pot estar més aprop de A i de B)

però sí el conjunt

[][]A[]

[][]BC

[][][][]

ja que C es mogui o no ja no pot estar més aprop de A ni de B (i el mateix passa a A i a B)

O sigui, podríem definir l’apinyament de A, ap(A), com:

ap(A) =

i dir que A està apinyat si ap(A) és mínim (qualsevol reordenació dels Card(A) elements de A tendria major apinyament)