Feladat: 1960. évi Arany Dániel matematikaverseny 2. forduló kezdők (speciális) 3. feladata Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1960/november, 106 - 108. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Arany Dániel
Hivatkozás(ok):Feladatok: 1960/szeptember: 1960. évi Arany Dániel matematikaverseny 2. forduló kezdők (speciális) 3. feladata

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.

I. megoldás: 24-en alul 12 páratlan természetes szám van: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23. Ezek bármely kettője között a különbség (a nagyobból vonva le a kisebbet) pozitív páros szám és 2-től 22-ig minden páros szám előfordul különbségként.
Ha kiválasztunk hetet páratlan számaink közül, ezekből 21 pár képezhető és így 21 különbség lép fel (ismét mindig a nagyobból vonva ki a kisebbet).
Kíséreljük meg úgy választani ki a két számot, hogy a 21 különbség között a lehetséges 11 érték mindegyike legfeljebb kétszer forduljon elő. Be fogjuk látni, hogy ez lehetetlen. A követelmény teljesítéséhez minden esetre szükséges, hogy mind a 11 érték fellépjen a hét szám különbségei közt, mert ha kevesebb lépne fel, még ha mind elő is fordul kétszer, az is legfeljebb 20 értéket adna.
A legkisebb és legnagyobb szám különbsége nyilván nagyobb a többi 20 különbségnél, tehát csak egyszer lép fel a különbségek közt. Ennek tehát a lehetséges legnagyobb értéknek kell lennie, és a többi lehetséges értéknek mindnek kétszer kell fellépnie a 7 szám közti különbségek közt, mert még 20 különbség lép fel. A legnagyobb fellépő különbség tehát 22 lesz és ez csak úgy léphet fel, ha 1 és 23 szerepel a kiválasztott számok közt. Két kiválasztott számpár közt kell, hogy 20 legyen a különbség, ekkora különbséget azonban csak az 1 és 21, továbbá a 3 és 23 számok adnak. Így 3 és 21 is elő kell forduljon a hét kiválasztott szám között. Ezek különbsége, 18, még egy számpár között is fel kell, hogy lépjen. Ilyen számpár kettő van: az 1, 19 és az 5, 23. Azonban akár az 5, akár a 19 szerepel 1, 3, 21, 23-on kívül, a kiválasztott számok között, a 2 már háromszor lép fel mint különbség: az 1 és 3 továbbá a 21 és 23 számokon kívül a 3 és 5, ill. a 19 és 21 számok különbsége is 2. Nem lehetséges tehát a hét számot a kívánt módon kiválasztani. Ezzel a feladat állítása igazolást nyert.
Lényegében így oldotta meg a feladatot Kászonyi László (Szombathely, Nagy Lajos gimnázium).

 

Megjegyzések. 1. Többen azt állították, hogy a hét kiválasztott szám között 42 különbség lép fel, amelyek 11 féle értéket vehetnek fel. Ebből nyilvánvalóan következnék a feladat állítása, sőt az is, hogy van érték, amelyik négyszer is fel lép a különbségek közt. Hibás azonban az okoskodás, mert a fellépő különbségek közt a negatívakat is figyelembe veszi, a lehetséges különböző értékekként azonban csak a pozitívakat veszi számba. Az okoskodás helytelensége abból is látszik, hogy pl. az 1, 3, 7, 9, 17, 21, 23 számok különbségei közt egyetlen érték sem szerepel négyszer.
2. Voltak, akik beérték annak megállapításával, hogy néhány általuk felírt kiválasztás esetén találnak a különbségek közt legalább háromszor fellépő értéket. Ebből azonban nem következik semmi a további lehetséges kiválasztásokra. Az összes lehetséges (792) esetet végigpróbálgatni pedig igen fáradságos munka lenne.
 

II. megoldás: A hét kiválasztott számot rendezzük nagyság szerint sorba és vizsgáljuk a szomszédosak közt fellépő különbségeket. Ezek összege megadja a legkisebb és legnagyobb kiválasztott szám különbségét, tehát nem lehet nagyobb, mint 22. A tekintetbe vett különbségekként tehát hat pozitív páros számot kell keresnünk, amelyek összege nem nagyobb, mint 22. Ezek közt elő kell fordulnia a 2-nek, mert különben a hat szám összege legalább 6⋅4=24 volna. Ha további 5 szám 2-nél nagyobb, ez csak úgy lehet, hogy mind 4, tehát a 4 előfordul háromszor (többször is) a különbségek közt.
Tegyük fel most, hogy két különbség értéke 2. Ha a további különbségek közt is fellép még a 2, akkor ez az érték már legalább háromszor előfordul a különbségek közt. Ha viszont a további négy különbség mind nagyobb 2-nél,akkor vagy mindegyik a 4 értéket veszi fel, vagy a 2, 2, 4, 4, 4, 6 értékek lépnek fel valamilyen sorrendben a kiválasztott számok közül a szomszédosak különbségeiként.
Ezzel igazoltuk a feladat állítását, sőt annál többet is. Beláttuk, hogy a 24-nél kisebb páratlan természetes számok közül bárhogy választva ki hetet és azokat nagyság szerint rendezve a szomszédos számok közti hat különbség közül legalább három veszi fel a 2 értéket, vagy legalább három a 4 értéket. Mind a két eset elő is fordulhat. Csak a 2 lép fel háromszor pl. a 2, 2, 2, 4, 4, 8 értékek közt (összegük 22), és ezek lépnek fel az 1, 3, 5, 7, 11, 15, 23 számok közül a szomszédosak különbségeiként, vagy más sorrendben pl. az 1, 9, 11, 13, 15, 19, 23 számok közt. A 2, 2, 4, 4, 4, 4 számok közt (összegük 20) viszont csak a 4 lép fel kettőnél többször. Ennek megfelel pl. a 3, 5, 7, 11, 15, 19, 23 számok, vagy az 1, 3, 7, 11, 13, 17, 21 számok kiválasztása is.
 

Megjegyzések. 1. Ha még a 25 előfordulását is megengedjük a kiválasztandó hét szám közt, akkor a szomszédosak különbségei közt nem föltétlenül szerepel egy érték háromszor, így lehetnek a kérdéses különbségek 2, 2, 4, 4, 6, 6 és könnyen látható, hogy sorrendtől eltekintve csak ezek (minden más esetben vagy a 2, vagy a 4, vagy a 6 legalább háromszor fordul elő köztük). Ez esetben is előfordul azonban az összes különbségek közt legalább egy érték háromszor. Ha ugyanis kétszer egymásután következik 2 távolságra két szám, akkor az első és harmadik közt 4 a különbség (és ez a különbség még két szomszédos számokból álló párban is fellép); ha az egyik 2-es különbség mellett egy 4-es különbség lép fel, akkor fellép egy ,,második szomszéd'' pár közt is a 6-os különbség; végül a 2-esek csak a 2, 6, 2, 6, 4, 4, a 2, 6, 4, 4, 6, 2 és a 4, 4, 6, 2, 6, 2 sorrendekben nem szomszédosak sem egymással, sem 4-es különbséggel. Ekkor azonban az első és harmadik, harmadik és ötödik, ötödik és hetedik szám különbsége egyaránt 8 mind a három esetben.
Beláttuk tehát, hogy a feladat állítása akkor is helyes marad, ha a 26-nál nem nagyobb páratlan természetes számok közül választunk ki hetet.
2. Ezen túl már nem tágíthatjuk a kiválasztható számok körét, mert pl. az 1, 3, 7, 15, 17, 23, 27 számok különbségei közt egyetlen érték sem fordul elő háromszor, amint erről az olvasó könnyen meggyőződhet.
Az első megoldáshoz fűzött megjegyzésben említettük, hogy 3-nál többször egy értéknek sem kell szerepelnie a fellépő különbségek közt, és ha nem hét, hanem csak hat számot választunk ki, akkor az 1, 3, 7, 11, 17, 19 példán látható, hogy már a 20-nál kisebb páratlan természetes számok közül is kiválasztható hat úgy, hogy különbségeik közt egy érték se lépjen fel háromszor.
3. A feladat állítása általánosítható úgy, hogy egyidejűleg növeljük a kiválasztható páratlan számok körét és a kiválasztandó számok számát. Ekkor a II. megoldás gondolatmenetével a következő általánosabb tétel látható be: Legyen k a 2-nél nagyobb egész szám. Ha bárhogy választunk is ki a 2k(k+1)+2-nél kisebb természetes számok közül 2k+1-et, van olyan érték, amelyik az ezek közt fellépő különbségek közt legalább háromszor előfordul.