10. príklad - Vzorové riešenie

Počet trojkových čísel vieme vypočítať ako počet čísel, ktoré obsahujú cifru 3 , plus počet čísel ktoré ju neobsahujú, ale sú deliteľné tromi.

Najskôr vypočítame počet takých čísel do 10^n , ktoré obsahujú cifru 3 . Najjednoduchšie to vieme urobiť tak, že od celkového počtu čísel odpočítame tie, ktoré trojku neobsahujú. Počet všetkých čísel je zjavne 10^n . Teraz sa pozrieme na tie z nich, ktoré neobsahujú cifru 3 . Na mieste každej cifry môže byť ľubovoľné číslo od 0 do 9 okrem trojky. To je 9 možností pre každú z cifier n -ciferného čísla, teda celkovo dostávame 9^n možností. Môžeme si rozmyslieť, že sú všetky naozaj rôzne. Týmto kombinovaním cifier vznikli aj čísla, ktoré sa začínajú na jednu alebo viac núl. Tie po odstránení núl na začiatku predstavujú všetky menej ako n -ciferné čísla. Okrem toho vznikne aj číslo 0 , ktoré nie je prirodzeným číslom od 1 do 10^n . Zároveň 10^n sme týmto spôsobom nedostali, aj keď neobsahuje cifru 3 . Jedno číslo sme teda zarátali aj keď sme nemali, jedno iné sme nezarátali, aj keď sme ho mali zarátať. Počet čísel od 1 do 10^n , ktoré neobsahujú cifru 3 je teda 9^n-1+1=9^n .
Čísel, ktoré obsahujú cifru 3 je 10^n-9^n .

Nuž a koľko je čísel, ktoré cifru 3 neobsahujú, ale sú deliteľné tromi? Tu si pomôžeme poznatkom, že číslo je deliteľné tromi práve vtedy, keď je jeho ciferný súčet deliteľný tromi. To dosť zjednodušuje úlohu a umožňuje to nepozerať sa na každú cifru zvlášť, ale urobiť menší trik.

Majme nejakú kombináciu pre prvých n-1 cifier, v ktorej nie je cifra 3 . Aká môže byť posledná cifra na to, aby bolo celé n -ciferné číslo deliteľné tromi a zároveň neobsahovalo trojku? Tu sú tri možnosti, ako \left(n-1\right) -ciferné číslo mohlo vyzerať.

1. Zvyšok po delení súčtu prvých n-1 cifier trojkou je 1 . Číslo po pridaní poslednej cifry bude deliteľné tromi práve vtedy, keď bude zvyšok po delení poslednej cifry 2 . Zvyšky sa totiž sčítajú, 1+2=3 , čo dáva po delení tromi zvyšok 0 . Číslo bude teda deliteľné troma. Jednociferné čísla, ktoré dávajú po delení tromi zvyšok 2 sú tri, a to 2,\, 5,\, 8 .
2. Zvyšok po delení súčtu prvých n-1 cifier je 2 . Keď pridáme poslednú cifru, číslo bude deliteľné tromi, ak sme pridali číslo, ktoré má po delení tromi zvyšok 1 . Tieto čísla sú tiež tri, a to 1,\,4,\,7 .
3. Súčet prvých n-1 cifier je deliteľný tromi, teda dáva zvyšok 0 . Súčet aj s poslednou cifrou bude potom deliteľný troma vtedy, keď bude posledná cifra deliteľná tromi. Číslo 3 samotné nepoužívame, lebo hľadáme čísla deliteľné tromi, ktoré trojku neobsahujú. Zostali tak tri možnosti, a to 0,\,6,\,9 .

Ako vidíme, možnosti na doplnenie poslednej cifry sú vždy tri.
Počet kombinácií cifier na prvých n-1 miestach bez použitia trojky je 9^{n-1} . Použili sme na to rovnakú úvahu ako keď sme zisťovali na začiatku počet čísel do 10^n , ktoré neobsahujú trojku, len to robíme s o jedna menším počtom cifier. Tým dostávame 9^{n-1} \cdot 3 čísel. Ošetriť ešte musíme čísla 0 a 10^n . V počte 9^{n-1} \cdot 3 je zarátaná aj 0 , ktorá nie je číslom od 1 do 10^n . Číslo 10^n sme kombináciami cifier nemohli dostať, lebo sme sa pozerali na najviac n-ciferné čísla. Zároveň ale nejde o číslo deliteľné tromi, takže ho do počtu čísel, ktoré sú deliteľné tromi a neobsahujú trojku pripočítavať nejdeme. Po odpočítaní možnosti, kde vyšla 0 dostávame, že čísel, ktoré sú deliteľné tromi ale cifru 3 neobsahujú je 9^{n-1} \cdot 3 -1 .

Odpoveď: Počet trojkových čísel od 1 do 10^n je \left(10^n-9^n\right) + \left(9^{n-1} \cdot 3 -1\right) .

Komentár

Pomohlo nám, že číslo je deliteľné tromi práve vtedy, keď je jeho ciferný súčet deliteľný tromi. Platí dokonca aj silnejšie tvrdenie, číslo má po delení tromi rovnaký zvyšok ako jeho ciferný súčet. A keby to nestačilo, podobne to funguje aj pre deviatku, číslo má po delení deviatimi zvyšok rovnaký, ako má jeho ciferný súčet. V úlohách s deliteľnosťami a hľadaním rôznych čísel podľa podmienok sa tieto tvrdenia veľmi často dajú využiť, je dobré si ich pamätať.
Viacerí z vás použili v riešení takzvané sumy. Tie nepovažujeme za základné aritmetické operácie, strhávali sme za ne body.