Hány olyan 2011-nél kisebb pozitív egész szám van, amelyben a számjegyek szorzata 20-nál nagyobb, de 30-nál kisebb?

A számjegyek szorzaza

21 (4*3+3*2+2*1)-féleképpen lehet a szorzat, mert a szám csak 1-es 3-as és 7-es jegyeket tartalmazhat,

22 nem lehet,

23 nem lehet,

24 (4*3+3*2+2*1)*2 + (4*3+3) + (4*3*2+3*2*1) + 4-féleképpen lehet,

25 (6+3+1)-féleképpen lehet,

26 nem lehet,

27 (4*3+3*2+2*1) + (4+1)-féleképpen lehet,

28 (4*3+3*2+2*1) + (4*3+3)-féleképpen lehet és

29 nem lehet.

Remélem, szorozni és összeadni tudsz.

(Amúgy ez inkább egy kombinatorikai kérdés. Bár egy kevés számelmélet sem árt, az igaz. Remélem, nem rontottam el.)

Nem nehéz rájönni, hogy egyjegyű szám nincs ilyen.

Kétjegyű számok: írjuk fel a 20-nál nagyobb, de 30-nál kisebb számokat két egyjegyű szám szorzataként; hogy minden esetben fel tudjuk írni, előbb érdemes felírni prímtényezős alakban:

-21=3*7, ez a prímtényezős alakja, ezt tovább nem tudjuk bontani. Ebből két 2-jegyű számot tudunk felírni: 37 és 73.

-22=2*11, ezt sem tudjuk tovább bontani, és mivel a 11 nem egyjegyű, ezért 22 nem lehet a számjegyek szorzata

-23 prímszám, tehát ez sem fog előállni két egyjegyű szám szorzataként.

-24=2*2*2*3, ezekből a prímtényezőkből a 3*8-as és a 4*6-os szorzatot tudjuk felírni, ami jó nekünk. Ezekből összesen 4 szám rakható ki: 38, 46, 64 és 83.

-25=5*5, ebből csak az 55 jön ki.

-26=2*13, az előzőek miatt ez sem jó nekünk.

-27=3*3*3, ebből csak a 3*9-et tudjuk kirakni, vagyis a 39-et és a 93-at, ez újabb 2 szám.

-28=2*2*7, vagyis 4*7, tehát ismét 2 szám jó nekünk: 47 és 74

-29 prímszám.

Tehát kétjegyűből 11 jó nekünk.

Nézzük a háromjegyű számokat; ahol csak 1 megoldás volt (tehát csak 2 egyjegyű prímszámból tudtuk felírni), azok ide is jók lesznek, mivel ha egy 1-est hozzáírunk, akkor a számjegyek szorzata nem változik, ezek:

-21=1*3*7, tehát az 1;3;7 számjegyekből kellene nekünk egy háromjegyű szám, erre 6 lehetőség van.

-25=1*5*5, ezekből 3 számot tudunk felírni.

Ahol 3 prímtényezőt találtunk, azoknál mindháromból kitehetünk egy számot, vagy pedig 2 tagot összevonunk és egy 1-est hozzáírunk:

-27=3*3*3, ebből 1-et tudunk kirakni.

-27=1*3*9, ebből már 6-ot.

-28=2*2*7, ebből 3 jön ki.

-28=1*4*7, ebből szintén 6.

A 24 esetén több variációs lehetőségünk is van:

-24=2*3*4, ebből 6 jön ki.

-24=2*2*6, ebből csak 3.

-24=1*4*6, ebből 6.

-24=1*3*8, ebből is 6.

Ezzel a 3-jegyűeket mind megtaláltuk, 46 van belőlük.

Mivel 2011-ig kell nézni a számokat, ezért értelemszerűen az ezres helyiértékre csak 2 vagy 1 mehet. Nézzük meg, hogy 2000-től 2011-ig hány jó négyjegyű szám van. Egy sem, úgyhogy csak az 1 mehet az ezresek helyére. Az 1-essel (mind eddig sem) nem változik a számjegyek szorzata, vagyis úgy találjuk meg a jókat, hogy a 3-jegyűek elé írjuk az 1-est. Ez azt jelenti, hogy ugyanannyi 4-jegyű van, mint 3-jegyű, vagyis 46.

Összesen tehát 11+46+46=103 jó szám van.

> „Remélem, nem rontottam el.”

Dehogynem. Én 10000-ig számoltam össze őket… (Amúgy az 179 lesz.)

De ha valaki felvetette a programozást, akkor érdekes feladat lehet kibogozni, hogy miért jó ez a kód erre a feladatra (C-ben):

int i, n, p, db=0, b=10, max=2011;

for(i=1;i<=max;i++)

{p = 1; n = i;

for(;n%b||n/b;n/=b) p*=n%b;

if(20<p && p<30) db++;

}

printf("%d ilyen szám van.\n", db);

Ez is 103-at ír ki.