5. Okno do študentovej duše vzorové riešenie

0 1 1 1 1 1 1 1 1 1
2

11

0 0 0 0 0 0 0 0 0 0
3

39

2 0 0 0 0 0 0 0 0 1
2

0

2 1 2 2 1 1 1 0 1 0
6

268

Pripomeňme si, akú úlohu riešime. Máme predpísané, aké skóre majú jednociferné čísla. Každé väčšie číslo má skóre o jedno väčšie ako je skóre jeho ciferného súčinu. Našou úlohou je pre dané \(c\) nájsť najmenšie číslo \(n\), ktorého skóre je \(c\).

Pointa celej úlohy

Môže byť správnou odpoveďou číslo \(n = 3\,141\,592\)?

Nemôže. Prečo? Lebo číslo \(1\,123\,459\) má presne tie isté cifry (a teda ten istý ciferný súčin, a teda aj to isté skóre) a je od \(n\) menšie.

A môže byť číslo \(1\,123\,459\) správnou odpoveďou?

Tiež nie. Prečo? Lebo číslo \(23\,459\) má tiež ten istý ciferný súčin a je ešte menšie.

Ale poďme sa na to celé pozrieť od začiatku a pekne pomaly.

Každé číslo má skóre

Keď sa chvíľu pohráme s cifernými súčinmi, pomerne rýchlo si všimneme, že pre ľubovoľné \(n\geq 10\) nám jeho ciferný súčin \(s(n)\) vyjde menší ako \(n\). Je toto naozaj vždy pravda?

Keď už si to všimneme, dokázať to nie je ťažké. Pointa je v tom, že dopísanie ďalšej cifry na koniec čísla zväčší samotné číslo aspoň desaťkrát, zatiaľ čo jeho ciferný súčin len nanajvýš deväťkrát.

To isté ešte raz a poriadnejšie: Majme nejaké \(x\)-ciferné číslo \(n\) ktorého prvá cifra je \(y\). Čo o ňom vieme povedať?

• Hodnota \(n\) je aspoň \(y\times 10^{x-1}\).
• Každá z \(x-1\) cifier nasledujúcich za úvodným \(y\) je nanajvýš 9, takže hodnota \(s(n)\) je nanajvýš \(y\times 9^{x-1}\).
• A teda pre \(x\geq 2\) máme \(n > s(n)\).

No a z toho už by malo byť zjavné, že úplne každé nezáporné celé číslo má korektne definované skóre. (Indukciou podľa \(n\). Ak všetky čísla menšie ako \(n\) majú korektne definované skóre, \(s(n)\) je jedným z nich, a keďže \(s(n)\) má skóre, aj \(n\) má skóre.)

Malé skóre vieme efektívne počítať

Pripomeňme si, že nás zaujímajú len čísla, ktorých skóre je nanajvýš 11. Skóre ľubovoľného čísla \(n\) preto vieme ľahko a efektívne vyhodnotiť: postupne počítame \(s(n)\), \(s(s(n))\), atď., až kým sa buď nedostaneme k jednocifernému číslu (kedy vieme povedať, aké skóre má \(n\)) alebo nespravíme 12 krokov (kedy vieme povedať, že \(n\), z ktorého sme začínali, bude mať určite priveľké skóre).

Neskôr si ukážeme, že ani to počítanie krokov do 12 nie je potrebné robiť, lebo úplne každé číslo do \(10^{18}\) má vždy maličké skóre. Ak ste teda v programe len priamo implementovali počítanie skóre podľa definície, bolo to v praxi rovnako dobré.

Ako vyzerá hľadané riešenie?

Zamyslime sa teraz, čo vieme povedať o správnej odpovedi.

Začneme tým, že skontrolujeme čísla od 0 po 19. Čísla od 0 po 9 majú skóre dané na vstupe a hociktoré z nich môže byť tým, ktoré hľadáme. Čísla od 10 po 19 sú najmenšie viacciferné čísla, ktorých ciferný súčin je od 0 po 9. Aj každé z nich môže byť správnou odpoveďou. Ak sme medzi nimi správnu odpoveď nenašli, vieme, že má hodnotu aspoň 20. Uvažujme teraz o situáciách, kedy je správna odpoveď aspoň 20:

• Správna odpoveď nemôže obsahovať cifru 0. Ak by ju obsahovala, mala by ciferný súčin 0, a teda rovnaké skóre ako číslo 10, ktoré je od nej menšie.

• Ako už vieme, správna odpoveď musí mať cifry usporiadané od najmenšej po najväčšiu. (Keďže už vieme, že nemáme cifru 0, nemôže nám pri usporadúvaní cifier vzniknúť problém s nulou na začiatku čísla.)

• Správna odpoveď následne nemôže obsahovať ani cifru 1. Takéto číslo musí byť aspoň trojciferné (dvojciferné začínajúce 1 sme už pozerali) a keď mu úvodnú cifru 1 zmažeme, tak sa samotné číslo zmenší a jeho ciferný súčin sa nezmení.

Už sme vyhrali?

Áno. Totiž po úvahe, ktorú sme práve spravili, nám ostane tak malé množstvo kandidátov na správnu odpoveď, že si môžeme dovoliť všetkých vygenerovať a skontrolovať. Dokopy je medzi nanajvýš 18-cifernými číslami len pribiližne 1.5 milióna takých, ktorých cifry sú 2-9 a sú usporiadané od najmenšej po najväčšiu.

Implementácia

Samotná implementácia je už pomerne priamočiara. Všetkých \(k\)-ciferných kandidátov na riešenie vieme vygenerovať tak, že vygenerujeme všetkých \((k-1)\)-ciferných a každému na koniec pridáme všetky možnosti pre ďalšiu cifru. Takýmto postupom vieme dokonca všetkých kandidátov generovať v usporiadanom poradí, takže akonáhle narazíme na nejakého so správnym skóre, môžeme si byť istí, že sme práve našli riešenie.

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL << 62;

vector<int> base;
vector<long long> answers;
int answers_found;

long long product(long n) {
    if (n == 0) return 0;
    long answer = 1;
    while (n > 0) { answer *= n%10; n /= 10; }
    return answer;
}

int f(long long n) {
    if (n < 10) return base[n];
    return f(product(n))+1;
}

void record_answer(long long number, int score) {
    if (score > int(answers.size())) return;
    if (answers[score] == INF) {
        answers[score] = number;
        ++answers_found;
    } else {
        assert( number > answers[score] );
    }
}

void go(long long prefix, int add_digits) {
    if (add_digits == 0) {
        record_answer( prefix, f(prefix) );
    } else {
        int last2 = prefix % 100;
        if (last2 == 22 || last2 == 23 || last2 == 33) return;
        int last = prefix % 10;
        for (int d=last; d<=9; ++d) {
            go(10*prefix+d, add_digits-1);
            if (answers_found == int(answers.size())) return;
        }
    }
}

int main() {
    base.resize(10);
    for (int i=0; i<10; ++i) cin >> base[i];
    int goal;
    cin >> goal;

    answers.clear();
    answers.resize(12, INF);
    answers_found = 0;

    for (int n=0; n<100; ++n) record_answer(n, f(n));
    for (int l=3; l<=18; ++l) for (int d=2; d<=9; ++d) go(d,l-1);
    cout << answers[goal] << endl;
}

Efektívnejšie hľadanie

Množinu kandidátov, ktorých treba prezrieť, vieme ešte ďalej celkom výrazne prečistiť. Napríklad takto:

• Číslo \(n\) nebude obsahovať cifry 22 (lepšie je mať jednu štvorku), 23 (šestku), 24 (osmičku) ani 33 (deviatku).

• Číslo \(n\) nebude obsahovať cifry 34, lebo lepšie je mať cifry 26 – číslo bude menšie a ciferný súčin rovnaký. Podobne vieme, že \(n\) nebude obsahovať cifry 36 (lepšie je 29), 44 (lepšie je 28), 46 (lepšie je 38) ani 66 (lepšie je 49).

• Ak máme v \(n\) cifru 5 tak nemôžeme mať žiadnu párnu cifru – lebo \(s(n)\) bude končiť nulou a potom \(s(s(n))\) bude nula. Medzi zakázané dvojice cifier teda môžeme pridať aj 25, 45, 56 a 58.

Ak do generovania kandidátov pridáme tieto obmedzenia, zredukujeme ich počet z vyššie spomínaného približne 1.5 milióna na iba približne \(9\,000\).

def je_validne(cislo):
    cifry = [0]*10
    while cislo:
        cifry[cislo%10] += 1
        cislo //= 10

    if any( cifry[x] >= 2 for x in [2,3,4,6] ):
        return False

    forbidden_pairs = [ (2,3), (2,4), (2,5), (3,4), (3,6), (4,5), (4,6), (5,6), (5,8) ]
    if any( cifry[x] >= 1 and cifry[y] >= 1 for x, y in forbidden_pairs ):
        return False

    return True

def pridaj_dalsiu_cifru(zoznam):
    novy_zoznam = []
    for cislo in zoznam:
        posledna = cislo % 10
        for nova in range(posledna, 10):
            if je_validne( cislo*10 + nova ):
                novy_zoznam.append( cislo*10 + nova )
    return novy_zoznam

def generuj_vsetkych_kandidatov():
    for n in range(100):
        yield n
    kandidati = list(range(2,10))
    kandidati = pridaj_dalsiu_cifru(kandidati)
    for d in range(3,19):
        kandidati = pridaj_dalsiu_cifru(kandidati)
        for k in kandidati:
            yield k

def ciferny_sucin(n):
    odpoved = 1
    while n: odpoved, n = odpoved * (n%10), n // 10
    return odpoved

def skore(n, Z):
    odpoved = 0
    while n >= 10:
        odpoved += 1
        n = ciferny_sucin(n)
    return odpoved + Z[n]

Z = [ int(_) for _ in input().split() ]
c = int( input() )
for kandidat in generuj_vsetkych_kandidatov():
    if skore(kandidat, Z) == c:
        print(kandidat)
        break

Checkpoint

Niekde tu by sa dalo vzorové riešenie tejto úlohy ukončiť. My v ňom však ešte nejakú tú chvíľu budeme pokračovať a doplníme ešte nejaké detaily a zaujímavostí navyše.

Počítanie kandidátov

Vyššie sme uvádzali nejaké číselné odhady počtov kandidátov. Tie samozrejme vieme získať tak, že ich naozaj vygenerujeme a spočítame. Vieme ich ale veľmi ľahko spočítať aj pomocou kombinatoriky.

Pozrime sa napríklad na všetky \(d\)-ciferné čísla, ktorých cifry sú od 2 po 9 a sú usporiadané od najmenšej po najväčšiu. Koľko ich je?

Predstavme si, že máme premennú, v ktorej je na začiatku cifra 2, a dve rôzne inštrukcie: inštrukcia + zväčší hodnotu v premennej a inštrukcia p ju vypíše.

Pomocou takýchto inštrukcií vieme vyrábať čísla, ktorých cifry sú usporiadané. Napr. postupnosť inštrukcií ++p+pp+++p+ vyrobí číslo 4558.

Pozrime sa na postupnosti inštrukcií, ktoré obsahujú práve sedem inštrukcií + a práve \(d\) inštrukcií p. Každá takáto postupnosť vyrobí nejaké \(d\)-ciferné číslo, ktorého cifry sú od 2 do 9 a postupne rastú. A naopak, keď zoberieme ľubovoľné takéto číslo, vieme nájsť práve jednu takúto postupnosť inštrukcií, ktorá ho vyrobí: ideme zľava doprava a pri každej cifre najskôr stlačíme správne veľa + aby sme premennú nastavili na jej hodnotu a potom stlačíme p. (Po poslednej cifre ešte doplníme prípadné chýbajúce +.)

Hľadaných čísel je teda presne toľko isto ako reťazcov dĺžky \(d+7\), ktoré obsahujú \(d\) péčok a 7 plusov. No a takýchto reťazcov je zjavne \({d+7\choose 7}\): vyberieme, na ktorých siedmich pozíciách sú plusy a tým je jednoznačne určené, kde sú péčka.

Asymptotické odhady

Môžeme rozpísať, že \({d+7\choose 7} = \frac{(d+7)(d+6)\cdots(d+1)}{7!}\). Z toho je zjavné, že počet čísel, ktoré majú usporiadané cifry od 2 po 9, závisí od ich dĺžky \(d\) len polynomiálne: je ich \(\Theta(d^7)\).

Keď sme prečistili množinu kandidátov, ostali nám v nej len čísla, ktoré mali nanajvýš po jednej z cifier 2, 3, 4, 6. Navyše buď mali len nepárne cifry (vtedy sú premenlivé len počty cifier 5, 7 a 9) alebo neobsahovali cifru 5 (a vtedy sú premenlivé zase len počty cifier 7, 8 a 9). Podobnou kombinatorickou úvahou dostávame, že čísel dĺžky \(d\) jedného aj druhého typu je len \(\Theta(d^2)\).

Otvorený problém na záver

Najjednoduchšou možnou formou zadania našej úlohy je verzia v ktorej všetky jednociferné čísla majú skóre nula. Pre takýto vstup platí, že skóre čísla udáva jednoducho počet opakovaní operácie “nahraď číslo jeho ciferným súčinom” po ktorom dostaneme jednociferné číslo. Matematici v teórii čísel toto občas nazývajú nie skóre, ale multiplikatívna perzistentnosť čísla.

Ak ste si skúšali svoj program spustiť pre najväčšie platné vstupy, určite ste v jeho výstupoch často narazili na číslo \(277\,777\,788\,888\,899\). Toto je najmenšie číslo, ktoré má multiplikatívnu perzistentnosť 11.

Prečo sme ako najväčšie povolené \(c\) v zadaní zvolili práve 11? O koľko väčšia je vlastne správna odpoveď pre \(c=12\)? Nevieme podobným postupom nájsť aj tú?

Nuž… nielen že nevieme, my vlastne dodnes ani nevieme, či vôbec nejaké takéto číslo existuje. Jeho existencia je otvoreným problémom, ktorý už nejaký ten rok odoláva snahám matematikov. Zatiaľ vieme dokázať, že ak takéto číslo existuje, tak určite musí mať výrazne viac ako \(20\,000\) cifier. Ale skôr si myslíme, že neexistuje. A dokonca pravdepodobne platí ešte podivuhodnejšie tvrdenie: je možné, že už poznáme úplne všetkých kandidátov, ktorí majú multiplikatívnu perzistentnosť väčšiu ako 2. Vyzerá to totiž tak, že keď budeme postupne prezerať väčších a väčších kandidátov, tak nielen že nenájdeme žiadneho s multiplikatívnou perzistentnosťou 12, ale naopak sa veľmi rýchlo minú všetci s multiplikatívnou perzistentnosťou väčšou ako 2.

Prečo je to tak? Intuitívne sa to dá priblížiť nasledovne. Majme nejakého kandidáta s veľmi veľkým počtom cifier. Toto je nejaké pekné systematické číslo, ktorého cifry sú od 2 od 9. Jeho ciferným súčinom je nejaké iné, tiež ešte obrovské číslo. Toho cifry sú však už všelijaké chaotické a skoro vždy niekde medzi nimi vybehne nejaká tá nula. Takže to vyzerá tak, že pre ľubovoľného veľkého kandidáta \(n\) skoro určite platí \(s(s(n)) = 0\).

Posledná známa výnimka má 140 cifier. Presnejšie, 140-ciferné číslo \(v = 2^{25} \times 3^{227} \times 7^{28}\) neobsahuje žiadnu nulu a jeho multiplikatívna perzistentnosť je presne 2. Toto číslo \(v\) je rovné \(s(n)\) pre niekoľko podobne veľkých kandidátov \(n\) ktorí potom majú multiplikatívnu perzistentnosť až 3. Ale od 140 cifier ďalej až po vyše \(20\,000\) cifier už sme prezreli všetky možnosti a sme si úplne istí, že úplne všetky možné \(s(n)\) obsahujú v sebe aspoň jednu nulu.

Zrejme to bude platiť aj ďalej pre ešte väčšie čísla. Hja, ale ako takéto niečo exaktne dokázať?