Sakrij rješenje
Zadatak: 1. lakša simulacija državnog natjecanja 2020. zadatak 3 (Sakrij tekst zadatka)
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 u prethodnom redu napišemo broj gdje predstavlja broj pojavljivanja broja u prethodnom redu. Dokažite da ćemo u nekom trenutku, jedan za drugim, napisati isti red brojeva.
Kliknite ovdje kako biste prikazali rješenje.
Pokušajmo prvo 'igrati igru' na malim primjerima. Recimo da imamo sedam brojeva i krećemo s brojevima .
Uočimo nekoliko stvari. Prije svega, svaki od brojeva od 2. retka nadalje je manji od . Naime, to je sasvim jednostavno dokazat, naime, svaki od tih brojeva predstavlja broj pojavljivanja u prethodnom retku, a kako je ukupan broj brojevs 7, ne može biti više od 7 pojavljivanja.
Druga stvar koju treba uočiti jest da od drugog retka nadalje, brojevi unutar svojih 'stupaca' rastu ili ostaju isti. Naime, s obzirom da broj predstavlja broj pojavljivanja nekog broja u prethodnom retku, znamo da će se ispod svakog pojavljivanja broja naći isti takav broj. Kako je tih pojavljivanja točno onoliko koliki je broj, on se sigurno neće smanjiti.
Sada se možemo vratiti na postavku s brojeva. Uočimo da se od drugog retka nadalje, u svakom retku nalaze brojevi koji su nužno manji od 2021, a u svakom koraku se povećaju ili ostanu isti. Kako ne mogu neograničeno rast (jer manji su od 2021), nužno je da u nekom trenutku svi ti brojevi ostanu isti, odnosno, tvrdnja je dokazana.