Feladat: 2002. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csikvári Péter ,  Harangi Viktor ,  Rácz Béla András ,  Steller Gábor 
Füzet: 2003/február, 74 - 77. oldal  PDF  |  MathML 
Témakör(ök): Konvex sokszögek, Háromszög-egyenlőtlenség alkalmazásai, "a" alapú számrendszer (a >1, egész szám), Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2003/február: 2002. évi Kürschák matematikaverseny 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 (Csikvári Péter megoldása alapján). A sokszög csúcsaihoz rendeljük hozzá a 0,1,2,...,3n-1 számokat, 3-as számrendszerben felírva. Minden leírt számnak legfeljebb n jegye van. Ha a jegyek száma n-nél kisebb, akkor írjunk a szám elé még annyi 0 számjegyet, hogy végül egy n számjegyből álló sorozatot kapjunk, amelynek tehát minden számjegye 0, 1 vagy 2. Úgy is fogalmazhattunk volna, hogy a sokszög csúcsaihoz rendeljük hozzá az n hosszúságú 0‐1‐2 sorozatokat.
Tekintsük azokat a háromszögeket, melyekre teljesül a következő feltétel: bármelyik helyiértéket választjuk is ki, a háromszög csúcsaihoz rendelt három szám az adott helyiértéken vagy mind megegyezik, vagy páronként különböző. Világos, hogy bármely két csúcsot kiválasztva, pontosan egy olyan csúcsa lesz a sokszögnek, hogy a három csúcs által meghatározott háromszög kielégíti a fenti feltételt. Az eredeti sokszögnek tehát minden egyes oldala és átlója pontosan egy háromszögnek lesz valamelyik oldala, ami azt jelenti, hogy azok a szakasz-hármasok, melyek egy-egy háromszög három oldalát alkotják, rendelkeznek a feladatban megkövetelt tulajdonsággal.

 
II. megoldás. A bizonyítást n-re vonatkozó teljes indukcióval végezzük. Ha n=1, akkor az állítás nyilvánvaló. Az indukciós lépéshez tegyük fel, hogy valamilyen pozitív egész n-re az állítást már beláttuk. Tekintsünk most egy konvex 3n+1-szöget, és ennek csúcsait jelölje Ai, Bi, Ci, ahol 1≤i≤3n. Az Ai csúcsokat összekötő szakaszokat az indukciós feltevés miatt be tudjuk osztani hármas csoportokba az előírt módon, és ugyanez igaz a Bi csúcsokat összekötő szakaszokra és a Ci csúcsokat összekötő szakaszokra is.
A többi szakaszt pedig a következő módon oszthatjuk be. Alkossanak egy csoportot az AiBj, BjCk és CkAi szakaszok, valahányszor i+j+k osztható 3n-nel; három ilyen szakasz nyilván egy háromszögvonalat alkot. Mivel az i, j, k számok közül bármely kettőt lerögzítve, az oszthatósági feltétel a harmadik számot egyértelműen meghatározza, minden szakasz pontosan egy hármas csoportban fog szerepelni. Ezek szerint az állítás (n+1)-re is igaz, az indukciós lépést befejeztük.
 
III. megoldás (Steller Gábor megoldása alapján). Mint az előző megoldásokban is láttuk, célunk olyan háromszögeket találni, melyek mindhárom csúcsa az eredeti sokszögnek is csúcsa, minden szakasz valamelyik háromszögnek oldala, továbbá minden szakasz csak egy háromszögnek lehet oldala, amit úgy is fogalmazhatunk, hogy bármely két háromszögnek legfeljebb egy közös csúcsa van. Ismét teljes indukciót használunk. Tegyük fel hogy egy P1P2...P3n sokszög esetén már megtaláltuk a keresett PiPjPk háromszögeket, ezek száma a feltételek szerint éppen a szakaszok számának harmada, vagyis
13(3n2n)=3n-1(3n-1)2.

Jelölje egy konvex 3n+1-szög csúcsait Ai, Bi, Ci (1≤i≤3n). Tekintsük az AiBiCi háromszögeket, ahol 1≤i≤3n. Nevezzük ezeket egyes típusú háromszögeknek. Ezen kívül minden, az előző felosztásban szereplő PiPjPk háromszögre készítsük el az AiAjAk, BiBjBk, CiCjCk (kettes típusú) és az AiBjCk, AiCjBk, BiAjCk, BiCjAk, CiAjBk, CiBjAk (hármas típusú) háromszögeket is. Ez éppen
9⋅3n-1(3n-1)2+3n=3n(3n+1-3)2+3n=3n(3n+1-1)2
háromszög, éppen annyi, amennyi az alkalmas felosztáshoz szükséges. Ezért elegendő annyit megmutatni, hogy bármely két fenti háromszögnek legfeljebb egy közös csúcsa van.
Az egyes típusú háromszögeknek nyilván nincs közös csúcsuk, és kettes típusú háromszöggel is csak legfeljebb egy közös csúcsuk lehet. A kettes típusú háromszögeknek vagy nincs közös csúcsuk, vagy az indukciós feltevés miatt legfeljebb egy közös csúcsuk van. A hármas típusú háromszögeket tekintve, ezeknek mind az egyes, mind a kettes típusú háromszögekkel legfeljebb egy közös csúcsa lehet. Végezetül pedig két hármas típusú háromszögnek is csak legfeljebb egy közös csúcsa lehet az indukciós feltevés miatt. Ha ugyanis mondjuk AiBjCk és AiBjCk' is hármas típusú háromszögek, akkor az eredeti 3n-szög felbontásában szerepelnie kellett a PiPjPk és PiPjPk' háromszögeknek is, ami csak k=k' esetén lehetséges.
 
IV. megoldás (Harangi Viktor megoldása alapján). Az általánosság megszorítása nélkül feltehetjük, hogy a sokszög szabályos; ez lehetőséget nyújt egy geometriai jellegű okoskodásra. Ismét n szerinti teljes indukciót alkalmazunk. Ha n=1, akkor az állítás semmitmondó. Tegyük fel, hogy valamely n≥1 esetén a feladatot már megoldottuk, és tekintsünk egy P szabályos 3n+1-szöget. Ennek csúcsait jelöljük meg az A, B, C betűkkel úgy, hogy valamilyen körüljárás szerint végighaladva a sokszög csúcsain, egy A jelű csúcs után mindig B jelű csúcs következzék, B jelű után C jelű, azután pedig ismét A jelű. Az azonos betűvel jelölt csúcsok egy-egy szabályos 3n-szöget alkotnak, melyeknek élei feltevésünk szerint már beoszthatók hármas csoportokra a kívánt módon. Most már csak a különböző jelű csúcsokat összekötő éleket kell beosztani.
Tekintsük a P sokszög egy A jelű csúcsán átmenő t szimmetriatengelyét. Mivel P-nek páratlan sok csúcsa van, ezen nem helyezkedhet el más csúcs. Egy A jelű csúcsot t-re tükrözve ismét A jelű csúcsot kapunk, B jelű csúcsot tükrözve C jelűt kapunk, C jelűt tükrözve pedig B jelű csúcshoz jutunk. Hasonlóképpen B és C jelű csúcsokon átmenő szimmetriatengelyekre való tükrözésnél éppen a B, illetve C jelű csúcsok lesznek azok, amelyek ugyanolyan jelű csúcsba kerülnek.
Konstrukciónk ezek után legyen a következő: egy ABC típusú háromszög élei pontosan akkor alkossanak egy hármas csoportot, ha a háromszög szimmetrikus az A jelű csúcson áthaladó szimmetriatengelyre. Azt állítjuk, hogy ezzel a P sokszög minden AB, BC és CA típusú élét pontosan egyszer használtuk fel, amiből az indukciós lépés helyessége következik.
Valóban, egy AB típusú él pontosan abban az egy háromszögben lesz benne, amelynek harmadik csúcsát úgy kapjuk, hogy a B jelű csúcsot tükrözzük a P sokszög A jelű csúcson áthaladó szimmetriatengelyére; fenti megállapításaink alapján ez éppen egy C jelű csúcs lesz. Szimmetria okok miatt minden AC típusú él is pontosan egy háromszögben lesz benne. Végül egy BC típusú élből kiindulva, tekintsük annak felező merőlegesét. Ez szimmetriatengelye lesz a P sokszögnek, éppen ezért áthalad annak egy jól meghatározott csúcsán, ami a fenti megállapítások miatt csakis A jelű lehet. Ez és csakis ez lehet a keresett háromszög harmadik csúcsa.
 

Végezetül lássuk azt a megoldást, amely rávilágít a feladat valódi geometriai, vagy ha úgy tetszik, algebrai hátterére. A keresett hármas csoportokra való felosztás ugyanis megvalósítható a 3 elemű test feletti n-dimenziós affin tér egyeneseinek segítségével. Hogy ez pontosan mit is jelent, az remélhetőleg kiderül az alábbi gondolatmenetből.
 
V. megoldás (Rácz Béla András megoldása alapján). Legyen p egy tetszőleges prímszám. A következő általános tételt fogjuk bebizonyítani: egy pn szögpontú teljes gráf éleit csoportosítani lehet úgy, hogy az egyes csoportokban lévő élek egy-egy p szögpontú teljes gráf élhalmazát alkossák. Láthatjuk, hogy p=3 esetén ez ekvivalens a kitűzött feladattal.
Tekintsük az a=(a1,a2,...,an) sorozatokat, ahol minden i-re ai p-nél kisebb nemnegatív egész. Ezek száma éppen pn. Ezek lesznek a p elemű test feletti n-dimenziós affin tér pontjai, melyeket az adott teljes gráf szögpontjaival azonosítunk. Ezekre a pontokra egyben vektorként is gondolunk ugyanúgy, ahogyan a 3-dimenziós euklideszi tér pontjait azonosíthatjuk az origóból oda mutató vektorokkal. Az a és v pontok összegén, vagy ha úgy jobban tetszik, az a pont v vektorral való eltoltján az a+v=(a1+v1,a2+v2,...,an+vn) pontot értjük, ahol az ai+vi összegeket moduló p kell tekinteni. Nyilván két pont különbségét is értelmezhetjük hasonló módon, és igaz lesz az, hogy a+(b-a)=b. A v pont (vektor) α-szorosán, ahol α∈{0,1,...,p-1} pedig az αv=(αv1,αv2,...,αvn) pontot (vektort) értjük, ahol természetesen az αvi szorzatokat ismét csak moduló p kell értelmezni. Ezt persze megtehetjük tetszőleges β egész szám esetén is, és ha α és β ugyanolyan maradékot adnak p-vel osztva, akkor nyilván αv és βv ugyanazt a pontot jelöli ki.
Hogyan lehetne értelmezni két különböző a és b ponton átmenő egyenest? Kézenfekvő, hogy az a ponthoz adjuk hozzá a v=b-a vektor skalárszorosait, ahogy azt az euklideszi esetben is tennénk. Nem nehéz megmutatni, hogy minden egyenes p különböző pontból áll. Először is, legfeljebb p pont lehet az egyenesen, hiszen elegendő a v vektor 0,1,...,p-1-szeresét hozzáadni a-hoz. Ha most a+jv=a+kv lenne két különböző j,k∈{0,1,...,p-1} számra, akkor a v vektor minden egyes vi koordinátájára jvi és kvi megegyezne moduló p. Vagyis (k-j)vi osztható lenne p-vel, ami csak úgy lehetséges, ha minden vi=0, ami ellentmond annak, hogy a és b különböző pontok voltak.
Bármely két különböző pont meghatároz tehát egy egyenest, melynek p pontja van. A sorsdöntő észrevétel az, hogy bármely két különböző egyenesnek legfeljebb egy közös pontja van, vagy másképp szólva, bármely két pont pontosan egy egyeneshez tartozik hozzá. Ebből a bizonyítandó állítás már következik: a keresett p szögpontú teljes gráfokat éppen a különböző egyeneseknek feleltethetjük meg.
 
Feladatok
1) Igazoljuk, hogy az a és b pontokon átmenő egyenes meghatározásában a és b szerepe felcserélhető.
2) Igazoljuk, hogy ha c=a+α(b-a) és d=a+β(b-a) az a és b pontok által meghatározott egyenes két különböző pontja, akkor a és b rajta van a c és d pontok által meghatározott egyenesen. Hogyan következik ebből a megoldásban említett ,,sorsdöntő'' észrevétel?
3) Hogyan értelmezhetnénk két egyenes párhuzamosságát?
4) Hogyan lehetne síkokat definiálni? Hány pontja lesz egy síknak? Hogyan nézhet ki két sík közös pontjainak halmaza?
5) Milyen problémákba ütköznénk, ha egy p prímszám helyett egy m összetett számra próbálnánk a fenti tételt és annak bizonyítását átvinni?