24 de setembre de 2014

Jo sé que tu saps que jo sé... el "problema impossible" i el "problema viral de Singapur"

Corren uns temps polítics ens el que el "jo sé que tu sap que jo sé que saps que sabem que saps que sé que sabem que..." estan a l'ordre del dia. Prescindint de raons (entenent-les com motius i no arguments) la situació fa recordar la genial "batalla d'enginy" entre Vizzini i el Pirata Roberts a la pel·lícula La princesa promesa, tot i que ara no sabem qui acabarà prenent el verí i si es farà per voluntat o a per la força.


En tot cas hi ha alguns problemes matemàtics que no es poden resoldre sense saber què saben i deixen de saber alguns dels seus protagonistes. Potser el més popular és els de les edats de les tres germanes (A i li diu a B que té tres filles, que els producte de les edats és 36, que la suma és el número de casa del carrer on viu B i quan B diu que no ho pot resoldre A li reconeix que té raó i afegeix la informació de que la més gran toca el piano). En aquest tipus de problemes la gràcia rau en que tenim una aparent manca de dades per contestar els que se'ns demana però justament les dades amagades són el que els protagonistes reconeixen a cada moment què saben o què desconeixen.

Probablement el rei d'aquests problemes és el que en Martin Gardner va batejar com "el problema impossible". Plantegem-lo en una de les seves versions clàssiques.

L'Albert, el Blai, el Pere i el Sergi vitajen en la seva superbicicleta. Mentre en Blai pedala sent la següent conversa entre els altres tres.
     - Albert: He triat dos números, no necessàriament diferents, entre 2 i 20. A tu Pere et dono un paper on he anotat el seu producte. A tu Sergi te'n dono un altre on he anotat la seva suma.

- Pere: Amb el producte no en tinc prou per saber els nombres.
- Sergi: Això ja ho sabia jo.
- Pere: Doncs ara ja sé els nombres.
- Sergi: I ara jo també.
Mentre li donava als pedals en Blai anava fent números amb el cap i al cap d'una estona va dir: "Jo també sé ara quins són els dos nombres".
De quina parella de nombres es tracta?

Abans de mirar la solució, que només demana algunes nocions de divisibilitat bàsiques, no us en priveu d'intentar la seva resolució.

Després de la solució d'aquest "problema impossible" us en parlarem d'un més accessible: "el problema viral de Singapur" que va córrer viralment pels mitjans de comunicació i les xarxes socials a l'abril del 2015.

Continuem?
La solució del "problema impossible"

En aquesta mena de problemes convé anar pas a pas i mirar què pot saber o fer cada protagonista a cada moment.

Comencem pel Pere.
  • Pere, moment 1
Si els nombres estan entre 2 i 20 els possibles productes rebuts per en Pere estaran entre entre 4 i 400. Però no tots els productes són possibles. Imaginem que en Pere, en rebre el resultat, fa la descomposició en tots els productes possibles de dos nombres. Si hagués rebut el nombre 20 obtindria 2·10 i 4·5. No podria decidir quina és la parella bona. Un cas diferent és si hagués rebut el 13 ja que no podria fer cap descomposició. En canvi si hagués rebut 15 podria contestar sense dubtes perquè l'únic producte vàlid és 3·5. Com que el primer que diu en Pere és que "no en té prou per determinar els nombres" podrem eliminar de la llista de possibles resultats:
  • Tots els nombres primers. Això elimina 5, 7, 11, 13, 17...
  • Tots els productes directes de dos nombres primers. Això ens permet eliminar nombres com 4, 6, 8, 9, 10, 14, 15...
La llista P (nombres que ha pogut rebre en Pere) contindrà, així, només números que tinguin 5 divisors o més.

Llista P: 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 45, 48, 50, 52, 54, 56, 60, 63, 64, 66, 68, 70, 72, 75, 76, 78, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100, 102, 104, 105, 108, 110, 112, 114, 116, 117, 120, 124, 126, 128, 130, 132, 135, 136, 138, 140... (sèrie A058080)
  • Sergi, moment 1
Imaginem que en Sergi es dedica a fer descomposicions en dos sumands del seu número. Mirem alguns casos:
  • Si hagués rebut, per exemple, el nombre 7, podria pensar en les parelles 2+5 i 3+4. Per un costat no pot decidir quina és la parella bona perquè té dues possibilitats. Però en sentir el que diu en Pere ("no puc dir els nombres") sabria que la parella bona és 3 i 4. Per què? La raó és que 2·5 fan 10 i hem vist (i en Sergi ho sap també) que si el producte fos 10 en Pere hauria encertat. Si eliminem 2+5 només ens queda 3+4, el producte dels quals és 12, nombre que està a la llista P. En tot cas no és el que ha passat, en Sergi no ha pogut dir els nombres. Tampoc hauria pogut dir "Ja ho sabia" perquè la descomposició 2+5 no està a la llista P. La suma rebuda per en Sergi no pot ser d'aquesta mena de nombres.
  • Si hagués rebut el nombre 9 tindria tres sumes a estudiar: 2+7, 3+6 i 4+5- Els productes respectius són 14, 18 i 20. La llista P (nombres que ha pogut rebre en Pere) conté dos d'aquests nombres: el 18 i el 20. Per tant passen dues coses. La primera és que no pot triar una parella concreta perquè té tres casos. La segona és que no pot dir "ja ho sabia" perquè l'existència de la parella 2+7 l'impedia saber-ho. La suma rebuda tampoc pot ser com aquest nombre.
  • Si hagués rebut el nombre 11 tindria quatre sumes a estudiar: 2+9, 3+8, 4+7 i 5+6. Els productes respectius són 18, 24, 28 i 30. Tots quatre són de la possible llista d'en Pere. Per tant amb un nombre d'aquesta mena (que totes les descomposicions en sumands formin productes de la llista P) si que podria contestar "ja ho sabia".
Ara podrem fer una llista S que contingui tots els nombre que ha pogut rebre en Sergi. Aquesta llista estarà formada pels nombres que tinguin totes les seves descomposicions en dos sumands que multiplicats, donin un producte de la llista P. Agafem el pic i la pala, com diu una estimada companya d'institut, i confeccionem la llista que, com sabem, no ha de passar de 40:

Llista S: 11, 17, 23, 27, 29, 35 i 37 (sèrie A014092)
  • Pere, moment 2
Ara en Pere pot haver fet els mateixos raonament que nosaltres i saber, a més del producte que té escrit, que la suma és un dels nombres de la llista S. Com abans mirem algunes possibilitats.
  • Si hagués rebut, per exemple el nombre 18 tenim dos productes possibles: 2·9 i 3·6. El primer suma 11, que està a la llista S, però el segon suma 9, que no està a la llista. Per tant, podria contestar sense dubtes que els nombres són 2 i 9, perquè només té una opció entre dues que acompleixi la condició d'estar a la llista S.
  • Si hagués rebut, per exemple el 30, tenim tres productes possibles: 2·15, 3·10 i 5·6. Les sumes respectives són 17, 13 i 11. La primera i l'última estan a la llista S. No podrem triar entre la parella 2·15 o la 5·6
Sabem que en Pere ha contestat. El que ens toca és filtrar la llista P per deixar només el nombres que només tinguin una de les seves descomposicions de forma que la suma dels dos factors estigui a la llista S. De nou agafem el pic i la pala per obtenir una nova llista més reduïda:

Llista PS: 18, 24, 28, 50, 52, 54, 76, 92, 96, 98, 100, 112, 124, 140, 144, 148... (Sèrie A086473)
  • Sergi, moment 2
Sembla que no però ja hem reduït molt la llista de possibles resultats. Sabem que en Sergi, després de que Pere hagi dit que ja sabia els nombres, ha contestat que "llavors, jo també" Ara ens toca comparar les llistes S i PS fins a trobar un coincidència que ens solucioni el problema.

Comencem per 11. Farem parelles de sumes i entre parèntesi posarem els productes

2+9 (18)    3+8 (24)     4+7 (28)   5+6 (30)

Ens trobem que en els tres primers casos els productes estan a la llista PS: 18, 24 i 28. No podem quedar-nos amb un. Sabent que en Sergi sí que els ha endevinat podem afirmar que en Sergi no ha rebut l'11.

Provem ara el 17.

2+15 (30)   3+14 (42)   4+13 (52)  5+12 (60)
6+11 (66)   7+10 (70)   8+9 (72)

Només hi ha un cas en el que s'obtingui un producte de la llista PS: 4+13 que dóna 52.

Feu un acte de fe i, sense que els presenti, creieu-me que si continuem amb els altres nombres de la llista S no trobarem cap altre cas en el que hi hagi una sola opció. Per tant la solució és la següent:

  L'Albert va triar el 4 i el 13  
  En Pere va rebre el nombre 52  
  En Sergi va rebre el 17  

Un parell d'observacions finals sobre el "problema impossible"

El problema original es plantejava de forma que l'Albert pensava nombres del 2 al 100. Proposant-lo a l'aula es pot, fins i tot, baixar el límit superior fins al 15.

Si el proposeu a l'aula caldria anar discutint el que es pot descobrir cada vegada i després, entre tots, repartir la feina per construir les sèries i fer els darrers càlculs.

L'aniversari de la Cheryl; el problema viral de Singapur

Aquest problema de les olimpíades matemàtiques de Singapur, per a l'edat de 14 anys, ca córrer pels noticiaris explicant, equivocadament, que era per alumnes de 10 anys. Tot això lligat amb la fama dels creixement en resultats en matemàtiques de les proves PISA. El cas és que és un bon repte. El plantegem a continuació.

La Cheryl fa dos nous amics: l'Albert i el Bernard. Aquests volen saber la data de l'aniversari de la Cheryl i ella els hi proposa una llista de possibles dates:

15, 16 i 19 de maig
17 i 18 de juny
14 i 16 de juliol
14, 15 i 17 d'agost

Després la Cheryl li diu a l'Albert, en secret, el mes en què va néixer i al Bernard, sense que l'altre ho senti, el dia.
A continuació sentim aquesta conversa:
  • Albert: No sé quan és l'aniversari de la Cheryl, però sé que en Bernard tampoc ho sap.
  • Bernard: Abans no sabia la data de l'aniversari, però ara ja la sé.
  • Albert: Llavors jo també sé quan és el seu aniversari.
Quina és la data de l'aniversari de la Cheryl?

Aquest problema no us el solucionem: en podeu trobar moltes explicacions a internet.

... I un parell de variacions sobre el problema impossible

He descobert al web Zurditorium de Carlos Angosto dues variacions del "problema impossible" lleugerament més fàcils. Els diàlegs entre Sergi (S - coneixedor de la suma) i Pere (P - coneixedor del producte) són una mica diferents i, fins i tot a la segona variació bàsicament només hi ha un canvi d'ordre. Al web enllaçat també podreu veure les solucions. Els tradueixo a continuació:



Variació 1
Considerem ara exactament el mateix problema però canviant una línia del diàleg.
- P: No sé quins són aquests nombres.
- S: Doncs jo tampoc.
- P: Ah, doncs llavors ja sé quins nombres són.
- S: Doncs llavors jo també.
La pregunta torna a ser que quins són els nombres inicials.
Variació 2.
De nou considerem el mateix problema i el diàleg serà el mateix que a la variació 1 però canviant l'ordre en què parlen, és a dir:
- S: No sé quins són aquests nombres.
- P: Doncs jo tampoc.
- S: Ah, doncs llavors ja sé quins nombres són.
- P: Doncs llavors jo també.
En aquest cas tindrem una dada extra, sabem que la suma serà com a molt 100 (però P desconeix aquesta dada). Quins són els números inicials?

Cap comentari:

Publica un comentari a l'entrada