Cum treci râul cu un lup, o capră și o varză?
Un lup, o capră, o varză și o barcă prea mică. Un turn de discuri. O insulă unde unii mint mereu. Încearcă fiecare puzzle înainte să citești dezlegarea. Nu e grabă.
Lupul, capra și varza
Un țăran trebuie să treacă râul cu un lup, o capră și o varză. În barcă încape doar el și încă un singur lucru. Dacă rămân singuri, lupul mănâncă capra, iar capra mănâncă varza.
Primul pas e singurul posibil: duce capra. Dacă ar lua lupul, capra ar mânca varza. Dacă ar lua varza, lupul ar mânca capra.
Apoi se întoarce gol și ia lupul. Pe malul celălalt îl lasă pe lup, dar ia capra înapoi cu el. Pe primul mal lasă capra și duce varza lângă lup. Se întoarce gol și, la final, aduce capra.
Secretul: uneori trebuie să aduci ceva înapoi ca să mergi înainte. Sunt 7 traversări. Merge și invers: în loc de lup, la al doilea drum poți duce varza.
Puzzle-ul are peste 1.200 de ani. Apare într-o culegere de probleme în latină scrisă pe la anul 800, atribuită învățatului Alcuin de York. Matematicienii de azi îl rezolvă desenând toate situațiile posibile ca puncte și legând prin linii situațiile între care se poate trece cu o traversare. Rezolvarea e un drum prin acest desen, numit graf.
Turnurile din Hanoi
Ai trei bețe. Pe primul e un turn de discuri, de la mare jos la mic sus. Trebuie să muți tot turnul pe ultimul băț. Muți un singur disc o dată și nu pui niciodată un disc mare peste unul mai mic.
Cu 3 discuri îți trebuie cel puțin 7 mutări. Cu 4 discuri, 15. Cu 5 discuri, 31. La fiecare disc în plus, mutările aproape se dublează.
De ce? Ca să muți un turn de n discuri, muți întâi turnul de n - 1 discuri de deasupra pe bățul din mijloc, muți discul mare, apoi aduci iar turnul mic peste el. Deci mutările pentru n discuri sunt dublul celor pentru n - 1, plus una. Așa iese formula 2ⁿ - 1.
Puzzle-ul l-a inventat matematicianul francez Édouard Lucas, în 1883.
Lucas a vândut jocul cu o legendă: niște călugări mută 64 de discuri de aur, unul pe secundă, iar când termină, vine sfârșitul lumii. Liniștește-te: le-ar trebui peste 580 de miliarde de ani.
Cavaleri și mincinoși
Pe o insulă trăiesc cavaleri, care spun mereu adevărul, și mincinoși, care mint mereu. Întâlnești doi locuitori, A și B. A spune: „Amândoi suntem mincinoși.” Ce sunt A și B?
Dacă A ar fi cavaler, ar spune adevărul, deci ar fi mincinos. Imposibil. Deci A e mincinos, iar propoziția lui e falsă: nu sunt amândoi mincinoși. Cum A e mincinos, B e cavaler.
Și unul mai greu. Două uși: una duce la o comoară, cealaltă la un dragon. La fiecare ușă stă un paznic. Unul spune mereu adevărul, celălalt minte mereu, dar nu știi care e care. Ai voie la o singură întrebare, pentru un singur paznic.
Întrebi pe oricare: „Ce ușă mi-ar arăta celălalt paznic că e cea bună?” Apoi alegi cealaltă ușă.
De ce merge? Dacă vorbești cu cel sincer, el îți spune cinstit ce ar spune mincinosul: ușa greșită. Dacă vorbești cu mincinosul, el minte despre ce ar spune cel sincer: tot ușa greșită. În ambele cazuri primești ușa greșită, deci o alegi pe cealaltă. Insula cavalerilor și mincinoșilor a făcut-o celebră logicianul american Raymond Smullyan.
Fapt sau legendă?
„Legenda călugărilor care mută 64 de discuri de aur e veche de mii de ani.”
„Problema cu lupul, capra și varza apare într-o carte de acum peste 1.200 de ani.”
„La Turnurile din Hanoi poți câștiga cu mai puține mutări dacă ai noroc.”
Experiment: Turnurile din Hanoi din monede
Nu se știe încă
La multe puzzle-uri, ca un sudoku uriaș, verifici repede o soluție dată, dar găsirea ei poate dura enorm. Există oare o metodă rapidă de rezolvare pentru orice puzzle care se verifică repede? Întrebarea se numește „P contra NP” și e una dintre cele mai mari probleme nerezolvate din matematică.
Testul lui Kokodel
- Alcuin de York (atribuit). Propositiones ad acuendos juvenes, aproximativ anul 800.
- Lucas É. Récréations mathématiques. Gauthier-Villars.
- Smullyan R. What Is the Name of This Book? Prentice-Hall, 1978.
- Clay Mathematics Institute. „P vs NP Problem”. Millennium Prize Problems.