Feladat: 2013. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: - Nehézségi fok: -
Megoldó(k):  Nagy Róbert 
Füzet: 2013/október, 394 - 395. oldal  PDF  |  MathML 
Hivatkozás(ok):Feladatok: 2013/szeptember: 2013. évi Nemzetközi Matematika Diákolimpia 23. 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.

Nagy Róbert megoldása. Először olyan húrokat vizsgálunk, melyek végpontjain az összeg k ‐ nevezzük ezeket k-húroknak.

 
Lemma. Egy szép elrendezésben bármely három húrra teljesül, hogy az egyik elválasztja a másik kettőt.
 
Bizonyítás. Indukcióval bizonyítunk n szerint. Ha n≤3, akkor az állítás triviális. Legyen n≥4, és bizonyítsunk indirekten.
Tegyük fel, hogy létezik három olyan húr, melyek ,,nem elválasztóak''. Legyenek a három húr végpontjai: ab, cd, ef, ahol ezek a végpontokra írt számokat is jelölik. Ekkor ha n nem szerepel a hat végpont között, akkor n-et elhagyva a körről továbbra is szép elrendezést kapunk, melyben csak (n-1)-ig vannak az elemek. Erre már beláttuk, hogy teljesül az állítás, tehát ez ellentmondás. Ugyanígy, ha 0 nem szerepel a húr végpontok között, akkor ezt elhagyva és minden pont értékét eggyel csökkentve is szép elrendezéshez jutunk, melyben a legnagyobb elem megint csak n-1, ami ellentmondás.
Tehát a 0 és az n elemek is a húrok végpontjai között vannak. Vegyük észre, hogy az n és a 0 azonos húrok végpontjai, különben: n+b>n>0+d, tehát k=n.
Legyen A, B, C a három húr, mely nem elválasztó. Ezek közül legyen C az, melynek két végpontja 0 és n. Ekkor vegyük azt a D húrt, mely közvetlenül a C húr mellett van, azonos oldalon az A és B húrokkal. Ennek két végpontja legyen u és v, u+v=t.
Ha t=n, akkor a C húr két végpontját elhagyva és az összes elemet eggyel csökkentve megint olyan elrendezést kapunk, amire már beláttuk az állítást az indukció miatt.
Ha t<n, akkor t nyilvánvalóan a C húr másik oldalán van, hiszen különben a D húr és a {0,t} húr metsző lenne. Így (n-t) (hiszen t, n-t nem metsző C-vel) is C másik oldalán van, ekkor viszont a C húr végpontjait elhagyva megint kapunk három húrt, melynek végpontjain a számok összege megegyező és nem szétválasztóak. De (n-2)-re már beláttuk az állítást az indukció miatt.
Ha t>n, akkor vegyünk minden x szám helyett n-x-et. Vegyük észre, hogy ekkor az elrendezés nyilvánvalóan továbbra is szép lesz, és ekkor visszakapjuk az előző esetet. Tehát beláttuk, hogy minden elrendezésben a k-húrok szétválasztóak.  □
Bizonyítsuk az eredeti állítást teljes indukcióval. n=2-re az állítás nyilvánvaló. Ezek után legyen n≥3. Legyen S egy szép elrendezés 0,...,n számozással. Ekkor ha n-et elhagyjuk, akkor kapunk egy T szép elrendezést 0,...,n-1 számozással. Az n-húrok T-ben szétválasztóak, így 0-n kívül minden pontnak van párja. Legyen T 1-es típusú, ha 0 két n-húr között van, és legyen T 2-es típusú, ha nem, tehát a 0-t egy húr választja el a többitől.
Megmutatjuk, hogy minden 1-es típusú T elrendezés pontosan egy S elrendezésből származik, míg minden 2-es típusú elrendezés 2 különböző 2-es S elrendezésből ered.
Ha T 1-es típusú, akkor legyen 0 az A, B n-húrok között. Mivel az n-húrok szétválasztóak, ezért a T elrendezésből egyértelműen visszakaphatjuk az S elrendezést, mivel az n pontnak A, B másik végpontjai közötti íven kell lennie. Ha belátjuk, hogy egy 1-es típusú T elrendezésbe a megfelelő helyre visszarakva n-t egy megfelelő S-t kapunk, akkor készen vagyunk, hiszen a másik irány nyilvánvaló. Ha 0<k<n, akkor nyilván teljesül az állítás, hiszen a T-ben levő k-húrok S-ben is azok.
Ha n<k<2n, akkor az n-húrok párhuzamosak az elrendezés miatt, tehát létezik egy l tengely, melyre x és n-x szimmetrikusak. Ha lenne két k-húr, mely metsző, akkor az l-re szimmetrikus párjai is metszők, de ezekben a húrok végén levő számok összege 2n-k<n, ami ellentmondás.
Ha T 2-es típusú, akkor ugyanígy megy a bizonyítás, csak az n-et a 0 mindkét oldalára be tudjuk rakni, tehát kétszer annyi eset keletkezik.
Legyen Mn a szép elrendezések száma 0,...,n számozással, és legyen Ln a 2-es típusú szép elrendezések száma 0,...,n számozással. Ekkor
Mn=(Mn-1-Ln-1)+2Ln-1=Mn-1+Ln-1.

Tehát elég belátni az indukció miatt, hogy Ln-1 azon (x,y) párok száma, melyre x+y=n és lnko(x,y)=1. Ahhoz, hogy ezt belássuk, vegyünk egy 2-es típusú szép elrendezést 0,...,n-1 számozással. Számozzuk a helyeket a 0,1,2,...,(n-1)-gyel (mod n), mégpedig úgy, hogy a 0 elem a 0-s helyen legyen.
Legyen F(i) az i-edik pozícióban levő elem értéke. f egy permutációja a [0,n-1]-nek. Legyen f(a)=n-1. Mivel az n-húrok szétválasztóak 0-val, és minden pont valamely húrnak az eleme, azért az n-húrok párhuzamosak egymással, így f(i)+f(-i)=n minden i-re.
Mivel az n-1 húrok is szétválasztóak, és minden pont valamely húrnak az eleme, ezek a húrok is párhuzamosak, így f(a-1)=f(-i)-1 minden i-re, és mivel f(0)=0, azért f(-ak)=k minden k-ra. Ez egy egyenlőség modulo n, és f az 0,...,n-1 elemek egy permutációja, így (a,n)=1. Tehát Ln-1≤φ(n).
Már csak azt kell belátnunk, hogy ezek az esetek valóban megoldások. Ehhez vegyünk négy számot a körön, melyekre teljesül, hogy w+y=x+z. Ekkor a pozíciókra teljesül, hogy (-aw)+(-ay)=(-ax)+(-az), ami azt jelenti, hogy a wy és xz húrok párhuzamosak, tehát az elrendezés valóban szép, így beláttuk az állítást.