Solution of task "1. lakša simulacija državnog natjecanja 2020. zadatak 3" by user "loki6"

Neocijenjeno

April 12, 2025, 7:53 p.m. (1 year, 4 months)

User: loki6
Task: 1. lakša simulacija državnog natjecanja 2020. zadatak 3 (Hide problem text)

Na ploči je napisano 2020 prirodnih brojeva. Svaku minutu, na ploču dopišemo novi red brojeva na sljedeći način. Ispod svakog broja $a$ u prethodnom redu napišemo broj $f(a)$ gdje $f(a)$ predstavlja broj pojavljivanja broja $a$ u prethodnom redu. Dokažite da ćemo u nekom trenutku, jedan za drugim, napisati isti red brojeva.

Warning: You haven't solved this problem yet.
Click here to display the solution.

Nadalje, neka je $k$ ukupan broj različitih brojeva koji se pojavljuju jednak broj puta (tj. za niz $123455$ je $k=4$ , a za $12345566$ imamo $k=6$ ). Primijetimo da, ako je u nekom trenutku $k>0$ , imamo neki niz međusobno različitih brojeva, recimo $a_1,a_2,...,a_i, 2\le i\le k$ koji se pojavljuju jednak broj puta, dakle $f(a_1)=f(a_2)=\cdots=f(a_i)$ , ako označimo s $S_a=f(a_1)+\cdots+f(a_i)$ , u idućim redcima slijedit će brojevi $f(a_1)...f(a_2)...f(a_i)\dots$ $\implies S_a...S_a...S_a\dots$ a broj $S_a$ pojavljivat će se $S_a$ puta. Tada se $k$ smanjio za barem $i\ge2.$ (Možemo zamisliti da su brojevi $a_1,a_2,...,a_i$ zamijenjeni s $S_a, S_a,...S_a$ .) Dakle, $k$ će se uvijek smanjivati, a kako $k<2021$ , slijedi da će u nekom trenutku svi brojevi biti različiti (jer se različiti brojevi u prethodnom retku pojavljuju različit broj puta), a pokazali smo da će se u tom trenutku brojevi ponoviti.

P.S. Ne znam je li ovo bilo malo nespretno objašnjeno, cijela je ideja bila gledati broj pojavljivanja različitih brojeva, tako da je moguće da su neki djelovi mogli biti malo jasniji.

Primijetimo da redoslijed brojeva nije bitan. Broj ispod samo ovisi o broju iznad njega, ne o redoslijedu, tako da su nizovi npr. $11222$ i $22211$ suštinski isti, lakše vidimo ako brojeve rasporedimo u stupce, raspored brojeva u stupcima ovisi isključivo o broju pojavljivanja, ne o redoslijedu. Primijetimo da to znači da brojeve uvijek možemo rasporediti na taj način i da to neće utjecati na naš rezultat. Dakle, bez smanjenja općenitosti možemo pretpostaviti da su svi jednaki brojevi "u skupinama" (tj. niz brojeva može izgledati ovako: $aa...abb...b...zz...z$, ovo je samo zbog jednostavnosti; u rješenju čak mislim da nije ni potrebno, ali bar je meni bilo lakše pratiti).\\ Sada, promotrimo niz gdje su svi brojevi disjunktni. Neka redak prije toga sadrži brojeve $aa\dots abb\dots b\dots zz\dots z$. Tada je redak koji promatramo jednak $f(a)f(a)...f(a)f(b)...f(b)...f(z)...f(z)$. Kako smo pretpostavili da su svi brojevi disjunktni, slijedi da se broj $f(a)$ pojavljuje jednak broj puta kao i broj $a$ u prethodnom retku, dakle promatrani niz bit će identičan onom prethodnom; $f(a)f(a)...f(a)f(b)...f(b)...f(z)...f(z)$.\\ Nadalje, neka je $k$ ukupan broj različitih brojeva koji se pojavljuju jednak broj puta (tj. za niz $123455$ je $k=4$, a za $12345566$ imamo $k=6$). Primijetimo da, ako je u nekom trenutku $k>0$, imamo neki niz međusobno različitih brojeva, recimo $a_1,a_2,...,a_i, 2\le i\le k$ koji se pojavljuju jednak broj puta, dakle $f(a_1)=f(a_2)=\cdots=f(a_i)$, ako označimo s $S_a=f(a_1)+\cdots+f(a_i)$, u idućim redcima slijedit će brojevi $$f(a_1)...f(a_2)...f(a_i)\dots$$ $$\implies S_a...S_a...S_a\dots$$ a broj $S_a$ pojavljivat će se $S_a$ puta. Tada se $k$ smanjio za barem $i\ge2.$ (Možemo zamisliti da su brojevi $a_1,a_2,...,a_i$ zamijenjeni s $S_a, S_a,...S_a$.) Dakle, $k$ će se uvijek smanjivati, a kako $k<2021$, slijedi da će u nekom trenutku svi brojevi biti različiti (jer se različiti brojevi u prethodnom retku pojavljuju različit broj puta), a pokazali smo da će se u tom trenutku brojevi ponoviti. P.S. Ne znam je li ovo bilo malo nespretno objašnjeno, cijela je ideja bila gledati broj pojavljivanja različitih brojeva, tako da je moguće da su neki djelovi mogli biti malo jasniji.

Školjka