Un om doreste sa-si dea seama care din cei 2014 servitori sunt loiali. El stie cu certitudine ca servitorii credinciosi vor spune intotdeauna adevarul, in timp ce tradatorii vor minti. Slujitorii sunt asezati la o masa circulara si fiecare dintre ei sustine ca primii cincizeci de oameni la dreapta lui sunt tradatori. Care este numarul minim de servitori credinciosi?

[Citat] Un om doreste sa-si dea seama care din cei 2014 servitori sunt loiali. El stie cu certitudine ca servitorii credinciosi vor spune intotdeauna adevarul, in timp ce tradatorii vor minti. Slujitorii sunt asezati la o masa circulara si fiecare dintre ei sustine ca primii cincizeci de oameni la dreapta lui sunt tradatori. Care este numarul minim de servitori credinciosi?

Sa incercam sa rezolvam o problema invecinata.


Un om doreste sa-si dea seama care din cei

N = 20

servitori sunt loiali.
El stie cu certitudine ca servitorii credinciosi vor spune intotdeauna adevarul, in timp ce tradatorii vor minti intotdeauna.
Slujitorii sunt asezati la o masa circulara si fiecare dintre ei sustine ca primii

K = 3

oameni la dreapta lui sunt tradatori.
Care este numarul minim de servitori credinciosi?

Eu as incerca mai intâi asa, sa vedem daca am inteles bine enuntul:
Numaram servitorii cu 0,1,2,...,(N-1).
Scriem pe un servitor credincios (pe piept) un 1, altfel un 0.
Ii punem la masa si obtinem un sir

s

de 0-uri si 1-uri, indexat dupa 0,1,2,...,(N-1).
Se poate cumva sa fie toti servitorii tradatori?
Nu, constelatia 0,0,0,0,0 ... nu respecta conditiile enuntului.
Primul 0 de pe pozitia 0 sugereaza faptul ca propozitia este falsa:
"Cei trei oameni de pe pozitiile 1,2,3 sunt mincinosi."
Dar pe aceste pozitii avem 0,0,0, trei mincinosi, deci servitorul 0 spune adevarul, contradictie cu plasarea unui 1 pe pozitia 0. Adica s(0)=1.

Deducem ca intr-o constelatie viabila avem cel putin un 1.
Simetria circulara ne permite sa il plasam pe pozitia 0.
Incepem cu

1, s(1), s(2), s(3), s(4), s(5), ...

si faptul ca servitorul 1 spune adevarul ne ajuta sa scriem:

1, 0, 0, 0, s(4), s(5), ...

si acum ne legam de servitorul 1. Cel cu s(1)=0, un mincinos.
El minte când afirma ca toti cei trei servitori de pe pozitiile 2,3,4 sunt mincinosi. Singura sansa este sa avem s(4) = 1.
Continuând in acest mod dam de configuratia "viabila" in conditiile enuntului, asta daca l-am inteles eu bine:

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 .

Aceasta este o solutie, un mod de a realiza valorile de credinta ale supusilor, orice alta solutie se obtine din aceasta prin permutare ciclica.
Acel numar "minim" este o intorsatura de condei acum, pusa doar sa il incurce pe cel ce cauta solutia...

Sa vedem ce putem face cu alte valori ale lui N si K:

TEMA:
(1) Ce constelatii posibile avem pentru N=19, K=3 ?
(2) Ce constelatii posibile avem pentru N=21, K=3 ?
(3) Ce constelatii posibile avem pentru N=1989, K=50 ?
(4) Ce constelatii posibile avem pentru N=2014, K=52 ?
(5) Ce constelatii posibile avem pentru N=2014, K=50 ?

Am inteles. Multumesc pentru explicatie si mai ales pentru tema, m-a ajutat sa inteleg mai bine si sa retin metoda. Am obtinut si raspunsul pentru problema initiala, 106 daca nu ma insel.

Dar, catul impartirii numarului 2014 la 51 este 39, deci ar trebui ca numarul minim sa fie 39; 106 era rezultatul care este scris intr-o carte cu intrebari grila. Cum acest caz cu 39 verifica conditiile problemei, si 39<106 , nu vad de ce raspunsul ar fi 106. Si mai mult decat atat, si eu consider ca raspunsul este 39, mai putin nu putem avea, dupa cum bine ati explicat. Pentru a fi 106, cu siguranta trebuie adaugata o conditie, care din pacate lipseste. Asa ma gandisem si eu initial, dar am crezut ca nu inteleg eu bine problema si de aceea am cerut ajutor. Va multumesc oricum pentru ajutor!

Abia acum am citit atent cele de mai sus, trebuie sa intervin.
Verdictul matematic trebuie sa fie sigur si precis, chiar daca problema se clatina rau in enunt si raspuns.

[Citat] TEMA: (1) Ce constelatii posibile avem pentru N=19, K=3 ?

Plecam ca si mai sus cu 1, ?, ?, ?, ...
O sa scriu pur si simplu 1???... sau 1... mai departe si similar in situatii similare.
Rezulta ca avem chiar 1000?...
Semnul de intrebare trebuie sa fie 1, deoarece "primul 0 minte".
Dam de 1000 1???...
Apoi de 1000 1000 ?...
Si destul de repede completam toate cele 19 valori pâna la
1000 1000 1000 1000 100...
si scriind ciclic mai departe urmatorul zero il scriem peste primul unu!
Contradictie.
Inseamna ca nu exista nici o constelatie care realizeaza enuntul pentru N = 19 si K = 3. Avem probleme, deoarece N nu se divide cu (K+1).

[Citat] (2) Ce constelatii posibile avem pentru N=21, K=3 ?

La fel, plecam cu 1... si ajungem repede la
1000 1000 1000 1000 1000 1
dupa care completând mai departe ciclic cu 000 (grup cerut de ultimul 1) scriem un 0 peste primul unu. Contradictie.
Avem din nou probleme, deoarece N nu se divide cu (K+1).

[Citat] (3) Ce constelatii posibile avem pentru N=1989, K=50 ?

Aici avem divizibilitatea lui 1989 prin 51. Câtul este 39.
Avem in solutia (unica daca avem voie sa rotim masa cu servitorii) cu 39 de grupuri 1000...000 de lungime 51. Raspunsul este 39 si exercitiul se distinge prin enervare in momentul in care cere "minimul" (multimii {39}, enuntul sugereaza psihologic o complexitate, unii nici macar nu se chinuie sa citeasca pâna la capat, din cei ce citesc multi nu inteleg, din cei ce inteleg multi nu isi pot imagina cum arata doua constelatii, din cei ce deduc ca este doar o constelatie - in esenta - dupa predarea lucrarii majoritatea au inca un sentiment mixt despre unde ar fi greseala - de intelegere sau de rezolvare. Toate aceste lucruri contribuie la succesul invatamântului matematic pentru formarea unui numar cât se poate de mare de medici, juristi si bisnitari, care din pacate nu se pot afirma cum trebuie, deoarece ignora consecvent gândirea (sintetica) dupa astfel de experiente nefaste.)

[Citat] (4) Ce constelatii posibile avem pentru N=2014, K=52 ?

Avem... deoarece 2014 / (52+1) = 38 .

[Citat] (5) Ce constelatii posibile avem pentru N=2014, K=50 ?

Nici una...
Probabil ca "autorul problemei" a incercat sa adapteze ceva, dupa ce a citit undeva, intr-o culegere din 1989... Adaptarea nu a functionat prea bine, de aceea a introdus acel minim... Sigur a gasit un argument genial pentru a demonstra ca "pentru orice constelatie x posibila numarul de credinciosi din x este mai mare sau egal cu 106". Numai noi nu apreciem astfel de rezultate importante legate de multimea vida.