Matek! Hány olyan négyjegyű szám van, amelyben a számjegyek összege 12?

Hát spec mat tagozatban nem vagyok jártas. Gondolkodtató feladatnak esetleg valóban fel lehet adni.

Külön ismeretek nem kellenek hozzá, csak azt kell kitalálni, hogy lehetne összeszámolni a számokat úgy, hogy végül ne maradjon ki egyik se.

Tom Benko (12): Ez azért nem ilyen egyszerű, mert nem számolsz a számok ismétlődésével. Ezeket ki kell szűrni (pl. A 3333 csak egyféle sorrendben fordulhat elő, míg az 1236 24 féle sorrendben.)

A 342 megoldást tartalmazó megoldás egyébként helyes.

A megoldás egyik lehetséges módját leírom, bár nem biztos, hogy 7. osztályos gyerek is eljuthat ehhez kombinatorikai ismeretek nélkül. Persze ma már ki tudja. Gauss ilyen korában fedezte fel egy matek órán a számtani sorozat elméleti megoldását.

Első lépésben úgy rendezzük a számokat, hogy azok emelkedő sorrendűek legyenek, vagy legfeljebb azonos szám kövesse az előzőt, sohasem kisebb. A következő számcsoportokat kapjuk a legkisebbektől a nagyobbak felé haladva (most ne foglalkozzunk azzal, hogy a nullákkal kezdődő számcsoportok majd kiesnek a végelszámolásnál):

Két 0-val kezdődőek: 0039, 0048, 0057, 0066

Egy 0- val kezdődőek: 0129, 0138, 0147, 0156, 0228, 0237, 0246,0255, 0336, 0345, 0444

1-el kezdődőek: 1119, 1128, 1137, 1146, 1155, 1227, 1236, 1245, 1335, 1344

2-vel kezdődőek: 2226, 2235, 2244, 2334

3-al kezdődő: 3333

Ez összesen 30 négyjegyű számcsoport Azért hagytam ki a csökkenő sorrendűeket, mert a fentiek összes lehetséges sorrendjének meghatározásával majd azokat is létrehozzuk.

Akkor nézzük, hogy az egyes számokat hány féleképp rendezhetjük:

A két nullával kezdődőek közül a 0066-nak mindössze 3 olyan különböző megoldása van, amely négyjegyű számot eredményez (6006, 6060 és 6600). A másik három ilyen csoport 6-6 megoldást ad. Ez összesen 21 szám.

Az egy nullával kezdődőek közül a 0444 adja a legkevesebb kombinációt (4044, 4404 és 4440). A két azonos számjegyet tartalmazó csoportok (0228, 0255 és 0336) egyenként 9 megoldást adnak, míg a többiek 18-at. Ez összesen 3+3*9+7*18=156 szám.

Az 1-el kezdődőek között van egy, amely 3 db egyessel kezdődik (1119). Ennek 4 megoldása lehet (1119, 1191, 1911 és 9111). Egy olyan számcsoport van, amely 2 számpárból áll (1155). Ennek 6 különböző megoldása van. 6 olyan csoport van, amelyben 1 számpár van (1128, 1137, 1146, 1227, 1335 és 1344). Ezek egyenként 12 megoldást adnak. Végül 2 olyan csoport van, amelyikben minden számjegy különbözik (1236 és 1245). Ezeknek 24-24 megoldása van. Ez összesen: 4+6+6*12+2*24=130 szám.

A 2-vel kezdődőek között van egy, amely 3 db kettessel kezdődik (2226). Ennek is 4 megoldása lehet, mint az 1119-nek volt. Itt is van egy számcsoport 2 számpárral (2244), 6 féle megoldással. A fennmaradó 2 számcsoportban (2235 és 2334) 1-1 számpár van 12-12 megoldással. Itt nincs ismétlődés nélküli számcsoport. Ez összesen: 4+6+2*12=34 szám.

Végül hármassal kezdődő csoport kizárólag a 3333, aminek 1 megoldása van, ez saját maga.

Összeadva az egyes számcsoportok eredményeit: 21+156+130+34+1=342. Tehát ennyi olyan négyjegyű szám van, amelyben a számjegyek összege 12.

A dobozos módszer sajnos itt önmagában nem célravezető, mivel - gondolom 10-es számrendszerbeli számokról van szó - egy dobozban max. 9 golyó lehet. További nehezítés, hogy szám nem kezdődhet 0-val, vagyis az első dobozban mindig kell legalább egy golyónak lenni. Mindent figyelembe véve az eredmény:

1. lépés:

12 helyett 11 golyót osztunk szét 4 dobozba és a fennmaradó egyet mindig az első dobozba tesszük, így akadályozva meg, hogy az első dobozban ne legyen golyó. (Szám nem kezdődhet 0-val.) Ezen esetek száma:

N1 = \comb(11+3,3) = (14*13*12)/(2*3) = 364

(Ez egyben a feladat megoldása 12-nél nagyobb számrendszer esetén.)

2. lépés:

Ezek után már csak azokat az eseteket kell kiszűrni, amelyekben egy dobozba több mint 9 (10, 11, vagy 12) golyó került. Szerencsére ez 12 golyó esetében még viszonylag könnyen meghatározható:

12,0,0,0 -> 1 eset

11,1,0,0 -> 6 eset

10,1,1,0 -> 9 eset

10,2,0,0,-> 6 eset

Ez összesen N2=22 eset.

3. lépés:

N1-et N2-ből kivonva kapjuk a végeredményt:

N1-N2 = 364 - 22 = 342.

Remélem közérthető volt. Ha nem, további kérdésekre szívesen felelek. Üdv

VMS

Valóban elegáns megoldás.

De laikusként nem világos (néhány óra töprengés után sem), hogy a 11 golyó 4 dobozba való szétosztásakor hogyan lesz 14 alatt a 3, azaz miért a 11+3, és miért a 3 (és nem 4, ahogy az ember elsőre gondolná)

Aztán a kizárandó esteknél sem értem, hogy a 11,1,0,0 miért ad 6 esetet (miközben én csak háromra gondolnék), és az alatta lévő két esetben sem tudom értelmezni a 9 és 6 esetet.

Tudnál segíteni?

OK. Kezdjük az g golyó d megkülönböztethető (pl. számozott) dobozba való szétosztásával. Úgy hiszem, ez egy laikusnak (nem kombinatorikus) tényleg nem triviális. Tehát legyenek a golyók mondjuk fehérek és állítsuk őket sorba. Most vegyünk d-1 darab piros golyót és tetszőlegesen helyezzük el a fehérek közé a sorba. Ezek pont d részre osztják a fehér golyókat: Balról az első piros golyóig eső fehér golyók mennek az első dobozba, az első és a második piros golyó közé esők a másodikba, és így tovább. Ha két piros golyó kerül egymás mellé, akkor az adott doboz üres marad. Namármost hány ilyen felosztás lehetséges? Ennek meghatározásához tekintsünk most g+d-1 darab fehér golyót. Ezek közül kell d-1 darabot pirosra festeni, hogy létrehozzunk egyet a fenti felosztásokból. Hány ilyen lehetséges? Természetesen annyi, ahányféle képen g+d-1 golyóból ki tudunk választani d-1 darabot, vagyis \comb(g+d-1,d-1).

A fizikusok az így levezetett eloszlást Maxwell-Botzmann statisztikának hívják.

A másik kérdésedre azt hiszem kis tököléssel Te is meg tudod adni a választ, ha figyelembe veszed, hogy szám elején nem állhat 0 és ha két v. több azonos jegy szerepel egy számban azok felcserélése nem hoz létre új számot.