[PS285a] Numărătoare

Autor: www.faculty.missouristate.edu
Concurs: Problema saptamanii (#39/2007)
URL: http://egovbus.net/rdl/potw/potw12.doc

***

Motto: Proverbele sunt bune să-ţi alini durerea cu ele. (W. Shakespeare)

Săptămâna 285:
A. (Numărătoare):

Mai mulţi copii (numerotaţi de la 1 la n) s-au strâns în cerc.

Începând cu numărul 1 şi parcurgând cercul în sensul acelor de ceasornic, ei încep să numere în felul următor: 1, 2, 3, 1, 2, 3, 1, 2, 3, ...

Copiii care spun numărul “2” sau “3” părăsesc imediat cercul.

Când cercul este parcurs complet, numărătoarea continuă în acelaşi mod cu cei care au rămas.

Copilul care rămâne ultimul câştigă (fără a fi nevoit să spună vreun număr).

De exemplu, dacă sunt 14 copii, la prima rundă avem următoarea situaţie:

Copil:	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Numărătoare:	1	2	3	1	2	3	1	2	3	1	2	3	1	2

Deci după ce s-a parcurs complet cercul, în el au rămas numai copiii 1, 4, 7, 10 şi 13. Deoarece copilul cu numărul 14 a spus cifra “2”, la începutul rundei a doua copilul cu numărul 1 va spune “3” şi va fi eliminat.

A doua rundă se va desfăşura astfel:

Copil:	1	4	7	10	13
Numărătoare:	3	1	2	3	1

Deci în runda a treia vor trece numai copiii 4 şi 13. Deoarece 13 – ultimul copil din runda a doua - a spus numărul “1”, în runda a treia copilul 4 va trebui sa spună “2” şi va fi eliminat, rămânând câştigător copilul cu numărul de ordine 13.

Cine va câştiga concursul, dacă la el participă 2007 copii (n=2007) ?

Sursa: Challenge Problem Archive, www.faculty.missouristate.edu