Ultima persoană rămasă în cerc...

Question

Dacă dispunem k persoane în cerc, le numerotăm de la 1 la k în sensul acelor de ceasornic, și apoi parcurgem cercul astfel format în același sens, al acelor de ceasornic, eliminând fiecare a doua persoană (începând cu cea numerotată cu 2), a câta persoană este ultima rămasă ”în picioare” ?

Putem găsi o formulă ori o metodă de calcul a numărului asociat acestei ultimei persoane rămase în cerc, în funcție de k ?

Putem generaliza pentru un ”pas” diferit de 2 ?

Comments

k par, k=2n
2,4,6,8,10,12,14,16,18,20,..., 2n
3,7,11,15,19,...,2n-1
1,5,9,13,17,..,2n-3

/

k impar, k=2n+1
2,4,6,8,10,12,14,16,18,20,...,2n
1,3,5,7,9,11,13,15,17,19,...,2n+1,

/

Nu m-am gândit încă la o formulă pentru un pas diferit de 2.

---

Deci care este formula, fct. de k, pentru "the last man standing", atunci cand pasul este 2? Banuiesc ca a fost clar ca se elimina fiecare al doilea om dintre cei ramasi...

---

Pentru k par, a (k-3) -a persoană va fi ultima eliminată, iar dacă k este impar, a k-a persoană va fi ultima eliminată.

Mă gândesc că pentru generalizarea eliminării din m în m, m diferit de 2 am putea considera k=mn+q și să eliminăm în felul următor :

m, 2m, 3m, 4m, ..., mn

m-q, 2m-q, 3m-q,....

Dar nu am prea mult timp acum s-o analizez mai în detaliu.

---

Mie imi iese, de pilda, ca atunci cand k=13 ultimul ramas e numarul 11, iar ptr. k=10 ultimul ramas e 5...

---

Bănuiesc că te referi la pasul din 2 în 2.
Păi hai să vedem pentru k=13.
2,4,6,8,10,12,1,5,9,13, 7, 11, 3
Deci ultimul care rămâne este al 3-lea.
În acest caz, când k este impar, ultimul care rămâne de eliminat este al treilea.

Să vedem pentru k=10.
2,4,6,8,10,3,7,1,5,9.

Deci ultimul care rămâne de eliminat este penultimul.
Edit:

Am greșit mai sus.
Am ceva timp acum să mă ocup de cazul general m și să le analizez mai detaliat
Mai sus am greșit ceva în succesiunea eliminărilor.

---

Da...frumoasă problema.

Este ciudat că la prima vedere mi se par așa simple unele probleme.

Cred că din graba de a răspunde, o să încerc să fiu mai atent la asta.

Dar trebuie să recunosc că problema e frumoasă.

Pentru eliminarea din 2 în 2, rezultatul pare să fie de forma  pentru k par.

---

Si ce este m de la exponent?

Pentru pasul de doi mie mi se pare ca avem doua cazuri.

k multiplu de 4: ultimul ramas e primul (numarul 1)

k nu e multiplu de 4: ultimul ramas e penultimul.

---

Pentru k par, k=2n, răspunsul este un pic mai complicat și încadrat într-o relație.

Fie k=2n astfel încât 2^m   k <  2^m+1 .

Ultima persoană care va fi eliminată va fi cea cu numărul 2•(k-2^m)+1

N-am calculat încă pentru k impar.

Answer 1

Răspunsul trebuie încadrat într-o relație pentru a generaliza formula.

Fie k astfel încât 2^m   k < 2^m+1 .

Ultima persoană care va ramâne ”în picioare” va fi cea cu numărul 2•(k-2^m)+1.

Comments

Ce pot sa spun e ca mai vreau de la dvs. 2 lucruri: o demonstratie riguroasa, dar si o formula a lui m in functie de k, adica o formula a ultimului ramas in picioare scrisa exclusiv in functie de k (asta e partea usoara, as zice)...

---

Dacă vom considera q fiind ultima persoană rămasă în picioare dintre toate cele k persoane prin eliminarea din 2 în 2 începând de la al doilea, atunci cam așa ar trebui să apară un tabel:

Nu găsesc totuși o funcție f(k)=q, cu q exprimat doar în funcție de k.

Cât despre demonstrație, am analizat-o un pic aseară și cred că s-ar putea demonstra prin inducție, arătând că dacă pentru k the last man standing este q, atunci pentru k+1 the last man standing este q+2.

Dar pare să nu fie prea evident.

Poate au ceilalți o demonstrație frumoasă așa că o să rămân spectator în acest subiect, cel puțin pentru moment, până nu apare o demonstrație mai simplă decât cea pe care cred că o am eu acum.

---

Pe partea de demonstratie inca nu ma bag nici eu. In schimb, un sfat de la mine cu privire la scrierea lui m in functie de k. m este un exponent al puterilor lui 2. Iar inversa functiei exponentiale este... :-)

---

Într-adevăr, cred că se poate demonstra riguros pentru pasul de 2 în modul pe care l-am menționat anterior.

Principiul este următorul.

Prima dată eliminăm numerele pare mai mici/egale cu k.

Celelalte care rămân sunt numerele impare mai mici/egale cu k.

Numerotând consecutiv aceste numere impare 1, 2, 3, 4, ...,q+1 :

2•0+1,  2•1+1, 2•2+1,  2•3+1, ...,2•q+1,

,

după eliminarea din 2 în 2 a acestor q+1 numere impare rămase, rezultatul pentru ''the last man standing'', va fi ''identic'' cu cel pentru k' persoane, k' = q+1, cu completarea corespunzătoare.

Vis-a-vis de sfatul tău, chiar dacă folosesc logaritmul tot trebuie să știu cât de mare este m, nu-i așa ?

Oricum, poate culege și folosește cineva toate informațiile care s-au scris și le pune pe toate într-un răspuns frumos și complet.

---

Legat de logaritm, nu cautam decat o formula a lui m in functie de k, formula care rezulta din inegalitatea respectiva. Nu e cu logaritm "curat", se mai aplica o operatie pe log₂k :-)

Legat de demonstratie, trebuie sa ajung acasa, la hartie si creion, si sa analizez :-)

Answer 2

Dacă tot nu încearcă nimeni, îndrăznesc eu.

O demonstrație riguroasă a problemei ar arăta cam așa.

Separăm k în valori pare și valori impare și să stabilim o notație care ușurează scrierea matematică a demonstrației.

Să notăm ultima persoană rămasă în picioare prin eliminarea acestora din 2 în 2 cu R(k).

Analizăm pentru început cazul în care k este par, k=2q :

1, 2, 3, 4, 5, 6, ..., 2q

Evident, primele persoane ce vor trebui eliminate sunt persoanele corespondente numerelor pare. Persoanele care rămân sunt cele corespondente numerelor impare :

1, 3, 5, 7, 9, ..., (2q-1)

Dacă ultima persoană eliminată este cea cu numărul 2q, următoarea persoană eliminată va fi cea cu numărul 3 și să scriem un al doilea șir de q numere consecutive dedesubt:

1, 3, 5, 7, 9, ..., (2q-1)

1, 2, 3, 4, 5, ..., q

Putem stabili că poziția numărului corespondent ultimei persoane rămase în picioare din primul șir va fi identic cu poziția ultimei persoane rămase în picioare prin eliminarea în aceeași manieră din 2 în 2 în al doilea șir, pentru că în ambele șiruri eliminarea se începe cu al doilea termen al șirului.

De aici, relația de corespondență între un număr u din primul șir și cel de dedesubt, v,  este     , iar folosind notația menționată anterior, 

putem stabili că    ,

deci R(2q) = 2•R(q)-1 .

/

În continuare, cazul în care k este impar, k=2q+1 .

Și în acest caz, primele persoane care vor fi eliminate vor fi acelea corespondente numerelor pare, iar cele care rămân vor fi cele impare :

1, 3, 5, 7, 9, ..., (2q+1)

cu diferența că în acest caz următoarea persoană ce va trebui eliminată va fi prima.

Ca și în cazul anterior, rescriem acele două șiruri :

1, 3, 5, 7, 9, ..., (2q+1)

1, 2, 3, 4, 5, ..., (q+1)

În această situație însă, poziția ultimei persoane în primul șir nu va mai corespunde cu poziția ultimei persoane rămase în picioare în al doilea șir, prin eliminarea în aceeași manieră, deoarece în primul șir eliminarea începe de la 1, iar în al doilea șir eliminarea începe de la 2.

Pentru a sincroniza poziția, rescriem șirurile în felul următor :

1, 3, 5, 7, 9, ..., (2q+1)

....1, 2, 3, 4, ......., q

Chiar dacă șirurile nu mai corespund la prima poziție, nu mai este nevoie să luăm în calcul prima poziție pentru că în primul șir 1 va fi primul număr eliminat, iar în al doilea șir eliminarea începe în mod normal, de la 2, și putem spune că poziția ultimei persoane rămase în primul șir va corespunde cu poziția ultimei persoane rămase în al doilea șir.

În felul acesta, folosind notațiile respective, 

stabilim că    , 

deci R(2q+1) = 2•R(q)+1 .

Aceasta înseamnă că 

R(2q+1) - R(2q) = 2 = (2•R(q)+1) - (2•R(q)-1).

Să analizăm situația pentru k par , k = 2ⁿ :

R(2ⁿ) = 2•R(2^n-1)-1.

Pentru k=4, rezultă că R(2²) = 2•R(2¹)-1 = 1 și continuând în aceeași manieră consecutivă,  stabilim că dacă k este o putere de 2, ultima persoană  care va rămâne în picioare va fi întotdeauna cea cu numărul 1.

Să analizăm situația când k este impar, k = 2ⁿ - 1.

Pentru k = 2² - 1 = 3, ultima persoană rămasă în picioare este a treia persoană, ceea ce înseamnă că pentru k = 2³​ - 1, ultima persoană va fi 2•3 + 1 și tot așa, stabilim că pentru k = 2ⁿ - 1 , ultima persoană rămasă în picioare va fi cea cu numărul 2ⁿ - 1, adică ultima.

În concluzie, ultimele persoane rămase în picioare prin eliminarea din 2 în 2 începând cu a doua, vor fi în ordine consecutivă pentru valori consecutive ale lui k cuprinse între 2^n-1 inclusiv și 2ⁿ - 1 inclusiv :

1, 3, 5, 7, 9, ..., 2ⁿ - 1.

Comments

Admirabil efort. De neînțeles, deocamdată, de către mine.
Am văzut de-a lungul comentariilor și din tabel că ați stabilit: "pentru k = 2ⁿ rămîne în picioare întotdeauna numărul 1", adică numărul de la care se pleacă. Dacă nu este de forma respectivă, atunci k = 2ⁿ + p. Se începe procesul de eliminare de la indexul 1 (prima persoană) și ne oprim atunci cînd au fost eliminate p persoane. Pentru că am eliminat din doi în doi indexul este 2p și au rămas 2ⁿ persoane. Procesul de eliminare continuă dar în acest caz avem situația în care numărul de participanți este o putere a lui 2 și rezultatul l-ați oferit ca find numărul de la care se pleacă, adică 2p +1 = 2(k - 2ⁿ) +1. Partea întreagă a logaritmului îi aparține lui goguv. 

Dar de ce vă jucați de-a v-ați ascunselea, că mi-am văzut numele pomenit și nu am apucat să aflu de ce?

---

Dacă nu este de forma respectivă, atunci k = 2ⁿ + p. Se începe procesul de eliminare de la indexul 1 (prima persoană) și ne oprim atunci cînd au fost eliminate p persoane.

Nu, pentru orice valoare a lui k, eliminarea nu se începe de la prima, ci întotdeauna de la a doua. Este menționat în enunțul problemei.

În cazul pe care l-ați menționat dvs, k = 2ⁿ + p , ultima persoană va fi cea numerotată cu 2ⁿ + p și ne oprim după ce au fost eliminate 2ⁿ + p -1, persoane.

Prin eliminarea din doi în doi începând cu a doua persoană, prima dată vor fi eliminate persoanele pare.

Dacă acum rescrieți în continuarea celor 2ⁿ + p persoane, persoanele impare, șirul ar arăta cam așa pentru p par

1, 2, 3, 4, 5, 6, 7, 8, 9 ...2ⁿ+p, 1, 3, 5, 7, 9, 11, ...2ⁿ​+p-1

unde cifrele cu roșu sunt persoanele care vor fi eliminate prima dată, în ordine consecutivă.

Dar dacă rescriem partea a doua, cea cu numerele impare sub forma 

1, 3, 5, 7, 9,11, ...2ⁿ​+p-1

1, 2, 3, 4, 5, 6, ..., q

înseamnă că poziția ultimei persoane ce va fi eliminată în primul șir cu numerele impare, corespondentă pentru cele  2ⁿ​+p persoane, va fi identică cu poziția ultimei persoane ce va fi eliminată din șirul de dedesubt, unde sunt numai q persoane.

Maniera de eliminare fiind identică în ambele șiruri, din 2 în 2 începând cu a doua, pozițiile ultimelor persoane ce vor trebui eliminate vor corespunde în cele două șiruri.

Deci trebuie să găsim o relație între un număr de sus și numărul corespondent de dedesubt, pe care am scris-o mai sus.

Dacă ați înțeles asta pentru cazul par, principiul este asemănător pentru cazul impar, cu câteva precizări suplimentare.

La v-ați ascunselea, uff...mă simt un pic frustrat, am încercat să fac un test, să văd cum se postează întrebările, după care am observat că e ca și cum aș fi întrebat cât face 1+3 +5 +7=..., spre diferență de întrebările voastre foarte frumoase și suficient de dificile pentru a stârni interes.

---

Sau probabil că vă duce în eroare numerele respective.

Puteți să interpretați rezultatul și în felul următor.

Considerați două șiruri de numere :

a₁ , a₂ , a₃ , a₄ , a₅ , a₆ , ... , a_n

b₁ , b₂ , b₃ , b₄ , b₅ , b₆ , ... , b_n

Dacă în ambele șiruri se face o eliminare din 2 în 2 a numerelor din ambele șiruri, începând cu al doilea termen din fiecare șir, dacă în primul șir ultimul număr care rămâne prin această eliminare este a_i, atunci în al doilea șir, ultimul număr care rămâne prin această eliminare va fi b_i . 

Dacă există o relație de recurență între a_i și b_i , putem exprima unul dintre ele în funcție de celălalt.

Dacă în primul șir vor fi numerele impare consecutive de la 1 la 2q-1, 

iar în al doilea șir vor fi toate numerele de la 1 la q, 

atunci relația de recurență între termenii celor două șiruri va fi a_i = 2•b_i-1.

Este exact ceea ce am făcut în cazul în care k este par, k=2q.

În celălalt caz, când k este impar și l-am considerat imediat următorul, k=2q+1, dacă rescriem șirurile de mai sus în modul 

a₁ , a₂ , a₃ , a₄ , a₅ , a₆ , ... , a_n

......b₁ , b₂ , b₃ , b₄ , b₅ , ... ,  b_n-1

prin aceeași eliminare din 2 în 2 începând cu al doilea, dacă în primul șir ultimul termen care rămâne este a_i, atunci în al doilea șir, ultimul număr care rămâne prin același tip de eliminare va fi b_i-1.

În mod asemănător, dacă în primul șir vor fi numerele impare consecutive de la 1 la 2q+1, iar în al doilea șir vor fi toate numerele de la 1 la q, atunci relația de recurență între termenii celor două șiruri va fi a_i = 2•b_i+1.

Cam asta am făcut mai sus.

Cât despre logaritm, cu toate indicațiile lui goguv, nu reușesc să exprim exact care va fi ultima persoană rămasă în picioare, doar în funcție de numărul lor total k.

---

Deocamdată revin la comentariul meu. Prin index eu înțeleg poziția unei persoane din cercul uman. Procesul de eliminare începe de la index 1 - prin această afirmație înțeleg că încep să iau la rînd persoanele începînd cu prima, să trec prin fața fiecăreia și să decid care va fi executată  - dar nu înseamnă că elimin prima persoană.  Exemplific cu un scurt exemplu : k = 5 = 2² + 1 ( n = 2 și p = 1). Trec prin fața persoanei nr.1, indexul  = 1, nu o execut, trec prin fața persoanei nr.2, indexul  = 2  = 2p, o elimin. Am rămas cu 4 persoane = putere a lui 2. Pot considera că am problema inițială, dar numărul de persoane este o putere a lui 2  - și în acest caz știm soluția. În "noul cerc", distribuția persoanelor este 3, 4, 5, 1 => persoana supraviețuitoare va prima persoană de pe noul cerc, adică nr. 3. Iar persoana nr. 3 are indexul 2p + 1 => 2(k - 2ⁿ) +1.  Dar

)
Nici nu contează dacă numărul inițial de persoane este par, impar sau de o natură incertă.
Nu este nici o regulă privind gradul de dificultate al unei întrebări.

---

@Gheorghita:
Va multumesc mult pentru explicatiile oferite lui CiprianM, pe care altfel ar fi trebuit sa le formulez eu. E o rezolvare foarte eleganta, cea sugerata de dvs.

De ce nu ati scris un raspuns, ci doar un comentariu?

---

@Gheorghița

Da, acum am înțeles la ce v-ați referit.

Aveți dreptate, iar soluția dvs este mult mai simplă.

---

Acum, ca lucrurile s-au cam lamurit, pot  spune si eu ca problema asta e una celebra, si poarta numele de problema lui Josephus. Gasiti pagina pe Wikipedia. Ar mai fi interesat de dezbatut cazul cand pasul e mai mare decat 2 si, de asemeni, mai e frumos de gasit un raspuns in baza 2 la problema pentru cazul cand pasul este 2. Acea formula la care ati ajuns se traduce foarte elegant intr-o operatie pe reprezentarea binara a numarului de persoane aflate initial in cerc.

---

Revin eu cu regula in binar de aflare a solutiei: cel mai din stanga 1 din scrierea binara a lui k trebuie mutat la dreapta, in capat, si astfel se ajunge la rezultat (ideea fiind deci ca se cauta cea mai mare putere a lui 2 mai mica decat k, se scade din k, se dubleaza rezultatul si se mai adauga un 1).

Pentru o rezolvare cap-coada, scrisa mai pe indelete, pe ideea doamnei Gheorghita, iata un link:

http://www.exploringbinary.com/powers-of-two-in-the-josephus-problem/