Feladat: 1989. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Fleiner Tamás 
Füzet: 1989/november, 353 - 354. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1989/szeptember: 1989. é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.

A megoldásból talán látható, miért ez a feladat tetszik legjobban az összes közül, hiszen elkerüli a leszámolást vagy a becslést. Eleinte én is becsülgetős, vagy indukciós megoldást akartam adni, azonban mikor ez nem sikerült, és a másik két feladat eléggé felbosszantott, úgy döntöttem, hogy ezt hamar megoldom, ami sikerült is. Eleinte magam sem akartam elhinni, hisz mégis a hatodik ‐ a zsűri által a legnehezebbnek tartott ‐ feladatról van szó, de sokszori átgondolás után sem találtam hibát, így kényszerűen elhittem, hogy elegáns megoldást leltem.
Megadok egy kölcsönösen egyértelmű megfeleltetést, mely a nem jó permutációkat leképezi a jók egy részhalmazára.
Minden 1≦i≦2n egész számra az i párjának nevezem azt a k egész számot, melyre 1≦k≦2n és |i-k|=n. Így az 1,2,...,2n számokat párokba soroltam. Tekintem a nem jó x1,x2,x3,...,x2n permutációt. Legyen az x2n párja xk.
Ekkor e rossz permutáció megfelelője az

x1,x2,...,xk,x2n,...,x2n-1

jó permutáció lesz, hisz |xk-x2n|=n. A nem jó permutációk megfelelői azon jó permutációk lesznek, melyekre
∃i∈{1,2,...,2n-1},hogy|xi-xi+1|=n
és ezen i-re, i≠2n-1, tehát egyetlen szomszédos pár nincs a permutáció végén. Az így kapott jó permutációk mindegyikéből rekonstruálható az eredeti nem jó, tehát a megfeleltetés valóban kölcsönösen egyértelmű.
Ez azt jelenti, hogy a nem jó permutációk száma azonos az előbbi típusú, jó, permutációk számával.
Ezen permutációk pedig kevesebben vannak, mint a jók, hisz az 1,n+1 végű jó permutációk nem tartoznak a rosszak képeihez.