luni, 22 februarie 2010

Cadoul pentru învingători

ElZap

Aşadar, astăzi urcă pe podium, pentru a împărţi premiul renata şi klaus.

Dacă ar fi să fac un mic comentariu, principiul care stă la baza rezolvării propuse de renata e corect: trebuie găsit un mijloc de a discrimina situaţia în care se găsesc becurile, când dăm năvală în cameră. Mijlocul ăsta e căldura.
Klaus a venit însă cu o precizare care face ca soluţia să fie absolut riguroasă. Soluţia lui este ceea ce ar trebui să fie, adică... o soluţie riguroasă.
Nemulţumiţii pot depune contestaţii. Comentariile vă aparţin.

Buuuun!
Şi acum, întrucât sunt două soluţii, vor fi, aşa cum e şi normal, tot două premii.
Probleme desigur.

Prima problemă este ceva mai simplă, zic eu, pe câtă vreme a doua este ceva mai grea.
Poate se găsesc şi alte soluţii, la care nu m-am gândit eu, caz în care ambele probleme ar putea fi banale. În fond, fiecare soldat are în raniţă, bastonul de mareşal.


Aşadar... spor la treabă.

La sultan se adună supuşii ca să-i aducă tributul.
(Şi pe vremea aia se obişnuia)

Saci plini cu bani sunt orânduiţi în camera unde trebuia să vină sultanul.


Ca să fie clară problema, trebuie spus că toţi sacii ar trebui să conţină acelaşi tip de monezi de aur. Să zicem că fiecare monedă ar trebui să cântărească 10 grame (deşi sunt sigur că am greşi)

Ca să nu ne încurcăm în simboluri, să zicem că e vorba de 10 saci.

Serviciile îi şoptesc sultanului că unii supuşi au adus în saci monezi falsificate, care ar cântări doar 9 grame. Sacii care conţin monezi false, nu conţin decât monezi false, iar cei ce conţin monezi bune, doar monezi bune.

Problema 1.

S-a aflat că un singur supus, a schimbat monezile bune cu cele false.
Cum trebuie să procedeze sultanul, ca dintr-o singură cântărire să afle care este sacul ce conţine monezi false?

Problema 2.

Nu se ştie câţi saci au monezi false. Ar putea fi de la 0 la 10.
Cum trebuie să procedeze sultanul, ca dintr-o singură cântărire să afle care sunt sacii ce conţin monezi false?

Ce se va întâmpla cu cei ce au falsificat monezile nu se spune în problemă.

FINALA MARE

Cred că toată lumea e de acord, chiar dacă nu m-aş pronunţa eu, că cele mai interesante soluţii au fost date de data aceasta de klaus şi Doar F.

Eu cred că merită apreciat faptul că Doar F a dat soluţia corectă şi pentru problema 2, deşi încercarea cu numere prime dată de klaus, chiar dacă nu este o soluţie, este totuşi un pas spre rezolvarea problemei 2.

Dacă sunt alte opinii, pot fi luate în consideare.

Domnilor, laurii vă aparţin!


50 de comentarii:

  1. Grea problema ne propui, mai ales ca nu prea stim detalii despre "cantarire". Sultanul dispune de un cantar digital, sau de o balanta?

    RăspundețiȘtergere
  2. @DoarF

    Sultanul dispune de un cântar digital.

    RăspundețiȘtergere
  3. ElZap,
    zi că suntem în criză, că n-avem fonduri pentru premii... nu mă supăr!

    Dacă află klaus răspunsul, mă simt foarte bine.
    Dacă altul îl află, îi cedez şi premiul meu parţial.
    Măcar să aflu soluţia!

    RăspundețiȘtergere
  4. @renata

    Soluţia e simplă.

    Apăs pe y şi-l la apăsat cam cât cred eu că se încălzeşte zdravăn becul asociat.

    Sting y.

    Apăs pe z.

    Intru în camera.

    Palpez uşor cele două becuri stinse.
    Unul este cald, deci va fi legat de y.
    Cel aprins va fi legat de z.
    Cel rece, va fi legat de x.

    RăspundețiȘtergere
  5. pune toti sacii o data pe cintar. Luind cite un sac, pe scala cintarului ar trebui sa se vada o cantitate multiplu de 10g, reprezentind sacii ramasi (daca ridica sacul falsificat) sau ceva cu virgula, daca ridica un sac "bun". Ramine mereu cu virgula, pina in momentul in care ridica de pe cintar sacul falsificat, moment in care pe cintar ramine o cantitate multiplu de 10 g- si atunci, cu sacul vinovat in mina, urla: prindeti hotu'!
    Metoda e valabila si pentru varianta mai grea, doar ca e cu mai multe virgule (imi e mult prea lene sa detaliez, n-ai decit sa ma descalifici. Ceva cu multiplu de 10 plus suma de multipli de 9 blablabla).

    RăspundețiȘtergere
  6. varianta1: ridic un sac "bun", pe cintar ramine o cantitate: multiplu de 10 + multiplu de 9. Tot asa, pina il ridic pe ala care e fals, raminind pe cintar o cantitate multiplu de 10.
    varianta2: ridic un sac "bun", pe cintar ramine o cantitate: multiplu de 10 plus suma de multipli de 9; ridicind din asta un sac "rau", pe cintar ramine: multiplu de 10 + (suma de multipli de 9- 1); pe bune daca imi amintesc cum se scria asta. Si asa mai departe, iei sac rau dupa sac rau, pina ramine o cantitate multiplu de 10. In fine, am detaliat putin, ca sa nu par chiar de-a dreptul puturoasa. Desi imi e in continuare lene.

    RăspundețiȘtergere
  7. @Ina

    Nu cumva faci mai multe cântăriri?

    Prima cântărire e cea a celor n saci, pe urmă n-1, şamd

    Şi apoi ce te faci dacă un sac ar avea un număr de monezi care este multiplu de 9 şi 10?
    (90, 180, etc.)

    Să ne mai gândim.

    RăspundețiȘtergere
  8. Sa intelegem ca in fiecare sac exista un numar diferit de monede?

    klaus

    RăspundețiȘtergere
  9. @klaus

    În fiecare sac se află un număr nespecificat de monede, posibil dar nu obligatoriu diferit.

    De asemenea, numărul de monede din fiecare sac este suficient de mare.

    RăspundețiȘtergere
  10. renata, incepe tu rezolvarea ca sa pot s-o termin eu :). NU prea stiu de unde s-o apuc :(.

    klaus

    RăspundețiȘtergere
  11. @klaus

    Începe cu prima problemă.

    Ia din fiecare sac un număr de monezi și fă cu ele o grămadă.

    Pe urmă vezi cum mergi mai departe.

    RăspundețiȘtergere
  12. klaus,
    nu mă pricep la bani. Nu trag la mine!
    Da' uite ce zice ElZap! Că putem face ORICE cu banii, dar doar o singură cântărire. Adică putem desface fiecare săculeţ, scoatem bănuţii, îi facem turnuleţe, îi măsurăm?
    Aşa e, ElZap?
    Ne putem juca liniştiţi cu ei ÎNAINTE de-a face vreo cântărire?

    Eu, ca s-o zic p-a dreaptă, mă aşteptam să ne dea ElZap un premiu de care să ne bucurăm, nu unul la care să muncim.
    Ceva de privit, de ascultat, de bucurat...
    Cred că ElZap e profesor. Şi dacă nu e, asta trebuia să fie.
    Ne recompensează cu altă întrebare, aşa cum făceau profesorii noştri pe vremuri.
    Ce vremuri!...

    RăspundețiȘtergere
  13. @renata

    Din nefericire, numai din cântărire avem voie să tragem concluzii. Nu avem voie să măsurăm diametre, să facem teste chimice, să măsurăm impulsuri, sau alte operaţii fizico-chimice.

    Putem scoate doar o singură dată cântarul din dulap, sau de unde este el pus, putem cântări, ne putem nota ce am obţinut, şi putem face orice socoteli vrem noi.

    În final, trebuie să ştim care este sacul ce conţine monezi false.

    Subliniez, monezile false seamănă leit cu cele bune, cu excepţia greutăţii.

    Nu. Nu sunt profesor, numai că am văzut că mai am în tolbă nişte probleme ce i-ar putea încurca chiar şi pe unii profesori. Mă refer la Problema 2.

    Deocamdată să ne mulţumim cu Problema 1.

    RăspundețiȘtergere
  14. ElZap, pai trebuie sa astept ipoteza in mai multe transe? :))

    Din ultimele tale postari reiese cum ca un singur sac ar avea monede false:
    ,,În final, trebuie să ştim care este sacul ce conţine monezi false.''
    Mai este ceva ce ar trebui sa stiu? :)

    klaus

    RăspundețiȘtergere
  15. @klaus
    În prima problemă se cere să se găsesească sacul ce conţine doar monezi false.

    În a doua problmă se cere să se dezvolte o procedură care să găsească sacii ce conţin monezi false.

    În ambele probleme se presupune că sacul/sacii ce conţin monezi false conţin doar monezi false, iar sacii ce conţin monezi bune conţin doar monezi bune (ori fură ori e om cinstit).

    Monezile bune sunt la fel în oricare sac (au 10g), iar monezile false sunt la fel, indiferent de sac (9g)

    RăspundețiȘtergere
  16. 1. canteresti o moneda din sacul #1, o inlocuiesti cu alta din sacu #2 s.a.m.d. pana gasesti moneda de 9 grame dupa care marchezi ca fiind "fals" sacul din care provine. [Pe ala l-as lua cu drag acasa:))))]
    2. continui operatia de punctul 1 pana termini de verificat toti sacii eliminand pe cei din care provin monedele "false" si...i-ai imparti celor care s-au straduit sa gasesca o solutie la problema lui ElZap:)))

    Solutia mea pare asemanatoare cu aceea a Inei doar ca elimina posibilitatea de a ne pacali cu saci continand 9 X 10 X n monede.
    O fi bine?

    RăspundețiȘtergere
  17. @Hai-Hui

    Din nefericire şi tu faci aceeaşi eroare ca Ina.

    Faceţi mai multe cântăriri!
    E voie doar o singură cântărire.

    RăspundețiȘtergere
  18. pui DEODATA toti n-saci pe cantar si scoti cateo mondeda din fiecare citind scala.....

    profesore, ma dau batut, problema devine enervanta daca dumneata nu consideri catarirea tuturos sacilor ca fiind doar UNA SINGURA....

    eh, zic si eu asa de oftica pentru ca ma-nnervozez rau:))))

    RăspundețiȘtergere
  19. Hai-Hui Nelamuritu25 februarie 2010 la 05:32

    ultima incercare.

    problema 1
    daca serviciilor li s-a soptit (turnat) ca un supus a schimbat monedele, atunci individului i se cantareste o moneda din buzunarul personal acea moneda fiind negresit(!) veritabila.
    sacul adus sultanului de catre acel supus contine monede false. la ghilotina cu supusul necinstit!
    cantarirea este ... facultativa, ghilotina, obligatorie.

    problema 2
    se cantareste o moneda din buzunarul personal al oricarui supus turnat de catre serviciile secrete....tot facultativ.
    cantaritul pentru ca turnatoria a fost obligatorie.
    se ia si se taie gatul supusilor care au adus banu fals.
    executia este obligatorie pentru a se sterge dovezile si ... pentru a nu lasa loc la contestatii :)))

    problema 3
    noapte buna.

    RăspundețiȘtergere
  20. @Hai-Hui
    Evident că şi acum răspunsul e tot greşit.
    Faptul că scoţi câte o monedă din toţi sacii, după ce i-ai pus odată pe cântar presupune că de fiecare dată tu vei citi cântarul, adică faci o câte o cântărire.

    Tu ai voie la o singură cântărire cinsită.

    Dacă serviile ştiau de la început care este cel ce a furat, la ce mai era nevoie de cântăriri. Nu cred că la Sultan ţinea cu prezumţia de nevinovăţie.

    RăspundețiȘtergere
  21. Bună dimineaţa!
    Mă gândeam că, dacă monezile false au doar 9g şi cele autentice au 10g, iar cel care aduce sacul cu bani falşi STIE că urmează a fi cântăriţi... el trebuie să pună mai multe monede de 9g în sac, ca să atingă greutatea unui sac cu monede adevărate. Posibil ca sacul lui să aibă un volum mai mare.
    Sultanul l-ar putea descoperi ochiometric, fără cântărire.

    RăspundețiȘtergere
  22. Pană una alta, am dat-o în bară cu pluralul: monedele, nu monezile! :(

    RăspundețiȘtergere
  23. Stai linistita renata, pluralul ,,monezi'' nu este indicat a se folosi dar nu este gresit. Suna doar mai ciudat :).

    klaus

    RăspundețiȘtergere
  24. rostogoleste monezile pe un plan inclinat. cea care ramane in urma e mai uoara si ramane in urma celorlalte. se cantareste.
    aceeasi procedura la problema #2.
    cantarire unica a monedei false. doar una din cele care se rostogolesc mai domol:))

    complicat si nesigur?
    eu asa face, le-as rostogoli pana le aflu, prin eliminare.
    bravo renata;)

    RăspundețiȘtergere
  25. @renata

    Nu se specifică faptul că toți sacii trebuie să aibă același număr de monezi/monede, prin urmare ceea ce nu este interzis e permis.

    Sacii ar putea avea un număr de monezi complet diferit, ba chiar este de presupus, că doar nu toți supușii vor plăti același bir.

    Așa că nu merge ochiometric...

    RăspundețiȘtergere
  26. @Hai-Hui
    Am precizat mai sus că nu este permisă folosirea altor fenomene fizico-chimice.
    Și apoi, ar trebui precizată frecarea, etc.

    Nu merge!

    RăspundețiȘtergere
  27. 1.Luam din fiecare din cei 10 saci un numar diferit de monede sub forma de numere prime dupa cum urmeaza: 1,3,5,7,11,13,17,19,23,27.
    2. Am luat in mod aleatoriu sacul nr5 ca fiind cel cu monede false.
    3. La singura cantarire a monedelor extrase ne iese o greutate de 1249 de grame.
    4. Observam ca numerele prime inmultite cu greutatea de 10g ne dau doar multipli de 10, evident:).
    5. Prin urmare, cifra 9 din finalul greutatii totale rezulta din inmultirea unui numar prim, 1 sau cu terminatie in 1, in cazul nostru 1 sau 11 cu greutatea monedelor false de 9g.
    Calculam greutatile pentru cei doi multipli astfel incat suma greutatii totale sa se verifice. Adica 1249!

    Modelul luat in calcul

    Sac 1-1moneda
    sac 2-3monede
    sac 3-5monede
    sac 4-7monede
    sac 5-11monede(monede falsificate)
    sac 6-13monede
    sac 7-17monede
    sac 8-19monede
    sac 9-23monede
    sac10-27monede

    klaus

    RăspundețiȘtergere
  28. Am gresit cu 27 ca fiind numar prim :)). A se inlocui cu 29 facand corecturile necesare :).

    klaus

    RăspundețiȘtergere
  29. "a permite orice nu este interzis" contravine folosirii ... altor fenomene fizico-chimice, fapt pentru care nu se admite niciun mikey-mouse; doar o cantarire UNICA.
    daca e asa cred ca toti suntem scosi din competitie.

    alta dilema pe care o am este ca dumneata ai interzis rostogolirea monedelor doar acum cateva momente...

    frecarea mondelor rostogolite cu aerul nu trebuie precizata cata vreme sustii ca este permis ceea ce nu este interzis, densitatea diferita le va diferentia pe cele grele de cele usoare, frecarea cu aerul e apa de ploaie...
    acum mentionezi ca rostolirea e inclusa in fenomenele fizico-chimice.
    de acord, nu contest dar sa te vad ce altceva "permis, neinterzis si nefizico-chimic" te va ajuta sa diferentiezi monedele false de cele veritabile...

    poate vreun certificat de autenticitate cu serial#'s pe monede, act semnat de regatele supusilor:)))

    astept cu interes.

    RăspundețiȘtergere
  30. Hai-Hui cel slab la mate:))25 februarie 2010 la 09:06

    da, dom'le klaus, corect:)

    RăspundețiȘtergere
  31. ma-ntreb cum se rezolva problema daca in niciunul din cei 10 saci nu-s mai multe decat 19 monede iar greutatea celor autentice nu e de 10 grame pentru ca....autorul problemei nu este sigur, precum a zis-o mai sus;)

    RăspundețiȘtergere
  32. Klaus, varianta cu numere prime rezolva si a doua problema. Pentru prima problema este suficient sa luam un numar diferit de monede: 1,2,3....10.

    @HH
    Problema se rezolva fix la fel daca pui alt numar in loc de 10. Daca vrei o rezolvare formala, foloseste X si X-1. Nu e nici o diferenta(atat timp cat X si N indeplinesc mici conditii intiale)

    RăspundețiȘtergere
  33. @Doar F

    Am ales numere prime pentru a elimina unele posibilitati greu de triat ulterior. Ma refer aici la numere care ar fi indeplinit conditii pentru mai mult de doi saci. Sincer, nici n-am mai verificat posibilitatea cu 1,2,3....
    Astept acum sa vad ce zice si dom' profesor :).

    klaus

    RăspundețiȘtergere
  34. Se pare ca rezolva si a doua problema :). Nu sunt inca foarte sigur, n-am timp acum sa verific riguros. Si asa am luat o pauza de cafea de 3 ore :)).
    Pe diseara!

    klaus

    RăspundețiȘtergere
  35. @klaus
    @Doar F

    Deocamdată, pentru prima problemă, rezultatul este corect. Așa-i?

    Mie mi se pare că aveți dreptate.
    Ce vor zice ceilalți.
    Doar F simplifică permis de mult soluția. E un pas înainte.

    Poate redactăm o soluție clară pentru Problema 1. Eu zic că o soluție este clară dacă poate fi prinsă de cel ce o citește din prima lectură.

    Oricum, prima problemă s-a fisurat zdravăn.

    RăspundețiȘtergere
  36. @klaus
    @Doar F

    Mie mi se pare că nu merge treaba cu numerele prime.

    RăspundețiȘtergere
  37. Corect. Dar merge cu puterile lui 2:
    2^0 = 1
    2^1 = 2
    2^2 = 4
    2^3 = 8
    2^4 = 16
    2^5 = 32
    2^6 = 64
    2^7 = 128
    2^8 = 256
    2^9 = 512

    RăspundețiȘtergere
  38. De ce nu merge, maestre? Nu ne-ai mustruluit mereu pentru rigurozitate? As vrea sa-mi si explici ce si cum.

    klaus

    RăspundețiȘtergere
  39. In lipsa maestrului...
    daca dupa cantarire obtinem 1127, avem cel putin 2 posibilitati pentru sacii cu monede false:
    1. sacul numarul 3: 10+20+27+50+70+...+290

    2. sacii 1 si 2: 9+18+30+50+...+290

    RăspundețiȘtergere
  40. Stiu io o solutie FARA cintarire!
    Punem fiecare supus care vine cu sacul la poligraf!
    Gata; hai ca am rezolvat problema. Sa vina alta, mai grea :)

    RăspundețiȘtergere
  41. @klaus
    @Doar F

    Problema 1.

    Aţi ajuns la rezultatul corect.

    Poate că ar fi fost bună o explicaţie mai clară şi menţionarea faptului că putem alege orice numere de monede pe care să le extragem din sac, cu condiţia ca două numere să nu fie egale.

    E păcat ca după ce am obţinut o soluţie bună să nu o formulăm simplu şi clar.

    RăspundețiȘtergere
  42. @klaus

    Alegerea numerelor prime nu este bună pentru că un şir de numere prime nu formează o bază.

    Dacă alegem pentru saci numerele:

    Sac: 1 2 3 4 5 6 7
    Numere: 1 2 3 5 7 11 13

    (las' că 1 nu e număr prim!)

    Avem numeroase situaţii în care nu putem spune cine a trişat.

    Astfel:
    1+5+7 ne dă to atâta cât pentru sacul 7, adică 13
    2+5+7=1+13

    Şi multe altele.

    Ar trebui lămurit de ce optăm pentru u anumit sistem de numere, şi cum trebuie ales el pentru a putea fi bun.

    RăspundețiȘtergere
  43. @Doar F

    Problema 2.

    Felicitări pentru rezolvare.

    Acum ar trebui să ne explic şi de ce ai luat numerele alea ciudate şi ce-ar trebui să facă sultanul cu ele.

    RăspundețiȘtergere
  44. @Ina

    Poligraful nu face parte din recuzita detectivului nostru.

    RăspundețiȘtergere
  45. Mi-ar fi placut sa discutam d'astea fata-n fata :). Tot n-am inteles daca da gres undeva metoda mea. Pana la urma trebuia rezolvata problema, nu enuntarea unei intregi teorii matematice. Cel putin la matematica, eu spun pas:).

    S-aveti o noapte frumoasa!

    klaus

    RăspundețiȘtergere
  46. @klaus

    1. Dacă e vorba de prima problemă, rezolvarea e corectă, oricum am alege o selecţie de monede din saci, cu singura condiţie ca numerele de monede extrase să fie diferit de la un sac la altul.

    2. Dacă e vorba de a doua problemă, numerele trebuie alese cu grijă. Altfel nu putem discrimina diferse configuraţii.

    Concret.

    Să zicem, pentru a simplifica calculele, că am avea 4 saci. Dacă alegem numerele 1, 3, 5, 7, atunci nu putem discrimina situaţia în care doar primul şi ultimul sac ar conţine monede false(1+7=8), de situaţia în care doar al doilea şi al treielea sac ar conţine monde false (3+5=8).

    Să refacem calculele, iar dacă nu e corect o să revin.

    Dacă însă luăm puterile lui 2, aşa cum a propus Doar F, lucrul nu se mai întâmplă.

    1, 2, 4, 8 dă o eroare diferită pentru fiecare configuraţie de monede false.

    1 2 3 4

    B B B B => E=0
    F B B B => E=1
    B F B B => E=2
    F F B B => E=3
    B B F B => E=4
    F B F B => E=5
    B F F B => E=6
    F F F B => E=7
    ...
    F F F F => E=15

    Astfel, dacă după cântărire ajungem la concluzia că sunt 6 monede false, putem merge sigur la sacii 2 şi 3.

    Am putea lua şi alte şiruri de numere, cum ar fi puterile lui 10. Nu-i aşa?

    RăspundețiȘtergere
  47. Pentru problema a doua, este necesar ca numerele alese sa indeplineasca urmatoarea conditie: nici unul sa nu poata fi scris ca suma a celorlalte.
    De ce am ales "ciudatele" astea? Defect profesional:p Tocmai ce am explicat, in alta parte, ca totul tine de unghiul din care privesti lucrurile. Cand am descoperit conditia, am stiut instantaneu, puterile lui 2 fiind extrem de familiare, ce numere satisfac cerintele.
    Se pot folosi puteri ale oricarui numar mai mare ca 2. Dar asta costa. Daca sultanul cucereste si America si mai primeste cativa saci si de acolo, sa zicem 10, din ultimul sac ar trebui luate 524 288 monede(in cazul meu - cu 2) si 10 000 000 000 000 000 000(in cazul tau - cu 10). Si asa am rezolvat si "necesitatea" SUV-urilor americane: ca sa poata aduce tributul sultanului.
    O problema si mai "interesanta" ar fi sa se gaseasca numarul minim de monede din care sultanul ar putea sa descopere tradatorii. Dar aceasta problema nu mai are nimic de-a face cu puterea de deductie, ci doar cu puterea muncitoreasca.

    RăspundețiȘtergere
  48. @Doar F

    Eu cred că condiția ca ”niciun număr să nu poată fi scris ca sumă din celelalte numere” nu este o condiție suficient de tare în alegerea unui șir de selecție corect.

    De exemplu, dacă luăm șirul de mai jos (pentru 5 saci):

    1, 2, 5, 9, 13

    Nici unul din numere nu se poate scrie ca suma a doua sau mai multe numere din șir.

    Cu toate astea

    2+13=15
    1+5+9=15.

    Așadar se poate confunda falsitatea apărută în sacii

    2 și 5
    cu aceea a falsității sacilor
    1, 3 și 4

    Ai drepate cu baza 10. Este valabilă doar teoretic.

    Problema pe care o pui este interesantă.

    RăspundețiȘtergere
  49. Corect. Ceea ce imi aduce aminte de un banc:
    Care este asemanarea dintre un caine si un inginer? Amandoi inteleg din priviri, dar nu se pot exprima.

    Revenind la problema: in cazul in care cineva doreste sa isi incerce norocul cu numarul minim, conditia corecta este: sa nu existe doua combinatii diferite care sa aiba aceeasi suma.

    RăspundețiȘtergere
  50. Asta cu laurii ma lasa cu moaca pleostita :)). Nu prea ma simt in largul meu la primit lauri.
    Oricum, multumesc!

    klaus

    RăspundețiȘtergere