Megoldások, megjegyzések a Héttusa 13. fordulójának feladataihoz

Beszámoló a 13. fordulóról

Ebben a fordulóban 17-en küldtek válaszokat, megoldásokat, összesen 109 helyes választ. 13-an adtak mind a 7 feladatra hibátlan választ. A táblázat fejléce a feladatok számát mutatja, a zöldre színezett cellák pedig a jó válaszokat.

Fordulónként a legjobb megoldók közül néhányan könyvjutalmat kapnak. A legújabb jutalmazottak Hornung Tamás és Udvari Tibor, ők a Typotex kiadó alábbi könyveit választották:

• Gindikin: Történetek fizikusokról és matematikusokról
• Keszthelyi Gabriella: Milyen színű a valószínű?

A feladatokra most is szép és tanulságos megoldásokat küldött Dombi Péter, ezeket érdemes itt megnézni.

Alább pedig a többiek ötleteit, meggondolásait felhasználva ismertetjük a feladatokat, a helyes válaszokat és a hozzájuk vezető utat.

85. Egy kört 14 ponttal egyenlő ívekre osztottunk. Ezek a pontok párosával összeköthetők-e 7 db különböző hosszúságú húrral?

Válasz: Nem köthetők össze úgy, hogy 7 db különböző hosszúságú húrt kapjunk.

Udvari Tibor megoldása: Számozzuk meg körben 1-től 14-ig a pontokat. A húrokat is egy-egy számmal jelöljük meg. Mindegyik húr azt a számot kapja, ahány kis ívet tartalmaz a két végpontja által meghatározott rövidebbik ív. A 7 db húrt az 1, 2, 3, 4, 5, 6, 7 számoknak kell jellemeznie.

Az 1, 3, 5 és 7 húr két végpontjának egyike páros, másika páratlan számot visel. A 2, 4 és 6 húroknak a végpontjai azonos paritásúak. Tehát a négy páratlan számú húrhoz négy-négy páros, illetve páratlan sorszámú pont tartozik. A maradék három-három páros és páratlan sorszámú pontból kellene három olyan párt alkotni, amelyek azonos paritásúak. Ez nem lehetséges, tehát a húrok a kívánt módon nem köthetők össze.

Ugyanezzel a gondolatmenettel igazolható, hogy 4, 6, 12, 14, 20, 22, … pont esetén nem kaphatunk semmilyen párosítással különböző hosszúságú húrokat. A 8, 10, 16, 18, 24, 26… darab pont esetén elvileg igen. A felsorolt hat esetre ténylegesen találtam is megfelelő párosítást (programmal).

8 pont: 1–2, 3–6, 4–8, 5–7 párok

10 pont: 1–2, 3–6, 4–8, 5–10, 7–9 párok

16 pont: 1–2, 3–5, 4–9, 6–12, 7–14, 8–16, 10–13, 11–15 párok

18 pont: 1–2, 3–5, 4–8, 6–13, 7–15, 9–18, 10–16, 11–14, 12–17 párok

24 pont: 1–2, 3–5, 4–7, 6–11, 8–17, 9–19, 10–21, 12–24, 13–20, 14–18, 15–23, 16–22 párok

26 pont: 1–2, 3–5, 4–7, 6–10, 8–17, 9–19, 11–22, 12–24, 13–26, 14–20, 15–23, 16–21, 18–25 párok

Megjegyzés: Dombi Péter általánosan is bizonyítja, hogy egy szabályos \(2m\)-szög csúcsait csak akkor lehet párokba állítani különböző hosszúságú húrokkal, ha \(m = 4k\), vagy \(m = 4k + 1\) (\(k=1, 2,\dots\)). Be lehet bizonyítani, hogy ez a feltétel elégséges is.

86. Felföldön a királyság térképén minden tartomány konvex alakú. Biztos-e, hogy a térkép kiszínezhető 3 színnel úgy, hogy a közös határú tartományok színe különböző?

Válasz: Nem, mert van olyan térkép, amely nem színezhető 3 színnel.

Megoldás. Ha egy tartományt páratlan számú tartomány vesz körbe, akkor a színezéshez kell 4 szín, hiszen a környező területek két színnel nem színezhetők, kell ehhez három szín, és a középső tartományhoz egy újabb szín.

Megjegyzések. Ezekben a példákban mindegyik tartománynak páratlan számú szomszédja van. Ha minden tartomány páros számú tartománnyal szomszédos és minden csúcsban három él találkozik, akkor kiszínezhető-e a térkép 3 színnel?

A Héttusa 2. feladatának kérdése ez volt: Egy asztallapra 11 egybevágó fehér korongot helyeztünk úgy, hogy a korongok között nincs átfedés. Igaz-e, hogy a korongokat mindig kiszínezhetjük úgy 3 színnel, hogy az egymással érintkező korongok különböző színűek?

Ez nehéz kérdés volt, kevesen adtak helyes választ. A válasz nem, mert van olyan elrendezés, amelyhez kell 4 szín.

Korongok helyett egybevágó négyzetlapokra is igaz, hogy 11 négyzetlap elrendezhető úgy, hogy színezésükhöz szükség van 4 színre.

87. Készítünk egy egész számokból álló sorozatot, a kiinduló szám a 13. A sorozatban a következő számot mindig úgy kapjuk, hogy a legutóbbi számhoz vagy 9-et adunk, vagy ha van, letöröljük a szám egyik 1-es számjegyét, és ha egy ilyen törlés után a szám elején néhány nulla áll, azokat is töröljük. Megkaphatjuk-e a 137-et egy ilyen sorozatban?

Válasz: Igen, megkaphatjuk.

Izsák Beatrix megoldása: \(137=15\cdot9+2\), tehát a 2-t kell előállítani, és azután 15-ször egymás után a 9-et hozzáadni. Ha a kiinduló szám a 13, letöröljük az 1-est, majd a kapott 3-hoz 9-et adunk, a kapott 12-ből letöröljük az 1-est és ezután 9-et adunk hozzá 15 lépésen keresztül, így eljutunk a 137-hez.

A legtöbb esetben is ez a megoldás érkezett: \(13\to 3\to 12\to 2\to 11\to 20\to\cdots\to128\to137\).

Sógor Tamás megoldása: Vegyük észre, hogy 11 darab 9-es hozzáadásával a szám 99-cel nő, tehát a 13-ból eljuthatunk a 112-be. Ekkor törölve a százas helyiértéken álló 1-est, a 12-es számot kapjuk.

Ezután ismét 11 darab 9-es hozzáadásával 111-hez jutunk, amelyből törölve a százasok helyén álló 1-est, a 11-et kapjuk.

Mivel a 11 és a 137 ugyanazt a maradékot adják 9-cel osztva (mindkettő 2 maradékot), így a 11-ből 14-szer ismételten 9 hozzáadásával elérjük a 137-et.

Vargáné Kis Anna példája: \(13+1262\cdot 9=11371\), és a 11371-ből a két szélső 1-es törlésével megkapjuk a 137-et.

Kallós Béla példája: \(13+1236\cdot9=11137\), és a 11137-ből két 1-es törlésével megkapjuk a 137-et.

Makay Géza belátja, hogy minden nemnegatív egész szám megkapható:

Vegyük észre, hogy ha már megkaptunk egy számot, akkor az összes annál nagyobb, 9-cel ugyanazt a maradékot adó számot is megkaphatjuk 9-ek hozzáadásával. Így csak azt kell belátni, hogy megkaphatjuk a 0, 1, 2, 3, 4, 5, 6, 7, 8 számokat. Kiindulva a 13-ból kaphatjuk a következő sorozatot: \[\displaystyle 13, 3, 12, 2, 11, 1, 0, 9, 18, 8, 17, 7, 16, 6, 15, 5, 14, 4, 13.\] Ebben a sorozatban benne van az összes „szükséges” szám, a 9-cel való osztás összes lehetséges maradéka. Belátható az is, hogy bármilyen számból kiindulhatunk, akkor is megkaphatjuk az összes nemnegatív egészet: például adjunk addig 9-et a számhoz, amíg csupa 1-essel nem kezdődik, legfeljebb az utolsó számjegy nem 1-es, és onnan az egyeseket elhagyva egyjegyű számot kapunk, ami a fenti sorozat alapján (mivel az periodikus) produkálni tudja az összes lehetséges 9-cel való osztási maradékot.

Deli Ádám általánosan, \(b\) alapú (\(b\geq2\)) számrendszerben bizonyítja, ha a két lehetséges lépés az 1-es törlése vagy \(b-1\) hozzáadása a számhoz, akkor bármely pozitív egész számtól indulva eljuthatunk bármely más pozitív egészhez.

Végül egy szép trükk: Hogyan lehet az \(n\) számból kiindulva az \(n+1\) számhoz eljutni ilyen lépésekkel? Például legyen \(n=23\). Az \(n+1=24\) elé írjunk 8 db 1-est: \(A=1111111124\). Ekkor \(n\) és \(A\) ugyanazt a maradékot adja 9-cel osztva, tehát \(n\)-ről 9-es lépésekkel eljutunk \(A\)-ig. Az \(A\) számból töröljük az 1-eseket, és megkapjuk az \(n+1\) számot.

88. Bence választott néhány egymást követő pozitív egész számot, és ezeket valamilyen sorrendben leírta egymás után. Ezután kiszámolta a szomszédos számpárok legnagyobb közös osztóját, és csupa különböző számot kapott. Legfeljebb hány számot választhat Bence?

Válasz: 5.

Az 5 el is érhető, pl. 10, 8, 12, 9, 11; vagy 22, 20, 24, 21, 23.

Kallós Béla megmutatja, hogy 6 számot már nem tudunk megadni. Tegyük fel, hogy van 6 megfelelő szám, \(a\), \(a+1\), \(a+2\), \(a+3\), \(a+4\), \(a+5\). Mivel két szám legnagyobb közös osztója osztja a két szám különbségét, ezért csak úgy kaphatunk csupa különböző számot a szomszédos számpárok legnagyobb közös osztóit kiszámolva, ha azok pontosan 1, 2, 3, 4, 5. Csak a két szélső legnagyobb közös osztójaként kaphatunk 5-öt: \((a,a+5)=5\). Emiatt ezek paritása különböző, és ez a két szám a sorrendben szomszédos lesz.

Ha a páros, akkor a 4 csak \((a,a+4)=4\) esetén fordulhat elő, tehát a sorban a másik oldalán lesz \(a+4\). A 2 előállításához fel kell használnunk az \(a+2\) számot és ezt csak \(a+4\) másik oldalára tehetjük. Tehát ezek a számok így következnek egymás után (esetleg fordított sorrendben): \[\displaystyle a+2,\quad a+4,\quad a,\quad a+5.\] A 3-at viszont ekkor már nem tudjuk előállítani, mert az \(a+1\) és \(a+3\) közül bármelyiket írjuk az eddigi sor bármelyik végébe, a 3 már nem állhat elő szomszédos számok legnagyobb közös osztójaként.

Ha \(a\) páratlan, akkor a mellette álló \(a+5\) páros, és a 4-et közös osztóként csak az \(a\), \(a+5\), \(a+1\) sorrend biztosítja. A közös osztó 2 csak úgy lehet, ha a harmadik páros szám, az \(a+3\) az előbbi sorrend végére kerül: \(a\), \(a+5\), \(a+1\), \(a+3\). A 3-at viszont ekkor már nem tudjuk előállítani, mert az \(a+2\) és \(a+4\) közül bármelyiket írjuk az eddigi sor bármelyik végébe, a 3 már nem állhat elő szomszédos számok legnagyobb közös osztójaként.

Lehet-e 6-nál több szám? Ahogy a sorozat hossza nő, úgy nőnek a számok sorrendjére vonatkozó kényszerek: a párosak egy kupacban, a 3-mal oszthatók sem mehetnek távolra, és így tovább (Turchányi Gyula).

Makay Géza bizonyítása: \(n\) darab egymást követő szám páronkénti különbségei az \(1, 2, \cdots, n-1\) számok lehetnek. A legnagyobb közös osztók értéke legfeljebb \(n-1\), és \(n\) darab szám esetén a szomszédos számpárok száma \(n-1\), ezért, ha a legnagyobb közös osztók különbözőek, akkor pontosan ezeknek a számoknak kell a legnagyobb közös osztóknak lenniük. Egy kis kísérletezéssel az ember találhat lehetséges megoldásokat, például: \[\displaystyle 5, 3, 6, 4\qquad 7, 9, 6, 8\qquad 9, 12, 8, 10, 11\qquad 23, 22, 20, 24, 21\] Azt akarjuk belátni, hogy ötnél több egymás utáni számmal nem lehet megoldani a feladatot.

Először is vegyük észre, hogy páros \(n\) esetén \(n\) egymást követő szám között pontosan \(n/2\) páros van, a legnagyobb közös osztók között pedig \(n/2-1\), így a páros számoknak a sorrendben egymás után kell szerepelniük, hogy kiadják ezeket a legnagyobb közös osztókat. Ugyanez igaz páratlan \(n\)-re is, hiszen ott legfeljebb \((n+1)⁄2\) páros számunk van, de azoknak ki kell adniuk az \((n-1))⁄2\) páros legnagyobb közös osztót.

A következő levezetésekben mindig az a cél, hogy bebizonyítsuk, van három olyan páratlan legnagyobb közös osztó, amelyek csak egy páros és egy páratlan szám legnagyobb közös osztójaként állhatnak elő. Ekkor ugyanis ellentmondásra jutunk, mert ennek a három párnak már nem lesz helye, mivel a páros számok egy blokkban vannak.

\(n=10\)-re és \(n\geq 12\)-re a három legnagyobb \(n\)-nél kisebb páratlan számmal pontosan két számnak kell oszthatónak lennie \(n\) egymást követő szám sorozatában, amelyek közül az egyik páros és a másik páratlan, így a fentiek alapján ilyen \(n\)-ekre nincs megoldás.

\(n=11\)-re – mivel az egyik lnko a 10, így kell, hogy legyen két egymás melletti 10-zel osztható szám, így a megmaradó páratlan, 5-tel osztható szám valamelyikkel szomszédos kell legyen. 9-cel és 7-tel osztható számból pedig 11 egymást követő között csak kettő van.

\(n=8\), 9-re hasonlóképpen kell, hogy legyen két egymás melletti 6-tal osztható szám, így a megmaradó páratlan, 3-mal osztható szám valamelyikkel szomszédos kell legyen. 7-tel és 5-tel osztható számból pedig megint csak kettő van.

\(n=6\) és \(n=7\) esetén a legnagyobb közös osztókban a 2 prímtényező legfeljebb második hatványon, a 3 és 5 első hatványon szerepel. Ezért, ha van egy szám \(n\)-es megoldás, akkor annak a \(4\cdot3\cdot5=60\)-nal való eltoltja is megoldás. Elegendő tehát ellenőrizni, hogy ha a számaink 1-gyel, vagy 2-vel, …, vagy 60-nal kezdődnek, akkor az ad-e megoldást. Ráadásul nem is kell ellenőrizni az összes ilyen esetet. \(n=6\) esetén a legkisebb és legnagyobb számnak 5-tel, a kettő közül az egyiknek 4-gyel oszthatónak kell lennie, így maradnak a következő esetek: \[\displaystyle 15 – 20,\quad 20 – 25,\quad 35 – 40,\quad 40 – 45,\quad 55 – 60,\quad 60 – 65.\] A páros számok és az 5-tel osztható számok miatt mindegyikben kényszerűen bizonyos számok sorrendje adott: \[\displaystyle \begin{array}{c@{\qquad\qquad\qquad}c@{\qquad\qquad\qquad}c} 15,\,20,\,16,\,18\qquad & 25,\,20,\,24,\,22\qquad & 35,\,40,\,36,\,38 \\[1ex] 45,\,40,\,44,\,42\qquad & 55,\,60,\,56,\,58\qquad & 65,\,60,\,64,\,62 \end{array} \] Minden esetben azt kapjuk, hogy a 3-mal osztható számok a sorozat szélén vannak, így már nem párosíthatóak, vagy az egyik 3-mal osztható szám a sorozat belsejében van, a másik még nem szerepel a sorozatban, és ezért nem párosíthatóak.

\(n=7\)-re hasonló módon csak a következő eseteket kell ellenőrizni: \[\displaystyle 24 – 30,\qquad 30 – 36,\qquad 54 – 60,\qquad 60 – 66.\] Itt is kényszerhelyzetben vagyunk bizonyos számokkal: \[\displaystyle 26, 28, 24, 30, 27\qquad 33, 30, 36, 32, 34\qquad 57, 54, 60, 56, 58\qquad 62, 64, 60, 66, 63\] Mindegyik esetben teljesül, hogy a még kimaradt 5-tel osztható páratlan szám már nem párosítható össze a másik 5-tel osztható páros számmal, mert az a sorozat belsejében van.

Összefoglalva: legfeljebb 5 egymást követő számot lehet a feltételeknek megfelelően sorba rendezni.

Udvari Tibor bizonyítása: Legfeljebb 5 számot választhat Bence.

A gondolatmenet vázlatosan: A kiválasztott \(n~\text{db}\) szám legyen \(a_1\), \(a_2\), \(a_3\), \(\cdots\), \(a_n\). Ezek \(n-1~\text{db}\) párt, azaz ennyi legnagyobb közös osztót határoznak meg. Két szám legnagyobb közös osztója legfeljebb akkora lehet, mint a két szám különbsége. Tehát pontosan az \(1,2,\cdots, n-1\) számokat kell kapni legnagyobb közös osztókként. Feltételezhetjük, hogy a továbbiakban mindig \(a_1\), \(a_3\), \(a_5\), \(\cdots\) a páros számok. (Ha nem így van, a szimmetria miatt a gondolatmenet nem változik, csak az indexek.)

Páros legnagyobb közös osztó csak két páros számnál lép fel. Ha \(n\) páros (\(n=2k\)), akkor a kiválasztottak között \(k\) darab páros szám van. Ezek \(k-1\) darab páros legnagyobb közös osztót (\(2,\,4,\,\cdots,\,n-2\)) állítanak elő. Ez csak úgy lehet, ha a páros számok egymás mellett, egy csoportban vannak az átrendezés után. Ha \(n\) páratlan (\(n=2k+1\)), akkor vagy \(k\), vagy \(k+1\) darab páros szám van a kiválasztottak között. De ilyenkor \(k\) darab páros legnagyobb közös osztót kell előállítani, tehát csak a \(k+1\) jöhet szóba. Most is csak úgy lehet, ha a páros számok egy csoportban vannak az átrendezés után.

Az \(n-1\), mint legnagyobb közös osztó csak akkor léphet fel, ha \(a_1\) és \(a_n\) egymás mellett vannak. Ha \(n\) páros, az \(a_n\) páratlan. Az \(n-2\) (páros) legnagyobb közös osztóhoz \(a_1\) és \(a_{n-1}\) szomszédsága kell. Tehát a sorrend egy része \(a_{n-1}\), \(a_1\), \(a_n\). Az \(n-3\) (páratlan) legnagyobb közös osztóhoz vagy \(a_{n-1}\) és \(a_2\), vagy \(a_n\) és \(a_3\) szomszédsága kell. De \(a_{n-1}\) páros, \(a_2\) páratlan szám, így nem lehet egy csoportban az összes páros szám, kivéve, ha csak \(a_1\) és \(a_{n-1}\) az összes. Ez \(n=4\) esetén lehet. A másik lehetőségnél \(a_n\) kettévágja a páros számok csoportját, hiszen \(a_n\) páratlan, \(a_3\) páros. Tehát ez sem lehet. Páros \(n\) esetén legfeljebb 4 szám választható ki úgy, hogy valamely sorrendjükkel csupa különböző legnagyobb közös osztót kapjunk. Az \(n=4\) esetében adhatja a 3, 2, 1 legnagyobb közös osztókat például a 3, 6, 4, 5 számsorrend.

Ha \(n\) páratlan, akkor az \(a_1\) és \(a_n\) egyformán párosak. Most is szomszédosak, hogy lehessen \(n-1\), mint legnagyobb közös osztó. Az \(n-2\) (páratlan) legnagyobb közös osztóhoz vagy \(a_{n-1}\) és \(a_1\), vagy \(a_n\) és \(a_2\) szomszédsága kell. Tehát az \(a_{n-1}\), \(a_1\), \(a_n\), illetve \(a_1\), \(a_n\), \(a_2\) sorrendek jöhetnek létre. Az \(n-3\) (páros) legnagyobb közös osztóhoz \(a_2\), \(a_{n-1}\), \(a_1\), \(a_n\), vagy \(a_{n-1}\), \(a_1\), \(a_n\), \(a_3\), illetve \(a_{n-2}\), \(a_1\), \(a_n\), \(a_2\) vagy \(a_1\), \(a_n\), \(a_2\), \(a_{n-1}\) sorrend kellene. Közülük az első és az utolsó tartalmazza az \(a_2\), \(a_{n-1}\) párt, de két páratlan számnak nem lehet páros legnagyobb közös osztója. Az \(n-4\) (páratlan) legnagyobb közös osztóhoz a maradék két sorrend mindkét végén a másik végén levő számot kellene beírni, amit nem tehetünk meg, kivéve, ha \(n-4\) éppen 1. Ez esetben (\(n=5\)) a 3, 4, 2, 1 legnagyobb közös osztókat adhatja például a 9, 12, 8, 10, 11 számsorrend.

89. Egy \(4\times 4\)-es sakktáblán minden mezőn áll egy bástya. Egyesével levehetjük őket, mindig olyan bástyát, amelyik páratlan számú bástyát tart ütés alatt. Legfeljebb hány bástyát lehet így leszedni a tábláról?

Válasz: Legfeljebb 11 bástyát vehetünk le.

Udvari Tibor megoldása: Legalább négy bástya mindenképpen marad, mert a sarkokban levő bástyák mindig két másikat tartanak ütés alatt, ezért nem vehetők le a tábláról. Azonban nem maradhat csak ez a négy. Ha lenne olyan lépéssorrend, ami után csak ezek maradnak, akkor az utoljára levett bástya csak olyan helyen lehetett, ahonnan a négy sarokbástya közül vagy kettőt, vagy egyet sem tartott ütés alatt. Így viszont le sem vehettük volna. Tehát legalább 5 bástyának kell maradnia, azaz legfeljebb 11 vehető le a tábláról. Ilyen lépéssorrendet meg is lehet adni (a számok a levett bástya által ütésben tartott bástyák számát mutatják).

Deli Lajos megjegyzése: Érdekes lehet az a módosítás, hogy mennyi a lehető legtöbb bástya, ahány fent maradhat, s ezt hány különböző helyzet valósíthatja meg? (Esetleg hány különböző lépéssorozattal érhető el?)

Hasonló kérdés a Héttusa 9. feladata: Marci bástyákat rak egy üres sakktáblára. Az első bástyát bárhová teheti, ezután minden újabb bástyát úgy tesz le, hogy az páratlan számú korábban elhelyezett bástyát tartson ütés alatt. Legfeljebb hány bástyát helyezhet a táblára Marci?

90. A 7-es totón hét különböző jegyből álló számmal lehet részt venni. A sorsoláson egy ilyen, hét különböző jegyből álló számot sorsolnak. Egy tipp akkor nyertes, ha az a szám valamelyik számjegyében megegyezik a kisorsolt számmal. Ha például 0123456 a tipp, és a kisorsolt szám 1234567, akkor ez a tipp nincs a nyertesek között, míg a 9876543 egy nyertes tipp. Egy játékos több számmal is játszhat.

Van-e 7 olyan tipp, amelyek között biztosan lesz nyertes is?

Válasz: Igen, van 7 ilyen tipp.

Koncz Levente megoldása: Mivel 7 különböző számjegyből áll a kisorsolt szám, biztosan előfordul benne a 0, 1, 2 vagy 3 közül legalább az egyik. A következő 7 tipp ezt a négy számjegyet mindegyik lehetséges helyiértéken tartalmazza, tehát legalább az egyik közülük nyertes lesz: \[\displaystyle \begin{gather} 0123456,\\ 6012345,\\ 5601234,\\ 4560123,\\ 3456012,\\ 2345601,\\ 1234560. \end{gather}\] (Többet is mondhatunk. A sorsolt szám 7 jegye közül legalább 4 olyan van, amely szerepel a 0, 1, 2, 3, 4, 5, 6 között, így biztosan el fogjuk találni legalább 4 számjegy pontos helyét a tippjeinkben. Persze lehet, hogy ezek legalább 4 különböző tippben szerepelnek, de az is lehet, hogy lesz egy legalább 4 találatos szám.)

Berkó Erzsébet megmutatta, hogy már 6 megfelelő tipp között is biztosan lesz nyertes: \[\displaystyle \begin{gather} 0123456,\\ 1234507,\\ 2345018,\\ 3450129,\\ 4501236,\\ 5012347. \end{gather}\] A kisorsolt szám első 5 jegye között van 0 és 5 közötti valahol (beleértve a 0-t és az 5-öt is), hiszen rajtuk kívül csak 4 számjegy van (6, 7, 8 és 9) erre az öt helyre. Bárhol is van ez a számjegy, az egyik tipp nyertes lesz.

91. Egy boszorkány fogságba ejtett hat törpét, és ezt mondta nekik:

„Van hét különböző színű sapkám, a szivárvány hét színében. Holnap reggel bekötöm a szemeteket, majd a fejetekre teszek egy-egy sapkát, és ezután leveszem a kötést a szemetekről. Mindenki látja a többiek fején lévő sapkát, de nem látja a sajátját. Egymásnak nem adhattok segítséget a sapkák színéről. Mindenki leírja egy cédulára azt a tippet, hogy milyen színű sapka van a fején. Ha legalább három válasz helyes, akkor szabadon engedlek benneteket, különben itt maradtok örökre.”

A törpék kitalálhatnak-e olyan módszert, amely biztosan sikerre vezet, vagy ez reménytelen?

Válasz: Van olyan módszer, ami biztosan sikerre vezet.

Deli Ádám megoldása: Igen, biztosan van sikerre vezető módszer. Alakítsunk ki 3 párost a törpékből. Egy adott párnál mindenki megnézi a másik két párban a 4 törpe sapkáját, így a 7 színből marad 3 szín.

Előző este beszéljék meg a színeknek egy rögzített sorrendjét. Ha a színek 1, 2, 3, 4, 5, 6, 7, akkor lehet a színsorrend: 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2…

Ha az egyik párosnál a kimaradt három szín 1, 2, 7, ezeket a sorrend szerint körbe rendezik, és mindkét törpe a partner fején látható szín rákövetkezőjét tippeli.

Ebből a három színből két szín a törpék fején van, a harmadik szín a boszorkány zsákjában maradt. A két törpe két különböző tippet ad, ezért az egyik hibázik, a másik tippje helyes.

Így a hat törpe 3 helyes és 3 hibás választ ad.

Ezt az eljárást Szemerédi Ferenc úgy találta meg, hogy megoldotta a 2 törpe – 3 sapka feladatot, és ezután adódott a megoldás a 6 törpe – 7 sapka feladatra.

Kallós Béla megoldása: Igen, van olyan módszer, amivel lesz három helyes válasz.

Jelöljük meg a színeket 1, 2, 3, 4, 5, 6, 7-tel.

Minden törpe 5 sapkát fog látni. Tehát a maradék két színből kell megtippelnie, hogy a fején milyen színű sapka van.

A módszer a következő:

Felírjuk egymás mellé kétszer a 7 db számot: 1 2 3 4 5 6 7 1 2 3 4 5 6 7. Egy törpe megnézi, hogy melyik két színből kell választania. Pl. legyen a két (általa nem látott) szín kódja 3 és 7. Megnézi, hogy legkevesebb hány lépéssel mehet át az egyik számból a másikba. 3-ból 7-be jobbra haladva 4 lépés, 7-ből 3-ba 3 lépés szükséges. A legrövidebb távolságnál (itt 3 lépés) a jobb oldali számot tippeli meg, azaz itt a 3-ast.

Ezzel a módszerrel 3 jó és 3 rossz tippjük lesz a törpéknek. Legyen pl. a fel nem használt sapka színe 3. Ekkor lesz két törpe, akik a (2, 3) és (3, 4) színeket nem látják. Az első rossz tippet fog megadni (2-es van rajta, de a módszer alapján 3-ast tippel), a második jót (4-es van rajta, és a módszer alapján 4-est is tippel). Hasonlóan az (1, 3) és (3, 5), illetve a (7, 3) és (3, 6) párosoknál az egyik törpe helyesen tippel, a másik nem.

Udvari Tibor megoldása: Van olyan módszer, ami biztosan sikerre vezet.

A hét szín sorba rendezhető a szivárványban elfoglalt helye alapján. Számozzuk meg a színeket az 1, 2, 3, 4, 5, 6, 7 számokkal. A törpék mindegyike öt színt lát. Előre megállapodnak abban, hogy mindegyik törpe összeadja az általa nem látott két szín számait. Akinél az összeg páros, az a kisebbik számnak megfelelő színt, akinél az összeg páratlan, az a nagyobbik számnak megfelelő színt írja a cédulára.

Például a boszorkány nem használja fel a 4-es színt, a törpék fejére pedig rendre a 6, 2, 3, 7, 5, 1 színű sapkákat teszi. A hat törpe összege sorban 10, 6, 7, 11, 9, és 5 lesz. A mondott színek pedig ez alapján 4, 2, 4, 7, 5 és 4. Tehát hárman eltalálják a saját sapkájuk színét.

Legyen ugyanis a kihagyott szín száma a \(k\). Ez két csoportra osztja a többi színt (az egyik lehet üres is). Lesz \(k-1\) darab nála kisebb sorszámú és \(7-k\) darab nála nagyobb sorszámú szín. Mindkét darabszám páros, ha \(k\) páratlan szám és mindkettő páratlan, ha \(k\) páros szám. Az első esetben ugyanannyi páros és páratlan szám található mindkét csoportban. Tehát mindkét csoportban megegyezik a jó és a hibás tippek száma, ezért együttesen is. Ekkor a hat törpe három jó tippet ír összesen a cédulákra. A második esetben mindkét csoportban eggyel több páratlan szám lesz, mint páros. Ezért a kisebb számok csoportjában eggyel kevesebb lesz a jó tipp, mint a rossz, a nagyobb számok csoportjában pedig fordítva. Együtt tehát most is megegyezik majd a jó és rossz tippek száma, ekkor is három jó tipp kerül a cédulákra.

Megjegyzés: Általában ha a színek száma 7 helyett egy \(n\) páratlan szám (de legalább 3) és a törpék száma \(n-1\), az eljárás biztosítja, hogy a törpék fele helyesen tippelje meg a sapkája színét. Ha \(n\) páros, akkor \((n-2)⁄2\) helyes tippet biztosít az eljárás. (Például 8 szín és 7 törpe esetén is három találat lesz biztos, bár előfordulhat négy találat is, a kihagyott színtől függően.)

A megoldásokat közölte: Róka Sándor