40
Cred ca la inceput de saptamana cand nici iarba nu creste, un imbold primit din partea unor probleme de logica ar fi binevenit pentru “demarajul” mintal necesar unei noi saptamani. Sper sa fiti mai inspirati decat sunt eu lunea.
Problema 1
Unui grup de condamnati i s-a dat oportunitatea de a fi eliberati daca reusesc sa ghiceasca culoarea palariei detinute de fiecare pe cap (niciunul dintre ei neputand vedea culoarea palariei de pe cap), fiind asezati pe o linie, iar fiecare purtand pe cap o palarie de culoare albastra sau rosie. Fiecare vede palariile de pe capetele celor din fata sa din linie, iar declararea incepe de la ultimul condamnat (cel care vede toate palariile celorlati condamanti), si continua secvential de-a lungul liniei pana la primul. Condamnatilor li s-a permis sa elaboreze o strategie.
Care este numarul de condamnati care pot fi eliberati?
Problema 2
Avem 3 galeti care contin un numar intreg de litri de lichid. Putem sa dublam continutul unei galeti turnand in ea o cantitate egala cu cea continuta, dintr-o galeata care contine mai mult lichid decat prima.
Aratati ca, indiferent de cantitatile de lichid continute la inceput, in cele din urma se poate goli de continut una dintre galeti.
Problema 3
Toate numerele de la 1 la 100 (cu exceptia unuia) ii sunt citite unei persoane, cate unul la 10 secunde, dar intr-o ordine aleatoare.
Cum poate sa-si dea seama cineva cu o memorie buna, dar normala, fara vreun mijloc de a nota numerele, care este numarul lipsa?
17 Comentarii
problema 3.
Insumeaza numerele care le aude si scade aceasta valoare din 1+2+3+…+100=5050 si obtine numarul lipsa.
iunie 28, 2010 - 8:42 amCorect.
iunie 28, 2010 - 9:14 amdoar trei, deci, una deja rezolvata, pana acum….problema cu palariile nu pare chiar asa de grea 🙂
iunie 28, 2010 - 9:25 amultimul condamnat il informeaza pe penultimul daca culorile palariei antepenultimului si penultimului sunt diferite sau aceleasi/aceeasi, penultimul putand spune ce culoare are palaria lui si reluand strategia pentru eliberarea antepenultimului. numarul pare a fi 99
iunie 28, 2010 - 9:31 amDin pacate, mi-e destul de greu sa gasesc probleme noi, din cauza asta numarul a fost mai redus azi.
iunie 28, 2010 - 11:30 amIn ceea ce priveste problema 1 esti “in zona”, dar fiecare declara doar o culoare pentru palaria proprie, asa ca solutia trebuie “ajustata” putin.
problema 2:
Fie (a, b, c) cele 3 galeti. Operatia de transferare a lichidului dintr-o galeata in alta se poate exprima printr-o transformare de genul:
(a, b, c) |—> (2a, b-a, c) cu conditia ca b >= a
Fie M = min(a, b, c). Vreau sa aplic urmatorul “truc”. Gasesc un algoritm prin care de la tripletul (a, b, c) se ajunge la tripletul (a1, b1, c1) cu M1 = min(a1, b1, c1) M1 > M2 > … Acest lucru implica faptul ca la un moment dat se va obtine un Mn = 0 ce implica o componenta nula.
Presupun a<=b<=c. Din teorema impartirii cu rest se obtine: b = a*q + r, cu r < a.
Va fi suficient sa elimin din vasul b lichid astfel incat sa raman cu r litri de apa, deoarece min(a', r, c') < r (2x, y-x, z) |—> (4x, y-3x, z) … |—> ( (2^k)*x, y’, z)
q poate fi scris in baza 2: q = 2^k1 + 2^k2 + 2^k2 + … + 2^kt
k1 < k2 < … = b = a(2^k1 + 2^k2 + … + 2^kt) + r >= a*2^kt ceea ce arata ca pot adauga de succesiv apa din vasul 3 daca e cazul, obtinand toate puterile lui 2 inmultite cu a, mai mici sau egale cu a*2^kt. ( am o rezerva de apa de cel putin a*2^kt, numai ca nu o pot transfera pe toata odata ci prin mai multe etape, trecand prin puteri succesive ale lui 2).
De ce am spus cand este cazul? Dupa o golire: (a*2^k1, b, c’) |—> (a*2^(1+k1), b-a*2^k1, c) este posibil ca a*2^(1+k1) = a*2^k2 (daca k2 = k1 + 1) si in acest caz nu mai este nevoie sa golesc din vasul 3.
Sper sa nu imi fi scapat ceva. Am incercat sa fiu cat se poate de clar.
iunie 28, 2010 - 11:34 amInainte de scrisul rosu trebuia sa apara:
Presupun a<=b<=c. Din teorema impartirii cu rest se obtine: b = a*q + r, cu r < a.
iunie 28, 2010 - 11:36 amVa fi suficient sa elimin din vasul b lichid astfel incat sa raman cu r litri de apa, deoarece min(a', r, c') <= r (2x, y-x, z) |—> (4x, y-3x, z) … |—> ( (2^k)*x, y’, z)
Am scris relatia pe mai multe randuri (sper sa fie okay de data asta)
Presupun a<=b<=c. Din teorema impartirii cu rest se obtine: b = a*q + r, cu r < a.
iunie 28, 2010 - 11:38 amVa fi suficient sa elimin din vasul b lichid astfel incat sa raman cu r litri de apa, deoarece
min(a', r, c')
< =
r
(2x, y-x, z) |—> (4x, y-3x, z) … |—> ( (2^k)*x, y’, z)
Nu m-am prins inca de se formateaza asa textul:
iunie 28, 2010 - 11:40 ammin(a’, r, c’) <= r (2x, y-x, z) |—> (4x, y-3x, z) … |—> ( (2^k)*x, y’, z)
Solutia poate fi citita aici .
iunie 28, 2010 - 11:56 amsolutia problemei 2
iunie 28, 2010 - 11:58 amLa problema 1 cred ca fiecare trebuie sa raspunda ca are pe cap o palarie de culoarea care predomina dintre cele aflate in vizorul sau, dar totusi nu cred ca strategia este optima.
iunie 29, 2010 - 7:48 amDin cate imi dau eu seama solutia lui Cosmin este corecta.
iunie 29, 2010 - 8:42 pmSolutiile lui Matador si Florin erau foarte aproape de cea optima. Ultimul condamnat va spune ca are palarie de culoare rosie (sa spunem) daca vede un numar impar de palarii de culoare rosie in fata, si ca are palaria de culoare albastra daca nu. Astfel cel din fata lui va stii ce culoare are palaria de pe capul sau, samd. In acest fel toti condamnatii, cu exceptia ultimului, se vor putea salva.
iunie 29, 2010 - 8:53 pmDaca ultimul tot se sacrifica, la problema cu palariile e mai simplu ca el sa spuna ce palarie are cel din fata sa; astfel scapa sigur toti si sansa lui de a nimeri-o este tot 50%, altfel vreunu poate fi suficient de prost sa judece cu par-impar 🙂
si apoi ramânând doar el, poate i se da drumul deoarece inchisoarea nu-si mai justifica rentabilitatea 😀
Daca acea problema cu 25 numere de acu’ cateva weeks are o solutie si la fel cea cu sahul cu albul fara pioni si mat in 4 mutari, m-ar interesa, daca se poate …, un email ceva, sau aici ,ca sigur intereseaza si pe altii…
iulie 7, 2010 - 8:10 amMultumesc !
Nu cred ca merge solutia ta. Daca ultimul spune ce culoare are palaria acelui din fata lui ce va face acesta cu informatia? Ori spune ce culoare are palaria proprie, ori anunta culoarea urmatorului, nu poate face ambele lucruri (decat daca culoarea coincide), samd.
iulie 8, 2010 - 9:24 pmmda 😀
iulie 8, 2010 - 9:29 pmNeatentie; chiar nu stiu de ce mi s-a parut asa!