IMO 2019 zadatak 5


Kvaliteta:
  Avg: 5,0
Težina:
  Avg: 8,0
Dodao/la: arhiva
3. listopada 2019.
LaTeX PDF

Banka Batha izdaje kovanice kojima se na jednoj strani nalazi H, a na drugoj T. Borna ima n takvih kovanica poredanih u niz slijeva nadesno te započinje proces sljedećih poteza: ako točno k > 0 kovanica pokazuje H, k-tu kovanicu slijeva okreće na drugu stranu; u suprotnom sve kovanice pokazuju T i proces staje. Na primjer, ako je n = 3, proces koji započinje konfiguracijom THT je THT \rightarrow HHT \rightarrow HTT \rightarrow TTT te on staje nakon 3 poteza.

(a) Dokaži da, za svaku početnu konfiguraciju, proces staje nakon konačno mnogo poteza.

(b) Za svaku početnu konfiguraciju C, neka je L(C) broj poteza potrebnih da proces stane. Na primjer, za n = 3 je L(THT) = 3 i L(TTT) = 0. Odredi aritmetičku sredinu brojeva L(C) po svih 2^n mogućnosti početne konfiguracije C.

Izvor: Međunarodna matematička olimpijada 2019, problem 5