Feladat: B.3612 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Németh Zsolt 
Füzet: 2004/április, 223 - 224. oldal  PDF file
Témakör(ök): Permutációk, "a" alapú számrendszer (a >1, egész szám), Feladat
Hivatkozás(ok):Feladatok: 2003/február: B.3612

Egy tízes számrendszerben felírt számból kiindulva készítsük el a szám jegyeinek permutációival nyerhető különböző számok összegét. Pl. a 110-ből kiindulva a 110+101+11=222 összeg adódik. Melyik a legkisebb szám, amelyből kiindulva a kapott összeg 4933284?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. A feladatunkban keresett szám nem lehet 4-jegyű vagy annál kisebb, mert egy ilyen számból a számjegyeinek felcserélgetésével legfeljebb 24 különböző számhoz juthatunk, amelyek mindegyike kisebb 10000-nél. Így e számok összege kisebb 240000-nél. Vizsgáljuk tehát az ötjegyű számokat.
Ha a keresett számban valamelyik számjegy legalább 3-szor fordul elő, akkor a számjegyek permutációival nyerhető számok száma legfeljebb 20 és ezek mindegyike kisebb 100000-nél. Így e számok összege kisebb 2000000-nál. Tehát ez sem lehetséges.
Az sem fordulhat elő, hogy két számjegy is pontosan 2-szer szerepeljen, mert egy ilyen számból kiindulva 30 különböző számot kapunk, melyek összege kisebb 30100000=3000000-nál.
Tehát ha van olyan 5-jegyű szám, ami megfelel a feltételeknek, akkor vagy minden jegye különböző, vagy pontosan két számjegye egyezik meg.
Nézzük először azt az esetet, amelyben minden számjegy különböző. A szám abcde¯ alakú (ahol a, b, c, d és e csupa különböző számjegyet jelöl). Ekkor a számjegyek permutálásával kapott számokban minden egyes számjegy minden helyiértéken 24-szer fordul elő. Így a kapott számok összege:

2411111a+2411111b+2411111c+2411111d+2411111e==2411111(a+b+c+d+e)=4933284,
ahonnan 2(a+b+c+d+e)=37 következik. Ez nyilván nem lehetséges, hiszen a bal oldalon páros szám áll, a jobb oldalon pedig páratlan.
Végül nézzük, van-e olyan ötjegyű szám, amelynek pontosan két jegye egyezik meg és megfelel a feltételeknek. Az ilyen szám jegyeiből készített permutációk között van pl. aabcd¯ alakú, ahol a, b, c és d különböző számjegyeket jelölnek. Ha az egyik a számjegyet rögzítjük valamelyik helyiértéken, akkor a többi számjegy minden lehetséges permutálásával 24 számot kapunk, azaz az a számjegy minden helyiértéken 24-szer fordul elő. Ha pedig bármelyik másik számjegyet rögzítjük valamely helyiértéken, akkor a többi jegynek 12 különböző permutációja létezik, vagyis minden a-tól különböző jegy 12-szer fordul elő minden egyes helyiértéken.
Így az aabcd¯ alakú szám számjegyeinek permutációival nyerhető számok összege: 2411111a+1211111b+1211111c+1211111d=4933284. Vagyis 2a+b+c+d=37. Akkor kaphatjuk meg az e feltételnek megfelelő legkisebb ötjegyű számot, ha az első helyiértékre a lehető legkisebb számjegyet választjuk. Ez pedig úgy lehetséges, ha a többi helyiértékre a lehető legnagyobbakat; eszerint a lehető legnagyobbak: 29+8+7=33, így az első helyiértéken 4-esnek kell állnia.
Található tehát az ötjegyű számok között olyan, amely kielégíti a feltételeket (a kisebb számok között pedig nem), így a legkisebb ilyen ötjegyű szám egyben a keresett legkisebb szám: 47899.