„KAVICS TANÁR ÚR” PÁLYÁZAT

A Fővárosi Fazekas Mihály Gyakorló Általános Iskola és Gimnázium

egykori, iskolát alapító tanára,

KŐVÁRY KÁROLY

„KAVICS”

emlékére a 2003/4-es tanévben kiírt

matematikai pályázata feladatainak megoldása
(A megoldásokat folyamatosan tesszük fel az oldalra)

A pályázat feladatai közül az első kettőt Kavics egy feladatgyüjteményéből vettük, a 3. és 4. feladatot Elekes György, az 5. és 6. feladatot Bali János, a 7-9. feladatot Surányi László, a 10-13. feladatot Ruzsa Imre, a 14. feladatot Hraskó András, az utolsó két feladatot Beleznay Ferenc javasolta.

1. feladat: Az AB átmérőjű O középpontú félkör egy pontja P. P vetülete az AB szakaszon Q, az AB ív felezőpontja C, QC és OP egyenes R-ben metszi egymást. Mi R mértani helye, ha P befutja a félkört?

MEGOLDÁS: Jelöljük T-vel az R pont vetületét az AB átmérőn, húzzunk továbbá párhuzamost C-n keresztül az AB átmérővel, és legyen R vetülete ezen az e egyenesen S. Belátjuk, hogy RS=RO, tehát az R pont egyenlő távol van az O középponttól és az e egyenestől. Ez azt jelenti, hogy rajta van azon az O fókuszú parabolán, amelynek vezéregyenese az e egyenes.

Állításunk igazolásához nyilván elég belátni, hogy az TR és az PR szakaszok egyenlő hosszúak, hiszen OP sugár és ST szakasz hossza egyenlő a vele párhuzamos OC sugárral.

Az RPQ és ROC háromszögek hasonlóak (két oldalegyenesük azonos, a harmadik pedig párhuzamos), ezért PR/RO=PQ/OC, s mivel OP is sugár, az utóbbi arány megegyezik a PQ/OP aránnyal is. Utóbbi viszont az OPQ és az ORT háromszögek hasonlósága miatt egyenlő az RT/RO aránnyal. Azt kapjuk, hogy a PR/RO arány egyenlő az RT/RO aránnyal, tehát PR=RT, s épp ezt akartuk igazolni.

Beláttuk tehát, hogy a P pont rajta van az O fókuszú, e vezéregyenesű parabolán, s nyilván annak a kör belsejébe eső ívén van. Be kell még látnunk, hogy ennek az ívnek minden pontja jó. Ehhez elég meggondolnunk, hogy minden OP félegyenesen pontosan egy R pont megfelelő, ez rajta van a parabolaíven és az OP félegyenesen is. Márpedig a parabolának és a félegyenesnek csak egy metszéspontja van. Tehát a parabolaív minden pontja előáll R pontként.

Mint a bevezetőben említettük, az első két feladat Kavics feladatgyüjteményéből származik.
A feladatra több megoldás is érkezett, ezek közös jellemzője, hogy koordinátarendszerbe "tették" a feladatot és kiszámolták R pont koordinátáit. (A koordinátarendszer kezdőpontját nyilván O-ban érdemes felvenni, feltehető, hogy a kör sugara egységnyi, végül nyilván érdemes az adott átmérő egyenesét az x-tengelynek választani.) A feladat így is megoldható, de Kavics feladatainak éppen az a szépsége, hogy bár van "számolós" megoldásuk, egy aránylag egyszerű, de szép geometriai ötlettel gyorsan megoldhatók. Erre példa a következő feladat is, amelyre szintén kizárólag hosszú, "számolós" koordinátageometriai megoldások érkeztek. Pedig, mint látni fogjuk, ennek is van egyszerű elemi geometriai megoldása.

2. feladat: A k kör AB átmérőjének egy kijelölt pontja P. Szerkesztendő az a P-n áthaladó CD húr, amelyre az ACBD húrnégyszög területe maximális.

MEGOLDÁS: Feltehetjük, hogy a kör sugara egységnyi. Jelöljük a kör középpontját O-val, C és D merőleges vetületét az AB átmérőn C’-vel és D’-vel. Az ACBD húrnégyszög területe éppen CC’ + DD’. Másrészt az OCD háromszög területe éppen OP/2-szerese ennek az összegnek. Mivel OP hossza állandó, ezért elég az OCD háromszög területét maximalizálni. Azt a legnagyobb területű (OCD) háromszöget keressük tehát, amelynek egyik csúcsa a kör középpontja, a vele szemben levő oldal pedig átmegy a P ponton. Az OC és OD oldalak hossza egység, tehát e háromszög területe, OC OD sin COD akkor maximális, ha sin OCD maximális, vagyis ha a COD szög a lehető legközelebb van a derékszöghöz. Két eset van:

1. Ha P elég távol van O-tól, akkor van olyan CD húr P-n keresztül, amely a középpontból derékszögben látszik. Az ilyen húr távolsága a kör középpontjától megegyezik az egységoldalú derékszögű egyenlőszárú háromszög magasságának hosszával, ami 1/2^1/2. Ha tehát OP nagyobb, mint 1/2^1/2, akkor van ilyen megoldás. Ezt a következőképpen szerkesztjük meg: szerkesztünk egy tetszőleges OC’D’ egységoldalú derékszögű egyenlőszárú háromszöget, ennek átmérőjén megszerkesztjük azt a (két, az átmérő felezőpontjára tükrös) Q pontot, amelynek a távolsága az adott - 1/2^1/2-nél nagyobb - OP. Ezután a háromszöget elforgatjuk O körül QOP szöggel. A kapott OCD háromszög C és D csúcsa lesz a keresett ACBD maximális területű húrnégyszög két hiányzó csúcsa. A feladatnak két megoldása van, kivéve az OP=1/2^1/2 esetet, amikor a két Q pont és így a két megoldás egybeesik.

2. Ha az OP távolság kisebb 1/2^1/2-nél, akkor a COD szög nem lehet derékszög, csak tompaszög. Ebben az esetben a lehető legközelebb kell lennie a derékszöghöz, vagyis a lehető legkisebbnek kell lennie. Ez akkor teljesül, ha a CD szakasz a lehető legtávolabb van a középponttól. Márpedig a CD szakasz átmegy a P ponton, így a középponttól mért távolsága mindig legalább OP, és egyenlő akkor lesz OP-vel, ha CD merőleges OP-re, azaz az AB átmérőre. Ebben az esetben tehát a legnagyobb területű négyszöget úgy kapjuk, ha P-ben merőlegest állítunk az adott AB átmérőre, s ez metszi ki a körből a hiányzó két csúcsot.

3. feladat: A 101 kiskutya nagyon szeret birkózni. Ma már több, mint 500 pár mérte össze erejét (minden pár legfeljebb egyszer). Bizonyítsuk be, hogy kiválasztható közülük néhány (legalább hét) kutya úgy, hogy a kiválasztottak közül mindegyik legalább hat másik kiválasztottal birkózott.

MEGOLDÁS: Elképzelhető, hogy kiválaszthatjuk az összes kiskutyát: ez akkor fordul elő, ha bármelyik kiskutya birkózott már legalább hat másikkal. Ebben az esetben nincs is mit bizonyítanunk.

Ha viszont van olyan kiskutya, amelyik csak legfeljebb öt másikkal birkózott, akkor hagyjuk el őt. Ismét elképzelhető, hogy a maradó kiskutyákat már mind kiválaszthatjuk, és ez ismét akkor fordul elő, ha a maradó kiskutyák közül már mindenki legalább öt másikkal birkózott. Ebben az esetben ismét nincs mit bizonyítanunk. Ellenkező esetben a maradó száz kiskutya között is van legalább egy, amelyik csak öt másikkal birkózott. Hagyjuk el őt, és folytassuk ezt az eljárást, amíg lehet. Két eset van: vagy valamelyik lépésben azt találjuk, hogy a maradó kiskutyák közül mindenki legalább hat másikkal birkózott, vagy elfogynak a kiskutyák. Előbbi esetben nyilván legalább hét kiskutya maradt (különben egyikük sem birkózhatott volna legalább hat maradó kiskutyával), s ekkor a feladat állítása igaz. Nézzük, lehetséges-e az utóbbi eset, tehát hogy elfogynak a kiskutyák. Az először elhagyott kiskutya csak legfeljebb öt másikkal birkózott, a második is, és így tovább, egészen a kilencvenötödikig. Ez eddig legfeljebb 95 . 5=475 birkózó párt jelent. A kilencvenötödik elhagyása után már csak hat kiskutya marad, ezek közül összesen tizenöt pár választható ki, tehát legfeljebb ennyi „mérkőzés” lehetett. Ez összesen is legfeljebb 490 mérkőzést jelent. Beláttuk tehát, hogy a feladat állítása mindenképpen igaz, ha a kiskutyák legalább 491 „birkózómérkőzést” lejátszottak.

MEGJEGYZÉS: A feladat valójában gráfelméleti feladat és azt mondja ki, hogy ha egy gráfnak százegy csúcsa és legalább 491 éle van, akkor van olyan feszített részgráfja, amelyben minden pont foka legalább hat. A fenti megoldás általánosabban is elmondható, százegy helyett n kiskutyára és hat helyett k+1 mérkőzésre. A fenti megoldás általában azt adja, hogy ha n kiskutya van és legalább (n–k)k + k(k–1)/2 + 1 „mérkőzést” játszottak, akkor kiválasztható közülük néhány (legalább k+1), hogy azok közül mindenki legalább k+1 másikkal „mérkőzött”. Gráfelméleti nyelven: ha egy gráfnak n csúcsa és több, mint nk – k(k+1)/2 + 1 éle van, akkor van olyan feszített részgráfja, amelyben minden pont foka legalább k+1.
A feladat közeli rokona egy korábbi versenyfeladatnak, lásd: Gráfelmélet I/30.

4. feladat: Az „abesszin makaó” nevű kártyajátékot hárman játsszák (a szabályok most nem fontosak). Egy kártya-klub tizenkilenc tagja egy este összesen ötszáz partit fejezett be. Bármely három ember legfeljebb egyszer játszott egymás ellen. Bizonyítsuk be, hogy kiválasztható közülük néhány (legalább hat) úgy, hogy a csak e kiválasztottak által játszott játékokra igaz legyen a következő:
Minden kiválasztotthoz van két másik kiválasztott, akikkel legalább két-két partit játszott.

A feladat megfogalmazásából nem egyértelmű, hogy mi van akkor, ha három kiválasztott játszott egymással egy partit: beleszámítjuk-e ezt is a két-két partiba, vagy sem. A beküldött megoldások általában ezt a játékot is beleszámították a két-két partiba. Így az ötszáz helyett lényegesen kevesebb parti mellett is igaznak bizonyult a feladat állítása. Mi most abban az esetben oldjuk meg a feladatot, amikor az ilyen hármasok nem számítanak bele a két-két partiba. Megmutatjuk, hogy még így is igaz az állítás ötszáznál jóval kevesebb parti esetén is.

A feladat bizonyos szempontból nagyon hasonlít az előzőre. A megoldása is hasonlít annak megoldására. Azt vizsgáljuk meg, összesen hány partit játszhattak, ha nem választható ki a feladat feltételének megfelelő csoport. Ha ők tizenkilencen nem felelnek meg a feladat feltételének, akkor van közöttük valaki, akihez nincs a társaságnak további két tagja, akikkel kétszer-kétszer kártyázott együtt. Legyen ez az ember A és tekintsük azt a G_A gráfot, amelynek csúcsai a társaság többi tagjai és két csúcs, B és C között akkor húzunk be élt, ha sor került az ABC hármas kártyapartijára. Ebben a gráfban nem lehet két harmadfokú pont, mert ha például B és C harmadfokú volna, akkor legfeljebb egyszer lehetnek egymással összekötve, tehát van még két-két szomszédjuk, legyenek ezek D és E, illetve F és G. Ez viszont azt jelenti, hogy a következő partikat lejátszották: ABD, ABE, ACF, ACG, ami ellentmond az A-ra tett kikötésünknek. Vagyis az A-hoz tartozó G_A gráfban tényleg nincs két harmadfokú pont. De ez azt jelenti, hogy egy hijján minden pontja legfeljebb másodfokú, míg a maradó pont lehet akárhanyadfokú. A gráfnak tizennyolc pontja van, tehát tizenhét csúcsa legfeljebb másodfokú, a maradó csúcsa legfeljebb 17-edfokú, ez összesen legfeljebb 51/2 él, s mivel az élszám egész, legfeljebb huszonöt él. Azt kaptuk, hogy ha A nem megfelelő, akkor legfeljebb huszonöt partit játszhatott.

Mielőtt azonban továbbmennénk, nézzük meg, mit ad a fenti gondolatmenet, ha egy n játékosból álló csoport nem felel meg a feladat feltételének. Ugyanígy azt kapjuk, hogy ha egy A' játékos nem felel meg, akkor a hozzá tartozó G_A gráfban legfeljebb egy kivétellel minden pont legfeljebb harmadfokú. Ez azt jelenti, hogy ennek a n–1 pontú gráfnak n–2 pontja legfeljebb másodfokú, a maradó pont legfeljebb n–2-ed fokú, azaz a gráfnak legfeljebb 1.5n–3 éle van, A' tehát legfeljebb ennyi partit játszhatott.

Most térjünk vissza a kiinduló helyzethez, Hagyjuk el A-t és ismételjük meg a gondolatmenetet a maradó társaságra. Ha ez a 18 tagú társaság nem felel meg a feladat feltételének, akkor a mondottak szerint van egy tagja, aki a többivel legfeljebb 24 partit játszott. Hagyjuk el őt is, a maradó 17 tagú társaság vagy megfelel, vagy egyik tagja legfeljebb 22 partit játszott. Ezt az eljárást folytatva vagy találunk egy megfelelő társaságot, vagy rendre találunk egy-egy tagot, aki az épp megmaradt társaság többi tagjával legfeljebb 21, 19, 18, 16, 15, 13, 12, 10, 9, 7, 6 mérkőzést játszott. Ez összesen 217 mérkőzés és marad egy öttagú társaság. Az öttagú társaság egymással összesen legfeljebb tíz partit játszhatott, a többi partit pedig összeszámoltuk. Ez összesen legfeljebb 227 mérkőzés. A feladat állítása tehát ötszáz helyett már 228 parti esetén is igaz.

A következő két feladatban olyan térbeli élhálózatot kell szerkeszteni, amelynek élei (merev) fapálcikák és (kifeszített) madzagok. A csúcsaiban egy madzagok és legfeljebb egy pálcika érintkezhet. (Fapálcikák nem érintkezhetnek.) Élek sehol másutt nem érintkezhetnek. Az élhálózatnak ennek ellenére merevnek kell lennie. itt oda vannak erősítve a velük érintkező pálcikákhoz és madzagokhoz. A madzagok a csúcsokban oda vannak erősítve egymáshoz és a pálcikához. A madzagok között nem lehet felesleges, tehát bármelyik madzagot meglazítva az élhálózat megszűnik merev lenni.

5. feladat: Szerkesszünk ilyen élhálót, amely 12 élből áll, ezekből három fapálcika, a többi madzag.

6. feladat: Szerkesszünk ilyen élhálót, amelyben minden pálcika mindkét végéhez pontosan négy madzag csatlakozik.

7. feladat: Jancsi és Pisti a következő játékot játssza: Jancsinak van tíz érméje, de nem tudja a súlyukat (az érmék nem feltétlenül azonos súlyúak). Pistinek van egy mérlege, amely pontos. Ha Jancsi odaad neki egy érmét, akkor Pisti megméri, majd megmondja, hogy mennyit mért a mérleg. Ám Pisti szeret kicsit hazudni. Megállapodnak, hogy csak tíz mérésnél hazudhat, de nem kell megmondania, hogy melyiknél hazudik. Mutassuk meg, hogy ha Jancsi csak 110 mérést kér, akkor Pisti elérheti, hogy Jancsi ne lehessen biztos minden érme súlyában, de ha Jancsi 120 mérést kér, akkor ügyesen játszva már megtudhatja minden érme súlyát.

MEGOLDÁS (PACH Péter Pál megoldása): Megmutatjuk, hogy Pisti még akkor is tud ügyesen hazudni, ha Jancsi 119 mérést kér, vagyis ha Pisti ügyesen válaszol, akkor Jancsi 119 kérdésből sem tudhatja meg mind a tíz érme pontos súlyát. Ezt Pisti elérheti úgy, ha "addig mond igazat, amíg csak lehet". Azaz a következőt teheti. Amíg Jancsi egy érme súlyát csak tízszer kérdezi, addig az igazi súlyt mondja. Csak akkor kezd figyelni, amikor egy érme súlyát Jancsi 11-edszer kérdezi. Az első kilenc ilyen érme esetében továbbra is a helyes választ adja. Viszont annak az érmének az esetében, amelyikre Jancsi utoljára kérdez rá 11-edszer, most tíz egyforma, de hamis választ ad. (Ez az érme is biztosan sorra kerül 11-edszer, hiszen Jancsi eddig még nem kaphatta hazugságon Pistit, így nem tudhatja, hogy az erre az érmére kapott tíz eredmény nem mind hamis-e.) Most a következő helyzet áll elő: Jancsi legalább 11-szer kérdez kilenc érmére, és legalább húszszor a tizedikre, ami legalább 119 kérdés. Az első kilenc érme esetében biztos lehet, hogy mindig a jó választ kapta, a tizedik érméről viszont még nem tud semmit, hiszen tíz-tíz egyforma választ kapott, s ezek közül bármelyik tíz lehet a jó válasz.

Most megmutatjuk, hogy ha Jancsi 120 választ kér, akkor ügyes stratégia esetén már biztosan megtudhatja minden érme súlyát. Tegye ugyanis a következőt. Vegye az első érmét és ennek a súlyát kérdezze Pistitől addig, amíg 11 egyforma választ nem kap. Ezt az érmét már félre teheti, hiszen tudja a súlyát. Tegyük fel, hogy h hamis választ kapott. Pisti most már csak 10–h esetben hazudhat. A második érmét tehát elég addig kérdeznie, amíg 11–h egyforma választ nem kap. A közben kapott hamis válaszok számát is levonja 10–h-ból.
Ezt az eljárást folytatja: számon tartja, hogy Pistinek még hányat "szabad" hazudnia, s a soron következő érmé súlyát addig kérdezi, amíg ennél egggyel több egyforma választ nem kap. A közben kapott hamis válaszok számát ismét elkönyveli.
Nézzük, hányat kell Jancsinak kérdeznie, amíg ezzel a módszerrel megtudja minden érme súlyát. Minden érmére legfeljebb 11-szer hallhat jó választ (legkésőbb ez után félre teszi), másrészt Pisti összesen legfeljebb tízszer hazudhat, s ez összesen legfeljebb 120 kérdés. Jancsi a megadott stratégiával tehát legkésőbb 120 lépésben megtudhatja az igazat minden érméjéről. (Előbb láttuk, hogy kevesebből nem tudhatja meg, ha Pisti is ügyesen hazudik.)

PAULIN Roland megjegyzése: Ugyanezzel a módszerrel mutatható meg, hogy ha Jancsinak n érméje van, Pisti h-szor hazudhat, és Jancsi ügyesen kérdez, akkor n(h+1)+h kérdéssel megtudhatja az érméi pontos súlyát, míg ennél kevesebb kérdés nem elég, ha Pisti ügyesen válaszol.

PACH Péter Pál megjegyzése: A megoldásban lényegesen használtuk, hogy Pisti nem hazudott, amikor megígérte, hogy csak tízszer fog hazudni. Ha ugyanis ez volt az első hazugsága, akkor sajnos semmit nem tudunk javasolni Jancsinak.

8. feladat: Változtatunk az előző játék feltételén: Jancsi most minden mérésnél egyszerre két érme súlyának az összegét méretheti meg, viszont Pisti csak egyszer hazudhat.
Mutassuk meg, hogy ha Jancsinak n=(2k – 1)² = 4k² – 4k + 1 érméje van, akkor 4k² – k + 1 méréssel megtudhatja minden érme súlyát.

Feltehetjük, hogy k legalább kettő, mert k=1 esetén nincs értelme a feladatnak.

I. MEGOLDÁS (PACH Péter Pál megoldása nyomán): Vegyük észre a következőt. Válasszunk ki páratlan számú, 2k – 1 érmét, és számozzuk meg őket nullától 2k – 2-ig, majd méressük meg az egymás utáni sorszámúakat, továbbá az utolsót és az elsőt is. Ha minden mérésnél helyes eredményt mond Pisti, akkor minden érme súlyát pontosan kiszámolhatjuk. Például a nullás sorszámúét kiszámolhatjuk abból, hogy

2e₀ = (e₀ + e₁) – (e₁ + e₂) + (e₂ + e₃) – (e₃ + e₄) + ... – ... + (e_2k–2 + e₀).

Ebben a felírásban minden mérés pontosan egyszer szerepel. Ha tehát Pisti minden mérésnél a helyes eredményt mondja, akkor a nulla sorszámú érmére (és ugyanígy a többire is) pontos eredményt kapunk, ha viszont egynél hazudik (többnél nem hazudhat), akkor helytelen eredményt kapunk.
Ennek alapján a következőt javasoljuk Jancsinak. Válasszon ki egy E érmét, a többit ossza 2k darab egyforma, 2k – 2-es csoportba. Számozza meg minden csoportban az érméket egytől 2k – 2-ig és minden csoporthoz vegye hozzá az E érmét nullás sorszámmal. Méresse meg az azonos csoportbeli egymás melletti elempárokat, valamint az utolsót és E-t.
Ez eddig csoportonként 2k – 1 mérés, összesen 4k² – 2k mérés.
A fenti számolással minden érme súlyára kap egy eredményt, sőt az E érme súlyára minden csoportban kap egy eredményt. Vagy minden csoportban ugyanazt az eredményt kapja, vagy van pontosan egy csoport, ahol más eredményt kap, mint a többiben. (Több "rossz" csoport nem lehet, mert Pisti csak egyszer hazudhat. Megjegyezzük még, hogy legalább négy csoport van, mert k legalább kettő, ezért legalább három jó eredményt kap, így meg tudja állapítani, hogy melyik a rossz eredmény, ha van ilyen.) Ha minden csoportban ugyanaz az eredmény, akkor egyik csoportban sem lehetett hamis részeredmény (mert minden részeredményt pontosan egyszer használtunk), így ebben az esetben minden érme súlyát tudhatjuk. Ha van egy rossz eredmény, a többi csoportban akkor is tudjuk minden érme súlyát, így tudjuk E súlyát is. Azt is tudjuk, hogy Pisti már hazudott egyet, ezután tehát már minden mérésnél a jó eredményt kell közölnie.
A kényelem kedvéért ebben a rossz csoportban átszámozzuk az érméket: E marad a nulladik és az első k–1 sorszáma is változatlan marad, viszont utána a k-adikat –(k–1)-ediknak, a következőt a –(k–2)-ediknek vesszük, tehát mindegyik sorszámából levonunk 2k–1-et. Ezt azért tesszük, mert így könnyebben megmondhatjuk, mit méretünk most le Pistivel (Jancsi nevében): minden i=1,2,...,k–1-re az i-edik és a –i-edik összegét. Ez további k – 1 mérés.
Most ez utóbbi mérésekből minden i=1,2,...,k–2-re van egy biztos eredményünk az i-edik, i+1-edik, –i-edik és –(i+1)-edik összegére. Másrészt a "régi" mérésekből is van egy eredményünk ugyanennek a négynek az összegére, hiszen ott Jancsi lemérette az i-edik és i+1-edik összegét, valamint a –i-edik és –i–1-edik összegét. Ha a "régi" és az "új" eredmény egyezik, az csak úgy lehet, ha a "régi" eredmények is pontosak voltak, hiszen mindkettő nem lehetett hibás. Eltérés csak úgy lehet a "régi" és "új" eredmény között, ha valamelyik "régi" eredmény hibás volt. Ez csak egy helyen fordulhat elő, azt a két "régi" eredményt újra mérjük - ez további két mérés -, s így mostmár sikerült kijavítanunk a rossz "régi" eredményt is, tehát ebben a csoportban is kiszámolhatjuk minden érme pontos súlyát. Összesen

4k² – 2k + k – 1 + 2 = 4k² – k + 1

mérést használtunk.

A megoldás egyik alapötlete az az észrevétel volt, hogy ha páratlan sok érmét "körbe állítunk" és a szomszédosakat leméretjük, akkor minden érme súlyára kapunk egy eredményt. Ha Jancsi minden mérésnél a helyes eredményt mondja, akkor minden eredmény pontos lesz, ha egy helyen hazudik, akkor minden eredmény rossz lesz. Erre az észrevételre, mint 'segédtételre' fogunk hivatkozni a következő megoldásban és a a következő feladat megoldásában is. A továbbiakban Pisti helyébe lépünk és mi játszunk Pisti helyett.

II. MEGOLDÁS (PUSKÁS Anna és PAULIN Roland megoldása alapján): A (2k – 1)² érmét tegyük be egy 2k – 1 sorból és ugyanennyi oszlopból álló táblázatba. Mérjük le az azonos sorban szomszédos elemeket, a szomszédosságot "ciklikusan" értve, azaz az utolsó és első elemet is szomszédnak tekintjük. A 'segédtétel' szerint ezzel az eljárással minden sorban minden érmére kapunk egy eredményt és ha Jancsi valamelyik sorban hazudott, abban a sorban minden érmére helytelen eredményt kapunk, míg minden más sorban helyes eredményt kapunk.
Eddig 4k² – 4k + 1 mérést használtunk.

Jancsi csak egyszer hazudhat, tehát legfeljebb egy "rossz" sorunk van. Ellenőriznünk kell, van-e rossz sor. Ehhez felhasználjuk, hogy k legalább kettő, így már az első 2k – 2 sor valamelyikében is biztosan helyes eredményt kapunk minden érmére. Párokba rendezzük e sorok első elemeit és leméretjük ezeket a párokat. Így ezek összegére már két-két eredményünk van, s a két eredmény közül legalább az egyik helyes. Ha tehát a két eredmény egyezik, akkor biztosak lehetünk, hogy e sorokban minden eredmény helyes. Ha valamelyik párban két eredményt kapunk, akkor e két sor egyikében van a hibás eredmény, utóbbi esetben az utolsó, ellenőrizetlen sor eredményei biztosan jók. Újabb k – 1 méréssel tehát elértük, hogy vagy egy "kétes" sorunk maradt (az utolsó), vagy két sorunk, amelyikből az egyik biztosan tartalmazott hibás mérést. A többiben megvan a helyes eredmény.

Rendelkezésünkre áll még 2k + 1 mérés. Nézzük előbb azt az esetet, ha az utolsó sor maradt kétséges. Van olyan érménk, amelynek tudjuk a súlyát, válasszunk ki ezek közül egyet. Legyen ez M és méressük le M-et az utolsó sor első érméjével. Ha összegükre ugyanazt az összeget kapjuk, amit az eddigi mérésekből kiszámoltunk, akkor az utolsó sorban is csupa jó eredményünk van, tehát máris kész vagyunk. Ha viszont a két eredmény nem egyezik, akkor tudjuk, hogy Jancsi többet már nem hazudhat, így M-et az utolsó sor minden érméjével együtt leméretünk, s ebből M súlyának ismeretében számoljuk ki azok súlyát. Ez 2k mérés, tehát eggyel kevesebb, mint amennyit használhattunk volna.

Marad az az eset, amikor az első 2k – 2 sorban találunk kettőt, amelyek valamelyike hibás. Ismét tudjuk, hogy Jancsi már nem hazudhat és van még 2k + 1 mérésünk. Most hasonlóan keressük meg a javítandó mérést, mint az előző megoldásban. Leméretjük a két sorban egymás alatt álló érmepárokat, ezekre most biztosan a helyes eredményt kapjuk. Ez 2k – 1 további mérés. A j-edik és j+1-edik helyen álló összesen négy érme súlyösszegére kapunk tehát egy biztosan helyes eredményt. (Ismét "ciklikusan" értjük a dolgot: az utolsó és az első helyen álló négy érmére is kapunk egy biztosan helyes eredményt.) Az előző mérésekből is van egy eredményünk e négy érme összegére: az azonos sorban álló két-két érme súlyösszegét is lemértük korábban. Ha azok valamelyike volt a hibás, akkor most két eltérő eredményt kapunk a négy érme összegére. Ellenkező esetben a két összeg azonos lesz. Vagyis ezzel az eljárással ki tudunk szűrni az eredeti mérésekből kettőt, amelyik egyike a hibás. És pont két mérésünk van még: újra lemérjük tehát a két kiszűrt párt (az azonos sorban álló párokat), s ezután már minden érmére tudunk pontos eredményt mondani. Most pontosan annyi mérést használtunk, ahány rendelkezésünkre állt.

9. feladat: Ismét változtatunk az előző játék feltételén: Jancsi továbbra is két érme súlyösszegét méretheti meg, de Pisti kétszer hazudhat. Mutassuk meg, hogy most Jancsi 3n/2 + 100 méréssel célhoz érhet.

MEGOLDÁS (PACH Péter Pál megoldása): Az egyszerűség kedvéért azonosítjuk magunkat Pistivel, tehát az ő nevében beszélünk.
Egyrészt felhasználjuk az előző feladat első megoldása után kiemelt 'segédtételt': ha egy érmékből alkotott páratlan körben bármely két szomszédos érme súlyösszegére tudunk egy helyes eredményt, akkor e körben szereplő összes érme súlyát meg tudjuk állapítani. Ha másrészt tudjuk az M érme súlyát és tudunk egy helyes eredményt az MN érmepárra, akkor tudunk helyes eredményt az N érmére is. E két egyszerű megállapításból az következik, hogy ha az érmék egy halmazán van egy gráfunk, amely tartalmaz páratlan kört és összefüggő, és e gráf által kijelölt bármely érmepár súlyösszegére tudunk helyes eredményt, akkor e halmaz minden érméjére tudunk egy helyes eredményt.
Olyan gráfot keresünk tehát, amelynek másfélszer annyi éle van, mint pontja és bármely két élét elhagyva még mindig marad benne páratlan kör és összefüggő marad. Ha ugyanis találunk ilyen gráfot, akkor e gráf élei által kijelölt érmepárokat leméretve biztosan kapunk minden érmére egy-egy helyes eredményt (is). Hogy hogyan működik az, amit most mondtunk egyszerűbb lesz a konkrét eseten megmutatni. Tehát tekintsük az alábbi (úgynevezett Petersen-)gráfot:

Azt állítjuk, hogy e gráfból bármely két élt elhagyva továbbra is összefüggő marad és lesz benne páratlan (öt hosszú) kör. Nyilvánvaló, hogy ha a két elhagyott él egyike a "külső" és a "belső" ötszöget köti össze, akkor bármi is legyen a másik elhagyott él, e két ötszög közül legalább az egyik teljesen megmarad és belőle legfeljebb két (megmaradó) élen a másik ötszög minden pontja is elérhető marad. Maradnának még azok az esetek, amikor egyik elhagyott él sem a külső és a belső ötszöget köti össze. Véges sok lépésben ezek is ellenőrizhetők. De erre nincs szükség, mert a Petersen-gráf "nagyon szimmetrikus" gráf, sokkal szimmetrikusabb még annál is, amit elsőre látunk rajta. Elsőre csak azt látjuk, hogy a külső és belső ötszög élei "ugyanazt a szerepet" játsszák. A gráfot "geometriai középpontja" körül elforgatva például a külső ötszög bármely éle átvihető a külső ötszög bármelyik élébe úgy, hogy közben a gráf ne változzon. De a külső ötszög bármelyik éle átvihető a belső ötszög bármelyik élébe is. Ehhez elég például a (34) élt átvinni a (7(10)) élbe, utána már forgatással bármelyik másik belső élbe is át tudjuk vinni. Az alábbi ábra mutatja, hogy ha a 3-as és a 7-es, a 4-es és a 10-es valamint a 8-as és a 9-es pont számozását felcseréljük, akkor az élek ugyanolyan számú pontok között fognak futni:

A gráf pontjainak olyan átszámozását, amely mellett a gráf minden éle élbe megy át (és minden nem-éle nem-élbe), a gráf automorfizmusának nevezik. Ugyanez az automorfizmus például felcseréli a (23) és a (27) élt is, tehát egy "külső" él is átvihető egy "összekötő" élbe. Forgatással mostmár bármely élt bármely élbe át tudunk vinni. Vagyis a Petersen-gráf bármely két éle "felcserélhető", azaz bármely e és f éléhez van a gráfnak olyan automorfizmusa, amely az e élt az f élbe viszi át. (Az ilyen gráfokat éltranzitív gráfoknak nevezik.)

Mivel a Petersen-gráf éltranzitív, ezért feltehetjük, hogy az egyik elhagyott éle éppen a (27) él, s erre az esetre már beláttuk, hogy bármelyik másik élt elhagyva a gráf valóban összefüggő marad és marad benne ötszög.

Térjünk ezután vissza Pistihez. Méressük le azokat az érmepárokat, amelyeket a Petersen-gráf kijelöl. Ez tizenöt mérés. A gráfban rengeteg öt hosszú kör van, mindegyikből számoljuk ki a kapott eredmények alapján a benne szereplő érmék súlyát, majd minden lehetséges módon számoljuk ki ezekből a többi öt érme súlyát is. Jancsi legfeljebb kétszer hazudhat, tehát legfeljebb két élen van rossz eredményünk. De ezt a két élt elhagyva még mindig összefüggő marad a gráf és még mindig marad benne páratlan kör is, így minden érmére kapunk helyes eredményt. Másrészt ha az egyik elhagyott "rossz" él helyett egy "jó" élt hagyunk el, akkor egy olyan gráfban számoljuk ki az érmék súlyát, amely pontosan egy rossz eredményt tartalmaz, így biztosan lesz olyan érme, amelyre rossz eredményt kapunk. Tehát két eset van: vagy e tíz érme súlyát az összes lehetséges módon kiszámítva vagy mindig ugyanazt az eredményt kapjuk, s ekkor minden eredmény helyes, vagy eltérő eredményeket is kapunk, s ekkor Jancsi biztosan hazudott legalább egyszer.

Írjuk fel n-et 10m+l alakban, ahol l=0, 1, 2, ..., 9 lehet. Vegyünk el az érmékből l-et és osszuk a többit tizes csoportokba. Számozzuk meg minden csoportban az érméket egytől tízig Minden csoportban a fenti Petersen-gráf alapján tesszük fel a kérdéseket Jancsinak. Ez csoportonként tizenöt kérdés, összesen 3n/2 kérdés és a fent mondottak szerint minden csoportban lesz helyes eredményünk és legfeljebb két csoport kivételével csak helyes eredményünk lesz.

A) Ha minden csoportban csak helyes eredményünk van, akkor még l érme súlyát kell megtudnunk 3l/2+100 mérésből. Van olyan érménk, amelynek tudjuk a súlyát. Ha a hiányzó érmék mindegyikét ötször leméretjük egy ilyen jó érmével, akkor legalább három egyforma eredményt kapunk, s ezek jó eredmények (hiszen Jancsi csak kétszer hazudhat). Így legfeljebb 45 további méréssel minden érme súlyát tudjuk.

B) Ha két csoportban van rossz eredményünk is, akkor Jancsi már többet nem hazudhat. E két csoportban összesen húsz érme van, tehát összesen még 20+l érmének nem tudjuk a súlyát. De van olyan érménk, amelynek már tudjuk a súlyát. Egy ilyen érmét minden még ismeretlen súlyú érmével párba állítva leméretjük, így ezeknek az érméknek is megtudjuk a súlyát további legfeljebb 29 kérdéssel.

C) Ha egy csoportban van rossz eredményünk, akkor még 10+l érme súlyát nem ismerjük. Jancsi még legfeljebb egyet hazudhat. Van olyan érménk is, amelynek ismerjük a súlyát. Ha ezt az érmét méretjük le a még ismeretlen súlyú érmékkel, akkor az a helyzet állt elő, hogy van n=10+l érménk, amelyek súlyát kell megállapítanunk, Jancsi legfeljebb egyszer hazudhat és minden lépésben egy érme súlyát mondja meg. A 7. feladat megoldása után tett megjegyzés szerint ehhez elég 21+2l kérdés, ami jóval kevesebb a még rendelkezésünkre álló 3l/2+100 mérésnél.

MEGJEGYZÉSEK:

1. Az A) részben is használhattuk volna a 7. feladat megoldása után tett megjegyzést, s így a kérdések számát még lejjebb szoríthattuk volna. Valójában a 100-as konstans leszorítható harminc alá.
Másrészt az is nyilvánvaló, hogy a feladat feltételei több mint 3n/2 mérésre van szüksége Pistinek ahhoz, hogy az érmék súlyát megtudja. A feladat állítása tehát "lényegében", azaz egy konstans tagtól eltekintve pontos.

2. Az utóbbi állítást a következő meggondolás alapján lehet belátni. Tegyük fel, hogy Jancsi azt a stratégiát követi, hogy az érméket ő is egy gráf csúcsainak tekinti és Pisti minden kérdését egy-egy él behúzással jelzi. Ha Pisti többször kérdezi meg ugyanannak az érmepárnak a súlyát, akkor Jancsi gráfjában többszörös élek lesznek. Jancsi csak azt figyeli, hogy van-e még olyan pont, amelynek foka (a többszörös éleket többször, multiplicitással számítva) kisebb háromnál. Amíg ilyen pont van, addig az igazat mondja. Amikor az utolsó ilyen is eltűnik, akkor rossz eredményt mond. Amíg van másodfokú pont, addig Pisti nem lehet biztos benne, hogy ennek a súlyára jó eredményt tud-e, hiszen lehet, hogy Jancsi úgy hazudik, hogy minden más érme súlya jól jöjjön ki, csak ennek az érmének a súlyánál jöjjön ki rossz eredmény. Ezt Jancsi nyugodtan megteheti, amíg erre az érmére csak kétszer kérdezett Pisti, hiszen mindenütt másutt igazat mondott. Vagyis a helyzet a következő: Jancsi gráfjában most minden pont foka legalább három és Pisti még nem tudhatja minden érme súlyát. (Valójában még legalább két további kérdésre van szüksége.)

3. Általában is igaz, hogy ha Jancsi h-szor hazudhat és Pisti egyszerre k érme súlyát méretheti le, akkor n érme esetén (h+1)n/k-nél több mérésre van szüksége ahhoz, hogy minden érme súlyát megtudhassa. A bizonyítás pontosan ugyanaz, mint az előbb, csak most Jancsinak gráfok helyett k "élű" úgynevezett "hipergráfokat" kell használnia, vagyis olyan gráfot, amelynek "élei" a csúcsokból alkotott bizonyos k elemű részhalmazai. (A "rendes" gráfoknál k=2.) Jancsi akkor húz be egy ilyen "k-élt" a gráfjába, ha Pisti ezt a mérést kéri tőle. Megint csak arra kell ügyelnie, hogy amíg van a gráfban h-ad fokú, vagy annál kisebb fokú pont, vagyis amíg van olyan érme, ami legfeljebb h mérésben szerepelt, addig ne hazudjon, viszont amikor az utolsó ilyen is megszűnik, akkor hazudjon egyet.

4. Az előző megjegyzés alapján láthatjuk, hogy ha Pisti érmepárok súlyát kérdezheti és Jancsi csak egyszer hazudhat, akkor legalább Pistinek több kérdést kell feltennie, mint ahány érme van. Viszont ha n érme van, akkor Pistinek elég legfeljebb n+Cn^1/2 kérdés, ahol C egy abszolút konstans. Az előző feladat ezt állítja abban az esetben, ha n páratlan négyzetszám és C=3. A többi eset ebből már levezethető, csak C értéke nő meg valamelyest (például C=6 már minden esetben megfelel).

10. feladat: Jellemezzük a derékszögű rácsnak azokat a rácsháromszögeit, amelyekre teljesül, hogy
(a + b)² £ 8t + 1,
ahol t a háromszög területe, a és b pedig az oldalai közül kettő.

MEGOLDÁS: Jelöljük a háromszög területének kétszeresét T-vel. Ismeretes, hogy rácsháromszög esetében ez mindig egész szám. A feladat egyenlőtlenségét kiszorozva és rendezve azt kapjuk, hogy

a² + b²£ 4T + 1 – 2ab £ 2T + 1.

Itt felhasználtuk, hogy a háromszög területe legfeljebb a két oldal szorzatának fele. Másrészt derékszögű rácsban az oldalak hosszának négyzete a koordináták négyzetösszege, tehát a² és b² egész szám. A jobb oldalon is egész szám áll.
Ismeretes, hogy 2ab £ a² + b², másrészt egy háromszög területének kétszerese legfeljebb két oldalának szorzata, tehát a bal oldal alulról becsülhető 2T-vel. Azt kaptuk, hogy a² + b², ami egy egész szám, 2T és 2T + 1 között van. Ezek is egész számok, tehát két eset van:
a²+b² = 2T vagy
a²+b² = 2T + 1.

Az előbbi eset csak úgy állhat elő, ha egyrészt ab éppen a terület kétszerese, ebben az esetben a közbe zárt szög éppen derékszög, másrészt a²+b² = 2ab, ami csak úgy lehetséges, ha a=b. Az első esetben tehát derékszögű egyenlőszárú háromszögről van szó. Egyenlőszárú derékszögű háromszögekben valóban (a + b)² = 4ab=8t, teljesül a feladat feltétele. A második esetben írjuk be a feladat eredeti egyenlőtlenségébe az a²+b² = 2T + 1 egyenlőséget. Így azt kapjuk, hogy 2ab £ 2T. De tudjuk, hogy a fordított egyenlőtlenség is fennáll, tehát ab = T, vagyis a háromszög most is derékszögű. Továbbá most az is igaz, hogy

(a – b)² = a²+b² – 2ab = 2T + 1 – 2T = 1,

tehát a és b különbsége 1.
A háromszög oldalait és csúcsait a szokásos módon jelölve forgassuk el a C csúcs körül 90 fokkal a B csúcsot. A kapott B' pont ismét rácspont, másrészt 1 távolságra van az A csúcstól, ami szintén rácspont. Ez csak úgy lehet, ha AB' függőleges, vagy vízszintes rácsegyenes. Ebből viszont az következik, hogy háromszögünk CA és CB oldalai a koordinátatengelyekkel párhuzamosak, ezért hosszuk egész szám. A második esethez tartozó háromszögek tehát olyanok, amelyekben a és b szomszédos egész számok, az oldalak a tengelyekkel párhuzamosak. Az ilyen háromszögek nyilván meg is felelnek a feladat egyenlőtlenségének: ha feltesszük, hogy a a rövidebb oldal, akkor a területük a(a+1)/2, ennek nyolcszorosa 4a² + 4a és ehhez egyet adva éppen (a + b)² = (2a + 1)²-et kapunk.

11. feladat: Legyen p páratlan prím. Legfeljebb hány választható ki a 0, 1, 2, …, p–1 számok közül úgy, hogy semelyik két különbözőnek se az összege, se a szorzata ne adjon egyet maradékul p-vel osztva?

MEGOLDÁS: Tekintsük azt a gráfot, amelynek pontjai ez a p szám. Kétféle élt húzunk be a gráfba. Két csúcsot akkor kötünk össze piros éllel, ha a megfelelő két szám összege egyet ad maradékul p-vel osztva (tehát ha összegük egy vagy p+1. Két csúcsot akkor kötünk össze fehér élllel, ha a megfelelő két szám szorzata egyet ad maradékul p-vel osztva. Nyilvánvaló, hogy egy tetszőleges k számhoz pontosan egy olyan van, amellyel összege egy maradékot ad: pk. Ha k=(p+1)/2, akkor ez a szám önmaga, minden más esetben különbözik tőle. Tehát a (p+1)/2 számból nem indul ki piros él, minden más számhoz tartozó csúcsból pontosan egy piros él indul ki. Másrészt ha k nem nulla, akkor pontosan egy olyan szám van a feladatban felsoroltak között, amellyel összeszorozva egy lesz a maradéka. (A nullához nyilván nincs ilyen szám.) Ez abból következik, hogy ha a 0, 1, 2, …, p–1 számok mindegyikét megszorozzuk k-val, akkor a kapott p szám úgynevezett teljes maradékrendszert alkot mod p. Ez azt jelenti, hogy minden j=0, 1, 2, …, p–1 számhoz pontosan egy olyan szorzat lesz, amely j maradékot ad p-vel osztva. (Ennek bizonyítását lásd például ERDŐS Pál és SURÁNYI János Válogatott fejezetek a számelméletből című könyvének 53. oldalán, vagy SZALAY Mihály: Számelmélet tankönyvének 89. oldalán.) A nullából tehát nem indul ki fehér él, ezen kívül csak azokból a csúcsokból nem indul ki fehér él, amelyekhez tartozó számok önmagukkal szorozva adnak egy maradékot. Vagyis az olyan k számokhoz tartozó csúcsokból nem indul ki még fehér él, amelyekre k²–1=(k–1)(k+1) osztható p-vel. Mivel p prím, ez csak úgy lehetséges, ha valamelyik tényezőt osztja, vagyis csak k=1 és k>=p–1 esetében. Azt kaptuk tehát, hogy a 0, az 1 és a p–1 számokból nem indul ki fehér él, minden más csúcsból pontosan egy fehér él indul ki.
Tekintsünk el egyelőre az élek színétől. Ekkor egy olyan gráfot kapunk, amelyben minden pont foka egy vagy kettő. Egy ilyen gráf csak pontfüggetlen utakból és körökből áll. (A pontfüggetlenség azt jelenti, hogy semelyik két útnak, két körnek vagy útnak és körnek nincs közös pontja.) A körök mindegyike páros, mert minden csúcsból egy piros és egy fehér él indul ki, tehát a kör élei felváltva piros és fehér színűek.

A feladat feltételét átfogalmazhatjuk úgy, hogy a gráf (akár piros, akár fehér) éllel összekötött csúcsai közül legfeljebb az egyik vehető ki. Vagyis az a kérdés, hogy maximálisan hány csúcsot választhatunk ki ebben a gráfban, amelyek közül semelyik kettő között nem megy él. A gráfban csak négy darab első fokú pont van: 0, 1, p–1 és (p+1)/2. Az első két számhoz tartozó csúcs között piros él fut, ezek tehát egy 1 hosszúságú utat alkotnak, a kettő közül bármelyik csúcsot kiválaszthatjuk. A másik két számhoz tartozó csúcs közül a p–1 számú csúcsból piros, a (p+1)/2 számú csúcsból fehér él megy a 2-es számú csúcshoz. E három csúcs közül a két szélső, p–1 és (p+1)/2 kiválasztható. Eddig találtunk két utat, az egyik 1, a másik 2 élből áll, összesen három csúcs választható ki belőlük.
Az összes többi csúcs körökben szerepel, mert nincs több elsőfokú pont. Másrészt láttuk, hogy minden kör páros, azokból tehát a csúcsoknak pont a fele (minden második) választható ki. Ez összesen 3+(p–5)/2=(p+1)/2. Ennyi szám választható ki a feladat feltételei mellett.

12. feladat: Jelöljük p(n)-nel az n-nél nem nagyobb pozitív prímek számát. Bizonyítsuk be, hogy végtelen sok olyan n szám van, amelyre p(n) osztója n-nek.

MEGOLDÁS: Felhasználjuk – egyelőre bizonyítás nélkül – azt a tényt, hogy az n-nél nem nagyobb prímek száma n-nel osztva nullához tart, ha n tart a végtelenhez. Ez azt jelenti, hogy bármely k pozitív egészhez van olyan n, amelyre (n–1)/p(n–1) kisebb, mint k, de n/p(n) már legalább k. Innen átszorzással azt kapjuk, hogy p(n–1)k nagyobb, mint n–1, másrészt a nála nem kisebb p(n)k legalább n. De p(n)k egész, így egyenlő n-nel. Amiből azt kapjuk, hogy p(n) osztója n-nek. Másrészt k tetszőlegesen nagy, ezért végtelen sok különböző ilyen n-et kapunk.

A bizonyításban felhasználtuk, hogy p(n)/n nullához tart, ha n tart a végtelenhez. Ez következik abból, hogy van olyan C pozitív konstans, amelyre p(n) kisebb Cn/log₂ n, másrészt ha n tart a végtelenbe, akkor log₂ n is a végtelenbe tart. Ennek bizonyítása megtalálható például Erdős Pál-Surányi János: Válogatott fejezetek a számelméletből című könyve 191. oldalán (az 5. fejezet 7. tétele) és SZALAY Mihály: Számelmélet című tankönyve 143. oldalán.

13. feladat: Legyen k olyan pozitív egész szám, amelyre p = 4k + 1 prímszám. Bizonyítsuk be, hogy ekkor k^k – 1 osztható p-vel.

A megoldást egy előzetes megjegyzéssel kezdjük. A "kis" Fermat tétel szerint 2^p–1 – 1 oszható p-vel, így elég azt bebizonyítanunk, hogy 2^p–1k^k – 1 osztható p-vel. De  2^p–1k^k=(16k)^k=(4p–4)^k. Ha ezt az utolsó kifejezést a binomiális tétel segítségével kifejtjük, akkor a (–4)^k tag kivételével minden tagban fog szerepelni p-nek valamilyen pozitív hatványa, ezek tehát oszthatók p-vel. Azt kell csak belátnunk, hogy (–4)^k–1 osztható p-vel. Erre több bizonyítást is bemutatunk.

I. (PAULIN Roland bizonyítása): Olyan A számot keresünk, amelynek negyedik hatványa éppen –4-et ad maradékul p-vel osztva, vagyis amelyre A⁴=np–4 alkalmas n egészre. Ha ilyet találunk, akkor emeljük ennek az egyenlőségnek mindkét oldalát k-adik hatványra. A bal oldalon A^4k=A^p–1 áll, s ez a "kis" Fermat-tétel szerint p-vel osztva 1 maradékot ad. A másik oldalt a binomiális tétellel kifejtve a (–4)^k tag kivételével minden tagban szerepel p valamely pozitív hatványa, tehát ez a tag p-vel osztva ugyanazt a maradékot adja, mint az egész jobb oldal. Vagyis 1-et. Ez pedig éppen a bizonyítandó állítás: (–4)^k–1 osztható p-vel.

Mostmár csak olyan A számot kell keresnünk, amelyre A⁴+4 osztható p-vel. Ilyen A számot több lépésben találunk.
Ismeretes a komplex számok körében, hogy ha i az imaginárius egység, akkor

(1 + i)⁴ = 1 + 4i + 6i² + 4i³ + i = 1 + 4i – 6 – 4i + 1= –4.

A komplex számok között tehát az 1 + i megfelelne A-nak. Itt csak azt használtuk, hogy i négyzete –1, vagyis i²+1=0. Az "egyenlő nullá"-nak a mi esetünkben az felel meg, hogy osztható p-vel (kongruens nullával mod p). Ha tehát találunk egy olyan a számot, amelynek négyzete p-vel osztva –1 maradékot ad, vagyis amelyre a² + 1 osztható p-vel, akkor készen vagyunk. Hiszen ekkor (1 + a)² és 2a ugyanazt a maradékot adja p-vel osztva (kongruens mod p). De akkor a négyzeteik maradéka is ugyanaz, tehát (1 + a)⁴ és 4a² maradéka is megegyezik és az utóbbi maradéka az a-ra tett feltevés szerint –4.

Ismeretes, hogy ((p–1)/2)! éppen megfelel ilyen a-nak, ha p=4k+1 alakú prím. Ez következik Wilson tételéből, amely szerint (p–1)!+1 osztható p-vel. A bizonyítás megtalálható SZALAY Mihály idézett könyvének 93. oldalán és az idézett ERDŐS-SURÁNYI könyv 80. oldalán (2. fejezet 15. tétel).

14. feladat: Adott a k kör és rajta kívül az A pont. Mutassuk meg, hogy van olyan B pont a síkon, amelyre igaz az alábbi állítás:
a k körön végtelen sok módon kiválasztható hat pont, A₁, B₁, A₂, B₂, A₃, B₃ úgy, hogy az A₁B₁, A₂B₂, A₃B₃ egyenesek átmennek A-n, a B₁A₂, B₂A₃, B₃A₁ egyenesek pedig átmennek B-n.

15. feladat: Egy körbe három szabályos háromszöget írtunk, az első csúcsai pirosak, a másodiké fehérek, a harmadiké zöldek. Bizonyítandó, hogy van olyan háromszög, amelynek mindhárom csúcsa különböző színű és tartalmazza a kör középpontját.

I. MEGOLDÁS (BOHUS Péter megoldása): A szabályos háromszögek csúcsait színeik kezdőbetűivel jelöljük és egytől háromig indexeljük (így például a piros háromszög csúcsai P₁, P₂, P₃). Az egyes háromszögek csúcsai megszámozhatók úgy, hogy a kört valamelyik irányban körbejárva a csúcsok ilyen sorrendben jöjjenek: P₁, F₁, Z₁, P₂, F₂, Z₂, P₃, F₃, Z₃. Az általuk alkotott konvex kilencszög biztosan tartalmazza a kör középpontját, hiszen már bármelyik három azonos színű által alkotott háromszög is tartalmazza. Márpedig ezt a kilencszöget lefedhetjük "háromszínű" háromszögekkel a következő módon. Kössük össze például a P₁ csúcsot minden zöld és fehér csúccsal, húzzuk be továbbá a F₂Z₁ és az F₃Z₂ átlókat. A kilencszöget így hat átlójával hét "nemzeti színű" háromszögre bontottuk, s ezek egyike biztosan tartalmazza a kör középpontját, ahogyan a feladat állítja.

A megoldásban csak azt használtuk, hogy az eredetileg megadott (egyszínű) háromszögek hegyesszögűek (tartalmazzák a köré írt kör középpontját), és csúcsaik "sorban" jönnek a körön. Ez teljesül, ha a három egyszínű háromszög egybevágó. A feladat állítása tehát igaz szabályos háromszög helyett bármilyen három egybevágó hegyesszögű háromszögre.

II. MEGOLDÁS: Ez a feladat speciális esete a következő feladatnak. Ehhez egyrészt azt kell észrevennünk, hogy a szabályos háromszög tartalmazza köré írt körének középpontját, másrészt azt, hogy a feladat "nem érzékeny" arra, hogy ha az egyik háromszög csúcsainak új (eddig még nem szereplő) színt adunk, tehát kékről fehérre változtatjuk őket.

16. feladat: A sík egy P pontja egy piros, egy kék és egy zöld háromszög közös részében van. Bizonyítandó, hogy kiválasztható a három háromszög egy-egy csúcsa úgy, hogy az általuk alkotott háromszög tartalmazza P-t.

MEGOLDÁS: Legyenek a piros, fehér, illetve zöld háromszög csúcsai P₁, P₂, P₃, F₁, F₂, F₃ és Z₁, Z₂, Z₃. Feltehetjük, hogy a kilenc pont egy körön van. Ha ugyanis bármely Q pontot a PQ félegyenesen mozgatunk, ettől a Q csúcsú háromszögeknek az a tulajdonsága, hogy tartalmazzák-e a P pontot, nem fog változni. Tekintsük az olyan szakaszokat, amelyek két különböző színű csúcsot kötnek össze. Ezekből véges sok (27) van. Tegyük fel először, hogy egyik sem megy át a P ponton és vegyük azt, amelyik a legközelebb van P-hez. Legyen ez például a P₁F₁ szakasz (a csúcsok átszámozásával és a színek cserélésével ez mindig elérhető). Nem lehet, hogy mindhárom Z_i pont a P₁F₁ egyenesnek P-t nem tartalmazó oldalán legyen, hiszen ekkor a zöld háromszög nem tartalmazná a P pontot. Az egyik Z_i tehát a P₁F₁ egyenesnek P-vel azonos oldalán van. De akkor a P₁F₁Z_iszögtartománynak tartalmaznia kell P-t, különben az F₁Z_i szakasz közelebb volna P-hez, mint a P₁F₁ szakasz. Ugyanígy a F₁P₁Z_i szögtartománynak is tartalmaznia kell P-t, különben a P₁Z_i szakasz volna közelebb P-hez a P₁F₁ szakasznál. Ezzel beláttuk, hogy a P₁F₁Z_i háromszög valóban tartalmazza a P pontot.