Az 1, 2, 3, 4, 5, 6 számjegyekből hány olyan 5jegyű szám készíthető, ahol bármely két egymás mellett álló számjegy különbsége legfeljebb 2?

A számjegyek közti különbség 5-féle lehet ((-2)-től (+2)-ig), tehát a különbségek 5*5*5*5=625-féleképpen alakulhatnak. Minden ilyen különbségsorozat egyértelműen megadja a számot, hogyha az első számjegyet ismerjük (csak el kell végezni a műveleteket), és az első helyre 6-féle számjegy kerülhet, így 6*625=3750 esetet tudtunk megszámolni. Viszont ezen esetek között több olyan van, ami a feltételeknek nem felel meg, emiatt ezzel a számítással a létező számok egy felső becslését tudtuk megadni, vagyis a kérdéses számok 3750-nél kevesebben vannak biztosan.

Egyelőre eddig jutottam.

Ágrajzzal össze tudtam számolni az eseteket;

1-essel kezdődőből 209 darab van,

2-essel kezdődőből 297 darab van,

3-assal kezdődőből 377 darab van.

Szimmetriaokokból 6-ossal kezdődőből annyi van, mint 1-essel kezdődőből, 5-össel kezdődőből annyi van, mint 2-essel kezdődőből, és 4-essel kezdődőből annyi van, mint 3-assal kezdődőből, tehát összesen

209+297+377+377+297+209=1766 darab van.

Nekem scripttel 1748 jött ki.

Valamelyiket nem számoltad el?

Rájöttem, hogyan lehet leszámolni. Igaz, indukcióval számolunk, de az is valami;

Visszafelé fogunk haladni. Először szedjük össze a jó kétjegyű számokat:

11, 12, 13, ebből 3 van

21, 22, 23, 24, ebből 4 van

31, 32, 33, 34, 35, ebből 5 van

42, 43, 44, 45, 46, ebből 5 van

53, 54, 55, 56, ebből 4 van

64, 65, 66, ebből 3 van.

Most nézzük meg azt, hogy a különféle számjegyeket hány kétjegyű szám elé írhatjuk;

-az 1-est csak az 1;2;3-mal kezdődők elé írhatjuk, így 1-essel kezdődő háromjegyű számból 3+4+5=12 darab van,

-a 2-est csak az 1;2;3;4-gyel kezdődők elé írhatjuk, így 2-essel kezdődő háromjegyű számból 3+4+5+5=17 darab van,

-a 3-ast csak az 1;2;3;4;5-tel kezdődők elé írhatjuk, így 3-assal kezdődő háromjegyű számból 3+4+5+5+4=21 darab van,

-a 4-est csak a 2;3;4;5;6-tal kezdődők elé írhatjuk, így 4-essel kezdődő háromjegyű számból 4+5+5+4+3=21 darab van,

-az 5-öst csak a 3;4;5;6-tal kezdődők elé írhatjuk, így 5-össel kezdődő háromjegyű számból 5+5+4+3=17 darab van,

-a 6-ost csak a 4;5;6-tal kezdődők elé írhatjuk, így 6-ossal kezdődő háromjegyű számból 5+4+3=12 darab van.

Most ugyanazt fogjuk csinálni, mint az előbb, vagyis megnézzük, hogy a különféle számjegyek hány háromjegyű szám elé írhatóak;

-az 1-est csak az 1;2;3-mal kezdődők elé írhatjuk, így 1-essel kezdődő négyjegyű számból 12+17+21=50 darab van,

-a 2-est csak az 1;2;3;4-gyel kezdődők elé írhatjuk, így 2-essel kezdődő négyjegyű számból 12+17+21+21=71 darab van,

-a 3-ast csak az 1;2;3;4;5-tel kezdődők elé írhatjuk, így 3-assal kezdődő négyjegyű számból 12+17+21+21+17=88 darab van,

-a 4-est csak a 2;3;4;5;6-tal kezdődők elé írhatjuk, így 4-essel kezdődő négyjegyű számból 17+21+21+17+12=88 darab van,

-az 5-öst csak a 3;4;5;6-tal kezdődők elé írhatjuk, így 5-össel kezdődő négyjegyű számból 21+21+17+12=71 darab van,

-a 6-ost csak a 4;5;6-tal kezdődők elé írhatjuk, így 6-ossal kezdődő négyjegyű számból 21+17+12=50 darab van.

És még egyszer ugyanezt:

-az 1-est csak az 1;2;3-mal kezdődők elé írhatjuk, így 1-essel kezdődő ötjegyű számból 50+71+88=209 darab van,

-a 2-est csak az 1;2;3;4-gyel kezdődők elé írhatjuk, így 2-essel kezdődő ötjegyű számból 50+71+88+88=297 darab van,

-a 3-ast csak az 1;2;3;4;5-tel kezdődők elé írhatjuk, így 3-assal kezdődő ötjegyű számból 50+71+88+88+71=368 darab van,

-a 4-est csak a 2;3;4;5;6-tal kezdődők elé írhatjuk, így 4-essel kezdődő ötjegyű számból 71+88+88+71+50=368 darab van,

-az 5-öst csak a 3;4;5;6-tal kezdődők elé írhatjuk, így 5-össel kezdődő ötjegyű számból 88+88+71+50=297 darab van,

-a 6-ost csak a 4;5;6-tal kezdődők elé írhatjuk, így 6-ossal kezdődő ötjegyű számból 88+71+50=209 darab van.

Ezeket összeadva kapjuk a megfelelő ötjegyű számok számát:

209+297+368+368+297+209=1748

Látható, hogy az ágrajzos megoldás is kijött, csak a 3-assal kezdődőek darabszámánál van egy kis probléma. Ez azért van, mert egy helyre 21-et írtam, ahova 12-t kellett volna, és ezért jött ki 9-cel több.

Nyugodtan itt is megköszönheted, nem muszáj privátot írni :)

Egyébként ez a feladat miben kapcsolódik az érettségihez? Mert még emelt szinten sem hiszem, hogy előfordulna, ez inkább már KÖMAL-szint.

Bár lehet, hogy van tisztán kombinatorikai megoldása, ami akár középszinten is megállna, de kétlem.

Mindenképp kíváncsi vagyok, hogy ő hogyan oldja meg kombinatorikailag (ahogy én oldottam meg, annak nem sok köze van a kombinatorikához). De hogy a „kicsit nehezebb”-nél sokkal nehezebb ez a feladat, az is biztos.

A többi feladatot meg tudtad oldani?