4 carti

[•Cosmin]

Comentarii la postul http://infoarena.ro/blog/4-carti

[•tzipleatud]

Putem stabili o ordine a culorile astfel incat intre oricare 2 carti sa poata fi stabilita o ordine (de exemplu trefla<romb<inima<frunza). Astfel avand 4 carti a,b,c,d putem presupune a<b<c<d.
Atunci pentru culoarea celei de-a 5 carti putem avea 4 configuratii:
a,b,c,d - trefla (toate in ordine crescatoare)
d,c,b,a - romb (toate in ordine descrescatoare)
a,d,b,c - inima (cate 2 in ordine crescatoare)
d,a,b,c - frunza (cate 2 in ordine descrescatoare)

Momentan nu imi dau seama de cum as putea comunica numarul cartii dar voi revenii daca imi vine ceva idee.

[•Andrei.Xwe]

Putem stabili o ordine a culorile astfel incat intre oricare 2 carti sa poata fi stabilita o ordine (de exemplu trefla<romb<inima<frunza). Astfel avand 4 carti a,b,c,d putem presupune a<b<c<d.
Atunci pentru culoarea celei de-a 5 carti putem avea 4 configuratii:
a,b,c,d - trefla (toate in ordine crescatoare)
d,c,b,a - romb (toate in ordine descrescatoare)
a,d,b,c - inima (cate 2 in ordine crescatoare)
d,a,b,c - frunza (cate 2 in ordine descrescatoare)

Momentan nu imi dau seama de cum as putea comunica numarul cartii dar voi revenii daca imi vine ceva idee.

Si daca sunt toate cartile de aceeasi culoare?

[•tzipleatud]

Putem stabili o ordine a culorile astfel incat intre oricare 2 carti sa poata fi stabilita o ordine (de exemplu trefla<romb<inima<frunza). Astfel avand 4 carti a,b,c,d putem presupune a<b<c<d.
Atunci pentru culoarea celei de-a 5 carti putem avea 4 configuratii:
a,b,c,d - trefla (toate in ordine crescatoare)
d,c,b,a - romb (toate in ordine descrescatoare)
a,d,b,c - inima (cate 2 in ordine crescatoare)
d,a,b,c - frunza (cate 2 in ordine descrescatoare)

Momentan nu imi dau seama de cum as putea comunica numarul cartii dar voi revenii daca imi vine ceva idee.

Si daca sunt toate cartile de aceeasi culoare?

Pai cartile sunt numerotate. Si consider ca prioritate o au culorile deci de exemplu trefla 7 < romb 6 (dupa ordinea pe care am zis-o eu).

[•Andrei.Xwe]

Putem stabili o ordine a culorile astfel incat intre oricare 2 carti sa poata fi stabilita o ordine (de exemplu trefla<romb<inima<frunza). Astfel avand 4 carti a,b,c,d putem presupune a<b<c<d.
Atunci pentru culoarea celei de-a 5 carti putem avea 4 configuratii:
a,b,c,d - trefla (toate in ordine crescatoare)
d,c,b,a - romb (toate in ordine descrescatoare)
a,d,b,c - inima (cate 2 in ordine crescatoare)
d,a,b,c - frunza (cate 2 in ordine descrescatoare)

Momentan nu imi dau seama de cum as putea comunica numarul cartii dar voi revenii daca imi vine ceva idee.

Si daca sunt toate cartile de aceeasi culoare?

Pai cartile sunt numerotate.

Eu ma gandesc ca nu e tocmai bine asa, prin ordinea culorilor se poate spune culoarea si prin ordinea numerelor numarul...
Spre exemplu, daca toate cartile sunt de aceeasi culoare, atunci cel de-al doilea jucator va sti automat(se face conventia asta). Dar depinde si de celelalte cazuri...cand sunt 2 de aceeasi culoare si celelalte 3 de o alta culoare, sau cand sunt 2-2-1 pe culori, etc....

[•tzipleatud]

Primul jucator poate sa puna pe masa intr-o ordine? Adica de exemplu sa puna prima carte, sa lase spatiu, sa puna inca o carte si apoi sa completeze acel spatiu?

Sau macar daca de exemplu poate sa le puna de la stanga la dreapta sau de la dreapta la stanga, exista 24 moduri de a aranja acele carti, 2 directii in care le poate aseza deci 48 de configuratii. 48+4 carti deja asezate=52 deci se poate afla a 5-a carte.

[•Andrei.Xwe]

Pai el are 5 carti din care o alege convenabil cea care poate fi ghicita prin conventia celor doi jucatori...si le pune pe celelalte 4 in asa fel incat al doilea jucator sa-si poata da seama prin conventia aia....cam asta inteleg eu din enunt

Da, calculul tau e corect, cam asa m-am gandit si eu, doar ca eu am zis ca el ar putea alege si cartea pe care o va lasa...adica si asta ajuta...in fine, noi trebuie sa gasim acest cod al lor(sau unul dintre ele...poate or fi mai multe)

[•Cosmin]

@tudor Al doilea jucator vede cele 4 carti cand sunt toate pe masa.

[•Andrei.Xwe]

@tudor Al doilea jucator vede cele 4 carti cand sunt toate pe masa.

  Inseamna ca devine ceva mai complicat....nu ma prind ce ar putea fi...ma dau batut. Poti, te rog, sa-mi trimiti solutia prin mesaj privat?

[•vdobrota]

Fiind 4 culori si 5 carti, e foarte probabil sa conteze ca 2 carti sunt de aceeasi culoare

[•Cosmin]

@adrian asta e partea frumoasa a problemei. Te dai batut prea repede.

[•klamathix]

Fixam o relatie de ordine intre carti (rosu < negru) (romb < inima etc.).

Daca toate cartile sunt pe fata, cartea noastra este printre primele 24 si numarul de ordine ii este dat de numarul de ordine al permutarii cartilor normalizate.
Daca cartea e in urmatoarele 24 folosim combinatii de genul (prima cu fata in jos * 6 permutari ale celorlate 3, a doua cu fata in jos * 6 permutari etc.)
Daca e intre ultimele 4 lasam doar o carte cu fata in sus, indicand a cata din ultimele 4 este (Daca prima e cu fata in sus, atunci e cartea cu nr 49).

Spune-mi te rog ca avem voie sa le punem cu fata in jos ).

[•Cosmin]

@Mihai nu e voie cu carti intoarse. Al doilea jucator va vedea 4 carti cu fata in sus aliniate pe masa, una langa alta.

[•raduberinde]

Frumoasa problema. Cred ca am o solutie.

Sa zicem ca setam o ordine globala pentru carti si putem sa ne referim la ele ca numere de la 1 la 52.

Impartim cele 52 de numere in 4 "binuri" de cate 13 carti. Din cele 5 carti primite vor fi neaparat cel putin 2 carti in acelasi bin.

Alegem o astfel de pereche de carti. Una din aceste carti va fi a 5-a carte ascunsa, iar cealalta carte va fi prima carte aratata din cele 4 (deci al doilea jucator va sti imediat binul cartii ascunse). Celelalte 3 carti aratate vor fi folosite pentru a "transmite" un numar intre 1 si 6 (a cata permutare din cele 6 posibile, ca si ordine relativa).

Cele doua carti fac parte din acelasi bin. Sa numerotam cartile din binul respectiv de la 1 la 13 in ordine crescatoare, si sa zicem ca cele doua carti au valorile x si y intre 1 si 13, cu x < y. Putem alege care din x sau y va fi aratata. Alegem asa: daca diferenta (y-x) e para, aratam cartea cea mare (y); altfel o aratam pe cea mica (x). Sa ne gandim ce inseamna asta pentru al doilea jucator, care vede prima carte cu valoare sa zicem z. El stie ca cealalta carte ori e mai mica si diferenta e para (deci z-2, z-4, etc) ori e mai mare si diferenta e impara (deci z+1, z+3, etc). Daca z e par, sunt (z-2)/2+(14-z)/2 = 6 posibilitati. Daca z e impar sunt (z-1)/2+(13-z)/2=6 posibilitati. Deci in toate cazurile, dandu-se prima carte aratata, sunt exact 6 carti posibile, si celelate 3 carti aratate pot indica valoarea necesara intre 1 si 6.


Edit: m-am grabit sa absractizez haha, in loc de "binuri" putem sa ne gandim la culori (deci prima carte aratata are aceeasi culoare cu a 5-a carte; apoi determinam numarul cum am spus)

[•Kira96]

Presupun ca nu te poti uita in pachetul de carti,nu?

[•raduberinde]

Mama ba ce intrebari/idei puteti sa aveti. Evident ca nu poti sa te uiti in pachetul de carti, care ar mai fi problema? Nu, nu poti sa folosesti felul cum asezi cartile (unghiuri, spatii, orientari), nu poti sa ii faci cu ochiu in timp ce le arati, si nici nu poti sa ii trimiti un SMS. Singura informatie pe care o transmiti sunt cele 4 carti in ordine.

[•maritim]

Am si eu o idee creata care poate sa-ti ofere 2 carti in care sigur se gaseste cartea intoarsa cu fata in jos.

Acest algoritm este cel care corespunde jucatorului care aseaza cartile jos, cel care trebuie sa isi dea seama de a 5-a carte trebuind doar sa reconstituie algoritmul din punctul lui de vedere.

• Pentru inceput stabilim o ordine globala (cum spunea si Radu Berinde) pentru cele 52 de carti.
• Acum putem vedea 4 carti distincte in mana, deci ne mai raman de cautat doar 48 de carti pe care le vom imparti in 4 gramezi de 12. Ordonam cele 4 carti din mana. Cartea asezata jos va fi cartea cu numarul de ordine al gramezii in care se afla cea de-a 5-a carte.
• Acum avem 3 carti ordonate in mana si o gramada de 12 carti in care sigur se afla cartea noastra. Impartim aceasta gramada de 12 in 3 gramezi de 4 carti. Urmatoarea carte asezata jos este cartea cu numarul de ordine (din cele 3) care corespunde cu numarul de ordine al gramezii in care se afla cea de-a 5-a carte.
• Acum avem 2 carti ordonate in mana si o gramada de 4 carti in care sigur se afla cartea nostra. Se imparte si aceasta gramada in 2 gramezi de 2 carti. Urmatoarea carte asezata jos este cartea cu numarul de ordine (din cele 2) care corespunde cu numarul de ordine al gramezii in care se afla cea de-a 5-a carte.
• Acum avem 2 carti in care stim sigur ca se afla cartea noastra si in plus o carte inutila in mana.

Aceasta solutie e un fel de cautare binara pe cele 48 de carti care iti ofera o solutie formata din 2 carti, nu o singura carte cum ar fi dorit.
Poate imi scapa ceva ?


Edit: Daca se pot aseza si intr-o ordine anume , am putea pune cea de-a patra carte la inceputul sau la sfarsitul liniei formata din cele 3 carti, astfel dand o informatie despre pozitia cartii din gramada de 2 carti.

[•Cosmin]

@Andrei problema iti cere sa poti spune o carte nu doua.

Pentru doua e foarte simplu sa indici 24 de grupuri de cate doua carti folosind de ordinea celor patru carti pe masa. Dificultatea problemei vine la pasul in care treci de la 24 stari care le poti exprima la 48.

@Radu da solutia ta e buna.

[•proflaurian]

Protocolul se defineste ca "o intelegere intre cei doi" cunoscuta de cei doi prin care primul "ii arata" celui de-al doilea care e cartea ascunsa?

[•pauldb]

Da.

[•proflaurian]

Geniala faza. Credeam ca primul "ascunde" cartea si al doilea trebuie sa ghiceasca si bineinteles ca ma gandeam la cautare binara. Abia cand am citit solutia lui Radu am inteles.  "Magie" curata.

[•proflaurian]

O solutie alternativa ar putea folosi distanta dintre carti asezate circular.
Primul alege doua carti cu aceeasi culoare (conform Dirichlet sigur exista) si se considera cartile acelei culori asa:
2 3 4 5 6 7 8 9 10 J Q K A 2 3 4 5 6 7 8 9 10 J Q K A
Se alege "distanta" minima dintre cele doua carti masurata de la cartea "mare" la cartea "mica" in sus sau in jos.
Daca distanta mica e "in jos" punem cu fata in sus cartea mica altfel punem cartea mare.
Permutarea de care zicea Radu poate fi folosita acum sa ne spuna cate carti trebuie sa numaram de la cartea "vizibila" la cartea "invizibila" Evident ca avand 13 carti distanta minima e cel mult 6 si poate fi "indicata" ca pozitia in ordine lexicografica a permutarii celorlalte 3 carti.

[•raduberinde]

Da, e mai usor asa. Cu alte cuvinte alegi diferenta mai mica modulo 13 (ori y-x<=6 ori 13-y+x <= 6).

[•Kira96]

Cartile alese trebuie sa fie consecutive?

[•Cristy94]

@ Radu Berinde
Poti te rog sa explici algoritmul tau pentru cartile: 4♠ , 4♣ , 4♦ , 4♥, 5♠ ?

Daca z e par, sunt (z-2)/2+(14-z)/2 = 6 posibilitati. Daca z e impar sunt (z-1)/2+(13-z)/2=6 posibilitati. Deci in toate cazurile, dandu-se prima carte aratata, sunt exact 6 carti posibile

Pai ai zis ca "daca diferenta (y-x) e para, aratam cartea cea mare (y); altfel o aratam pe cea mica (x)" . De unde stie cealalta persoana daca diferenta e para sau impara, sau daca acea carte pusa pe masa este cartea mai mica sau mai mare?