RSS Feed
Următoarea

Problema 334

23 Aprilie 2011

Vărsarea boabelor


Fie un șir infinit de castroane aranjate în linie dreaptă.
Fiecare castron conține fie 0, fie un număr finit de boabe.
Un copil se joacă un joc care permite un singur fel de mutare: îndepărtarea a 2 boabe din orice castron și punerea lor în cele 2 castroane adiacente.
Jocul se termină când fiecare castron conține fie un bob, fie nici un bob.

De exemplu, consideră 2 castroane cu 2, respectiv 3 boabe, toate celelalte castroane fiind goale. Următoarele 8 mutări ar sfârși jocul:

Este dat următorul șir:

t0 = 123456.
ti =
ti-1
2
, dacă ti-1 e par
ti-1
2
926252, dacă ti-1 e impar
unde ⌊x⌋ e funcția de rotunjire în jos
și e operatorul XOR aplicat bit-cu-bit.
bi = ( ti mod 211) + 1.

Primii 2 termeni ai ultimului șir sunt b1 = 289 și b2 = 145.
Dacă începem cu b1 și b2 boabe în 2 castroane adiacente, ar fi nevoie de 3419100 de mutări pentru a termina jocul.

Consideră 1500 de castroane adiacente care conțin b1, b2,..., b1500 boabe, toate celelalte castroane fiind goale. Află de câte mutări ar fi nevoie pentru a termina jocul.


>> Vezi problema originală <<