Hány olyan négyjegyű természetes szám létezik, amelynek a számjegyei az {1,2,3,4} halmazból vannak és a szám osztható 3-mal?

Az első válasza rossz.

Nézzük a megoldást: a feladat nem köti ki, hogy a négyjegyű szám számjegyei nem ismétlődhetnek. Így a legkisebb ilyen szám az 1111, a legnagyobb pedig a 4444. A 3-mal való oszthatósághoz a számjegyek összegét kell vizsgálni, a lehetséges legkisebb összeg a 4 (1+1+1+1), a lehetséges legnagyobb pedig a 16 (4+4+4+4). Tehát az ezek közé eső 3-mal osztható összegek: 6, 9, 12 és 15.

Vagyis, ezek az összegek állnak elő négytagú összegként. Ügyes felírással kapjuk:

6 = 1 + 1 + 2 + 2

6 = 1 + 1 + 1 + 3

Ez összesen 10 lehetőség ( ha a kombinatorikai alapok hiányoznak, szólj!)

9 = 2+2+2+3

9 = 1+2+3+3

9 = 1+2+2+4

9 = 1+1+3+4

Ez pedig összesen 40 lehetőség.

12 = 3+3+3+3

12 = 2+3+3+4

12 = 2+2+4+4

12 = 1+3+4+4

Ez összesen 31 lehetőség.

15 = 3+4+4+4 itt nincs más lehetőség négytagú összegként 15-öt előállítani, ennek a lehetséges száma a sorrendet figyelembe véve (hiszen számjegyekről van szó) 4 eset.

Összesen tehát 10 + 40 + 31 + 4 = 85 esetet számoltunk össze, vagyis 85 db olyan négyjegyű szám van, amelynek számjegyei az {1;2;3;4} halmazból valók.

Gyors ellenőrzés: ezekből a számjegyekből összesen 4^4 = 256 db négyjegyű szám képezhető. Reális, ha ebből 85 db osztható 3-mal.

A harmadik számolásánál van egy kicsit egyszerűbb megoldás is;

Az első három helyre 4*4*4=64-féleképpen lehet a jegyeket pakolni. Ezek összege vagy osztható 3-mal, vagy 1 vagy 2 maradékot adnak. Eszerint vizsgálódjunk;

Az első három számjegy összege

-osztható 3-mal -> az utolsó számjegy csak 3-as lehet.

-3-mal osztva 1 maradékot ad -> az utolsó számjegy csak 2-es lehet.

-3-mal osztva 2 maradékot ad -> az utolsó számjegy 1-es vagy 4-es lehet.

Tehát akárhogy nézzük, bármilyen első három számjegyű kezdéssel lehet utolsó számjegynek legalább egyféle számjegyet rakni a végére, így legalább 64-féle jó négyjegyű számunk létezik. Akkor van egy kis baj, hogyha a számjegyek összegének 3-as maradéka 2, de abból a fajtából (a 64-hez képest) elég csak az egyiket megszámolni.

Nézzük azt, hogy hány 1-re végződő 3-mal osztható négyjegyű szám van.

(Ezen a ponton nem látok jobb megoldást, csak ahhoz hasonlót, amit #3 írt, de lényegesen kevesebb lehetőséggel az összegekre.)

A legnagyobb négyjegyű, 1-re végződő szám a 4441, ezekben a számjegyek összege 17. Ezalatt keressük meg a 3-mal osztható számokat: 3, 6, 9, 12, 15.

Mivel az 1 fixen a végén van, ezért a keresett összegek: 2, 5, 8, 11, 14.

Az összeg nem nagyon lehet 2.

Az 5-ös összegre (szisztematikus kereséssel) az 1+1+3, 1+2+2, 1+3+1, 2+1+2, 2+2+1, 3+1+1 összegeket tudjuk mondani, ezekből 6 darab van.

A 8-as összegre: 1+3+4, 1+4+3, 2+2+4, 2+3+3, 2+4+2, 3+1+4, 3+2+3, 3+3+2, 3+4+1, 4+1+3, 4+2+2, 4+3+1, ezekből 12 van.

A 11-es összegre: 3+4+4, 4+3+4, 4+4+3, ebből 3 van.

A 14-es összegből 0 van, mivel a 444 esetén az összeg 12, tehát 12-nél több nem lehet.

(Mivel nincs túl sok lehetőség, ezért ágrajzzal is össze lehet szedni a lehetőségeket; kezdünk a végén lefixált 1-essel, előtte 4-féle számjegy lehet, azok után szintén 4-4-4-4, tehát a harmadik sorban már 16 szám található, az ágrajz negyedik sorát pedig aszerint töltjük ki, hogy mikor kapunk megfelelő összeget az adott ágon. Ekkor kapjuk ezt:

[link] )

Összesen tehát 6+12+3 = 21 darab van, tehát 21 darab 1-esre végződő "jó" négyjegyű szám van a korábbi 64-en felül, tehát 64+21 = 85-en vannak.

Mivel ugyanannyi jött ki, mint #3-nak, ezért lehet reménykedni, hogy nem számoltunk mindketten ugyanolyan rosszul :D