Zadanie
Matimu sa ale nepáčilo, že osud výletu bol ponechaný na náhodu. Myslel si, že sa tak nemôžu pokryť všetky možnosti výberu cesty. Marek sa urazil, lebo jeho vysnívaná kocka má všetky odpovede na všetky možné otázky a začal Matimu dokazovať svoje tvrdenie.
Dokážte aj vy Matimu, že pre každé kladné celé číslo existuje nejaký jeho celočíselný násobok, ktorý obsahuje (v desiatkovej sústave) každú cifru aspoň raz.
Pre ľubovoľné celé číslo \(n\) by sme chceli vedieť nájsť nejaký jeho násobok, ktorý obsahuje všetky cifry od \(0\) do \(9\). Keď sa zamyslíme nad tým, ako vyzerajú násobky konkrétneho čísla, tak si môžeme uvedomiť, že cifry blízko ku koncu násobkov silne závisia od čísla \(n\) a nemáme veľmi veľkú voľnosť v dosiahnutí nejakej konkrétnej kombinácie, ktorú by sme chceli. Napríklad pre ľubovoľné číslo deliteľné \(20\) (napr. \(37820\)) platí, že jeho posledná cifra bude vždy nula a predposledná párna.
Mohli by sme preto skúsiť ovplyvniť prvé cifry násobku. Skupina prvých cifier, ktorá by nám vyhovovala, je napríklad \(1234567890\), pretože už ona sama obsahuje každú cifru aspoň (práve) raz. Existuje však pre každé číslo násobok začínajúci \(1234567890\)?
Odpoveď je kladná. Čím väčší si stanovíme počet cifier, tým viac násobkov s takým počtom cifier číslo má. Každé \(n\)-té číslo je násobkom \(n\) – ak si vezmeme ľubovoľných \(n\) po sebe idúcich čísel, niektoré z nich musí byť násobkom \(n\). Stačí nám teda nájsť \(n\) po sebe idúcich čísel začínajúcich \(1234567890\) (rovnako by sme si mohli zvoliť iné poradie cifier).
To je už jednoduché. Ak má naše číslo \(n\) počet cifier \(d\), tak medzi číslami \[1234567890\underbrace{00\, \dots \, 0}_\text{$d$-krát}\ \text a\ 1234567890\underbrace{99\, \dots\, 9}_\text{$d$-krát}\] je určite nejaký násobok \(n\). Týchto čísel je totiž \(10^d = 1\underbrace{00\, \dots\, 0}_\text{$d$-krát}\), a keďže \(n\) má \(d\) cifier, je najviac \(\underbrace{99\, \dots\, 9}_\text{$d$-krát}\), čo je menšie ako počet čísel.
Jedno z týchto \((10+d)\)-ciferných čísel začínajúcich \(1234567890\) tak určite bude násobkom čísla \(n\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.