Dos problemes inductius
Els poliòminos, les figures formades per diversos quadrats iguals adjacents pels costats, permeten una gran varietat de problemes, molts d’ells inductius. Avui en presento dos relativament similars, que fan servir el joc dels 35 hexòminos.
És impossible col·locar els 35 hexòminos en un rectangle, però la demostració d’això, basada en la paritat és un tema que tocaré un altre dia. Però és possible col·locar-los en altres figures com per exemple un rectangle de 11 × 19 més una casella adjacent al mig del costat llarg. No és gaire fàcil fer-ho a mà amb un conjunt de les trenta-cinc peces, però amb un programa d’ordinador se’n poden treure milions de solucions, no l’he pogut deixar en marxa prou estona per saber el nombre.
Pels problemes d’avui parteixo de dues solucions d’aquest cas, però simplement com a il·lustració per mostrar les trenta cinc peces. La seva posició o orientació no hi té cap importància.
Els dos problemes són part d’una col·lecció de 12. Segurament seria exagerat posar-los tots aquí, però a l’hora de solucionar problemes d’aquesta mena, quants més n’hi ha, més possibilitats de solucionar-ne algun…
En el primer cas veiem els hexòminos pintats de dues maneres, uns de color rosa, i els altres verds.
Trenta-cinc hexòminos: 12 roses i 23 verds.
La pregunta és quin és el criteri.
Òbviament hi ha moltíssims possibles criteris per acolorir els hexòminos en diversos colors, aquesta és la gràcia i la dificultat dels problemes inductius. Fins i tot, algunes vegades passa que dos criteris que no tenen res o gaire a veure, ens porten al mateix acoloriment. Això vol dir que la solució a un problema inductiu sempre és probabilística, cal escollir el criteri subjectivament més senzill, és el que s’anomena navalla d’Occam.
En una entrada no fa gaire, en un problema també amb hexòminos, vam veure un criteri que era si la figura era el desenvolupament d’un cub o no. El criteri d’avui és subjectivament més senzill. Altres criteris a considerar poden ser: dimensions màximes, nombre de costats, nombre de costats d’una determinada mida, angles interns, enrajolats per peces més petites, mida màxima de una diagonal, caselles blanques s o negres sobre un tauler d’escacs, diàmetre màxim de la peça… Aquest problema té a veure amb algun d’aquests criteris.
Però potser una pista tangible i misteriosa sigui la primera que hi vaig veure: la dels «cucs». Un poliòmino pertany a la categoria dels cucs, si és possible fer per tot ell un recorregut quadrat a quadrat, pel costat, de manera que no es repeteixi cap casella. I la observació és que tots els cucs són verds i no hi ha cap hexòmino rosa que ho sigui. De totes maneres aquest no és el criteri perquè hi ha cinc hexòminos pintats de verd que no són cucs, per exemple el que sobresurt per la part superior.
Aquestes cinc peces són les que ens donen una pista definitiva si ens adonem que en totes elles hi ha un quadrat amb tres costats exteriors, que si comencem el camí de «cuc» per ell al següent pas ens trobem que hi hauria dues possibilitats de continuar de la mateixa mida, dues caselles. En els cucs normals, després de dues caselles, en podem fer dues més i dues més. En canvi en cap de les peces roses, en entrar des d’una punta i seguir una casella més, no trobem mai dues possibles continuacions de dues caselles. Aquest és la pista definitiva, en les peces verdes sempre podem fer dues dues i dues caselles per cobrir-les, en altre paraules, es poden recobrir amb tres dòminos i les roses, no.
En aquesta figura podem veure que les peces verdes es poden cobrir per tres dòminos.
En el següent problema, del qual avui no donaré més pistes llevat que el criteri té alguna semblança amb l’anterior, podem veure els hexòminos pintats de cinc colors.
Trenta-cinc hexòminos: 2 carabasses, 12 roses, 11 verds, 6 grocs i 4 blaus.
La pregunta torna a ser quin és el criteri.