Feladat: B.3464 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Deák Péter ,  Paulin Dániel ,  Tóth Ágnes 
Füzet: 2001/december, 545 - 546. oldal  PDF file
Témakör(ök): Számjegyekkel kapcsolatos feladatok, Kombinatorikai leszámolási problémák, Partíciós problémák, Feladat
Hivatkozás(ok):Feladatok: 2001/május: B.3464

Hány olyan n-jegyű szám van, amelyben a számjegyek összege 9n-8?

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.

A keresett szám minden jegye legalább 1, ezeket a számokat tehát úgy kaphatjuk meg, ha az n-jegyű, csupa 9-esből álló szám jegyei közül néhányat csökkentünk úgy, hogy a csökkentések összege éppen 8. Így minden szóban forgó számhoz egyértelműen hozzárendelhető egy természetes számokból álló n hosszúságú sorozat, amelyben az elemek összege 8.
Azt kell tehát meghatároznunk, hogy hányféleképpen lehet a 8-at n darab nemnegatív egész szám összegére felbontani úgy, hogy különbözőnek tekintjük azokat a felbontásokat is, amelyek csupán a tagok sorrendjében térnek el.
Próbáljunk ténylegesen elkészíteni egy ilyen felbontást: ha egy nyolc egységnyi rudat az egész osztópontokon áthaladó n-1 darab vágással n részre osztunk, akkor a sorozat elemeit az egymás után adódó részek hosszaként kapjuk. Az egyes osztópontokon több vágás is áthaladhat, ezek a sorozatban 0 értékű elemeket jelentenek az adott helyen.
Mivel a sorozat elején és végén is állhat 0, azért a 0, illetve a 8 egységnyi beosztáson áthaladó vágások is megengedettek. A feladat tehát az, hogy hányféleképpen lehet a 9 osztópont közül (n-1)-et kiválasztani, ha egy-egy osztópontot többször is kiválaszthatunk.
Mint ismeretes, ezek a kiválasztások éppen 9 elem (n-1)-osztályú ismétléses kombinációi, a számuk pedig (9+n-2n-1)=(n+7n-1). Ez azt jelenti, hogy (n+7n-1) darab olyan n-jegyű szám van, amelyben a számjegyek összege 9n-8.

 Tóth 370 Ágnes (Hajdúszoboszló, Hőgyes E. Gimn., 11. o.t.)

 
Megjegyzések. 1. Az n hosszúságú 8 összegű ,,kiegészítő sorozatok száma más okoskodással is meghatározható. Paulin Dániel (Fazekas M. Gyak. Gimn., 9. o.t.) az összesen 8 egységnyi csökkentést egyesével hajtotta végre, mégpedig helyiértékenként. Okoskodása szerint az n helyiérték közül kell összesen 8 alkalommal választanunk egyet-egyet, miközben ugyanazt a helyiértéket természetesen többször is kiválaszthatjuk. A lehetőségek most n elem 8-osztályú ismétléses kombinációi, számuk (n+8-18)=(n+78), természetesen ugyanannyi, mint az előbb.
2. Deák Péter (Fazekas M. Gyak. Gimn., 9. o.t.) közvetlenül meg is számlálta ezeket a kiválasztásokat, és ezzel lényegében igazolta az ismétléses kombinációk számát megadó összefüggést. A következő gondolatkísérlettel okoskodott: az utolsó kivételével minden egyes helyiértékhez érve kétféleképpen cselekedhetünk: csökkentjük az ott álló számot 1-gyel, vagy pedig továbblépünk a következő helyiértékhez. (Az utolsó helyiértékhez érve már nincs választásunk.) Összesen tehát (n-1)+8=n+7 döntési helyzetünk van, és ezek közül kell azt a 8-at kiválasztanunk, amikor csökkentünk. Ezt nyilván (n+78)-féleképpen tehetjük meg. (Vagy, ami ugyanennyi, (n+7n-1)-féleképpen választhatjuk ki az (n-1) darab továbblépést.)