5. Zadatak
Koliko ima prirodnih brojeva čiji zapis u dekadskome sustavu sadržava svaku od deset znamenaka točno jednom, a svaka je znamenka, osim znamenke , manja od barem jedne njoj susjedne znamenke?
Rješenje
Nazovimo dobrim deseteroznamenkaste brojeve koji zadovoljavaju uvjete zadatka. Cilj je naći broj dobrih brojeva. Neka blok označava niz susjednih znamenaka dobrog broja.
Promotrimo znamenku . Kako bi znamenka imala susjednu znamenku koja je veća od nje, znamenke i moraju činiti blok.
Promotrimo sada znamenku . Jedine znamenke koje su veće od nje su i , pa jedna od njih mora biti njoj susjedna. Kako i čine blok, zaključujemo da znamenke , i čine blok. Kako se ne smije naći između znamenaka i , mora se naći neposredno lijevo od bloka koje čine znamenke i ili neposredno desno od tog bloka.
Za svaku sljedeću znamenku (, , , , i ) slično zaključujemo da se mora naći neposredno lijevo ili neposredno desno uz blok koji čine znamenke veće od nje.
Poziciju svake znamenke od naniže možemo odabrati na dva načina (lijevo ili desno uz blok znamenaka većih od nje).
Konačno, znamenku također možemo smjestiti uz postojeći blok svih preostalih znamenaka, ali ne može doći lijevo od tog bloka jer broj ne smije početi znamenkom nula.
Zato ukupno imamo dobrih brojeva.