Problema dels mentiders (Cangur 2009)
En una illa remota unes quantes persones sempre diuen la veritat i les altres persones menteixen sempre. 25 persones d’aquesta illa estan col·locades en fila íındia. La primera persona de la cua diu que totes les altres són mentideres. Totes les altres persones de la cua diuen que la persona que tenen al davant és mentidera. Quantes persones mentideres hi ha a la cua?
A) 0 B) 12 C) 13 D) 24 E) És impossible saber-ho
Podeu veure que és un test de resposta múltiple i en tenim cinc de possibles. Abans de continuar i si esteu delerosos de saber la resposta cliqueu al "Mostra" que apareix més avall (només ho hauríeu de fer si heu intentat solucionar el problema i després d'uns minuts de reflexió):
Solució del problema dels mentiders
(+/- Mostra/Oculta)
La resposta correcta és la c. Hi ha tretze persones mentideres. És evident que la primera persona no diu la veritat perquè tota la resta no poden ser mentiders: un mentider no pot dir d'un altre mentider que ho és. Per tant, si la primera menteix, la segona diu la veritat i van alternant mentiders amb persones que diuen la veritat.
La mera presència d'aquesta pregunta en un examen de matemàtiques pot sorprendre a la majoria dels estudiants de secundària i del batxillerat actuals que identifiquen aquesta assignatura amb l'aritmètica, l'àlgebra, la geometria, l'anàlisi i un polsim de probabilitat i estadística. Encara que quatre de les respostes proposades són numèriques, el problema no és d'aritmètica, sinó de lògica (a més, de la més clàssica i aristotèlica lògica binària).
Tradicionalment la lògica s'ha considerat un camp d'estudi de la filosofia i, fins fa poc, el seu ensenyament als nostres joves ha estat en mans dels professors de filosofia de batxillerat (sense batxillerat, no hi havia continguts reglats de lògica). Hores d'ara i seguint el temari de Filosofia i Ciutadania (m'estalvio comentaris polèmics sobre el nom) de 1r de Batxillerat, el professorat d'aquesta matèria es pot estaviar els continguts més elementals de lògica formal. Com que a més els han castigat amb només dues hores de classe setmanals, ja us podeu pensar en quin estat tenim el raonament lògic. És clar que alguns ciutadans em poden replicar que en tenim prou amb el "sentit comú". Com que aquesta no serà la única entrada dedicada a Lògica i Metodologia — no se m'ha acudit cap altra etiqueta per tractar de la lògica i de la metodologia matemàtica— els deixarem, momentàniament, fruir de la perillosa inòpia intel·lectual en la qual viuen.
La lògica, no cal dir-ho, fonamenta també el coneixement científic i matemàtic. D'això i d'algunes anècdotes significatives a les aules, en parlarem més endavant.
Com que el plantejament del problema no diu si els 25 habitants d'Illa Binària que formen la fila es conèixen els uns als altres o no, cadascú és ben lliure de pensar el que vulgui. Tu, per exemple, has suposat que tots es coneixien; altrament, no hauries afirmat amb tanta alegria que «un mentider no pot dir d'un altre mentider que ho és». Jo, en canvi, he suposat que no, que no es coneixien –que ignoraven la condició de sempre-vertader o sempre-mentider dels seus companys de fila– i que, a més, tots sabien que ningú coneixia a ningú. La tercera opció, suposar que uns es conèixen i els altres no i no saber, a més, qui coneix a qui, complica massa el problema i l'he descartat ja de sortida. Vist des del meu punt de vista, doncs, el primer binarenc ha de ser per força un mentider compulsiu: si no ho fos hauria callat o hauria dit una cosa com ara «nom tinc ni idea de si aquests senyors són mentiders o no». Com que ni calla ni diu això, hem de conclore que és una mena de sempre-mentider barrut –o simplement agosarat– que tira pel dret i diu el primer que li passa pel cap arriscant-se a dir la veritat sense voler. A partir d'aquí el problema es bifurca: si el segon i la resta de la fila són prou espavilats i s'adonen que el primer és, per força, un mentider, el raonament continua com tu ens has dit i, curiosament, acaba amb el mateix resultat: 13 sempre-mentiders i 12 sempre-vertaders. Però, ¿i si no ho són prou, d'espavilats? Aleshores només pot ser que tots siguin sempre-mentiders i que tots diguin la veritat sense saber-ho: 25 sempre-mentiders barruts!
ResponElimina(La 'moralitat' del conte és doble: d'una banda, mostra que n'és de difícil, plantejar bé un problema (sense donar premisses per suposades); de l'altra, mostra que la solució dels problemes, pot ser molt enganyosa: es pot arribar al mateix resultat final per vies molt diferents que impliquin, fins i tot, raonaments oposats.)
T'agraeixo que sempre busquis cinc peus al gat perquè els teus comentaris sempre em porten a reflexions interessants. Cal dir, primer de tot, que els problemes i les preguntes s'enuncien en un determinat context i que, a l'hora de formular-los, no sempre ens n'adonem de possibles ambigüitats o vaguetats.
ResponEliminaRecordo que ja fa anys, en un examen de matemàtiques de l'extingit BUP, se'm va acudir donar una sèrie de condicions que determinaven una recta i demanar "Escriu l'equació d'aquesta recta de totes les maneres que sàpigues". Jo esperava com a resposta una equació vectorial, una implícita... Un alumne em va contestar molt breument: "No en sé cap". No va aprovar, però em vaig permetre el luxe gödelià o socràtic de contar-li bé la resposta i vaig prendre nota de que un professor de matemàtiques no havia de formular les preguntes d'aquella manera.
En el cas de l'illa Binària, o suposem que es coneixen tots o que, tal com dirien en teoria de jocs, la informació és de coneixement comú (en aquesta teoria es distingeixen diferents categories d'informació: perfecta, certa, simètrica, completa...). En el context de la prova i en les sessions de preparació amb alumnes als quals els he plantejat el problema, no crec que ningú hagi pensat en la variant que proposes (de fet, per descartar el teu raonament com a vàlid, n'hi hauria prou en afegir alguna frase aclaridora a l'enunciat).
El problema de la informació i el context, el pateixo més com a professor de física que de matemàtiques. Si un problema d'aquesta assignatura diu d'un vehicle que va a 100 km/h, i res més, sempre hi ha uns quants alumnes que demanen si té acceleració, si hi ha fregament, si va per les rondes (haurà de pagar la multa)... El conveni és que tota la informació que es necessita per resoldre un problema escolar està en l'enunciat i no cal complicar-ho més del compte.
Tornant al gat de l'inici, podem demostrar que té cinc peus:
1. Convenim que anomenen peu a aquella part de la seva anatomia que està a l'extrem distal d'allò que anomenen pota. Una propietat de la pota és que té la longitud justa perquè el peu arribi just fins a terra. No cal dir que no necessitem aquesta propietat per a la demostració.
2. El gat té una altre extremitat formada per les vèrtebres més allunyades del cap que hem convingut a anomenar "cua".
3. Només cal canviar la definició i establir que a partir d'ara cua = peu, i comptar en base 10 els peus. El nostre gat té 5 peus. q.e.d
De fet, hi ha una facció de matemàtics airats que diuen que el que acabem de demostrar és que el gat té 5 cues. No cal dir que són un sector minoritari.
1000001
ResponElimina1001101 1001001
1000101 1001100
1000011 1001111 1000100 1001001
1000010 1001001 1001110 1000001 1010010 1001001
1010011 1000101 1001101 1010000 1010010 1000101
1001101 1001000 1000001
1000001 1000111 1010010 1000001 1000100 1000001 1010100
La frase està codificada en binari, en base a un altre codificació
Guaita! Tot just estàvem parlant de buscar cinc peus al gat... Per cert, i com a curiositat, Google traductor tradueix "buscar cinc peus al gat" (català) com "buscar tres pies al gato" (castellà). Ho podeu comprovar en aquest bloc si, a dalt en la columna de la dreta, on diu Tradueix aquest bloc trieu castellà i llegiu el segon comentari d'aquesta entrada. És un cas estrany d'incompatibilitat aritmètica entre idiomes, o de canvi de base de numeració? Tothom sap que els gats que no han patit cap amputació tenen una pota, i dues, i tres, i quatre. Per tant, la dificultat està en trobar-ne cinc o més.
ResponEliminaFrederic, espero que aquesta vegada no hi hagi falses pistes i que no ens calgui trucar a John Nash ni fer espiritisme amb el fantasma d'Alan Turing per treure l'entrellat de l'enigma.
Com que no suportaria que cap nen de vuit anys m'aixafi la guitarra i se m'avanci en la solució, és urgent que l'escrigui ara:
ResponEliminaA
MI
EL
CODI
BINARI
SEMPRE
MHA
AGRADAT
Per cert, falta un apòstrof. Un xic elemental el repte en aquesta ocasió.
La propera vegada utilitzaré un algoritme un xic més complicat !!!
ResponEliminaNo Frederic, no! (emulant la conversa entre Hardy i Ramanujan a propòsit del nombre 1729). No cal que ho compliquis més. A matemàtiques definir termes com complexitat, resolubilitat o informació és difícil. El repte que proposaves era pràcticament irresoluble si ignoraves el codi ASCII i era trivial si en coneixies l'existència. De totes maneres el teu problema no era del tipus NP, afortunadament. Gràcies per augmentar la meva autoestima després del sorollós fracàs en el cas Un plat enigmàtic.
ResponEliminaEn honor al creador del blog, i traduïnt el seu cognom al castellà, m'he permés la llibertat d'inventar un codi.
ResponEliminaONA ONS
ONA OMO OOS OMN OMS
OMN ONN ONS ONA ONS ONT
El cognom de'n Francesc, en castellà, té una característica molt especial.
Prometo que serà la última intervenció amb codis !!!
Sort que el títol de l'entrada és La lògica i el currículum, que si no... El meu cognom en castellà? Montasel? I mira que el teu ve del llatí mons magnum.
ResponEliminaEn castellà la ll es una lletra en català no !!
ResponEliminaEntenc la pista, però és mentida això que dius. En castellà la ll tampoc és una lletra, almenys des de fa poc. Si et vols posar al dia i treure la pols dels teus coneixements de llengua castellana, mira't com aperitiu el següent article de El País (pots aprofundir més consultant el web de la Real Academia de la Lengua):
ResponEliminaLa "i griega" se llamará "ye"
Per la frase en el codi "Montasell" no importa gaire ja que la "ll" no hi surt, però si alguna de les vuit lletres que formen el nom.
ResponEliminaFinalment, he tingut un moment per pensar-hi. Ja veia per on anaven els trets, però ahir em vaig passar tot el dia en la interessant XIII Jornada Didàctica Matemàtica d'ABEAM i em calia deixar reposar el lòbul frontal unes hores.
ResponEliminaLa teva intervenció es mereix una entrada sense que doni ara la solució, però el meu ego no m'ho permet. Adopto una solució de compromís: escriure la solució sense desvetllar en detall com hi he arribat (així qui vulgui pot continuar intentant esbrinar el codi que has utilitzat). El teu missatge codificat és la traducció catalana d'una famosa frase de Juli Cèsar:
TU
TANBE
BRUTUS
Em sembla que has codificat malament la M de també i t'ha sortit un TANBE, però és una errada fàcil de cometre.
77 1001101 M 4D 115 OOS
ResponEliminaCrec que està ben codificat !!!!
On havia llegit Prometo que serà l'última intervenció amb codis? Els químics sou sempre tan poc rigorosos?
ResponEliminaEl teu missatge policodificat, una vegada desxifrat, és:
ResponEliminaMMMMMM
Pentines gats?
No m'has entés, et deia que la M està ben codificada es 77 en ASCI 1001101 en binari 4D en hexadecimal, 115 en octal i OOS en codi Montasell
ResponEliminaNo m'has dit això que em dius! Ho volies dir, però en realitat m'envies MMMMMM. Si per entendre un missatge codificat, necessitem els comentaris de l'autor "estem apanyats". Sense ambigüitats d'interpretació, el teu missatge havia de ser, per exemple:
ResponElimina01001101 00100000 01000101 01010011 00100000 01010000 01001111 01010100 00100000 01000011 01001111 01000100 01001001 01000110 01001001 01000011 01000001 01010010 00100000 01000011 01001111 01001101 77 1001101 M 4D 115 OOS
Ja dedicaré una entrada a tot això, però, ara mateix, em sento com si estigués jugant a barcos. A veure si compleixes la teva promesa de no codificaré en va!
Jag lovar !!!!
ResponEliminaNo sabia que parlessis suec! Espero que la promesa sigui solemne. Ses snart!
ResponEliminaSap que vol dir fer-se el suec, no??
ResponEliminadet gör inget !!
Hem passat dels missatges xifrats en codis numèrics a un curs a distància de suec? Fer-se el suec? Si vols conèixer diferents hipòtesis sobre d'on ve aquesta expressió, dóna-li una ullada a Hacerse el sueco. Això dels estereotips nacionals i els idiomes, té els seu perills. Per exemple, acomiadar-se a la francesa o "despedirse a la francesa" és, en francès, filer à l'anglaise. Apa, siau!
ResponElimina