4 carti

[•soriyn]

Daca am inteles eu bine ideea lui Radu Berinde din protocol face parte si regula "avand 2 carti cu valoarea x si y, cu x<y atunci daca y-x e par prima carte pe care o arat e y, altfel x".  In exemplul tau 5-4 e impar deci o sa puna mai intai cartea mica, pe 4. Acum al doilea jucator trebuie sa incerce ambele posibilitati :

1. Diferenta dintre y si x e para, deci cartea aratata e cea mare. Atunci singura carte ramasa ar mai fi 2.

2. Diferenta dintre y si x e impara, deci cartea aratata e cea mica. Atunci mai are posibilitatile 5,7,9,11,13.

In total sunt  6 variante. Iar numarul permutarii celor 3 carti din mijloc probabil ii arata a cata carte e cea ascunsa, considerand sortate toate cele 6 carti posibile in ordine crescatoare.

[•informatician28]

Cum adica numarul permutarii celor 3 carti din mijloc??

[•soriyn]

Cartile de pe pozitiile 2,3,4 sunt cele din mijloc. Sunt 6 posibilitati de a alege ultima carte. Exista 6 permutari pentru o multime cu 3 elemente. Daca le consideram in ordine lexicografica inseamna ca , de exemplu, daca primul formeaza din cele 3 carti a 4-a permutare posibila (in ordine lexicografica) ii indica celui de-al doilea ca trebuie sa alega a 4-a carte in ordine crescatoare.

[•Cosmin]

Solutia lui Radu combinata cu ideea lui Adrian curata si usor de realizat practic:
fixezi culoarea cu prima carte si alegi ca prima carte pe cea care e la distanta circulara mai mica decat 6 ca cealalta

Mai stiam o solutie:
metoda de decodare e simpla, alegem cea mai mare dintre cele 4 carti de pe masa si mergem de la ea circular cel mult 24 de pozitii. Cel ce pune cartile pe masa alege sa ascunda cea mai mica sau cea mai mare carte in functie de care varianta ii permita ca metoda de decodare pe care am zis-o sa functioneze.

Adrian Diaconu mi-a zis ca problema se poate rezolva si pentru un pachet de 124 de carti cu aceiasi restrictii 4 carti pe masa, una ascunsa. Incercati sa o rezolvati.

[•svalentin]

Ar trebui sa traducem aceste problemute si in engleza. Multa lume ar fi interesata de ele.

[•Sorin_Ionut]

Am si eu o solutie, tine de baze de numeratie si descompuneri. - nu foarte diferita de original.
Pentru ca nu sunt chiar asa de genial la matematica am testat solutia pe toate cazurile posibile si are 100% rata de raspuns corect simuland player.2
Revin cu descrierea pe seara cand ajung acasa.

Ps: faina problema gg

[•teo2mirce]

Dupa cum spuneau si ceilalti prima carte arata culoarea iar din celelalte 3 putem forma (cum mai zicea cineva) un cod binar in funtie de distanta fata de cartea precedenta: daca este lipita de cea din stanga cartea are codul 1 daca exista un spatiu atunci are codul 0. Deoarece numarul maxim pe care il putem forma este 111 <=> 7, recurgem la o intelegere intre cele 2 persoane daca numarul cartii = codul transormat in baza 10 sau 7+ codul transformat in baza 10. Acest lucru se poate realiza imediat in functie de ordinea celor 3 carti (crescatoare => numarul=codul in B10 /descrescatoare=> numarul=7+codul in B10). Pentru ca stiu ca o sa inceapa unii sa tipe la mine: "Ia zi tu ce se intampla cand toate cele 3 sunt la fel, cum sortezi?", se mai face inca o intelegere ex: daca 2 carti sunt egale atunci: inima neagra>inima rosie>trefla>caro.

[•proflaurian]

@cosminn

La varianta cu 124 de carti se intelege ca avem doua pachete de 52 de carti deci oricare carte apare exact de doua ori?

[•darkseeker]

@Adrian Panaete

Si eu m-am gandit la acelasi lucru, ca ar fi 2 pachete de carti dar atunci ar trebui sa fie 104 carti, nu 124.

[•raduberinde]

Nu, ai 124 de carti diferite. Cu alte cuvinte, primul jucator primeste 5 numere distincte intre 1 si 124, iar al doilea jucator trebuie sa ghiceasca al 5-lea numar vazand 4 dintre ele intr-o anumita ordine. (Si in toate astea de 3 lucruri tine cont, 2 platane si 1 microfon.)

Apropo, combinari de 124 luate cate 5 este exact egal cu aranjamente de 124 luate cate 4. Asta inseamna (pe langa ca 124 e cel mai mare nr pentru care problema asta e posibil sa aiba solutie), nu poate fi nimic redundant in codificare, si toate aranjamentele aratate trebuie sa fie "valide". De ex. in solutia mea cand 3+ carti au aceeasi culoare, nu toate valorile intre 1 si 6 sunt valide; insa, pentru varianta cu 124 de carti, orice aranjament trebuie sa fie cuplat cu exact o combinare (o bijectie).

Se poate in teorie scrie un program care sa determine un cuplaj complet intre cele 225M aranjamente si combinari, si asta ar gasi o solutie la problema (atata timp cat exista o solutie). But that would be cheating haha

[•teo2mirce]

Cu metoda mea poti ajunge la 385 de numere:
avem in mana 4 carti de forma: 1 2 3 4 (1 cea mai mica dintre carti,2 urmatoarea,3 urmatoarea,4 cea mai mare carte din mana)
Putem aranja cele 4 in 24 de moduri posibile ( 1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2,etc.)
Putem forma din cele 4 minimum 0000 si maximum 1111 adica 0 respectiv 15.
Cei doi pot stabili urmatoarea regula: numarul cartii este egal cu:
Pentru forma 1 2 3 4: 1  + codul adus in baza 10
Pentru forma 1 2 4 3: 17+ codul adus in baza 10
Pentru forma 1 3 4 2: 33 + codul adus in baza 10
.
.
.
Pentru forma 4 3 2 1: 369+ codul adus in baza 10

Este mai greu de tinut minte si de calculat dar este posibil!

[•klamathix]

Nu poti lasa spatii intre carti.

[•teo2mirce]

Spatiu de maximum juma de centimetru nu te gandi la cine stie ce.

[•pauldb]

Aaaa, numa' atat?

[•Cosmin]

M-am gandit si eu la cuplaj. Exista si o solutie curata.

[•mips]

Pentru cartile a b c d e extrase daca consideram ca se arata a b c d(le fixam) atunci de o parte avem
124-4=120 posibilitati(valorile ramase pt e) si de cealalta parte 4! = 24. Deci afisand a b c d putem reprezenta doar
1/5 din valorile posibile ale lui e. M-am gandit sa reprezint valori din 5 in 5 pentru ca pentru fiecare a b c d sa corespunda un invariant e%5 .
Ascundem intotdeauna cartea cu indexul (a+b+c+d+e)%5. Aranjam cartile sa reprezinte valoarea cartii ascunse / 5 ( 124/5 <= 4! deci ar trebui sa putem reprezenta toate valorile). Jucatorul 2 va avea 2 informatii cu care va reconstitui secventa: suma S a celor 4 carti ramase modulo 5 si numarul n de ordine al
aranjamentului. Incercand fiecare slot i (0<=i<=4) unde sa introduca cartea ascunsa,
valoarea acesteia ar fi val = ( 5+i-S )%5 + 5*n pentru ca i reprezinta si suma celor 5 carti initiale modulo 5. Dar cartea se poate potrivi doar intr-un slot deoarece:
Daca din a b c d e ascundem c, deci val=c , cu un slot inapoi(i-1), val va fi cu o unitate mai mica sau cu 4 unitati mai mare. Si a<val-1<b sau a<val+4<b  nu pusca. Similar in celalalt sens, sau la distante mai mari de 1 fata de pozitia corecta.

Practic ordinea cartilor afisate da catul impartirii la 5 si pozitia cartii ascunse da restul impartirii la 5.

Exemplu:
Jucatorul 1 primeste cartile 10 15 16 17 20
rest = 3, ascunde 17 pune cartile (10 15 16 20) in ordinea corespunzatoare lui 3

Jucatorul 2 primeste cartile (10 15 16 20) aranjate in ordinea 3
noul rest S = 1
n=3
i=0 => val = 4 + 3*5 = 19 dar 19<10 FALS
i=1 => val = 0 + 3*5 = 15 dar 10<15<15 FALS
i=2 => val = 1 + 3*5 = 16 dar 15<16<16 FALS
i=3 => val = 2 + 3*5 = 17      16<17<20 ADEVARAT!

Daca observati ceva erori in demonstratie va rog sa imi spuneti. N-as stii sa demostrez ca redundanta e zero la solutia mea...
Problema e foarte misto

[•mips]

Am uitat ceva destul de important. Inainte de a ascunde cartea (a+b+c+d+e)%5, a b c d e sunt sortate si abia apoi e aleasa cartea cu indexul respectiv. La fel la jucatorul 2, odata ce a extras informatia data de ordinea aranjamentului, sorteaza a b c d si abia apoi incearca cele 5 sloturi.

[•proflaurian]

@Mircea

As vrea sa imi explici cum functioneaza ideea ta pe cazul in care jucatorul 1 primeste numerele 1 2 3 4 6.

[•teo2mirce]

eu?

[•proflaurian]

Nu tu. Mircea Pavel )

[•mips]

@Adrian
Pentu exemplu dat de tine, algoritmul ar functiona asa:
Jucatorul 1:

1 2 3 4 6

r = 16%5 = 1, deci se ascunde cartea cu index 1, adica 2.
Aranjamentul  cartilor 1 3 4 6 trebuie sa codifice valoarea 2/5 = 0 ( deci jucatorul 2 le primeste in acceasi ordine ).
 
Jucatorul 2:

1 3 4 6

S = 14%5 = 4,
n=0(valoare din ordinea aranjamentului)
Daca i = 0 -> 5*0+(0-4+5)%5=1, dar 1<1 e fals, deci nu poate fi vorba de slotul 0.
Daca i = 1 -> 5*0+(1-4+5)%5=2, 1<2<3 ceea ce e ok, deci valoarea cartii e 2.

Cu toate astea din exemplul tau mi-am dat seama ca pentru carti mai mari de 119 algoritmul meu nu ar merge, pt ca permutarea codifica de la 0 la 23 nu pana la 24 si 23*5+rest<=119. Pentru a putea codifica 124 carti, trebuie transmisa valoarea cartii - pozitia ei, si cum pozitia ei este dedusa de jucatorul 2, cu o mica corectie la cat, se poate reconstitui valoarea.

Mai jos codul algoritmului, poate se intelege mai bine.Accepta carti de la 0 la 123:

Cod:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//#define CHECKALL

#define DEBUGMSG(bla) cout << bla
//#define DEBUGMSG(bla)

int getRest(vector<int> carti)
{
    int rest = 0;
    for (int i=0; i < carti.size(); i++)
    {
        if (carti[i] >= 124)
        {
            cout << "Eroare!";
        }
        rest = (rest + carti[i]) % 5;
    }
    return rest;
}

//codifica aranjament
vector<int> aranjament(vector<int> carti, int nr)
{
    while (nr)
    {
        next_permutation(carti.begin(),carti.end());
        nr--;
    }
    return carti;
}

//decodifica aranjament
int getVal(vector<int> carti)
{
    int nr=0;
    while (next_permutation(carti.begin(),carti.end()))
    {
        nr++;
    }
    return 23 - nr;
}

vector<int> jucatorul1(vector<int> carti)
{
    if (carti.size() != 5)
    {
        cout << "Eroare!";
    }

    sort(carti.begin(),carti.end());

    int rest = getRest(carti);
    int valC = carti[rest];
    carti.erase(carti.begin() + rest);
    return aranjament(carti , (valC - rest) / 5);
}

int jucatorul2(vector<int>carti)
{
    int sumaInitialaMod5 = getVal(carti);
    if (carti.size() != 4)
    {
        cout << "Eroare!";
    }

    int rest = getRest(carti);

    sort(carti.begin() , carti.end());

    for (int i=0; i<5; i++)
    {

        int r = ( i + 5 - rest ) % 5;      // restul cartii ascunse
        int corectieCat = (i>r)?1:0;
        int val = r + (sumaInitialaMod5 + corectieCat)*5;

        if (i==0)
        {
            if ( !(val < carti[i]) ) continue;
        }
        else if (i == 4)
        {
            if  ( !(val > carti[i-1]) )  continue;
        }
        else
        {
            if ( !( (carti[i-1] < val)&&(val < carti[i]) ) ) continue;
        }

        // slotul acesta e ok
        return val;
    }

    // slotul nu a fost gasit
    cout << "e gresit algoritmul!";
    return -1;
}



int main()
{

    int sumaVerificare=0;


#ifdef CHECKALL
    int carti[5];
    for (carti[0]=0; carti[0]<=123; carti[0]++)
        for (carti[1]=carti[0]+1; carti[1]<=123; carti[1]++)
            for (carti[2]=carti[1]+1; carti[2]<=123; carti[2]++)
                for (carti[3]=carti[2]+1; carti[3]<=123; carti[3]++)
                    for (carti[4]=carti[3]+1; carti[4]<=123; carti[4]++)
#else
    int carti[]= {6,4,3,2,1};
#endif
                    {
                        vector<int> vcarti(carti,carti+5);
                        DEBUGMSG("Initial:");
                        for (int i=0; i < vcarti.size(); i++)
                        {
                            sumaVerificare += vcarti[i];
                            DEBUGMSG(vcarti[i]<<" ");
                        }
                        DEBUGMSG(endl);
                        vector<int> arata = jucatorul1(vcarti);
                        DEBUGMSG("Aratate:"<<endl);
                        for (int i=0; i<arata.size(); i++)
                        {
                            DEBUGMSG(arata[i] << " ");
                            sumaVerificare -= arata[i];
                        }
                        DEBUGMSG(endl);
                        int ascunsa = jucatorul2(arata);
                        sumaVerificare -= ascunsa;
                        DEBUGMSG("ascunsa " << ascunsa);
                        DEBUGMSG(endl);

                        if (sumaVerificare != 0)
                        {
                            cout << "e gresit algoritmul!";
                        }
                    }
}

[•proflaurian]

Intradevar dupa ce am recitit cu atentie cele doua postari ale lui Mircea e clar ca protocolul descris de el e corect si pentru a fi inteles am sa imi permit sa il sintetizez descriind in pasi ce face fiecare jucator.
Cheia rezolvarii e urmatoarea: dispunem de 124 carti dintre care 4 vor fi vizibile si 120 invizibile. Jucatorul 1 trebuie sa transmita jucatorului 2 una dintre cele 120 de valori utilizand cele 4 numere vizibile.
De remarcat ca numerele ramase dupa afisarea celor 4 carti pot fi identificate unic cu valori de la 0 la 119 reprezentand pozitia lor in ordine crescatoare dupa ce au fost eliminate cartile vizibile.
Astfel pozitia se identifica unic prin teorema impartirii cu rest cu catul 5. Astfel daca pozitia este P=5C+R atunci C este de la 0 la 23 si R este de la 0 la 4. Acestea sunt cele doua informatii ce trebuie transmise pentru a fi realizata decodificarea. De remarcat ca numarul perechilor ( C , R ) este 24 X 5 = 120 ceea ce dovedeste redundanta 0 a codificarii.

Pasii efectuati de jucatorul 1 pentru codificare:

pas C1 -> se alege cartea care va fi ascunsa asezand cartile disponibile in ordinea a < b < c < d < e (astfel fiecare carte va fi identificata printr-un indice i de la 0 la 4) .
Acest indice va fi ales cu valoarea  

i = ( a + b + c + d + e ) % 5 .

In continuare vom considera
h=cartea ascunsa si  
x<y<z<t celelalte 4 carti care vor fi aratate jucatorului

Mai precis:

a+b+c+d+e=5k    => h=a
a+b+c+d+e=5k+1 => h=b
a+b+c+d+e=5k+2 => h=c
a+b+c+d+e=5k+3 => h=d
a+b+c+d+e=5k+4 => h=e


pas C2 -> Se calculeaza pozitia p de la 0 la 119 ce va fi codificata. Se observa ca
p = h - 1 - i
deoarece pozitia p este de fapt h -1 - cate carti sunt vizibile si strict mai mici decat h ( adica exact i carti)
Mai precis:

p=a-1 daca am ascuns a
p=b-2 daca am ascuns b
p=c-3 daca am ascuns c
p=d-4 daca am ascuns d
p=e-5 daca am ascuns e

pas C3 -> se considera cele 24 de permutari ale numerelor x<y<z<t pe care le ordonam lexicografic si acordam fiecareia un indice C de la 0 la 23.
Mai precis

x y z t C=0
x y t z C=1
....
t z x y C=22
t z y x C=23

Asezam cartile x y z t in ordinea data de C=p/5 si astfel se termina rolul primului jucator.

Ramane semnul de intrebare-> oare cine este R din p=5C+R

R= p % 5 = ( h - i - 1 ) % 5 = (h - a - b - c - d - e - 1 )% 5 = ( - x - y - z - t - 1 ) % 5

Deci deoarece h se reduce R depinde numai de x y z t adica de cartile vizibile !!!

Pasi efectuati de jucatorul 2 pentru decodificare

Pas D1 -> Determina C observand a cata permutare a numerelor vizibile x y z t a fost afisata de primul jucator ( acest numar va fi intre 0 si 23)

Pas D2 -> determina R =( -x - y - z - t - 1 ) % 5

Pas D3 ->  Determina h dupa urmatoarea regula p=5C+R si

h=p+1=a daca (x,y,z,t)=(b,c,d,e) deci daca p+1<x
h=p+2=b daca (x,y,z,t)=(a,c,d,e) deci daca x<p+2<y
h=p+3=c daca (x,y,z,t)=(a,b,d,e) deci daca y<p+3<z
h=p+4=d daca (x,y,z,t)=(a,b,c,e) deci daca z<p+4<y
h=p+5=e daca (x,y,z,t)=(a,b,c,d) deci daca t<p+5

Prescurtat se calculeaza valorile
p+1,p+2,p+3,p+4,p+5
iar h este unica (deci prima) valoare care se incadreaza resprctiv pe intervalul corespunzator adica
[ 1 , x ) ; ( x , y ) ; ( y , z ) ; ( z , t ) ; ( t , 124 ]

[•proflaurian]

Problema cu 52 de carti poate fi rezolvata folosind exact metoda de la 124 de carti.
Utilizam protocolul de la 124 de carti si avem informatia suplimentara
1 <= a <= b <= c <= d <= e <= 52.
Aceasta informatie nu este necesara si eventual se poate face abstractie de ea gandind cele 52 de valori de la 1 la 52 ca valori de la 1 la 124.

Forma generala a problemei ar fi urmatoarea:
Se considera un pachet cu M carti numerotate de la 1 la M.
Sa se stabileasca un protocol intre doi jucatori care sa permita primului sa aleaga N carti, sa aseze  in linie N-1 dintre ele astfel incat al doilea se poata indica a N-a carte pe care nu o vede.
Restrictie N+1 <= M <= N! + N - 1

De exemplu daca N = 5 vom obtine M maxim = 5! + 5 - 1 = 120 + 5 - 1 = 124.

Si pentru ca tot se vorbeste de plagiat peste tot in ultima vreme mentionez ca generalizarea nu imi apartine deci considerati tot ce am scris mai sus cu ghilimele cu sursa de informare google search    

[•Cosmin]

Misto Mircea.