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. 1. feladat. Egy kör mentén kártyát helyeztünk el úgy, hogy mindegyik kártyának a hátoldala látható. Egy lépésben három szomszédos kártyával az alábbi helycserét végezhetjük: a három közül az egyik szélső kártyát a másik szélső kártya helyére tesszük, a fennmaradó két kártyát pedig eggyel odébbtoljuk és megfordítjuk. Ilyen lépések sorozatával elérhető-e, hogy minden kártya a kiindulási helyére kerüljön és az előlapja legyen látható?
Megoldás. Állítjuk, hogy nem létezik a feladatban leírt lépéssorozat. Indirekt bizonyítunk: tegyük fel, hogy van ilyen. Figyeljük meg, hogy minden lépésben páros sok kártyát fordítunk meg, ezért a hátoldalukat mutató kártyák számának paritása sosem változik. Mivel kiinduláskor minden kártyának a hátoldala volt látható, a lépéssorozat végére pedig ilyen kártya lett, a kör mentén elhelyezett kártyák száma páros. A kártyák helyét ezek szerint kiszínezhetjük feketére és fehérre úgy, hogy a színek felváltva következzenek a kör mentén. A helycsere szabályából adódóan ha egy kártyát egy lépésben megfordítunk, akkor a helyének a színe is megváltozik, ha pedig nem fordítjuk meg a kártyát a lépés során, akkor az ugyanolyan színű helyre kerül, mint amilyenen a lépés előtt volt. Ebből az következik, hogy ha egy kártya az eredeti helyére kerül egy lépéssorozat során, akkor annak szükségképpen a hátlapja (tehát nem az előlapja) látszik. Ez ellentmond az indirekt feltevésünknek, vagyis igazoltuk, hogy nem létezik a feladatban leírt lépéssorozat.
2. feladat. Bizonyítsuk be, hogy ha egy -vel kezdődő, egészekből álló (véges vagy végtelen) számtani sorozat bármely szomszédos tagja között van olyan, amely a többi -hoz relatív prím, akkor bármely szomszédos tagja között van olyan, amely a többi -hez relatív prím.
Megoldás. Jelölje a szóban forgó számtani sorozat különbségét. Ha páros, akkor a sorozat csupa páros számból áll. Egy ilyen sorozatra csak úgy lehet igaz a feladatban leírt tulajdonság, ha a sorozatnak legfeljebb tagja van. Ekkor persze a feladat az üreshalmaz eleméről állít valamit, tehát nincs mit bizonyítanunk. Az érdekes eset az, amikor páratlan. Tekintsük a sorozat egymást követő tagját, legyen ezek halmaza mondjuk . Mivel páratlan, azért és ellentétes paritásúak; jelölje közülük a páratlant. Ekkor a vizsgált számtani sorozat szomszédos tagja, így a feltétel szerint valamelyikük (mondjuk ) relatív prím minden eleméhez. Állítjuk, hogy teljesíti a feladat által megkívánt tulajdonságot, azaz a halmaz minden eleméhez relatív prím. Ehhez pedig csupán azt kell igazolnunk, hogy és relatív prímek. Világos, hogy páratlan, hiszen a sorozatnak van -tól különböző páros tagja, amihez relatív prím. Márpedig ha és páratlan tagjai egy páratlan különbségű számtani sorozatnak, akkor sorszámuk páros számmal különbözik, így is tagja a számtani sorozatnak. Ráadásul, mivel a ,,szélső'' eleme, is teljesül. Ezért és relatív prímek a választása miatt. Jelölje a (páratlan) és számok legnagyobb közös osztóját. Világos, hogy és mivel páratlan, azért is teljesül. Azt kaptuk, hogy közös osztója a relatív prím és számoknak. Ezt azt jelenti, hogy , tehát és is relatív prímek. Nekünk pedig éppen ezt kellett igazolnunk.
Megjegyzés. Több dolgozatban szerepel, hogy a feladatban leírt tulajdonságú számtani sorozatok differenciája páratlan. Jóllehet ez az állítás nem igaz, az értékelés során ezt nem tekintettük komoly hibának, hiszen az ,,elnézett'' esetben a feladat állítása az üreshalmaz elemére vonatkozik. Felmerül azonban, hogy páratlan esetén nincs-e vajon ugyanerről szó. Más szóval: létezik-e egyáltalán olyan legalább 2007 tagú számtani sorozat, ami megfelel a feladat feltételeinek. ,,Szerencsére'' a válasz igen: könnyen belátható, hogy ha a -nél nagyobb és 1004-nél kisebb prímek szorzata, akkor a végtelen számtani sorozat bármely 2007 egymást követő tagja közül a középső relatív prím a többi 2006 tag bármelyikéhez.
3. feladat. Bizonyítandó, hogy a sík rácspontjainak tetszőleges véges halmazából kiválasztható olyan részhalmaz, melyre teljesülnek az alábbi tulajdonságok: a sík bármely tengelypárhuzamos (azaz függőleges vagy vízszintes) egyenese -t legfeljebb pontban metszi, bármely pontja rajta van egy -beli végpontokkal rendelkező, tengelypárhuzamos szakaszon.
1. megoldás. Azt mondjuk, hogy a megengedett részhalmaza, ha -nek minden függőleges egyenesen legfeljebb két pontja van (tehát vízszintes egyenesen lehet akár több is), és a pontjait összekötő tengelypárhuzamos szakaszok lefedik minden pontját. Létezik megengedett halmaz: ilyen -t alkotnak például mindazon pontjai, amelyek a saját függőleges egyenesükön legalsók vagy legfelsők, hiszen ekkor már a pontjai meghatározta függőleges szakaszok lefedik minden pontját. Legyen egy olyan megengedett halmaz, amelyre a pontjait összekötő függőleges (esetleg ponttá fajuló) zárt szakaszok által lefedett -beli pontok száma minimális. Állítjuk, hogy ez a kielégíti a feladat követelményeit. A halmaz megengedettsége miatt mindössze azt kell belátnunk, hogy -nak minden vízszintes egyenesen legfeljebb két pontja van. Indirekt bizonyítunk. Tegyük fel, hogy három pontja, mondjuk , és egy vízszintes egyenesre esnek úgy, hogy a a és az között van. Ha a pontot tartalmazó függőleges egyenesen -nak nincs más pontja, akkor legyen . Ha van, akkor pontosan egy van (mondjuk ). Legyen a nyílt félegyenesnek a végponthoz legközelebbi -beli pontja (ilyen van, mert ), és legyen . Mindkét esetben , -nek minden függőleges egyenesen legfeljebb két pontja van, és a pontjait összekötő tengelypárhuzamos szakaszok lefedik minden pontját. Ráadásul a pontjait összekötő függőleges (esetleg ponttá fajuló) zárt szakaszok által lefedett -beli pontok száma kisebb, mint ugyanez a szám a esetén. Ez nem lehetséges. A kapott ellentmondás igazolja, hogy a halmaz a feladatban megfogalmazott mindkét feltételt teljesíti. A fenti érvelés bár igazolja a feladat állítását, nem ad jól használható algoritmust egy megfelelő halmaz megtalálására. Az alábbi megoldás ezzel is szolgál.
2. megoldás. A halmaz mérete szerinti indukcióval bizonyítunk. Világos, hogy ha , akkor teljesíti a feladatbeli feltételeket. Tegyük fel, hogy legfeljebb pontú halmazra már igazoltuk az állítást, és legyen a halmaznak pontja. Alkossák a halmazt a azon pontjai, amelyek a saját függőleges egyenesükön legalsók vagy legfelsők. Világos, hogy teljesíti a feladat feltételét. Ha az feltétel is teljesül -ra, akkor készen vagyunk: megfelelő. Ha azonban az feltétel nem teljesül, akkor ennek az az oka, hogy van -nak olyan pontja, hogy a vízszintes egyenesén -tól balra és jobbra is van -nak pontja, mondjuk és . Az indukciós feltevés szerint az pontú halmaznak létezik olyan részhalmaza, ami minden tengelypárhuzamos egyenesen legfeljebb két pontot tartalmaz, és minden pontját lefedik a által meghatározott tengelypárhuzamos szakaszok. Állítjuk, hogy ugyanez a halmaz -hoz is megfelelő. Ehhez elegendő azt belátnunk, hogy rajta van egy -beli végpontokkal rendelkező vízszintes szakaszon. Vizsgáljuk a pontot! Mivel egy függőleges egyenes -beli legalsó vagy legfelső pontja, azért vagy , vagy egy -végpontú vízszintes szakaszon található, tehát vízszintes egyenesén van -től balra -nak pontja. Hasonlóan, ha , akkor is csak egy meghatározta vízszintes szakaszon lehet, így -nak -től jobbra is van pontja. Azt kaptuk, hogy csakugyan egy végpontú vízszintes szakasz belsejében van, tehát valóban megfelel a feladat feltételeinek, vagyis az állítás pontú halmazokra is igaz. Ezzel az indukciós lépést igazoltuk, a bizonyítást befejeztük.
Megjegyzések. 1. A 2. megoldásból úgy kaphatunk hatékony algoritmust a halmaz keresésére, hogy első lépésben képezzük a halmazt. Ha nem alkalmas -nak a bizonyításbeli pontja miatt, akkor a halmazra rekurzívan meghívjuk ugyanezt az algoritmust. Így legfeljebb alkalommal képezve a megfelelő halmazt, előbb-utóbb egy keresett -t kapunk. (Az is könnyen látható, hogy nem kell egyenként elhagyni a pontokat: megtehetjük azt is, hogy -ból egyszerre hagyjuk el összes olyan pontját, ami -beli végpontokkal rendelkező vízszintes szakasz belsejében van. Így az algoritmus gyorsabban végetér.) 2. Több hamis bizonyítás érkezett a feladatra. Legtöbbjük módszeréből az is következne, hogy tetszőleges halmazhoz egyértelműen létezik a keresett . A példa mutatja, hogy ez koránt sincs így.
3. Érdekes tulajdonsága a fenti megoldásokban konstruált halmaznak, hogy ha egy halmaz rendelkezik a feladatbeli és tulajdonságokkal, akkor minden -beli végpontokkal rendelkező függőleges szakasz része egy meghatározta függőleges szakasznak, továbbá minden meghatározta vízszintes szakasz része egy -beli végpontokkal rendelkező vízszintes szakasznak. Más szóval a ,,legmagasabb'' és egyben ,,legkeskenyebb'' a kívánt tulajdonságú halmazok között. Természetesen ha a -kal elforgatott ábrán végezzük el a konstrukciót (azaz a függőleges és vízszintes szavakat felcseréljük a bizonyításban), akkor a ,,legalacsonyabb'' és ,,legszélesebb'' megoldást kapjuk meg. 4. A feladat szoros rokonságot mutat Gale és Shapley (sajnos nem eléggé) ismert ,,stabil házassági'' tételével. |