dimecres, 26 de gener de 2011

5: Disseccions de pentominós

Problema 5
Els 12 pentominós són una font inexhaurible de problemes.
(Aquí podeu trobar una pàgina específica amb més informació)

Els 12 pentominós dins d’un rectangle de 6 × 10 unitats
 Un dels problemes més freqüents és  el de formar una determinada figura amb els diferents pentominós; aquí plantejarem un problema que en algun aspecte és l’invers: dividir un pentominó en parts que ajuntades d’una altra manera formin una figura diferent, per exemple un quadrat.
Els matemàtics de la Grècia clàssica ja van intuir, encara que no ho van explicitar mai, que qualsevol polígon —figura limitada per segments— es pot partir mitjançant rectes en un nombre finit de peces, que reunides convenientment formen qualsevol altre polígon de la mateixa àrea. Aquest fet es va demostrar —és relativament fàcil— a principis del segle XIX. Però la demostració no ens diu quin és el nombre mínim de parts en que podem descompondre una figura per formar-ne una altra de la mateixa àrea; aconseguir-ho amb un mínim de parts és un problema que pot ser força difícil.
En particular, és possible dividir cadascun dels pentominós en diverses parts, que disposades d’una altra manera formin un quadrat. Veiem-ne un exemple:

Dissecció del pentominó V en 4 parts que formen un quadrat
Quin és el menor número de trossos en que es pot dividir algun dels pentominós per formar un quadrat?
És possible dividir algun dels pentominós en quatre parts iguals que puguin formar un quadrat?

Solució 5 

Hi ha dos pentominós que es poden dividir en només tres trossos per recompondre un quadrat de la mateixa àrea. Curiosament les tres peces són les mateixes en ambdós casos.


Els pentominós Y i Z dividits en 3 parts per formar un quadrat

El més simètric dels pentominós, X, es pot dividir, com veiem a la il·lustració, de manera simètrica en quatre peces iguals que recomponen un quadrat.


Els pentominó X dividit en 4 parts iguals per formar un quadrat
Tots els altres pentominós es poden dividir també en 4 trossos, de manera que amb ells es pot fer un quadrat de la mateixa àrea.

Tots els pentominós dividits en parts per formar quadrats
No totes les divisions són úniques ni molt menys, per exemple la del pentominó X ara no és en quatre parts iguals.

4: Seixanta-quatre igual a seixanta-cinc?

Problema 4
Observen aquest quadrat format per quatre peces. La quadrícula ens permet veure que la seva àrea és 8 × 8 = 64 unitats quadrades.

Quatre peces formen un quadrat de 8 × 8
A continuació, reordenem les peces —les dues trapezoïdals les hem de girar 90º— per formar un rectangle. Si ara mesurem l'àrea podem veure que és de 5 × 13 = 65 unitats quadrades.

Les mateixes quatre peces formen un rectangle de 5 × 13
D'on ha sortit el quadrat suplementari?

Solució 4
Les quatre peces que formen el quadrat, tenen sumades, efectivament, una àrea de 64. Però no són exactament iguals a les quatre peces que formen la figura rectangular.

 Il·lustració acurada: les quatre peces del quadrat dins el rectangle

En un trencaclosques real, amb les peces fabricades amb una certa tolerància, vores una mica arrodonides i talls entre les peces de gruix no menyspreable, no es nota gaire. En un dibuix acurat és més fàcil d'apreciar.
Podem observar en particular que per fer veure que les peces ocupaven tot el rectangle de 5 × 13, les dues peces triangulars s'havien deformat per convertir-les en quadrilàters amb el quart vèrtex situat als punts blancs del centre del dibuix.
L'àrea de la zona blava, és exactament s'una unitat quadrada, precisament la que ens havia aparegut del no res.

Teorema de Pick
Per calcular aquesta àrea, podem fer ús d'un teorema publicat per primera vegada l'any 1899 pel matemàtic austríac Georg Alexander Pick que afirma:
L'àrea d'un polígon simple —sense forats ni costats que s'intersequin— que tingui tots els vèrtex en els punts d'una quadrícula regular, és igual a I + V/2 – 1, essent I el nombre de punts de la quadrícula interiors al polígon i V els que cauen en el seu perímetre, siguin els vèrtex o punts continguts en un dels costats.
En el cas del nostre problema, la figura blava és un polígon que té els quatre vèrtex a punts de la quadrícula —V = 4—, i cap punt a l'interior —I = 0—, o sigui que la seva superfície serà: 0 + 4/2 – 1 que val, precisament, 1.
Aplicant el mateix teorema podem veure que els triangles de la figura tenen una àrea de 12, i els trapezis de 15, o sigui un total de 12 + 12 + 15 + 15 = 64 unitats quadrades.
Els "triangles" tramposos de la figura rectangular, són de fet quadrilàters, amb 4 vèrtex a la quadrícula, 9 punts de la quadrícula als costats i 7 punts interiors; en conseqüència la seva superfície és de 12,5.

3: Totes les lletres dels números

Problema 3
A la il·lustració —no, no és una fotografia— hi podem observar com s’escriuen els números en català. Parlem aquí de nombres inferiors a 1.000.000.000.000 que és un bilió i que empra un mot no llistat a la taula, concretament és el primer número que conté la lletra B. Tots els números inferiors a un bilió es poden construir a base de juxtaposar les paraules de la llista, afegint-hi en alguns casos el guionet.
Podem veure, per exemple que les lletres M i L, només apareixen a les paraules MIL i MILIO —aquí, com en els mots encreuats, prescindim de l’accent—; una altra lletra, la X, només surt dins SEIXANTA; la Z només en els nombres entre l’ONZE i el SETZE; la Q, a tots els que contenen QUATRE, QUINZE, QUARANTA o CINQUANTA. Cada lletra té la seva pròpia idiosincràsia, els números entre el DEU i el SETZE introdueixen una curiosa irregularitat lèxica en la seqüència que ens complica una mica el problema…

Les paraules que forment tots els números inferiors a un bilió
Els problema d’avui consisteix en trobar el número enter més petit que conté, al menys una vegada cadascuna, totes les lletres possibles —Excloent la B de bilió que no ens aportaria res a la qüestió—.
Com a problemes subsidiaris podem preguntar també:
Quin és el número més gran que no repeteix cap lletra?
Quin és el número més petit on cada lletra que hi surt, al menys ho fa dos cops?

Solució 3
Aquesta mena de problemes, tenen l’avantatge que no calen gaire coneixements previs, llevat de saber com s’escriuen els números.
De totes maneres no vol dir això en absolut que siguin fàcils. Cal actuar amb força cura per tal de no ometre solucions, i cal elaborar estratègies adequades, per tal de no convertir-los en un examen inacabable, a mà, de totes les possibilitats. 
Deixem el problema principal pel final.
El segon problema ens parla del número el més gran possible sense repetició de lletra.
És evident que qualsevol número superior a un milió, tindrà al menys dues I, o sigui que la solució serà inferior a aquest valor.
Anem baixant per la sèrie dels “cents mils” i marquem les lletres que presentin repeticions: nou-cents mil, vuit -cents mil, set-cents mil, sis-cents mil, cinc-cents mil, quatre-cents mil, tres-cents mil, dos-cents mil… cent mil.
Cent mil, no té repetició de lletra, a partir d’aquí podem pujar fent servir valor que no continguin cap lletra ja emprada, Quins hi ha disponibles?
Resseguint la taula, podem veure que les números que tenim disponibles sense emprar cap de les lletres C, E, I, L, M, N o T són limitats, només tenim l’u i el dos. En conseqüència, el número més gran que es pot escriure sense repetir lletres és CENT Dos Mil U —o cent dos mil si per a 1 només admetem el cardinal un—.


El tercer problema exigeix que qualsevol lletra, o bé no aparegui, o bé surti al menys dues vegades al nom del número.
El procediment és més llarg que per trobar la solució del cas anterior, cal primer mirar tots els números fins al cent, combinant les unitats amb les desenes. És fàcil constatar que sempre hi ha alguna lletra que no es repeteix. El numero que busquem, serà doncs superior a cent.
Suposem que és menor que mil. Com que necessàriament tindrà una C de cent o cents, l’altre C ha d’aparèixer a cinc o a cinquanta. Podem descartar el cinquanta ja que la Q només es podria duplicar amb una altra de quatre, i no hi ha cap número de la forma x-cents cinquanta-quatre o quatre-cents cinquanta-x que dupliqui totes les lletres, perquè la xifra x, com a mínim hauria de tenir una I i una R que a la resta del número només surten un cop.
Sabem, doncs, que el número que busquem comença per cinc-cents, acaba en cinc, o ambdues coses. Podem descartar fàcilment que les desenes siguin zero, perquè amb una sola xifra d’unitats o centenes, no podem duplicar les lletres I, E i T.
Descartem també que la desena sigui vint o quaranta, perquè per duplicar respectivament la V o la Q, necessitaríem respectivament vuit o quatre i aleshores, en un cas ens mancaria, per exemple, una segona E, i en l’altre, una I. Seixanta, encara és més fàcil d’eliminar, ja que no hi pot haver una segona X.
Passem a setanta. Hauria de ser un número de la forma x-cents setanta-cinc o cinc-cents setanta-x. observem que fins aquí, totes les lletres estan repetides llevat de la I. Però la I la podem introduir fent precisament que x sigui cinc, que les altres lletres també les té duplicades.
En conseqüència el número buscat és CINC-CENTS SETANTA-CINC.


La deducció és un xic llarga i embolicada, i no dubto que se’n pugui fer una de més curta o entenedora, però és un exemple de recerca sistemàtica, amb pistes que ens estalvien de mirar tots els casos d’un en un.
No posaré aquí tots els passos detallats per trobar la solució al  problema principal: trobar el menor número que contingui totes les lletres possibles.
Peró sí algunes deduccions bàsiques.
Com que el número ha de tenir una X, ha de contenir seixanta.
Com que ha de tenir M i L, ha de contenir mil.
Com que ha de tenir Z, el número que cerquem ha de portar onze, dotze, tretze, catorze, quinze o setze, i si no és als milers, és incompatible amb que les desenes siguin seixanta. O sigui que el número, com a mínim serà de la forma (onze~setze) mil x seixanta-y, on x és de la forma cent o z-cents, i y és una dígit.
Altres lletres que ens donen pistes són la Q i la V.  La Q sols pot aparèixer a quatre o quinze, perquè quaranta seria incompatible amb seixanta, si és que no ens en anem a números molt alts. La V, per idèntic raonament, només pot venir de vuit i no de vint.
Amb onze mil quatre-cents seixanta-vuit ens manca la D, invertint quatre i vuit per fer onze mil vuit-cents seixanta-quatre, també; o sigui que hem de passar a DOTZE mil quatre-cents seixanta-vuit per tenir la solució.




dijous, 13 de gener de 2011

2: Triangle de diferències

Problema 2
Observem aquesta disposició triangular de fitxes numerades de l'1 al 10:

Triangle de diferències d'ordre 4, amb els números de l'1 al 10
Podem observar que cada fitxa té un valor numèric que és la diferència dels de les dues fitxes adjacents de la rengla superior. Diferència presa en valor absolut, sense tenir en compte el signe.
És possible construir un triangle similar de costat 5, amb fitxes —o boles de billar, per exemple— numerades de l'1 al 15?
I amb 21 fitxes formant un triangle de 6 de costat?

 Solució 2
Tan sols hi ha un triangle —llevat de la seva imatge especular— amb els números de l'1 al 15 que compleixi les condicions del problema:

La solució única del problema de les diferències
La recerca de solucions es pot simplificar una mica si observem que el número 15 ha d'estar necessàriament a la rengla superior i que cadascun dels números 1, 2, 3, 4 i 5 han d'ocupar files diferents.
Els triangles d'ordre 1, 2, 3, i 4 —més fàcils— tenen respectivament  1, 2, 4 i 4 solucions —sempre descartant les simetries especulars.
El triangle d'ordre 6, amb 21 números no té solució. Es pot demostrar per un argument de paritat considerant els números mòdul 2. En primer lloc hem de adonar-nos que mòdul 2, la suma i la diferència coincideixen.
Anomenem a, b, c, d, e, f als números del rengle superior.
La segona fila serà: a+b, b+c, c+d, d+e, e+f.
La tercera: a+2b+c, b+2c+d , c+2d+e, d+2e+f
La quarta: a+3b+3c+d, b+3c+3d+e, c+3d+3e+f
La cinquena: a+4b+6c+4d+e, b+4c+6d+4e+f
La sisena: a+5b+10c+10d+5e+f
La suma de tots els números del triangle serà, sempre mòdul 2, 6a+20b+34c+34d+20e+6f que necessàriament és un número parell ja que ho son tots els coeficients de l'expressió. Però la suma dels número de l'1 al 21 és 231, que és senar, o sigui que hem arribat a una contradicció i la solució no és possible.
La mateixa demostració val per a tots els triangles d'ordre 2ⁿ–2 llevat del d'ordre 2.
Hi ha una demostració que no existeix solució per a cap triangle de diferències d'ordre 9 o superior; els casos 7 i 8 es poden verificar mitjançant ordinador i resulta que tampoc no en tenen, o sigui que el triangle de la il·lustració és el més gran possible.