Surányi László
Fazekas táborok 1987-2003
Válogatás
Surányi László
Válogatás a Fazekas táborok feladataiból (1987-2003) Először pár olyan feladatot mutatunk be, amelyet „feladója” maga talált ki. Az első feladatot a 2002-es táborban adta fel Maga Péter: 1. feladat Legyen β tetszőleges pozitív egész. Bizonyítsuk be, hogy van olyan (n,p) számpár, ahol n≥2 egész és p pozitív prím, továbbá L=(pβn)1/n racionális, de csak véges sok ilyen számpár van. MEGOLDÁS: A számelmélet alaptételéből következik, hogy ha egy egész szám n-edik gyöke racionális, akkor egész. Tehát L egész, és pβn = Ln. Tegyük fel, hogy n osztható egy p-től különböző r prímmel. Ezzel L-nek is oszthatónak kell lennie. Ha L az r számnak pontosan h-adik hatványával osztható, akkor a jobb oldal és így n is a hn-edik hatványával osztható. De r legalább kettő, h legalább egy, így n legalább 2n volna, ami lehetetlen, mert 2n > n. Ezek szerint n-nek egyetlen prímosztója lehet: p. Minthogy p prím, szerepelnie kell L prímfelbontásában. Tegyük fel, hogy p a k-adik hatványon szerepel L-ben. Ekkor n-ben nk–β-adik hatványon szerepel. Azt kaptuk, hogy n=pnk–β. Ez teljesül, ha n=p a β+1 szám egy prímosztója és k=(β+1)/p. S valóban: ha p is, n is a β+1 szám azonos prímosztója, akkor L=(pβp)1/p=p(β+1)/p, s mivel itt a kitevő egész szám, ezért L racionális, sőt egész. Jelöljük most nk–β-t m-mel. Ekkor a feladat azt követeli, hogy p(β+m)/n racionális legyen. De mivel p prím, ez csak úgy lehetséges, ha a kitevő egész szám. Tehát β+m-nek oszthatónak kell lennie n=pm-mel. Ha m>β, akkor β+m<2m-nek kell oszthatónak lennie pm-mel, amiből következik, hogy pm<2m. β pozitív egész, tehát m legalább kettő, s ezesetben már 2m sem kisebb 2m-nél. Azt kaptuk, hogy m legfeljebb β lehet. Ez m-re véges sok lehetőség. Ha m minden lehetséges értékére megnézzük β+m prímosztóit, ezek is véges sokan vannak és kimerítik az összes lehetőséget p-re. Ezek közül csak azok felelnek meg, amelyekre pm-nel is osztható β+m. Így megkapjuk az (n,p) számpárok összes lehetséges értékét, és ez véges sok lehetőség.
1/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
A következő feladatot a 2003-as táborban adta fel Gáspár Merse Előd, és bár a tábori „játékszabályok” szerint csak egy csapatnak kellett volna megoldania, mindenkinek hamar a kedvence lett: 2. feladat Adott két tetszőleges hosszúságú (szakasznak tekintendő) rúd. Az egyik vége (A) egy asztalhoz (mint síkhoz) rögzített csukló körül szabadon elfordulhat az asztal síkjában (a csuklót pontnak tekintjük). A másik rúd az egyik végével (B) az első rúd még C A
B
szabad végéhez (amelyik elmozdulhat az asztalhoz képest) kapcsolódik ugyancsak egy csukló által, ami körül a második rúd is csak az asztal síkjában mozoghat. A második rúd szabad végét (C), ami nincsen csuklóhoz kapcsolva, nevezzük a csuklós szerkezet végpontjának. Valaki elkezdi véletlenszerűen mozgatni a csuklós szerkezetet és a végpontja által kijelöl hét pontot az asztalon. Bizonyítandó, hogy az adott hét ponttal rajzolható olyan teljes hét pontú gráf az asztalra, hogy utána a hét pont egyikéből indítva a csuklós szerkezet végpontját végig lehet vezetni úgy, hogy az éleken halad, mindegyiken pontosan egyszer, visszaérkezik az eredeti induló pontba és a folyamat során nincsen kétszer ugyanabban a helyzetben, kivéve amikor a végpont a hét pont valamelyikében van éppen. Ennek a feladatnak már a megértése is nagy izgalmakat jelentett. Ebben próbálunk itt segítséget adni. Előzetes megjegyzés a 2. feladathoz A nehézséget az okozza, hogy a hét pontú teljes gráfot (K7) csak úgy lehet lerajzolni a síkban, hogy az élek számos helyen metszik egymást. Egy-egy ilyen metszéspontban a csuklós szerkezet két vége (A és C) ugyanott van a metszésponton való két áthaladáskor, csak a B pont helyzete lehet más, ezért lehet a szerkezet a két alkalommal más helyzetben. Ha A és C helyét rögzítjük, akkor a szerkezet rúdjai hosszának rögzített volta miatt a B pont helyzetére két – egymásra az AC tengelyre tükrös – lehetőség van. A gráf lerajzolását majd bejárását tehát úgy kell megtervezni, hogy a metszéspontoknál a két áthaladáskor a két tükrös helyzet forduljon elő. A mellékelt ábrán pl. a szerkezet végpontja az egyik vonalon az (A, B-, C- ), (A, B, C ), (A, B+, C+ ) állapotokon keresztül, a másik vonalon a (A, B’, C’ ), (A, B’, C’ ), (A, B’+, C’+ ) állapotokon keresztül halad végig, a két vonal a C=C’ pontban metszi egymást, de a szerkezet állapotai különbözőek (B≠B’).
B'
B'-
C'-
C=C' B
A
BB+
C+ B'+
C-
C'+
Megoldás A rúdszerkezet lehetséges állapotai kölcsönösen egyértelműen megfeleltethetők egy tórusz (donut, amerikai fánk) felület pontjainak.
A kép forrása: http://www.jgytf.u-szeged.hu/tanszek/matematika/polieder/toroid/
2/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Valóban, a szerkezet állapotát két szög írja le. Az első szög az AB félegyenes forgásszöge egy előre rögzített AB0 félegyeneshez képest. A másik szög a BC félegyenes szöge az AB félegyeneshez képest. A tórusz pontjai is épp két szögértékkel jellemezhetők. A kapcsolat fizikailag is megteremthető. Ha a BC rudat nem az AB rúd mozgásának Σ síkjában, hanem egy arra merőleges AB-n átmenő síkban vesszük fel és ott forgatjuk, akkor a C pont egy tórusz pontjait írja le (feltéve, hogy BC < AB, amit feltehetünk, mert a bijekció kedvéért a BC-t a tórusz képzésekor egyszerűen lerövidíthetjük). A 2. feladat megoldása így visszavezet a következő feladatra (ami már korábbi táborban egyébként szerepelt).
2a. feladat Bizonyítandó, hogy a tóruszra lehet teljes hétpontú gráfot rajzolni úgy, hogy semelyik két él ne messe egymást az él belső pontjában. A 2a. feladat megoldása (az ábra a http://www.mathrec.org/old/2001nov/solutions.html honlapról származik) Az ábrán látható négyzetből tóruszt lehet készíteni, ha alsó és fölső vízszintes oldalait összeragasztjuk, majd az eredetileg bal és jobb oldali függőleges oldalakat is összeragasztjuk. A gráf csúcsai a színes tartományok középpontjai. A hét színes tartomány közül bármelyik kettő szomszédos, a szomszédok középpontját él köti össze, így létrejön a tóruszon a hét csúcsú teljes gráf.
A következő feladat Szobonya Lászlótól származik: 3. feladat Bizonyítsuk be, hogy a következő összeg kisebb egynél: 1 n 1 n 1 n 1 +∑ 3 +∑ 5 + ∑ 8 . ∑ 2 i=2 i i =2 i i =2 i i=2 i n
MEGOLDÁS Az összeget átrendezzük és minden i-re összeadjuk a négy megfelelő tagot. A négytagú összeget felülről
1 1 1 1 + 3 + ... + m < összeggel. Tehát a feladatban szereplő összeget felülről 2 i i i i (i − 1) n ∞ 1 1 becsülhetjük a ∑ <∑ = 1 összeggel. Természetesen a feladatban az összes, egynél magasabb i = 2 i (i − 1) i = 2 i (i − 1) becsülhetjük az
k-ra vehetjük a k-adik hatványok reciprokösszegét, így összegük pontosan egyhez tart. S mivel összetett k-ra a kadik hatványok több összegben is szerepelnek, azt kapjuk, hogy az egynél nagyobb hatványok reciprokösszege kisebb egynél.
Most egy másik érdekes tábori esetet írunk le. A szereplő feladat jó példa arra, hogy két, látszatra igen hasonló feladat mennyire különböző természetű lehet: az első változat lényegében halmazelméleti indukciós feladat, a második viszont számelméleti feladat. Az egyik tanuló az 1987-as táborban a következő feladatot adta fel (legalábbis összes jegyzeteink tanúsága szerint ebben a formában hangzott el a feladat): 4. feladat Az X halmaz a racionális számok tökéletes bázisa, ha részhalmaza a racionális számoknak, és bármely racionális számot megkaphatunk úgy, hogy néhányat közülük kiválasztunk és a kiválasztott számokat pozitív vagy negatív előjellel összeadjuk. Bizonyítandó, hogy X-ből véges sok elemet elvéve ismét tökéletes bázist kapunk.
3/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Ez a feladat egy nevezetes algebrai feladatot fogalmaz meg, kétértelmű formában. Az eredeti feladat azt mondja ki, hogy a racionális számok csoportjának nincs legszűkebb generáló rendszere. De valaki rákérdezett, hogy szerepelhet-e többször ugyanaz az elem, és a kitűző tévedésből azt a választ adta, hogy nem. Ebben a formájában a feladatot akkor senki nem tudta megoldani, és a megbeszélésére sem maradt idő. Viszont többször visszatértem rá következő táborokban, ott sem sikerült rá senkinek megoldást találnia rá. Sőt: akkor sem sikerült, amikor e táborok résztvevői is már egyetemisták, majd gyakorló matematikusok lettek. Próbálkoztunk mod 3 test fölötti megoldással is, semmi eredmény. Hogy miért nem, annak egyszerű magyarázata van: az állítás ugyanis ebben a formában nem igaz. Amint megpróbáltuk megcáfolni az állítást, rögtön sikerült. A feladat tehát most így alakult: 5. feladat Az X halmaz a racionális számok tökéletes bázisa, ha részhalmaza a racionális számoknak, és bármely racionális számot megkaphatunk úgy, hogy néhányat közülük kiválasztunk és a kiválasztott számokat pozitív vagy negatív előjellel összeadjuk. Bizonyítandó, hogy van olyan tökéletes bázis, amelynek bármely elemét elhagyva megszűnik tökéletes bázis lenni. MEGOLDÁS Rendezzük akárhogyan sorozatba a racionális számokat és vegyük sorra őket. A soron következőt akkor választjuk be a bázisba, ha nem áll elő már beválasztott számok előjeles összegeként. Nyilvánvaló, hogy az így kapott halmaz a racionális számok részhalmaza lesz, sőt tökéletes bázis lesz. Tegyük fel most, hogy egy x eleme fölösleges, azaz elhagyásával is tökéletes a bázis. Ekkor x felírható a bázis más elemeinek előjeles összegeként: x = ±y1 ±y2 ±… ±ym, ahol a ± azt jelenti, hogy minden yi-t vagy pozitív, vagy negatív előjellel számítunk. Feltehetjük, hogy az yi-ket olyan sorrendben írtuk fel, ahogyan sorra jöttek a rendezésben. Nyilvánvaló, hogy x nem jöhetett az összes szereplő yi után sorra, hiszen akkor nem választottuk volna be a bázisunkba. Tehát ym biztosan x után került sorra. De akkor átrendezhetjük az egyenletet ym-re: ym = ±x ±y1 ±y2 … ±ym–1. Vagyis ym előáll korábban szereplő és már kiválasztott számok előjeles összegeként, tehát nem választhattuk ki. Ez az ellentmondás bizonyítja, hogy x nem hagyható el a bázisunkból. Minthogy x tetszőleges elem volt, bebizonyítottuk, hogy ez a tökéletes bázis nem tartalmaz fölösleges elemet. MEGJEGYZÉS Transzfinit rekurzióval ugyanígy kapjuk, hogy például a valós számoknak is van olyan tökéletes bázisa, amelyből nem hagyható el elem. Vagyis ez a megoldás lényegében halmazelméleti megoldás.
Ezután lássuk az eredeti feladat helyes szövegét és annak megoldását: 4a. feladat Az X halmaz a racionális számok tökéletes bázisa, ha részhalmaza a racionális számoknak, és bármely racionális számot megkaphatunk úgy, hogy néhányat közülük kiválasztunk – egy számot többször is kiválaszthatunk! – és a kiválasztott számokat pozitív vagy negatív előjellel összeadjuk. Bizonyítandó, hogy X-ből véges sok elemet elhagyva ismét tökéletes bázist kapunk. Ez volt tehát az eredeti feladat, s ez, mint említettük, számelméleti feladat és szorosan kapcsolódik a racionális számokhoz. MEGOLDÁS Nyilván elég azt bebizonyítani, hogy ha egy – így értelmezett – tökéletes bázisból elhagyunk egy elemet, akkor ismét tökéletes bázist kapunk. A továbbiakban tökéletes bázis helyett egyszerűen bázist mondunk. Először is átfogalmazzuk a feladatot:
4/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
A racionális számok egy Y részhalmazát bázisnak nevezzük, ha minden racionális szám előáll ∑niyi alakban, ahol ni-k egész számok, yi-k pedig Y elemei. Bizonyítandó, hogy Y bármely eleme elhagyható úgy, hogy a maradó halmaz is bázis. Nyilvánvaló a következő: ha Y bázis, és minden elemét megszorozzuk a nullától különböző r racionális számmal, akkor továbbra is bázist kapunk. Az így kapott halmazt rY-nal jelöljük. (Ha az x számot akarjuk előállítani, az eredeti Y-ból előállítjuk az x/r számot és az előállítás minden elemét megszorozzuk r-rel, így kapjuk az rY-beli előállítást.) Legyen a az elhagyandó szám. Ekkor a Z=(1/a)Y bázisnak eleme az 1, és elég belátnunk, hogy ebből a bázisból elhagyva az 1-et továbbra is bázis marad. (Ekkor az eredeti bázisból az a-t elhagyva ennek a-szorosát kapjuk, és az is bázis.) Elég belátnunk, hogy Z-nek van 1/N alakú eleme, ahol N egész szám, hiszen ekkor 1 előáll N(1/N) alakban, s ha egy szám előállításában szerepel az 1, akkor ezzel helyettesíthető. Tegyük fel, hogy találunk olyan yi = ai/bi elemeket Y-ban, amelyek számlálói összességükben relatív prímek (ai/bi a redukált alak, tehát a számláló és a nevező relatív prím), s amelyek között nem szerepel az 1. Legyen ezek legkisebb közös nevezője N, és yi = xi/N. Azt állítjuk, hogy xi-k is összességükben relatív prímek. Tegyük fel ugyanis, hogy nem így van és mindegyiket osztja ugyanaz a p prím. Ez a prím nyilván nem osztója N-nek, hiszen akkor egyszerűsíteni lehetne vele minden törtet, s N nem volna a legkisebb közös nevező. De ha N-nek nem osztója p, akkor egyik bi nevezőnek sem osztója. Másrészt az eredeti számlálók összességükben relatív prímek voltak, tehát van egy tört, amelynek ai számlálója sem osztható p-vel. Ennek új számlálója csak úgy válhatott volna p-vel oszthatóvá, ha a közös nevezőre hozáskor p egy többszörösével bővítettük volna, erre viszont nem volt okunk, hiszen egyik nevező sem osztható p-vel. Tehát a bővített számlálók, azaz az xi-k is relatív prímek összességükben. Ismeretes, hogy ha az xi egész számok relatív prímek, akkor vannak olyan ni egészek, amelyekre ∑nixi = 1. De ekkor ∑niyi = 1/N, tehát az 1/N előáll a kívánt alakban, s ezt az előállítást N-nel szorozva az 1-nek is kapunk egy olyan előállítását, amelyben 1 nem szerepel az yi-k között. Minden olyan szám előállításában, ahol szerepel az 1, helyettesíthető ezzel az előállításával, s így 1 valóban elhagyható. Elég tehát olyan yi-ket keresnünk, amelyeknek számlálói relatív prímek, s amelyek között nem szerepel az 1. Legyen a/b a Z bázisnak egy tetszőleges, 1-től különböző eleme, legyenek a és b relatív prímek, és legyenek p1, p2,…, pn az a szám prímosztói. Azt állítjuk, hogy minden p prímhez van olyan eleme Y-nak, amelynek redukált alakjában a nevező osztható p-vel. Ebből viszont következik, hogy a számlálója nem osztható p-vel. Ha minden pi-hez kiválasztunk egy ilyen yi törtet, akkor a/b, y1, y2, …, yn számlálói összességükben relatív prímek. Pont ilyen számokat kerestünk. (Nyilvánvaló, hogy az yi számok egyike sem lehet 1.) Már csak azt kell belátnunk, hogy minden p prímhez van olyan tört a bázisban, amelynek redukált alakjában a nevező osztható p-vel. Ehhez elég meggondolni, hogy 1/p is racionális szám, tehát előáll ∑nixi/zi alakban, ahol xi/zi egy-egy bázisbeli szám redukált alakja. Ha itt egyetlen nevező sem volna osztható p-vel, akkor az egész összeget közös nevezőre hozva a nevező továbbra sem osztható p-vel, s így az előállított szám nem lehet 1/p. Ezzel a bizonyítást befejeztük.
Most egy másik feladatot mutatunk be, amelynek megoldására abban a táborban senki nem jött rá, kitűzője azonban két szép és tanulságos megoldást is mutatott rá: 6. feladat Egy szakaszban őrmesterek és közlegények szolgálnak. Minden közlegénynek egy vagy két őrmestere van. Bizonyítandó, hogy leszerelhető a szakasznak legfeljebb a fele úgy, hogy a le nem szerelt szakasz közlegényeinek pontosan egy őrmestere maradjon. I. MEGOLDÁS Ez a megoldás egy egyszerű, de jól használható ötleten alapszik: ahelyett, hogy bebizonyítanánk, hogy van olyan eset, amikor a leszerelt katonák száma nem haladja meg a kívánt mértéket (jelen esetben a katonák felét), azt bizonyítjuk be, hogy hogy az összes lehetséges esetben átlagosan a katonák legfeljebb felét kell leszerelni. Ehhez csak a binomiális együtthatókkal kell tudni kicsit bánni, és ezt a „bánásmódot” szintén nem árt elsajátítani. Legyen az őrmesterek száma o, a közlegényeké k. Először tegyük fel, hogy o=2l páros. Gondolatban szereljük le minden lehetséges módon az őrmesterek felét, és szereljük le hozzá azokat a közlegényeket, amelyeknek nem maradt őrmestere vagy továbbra is két őrmestere maradt. Ha egy közlegénynek eredetileg egy őrmestere van, akkor pontosan annyiszor szereljük le gondolatban, ahányszor az őrmesterét, ez az eseteknek pont a fele. Ha egy közlegénynek két őrmestere van, akkor akkor
5/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
szereljük le, ha a) mindkét őrmesterét leszereltük, b) egyik őrmesterét sem szereltük le. a) eset
2l − 2 l−2
2l − 2 alkalommal következik be. A két binomiális együttható értéke l
alkalommal következik be, b) eset
megegyezik, másrészt könnyen belátható, hogy
2l − 2 2l − 1 2l − 2 2l − 1 l 2l 1 2l 2 < = = = . Vagyis az ilyen közlegényt az eseteknek l − 2 l − 1 l − 2 l − 1 2l l 2 l kevesebb, mint felében szereltük le gondolatban. Ez azonban azt jelenti, hogy egy közlegényt átlagosan kevesebb mint félszer szereltünk le, tehát átlagosan a közlegényeknek kevesebb mint a felét szereltük le. És ezt kellett bizonyítanunk. Ha o=2l+1 páratlan, akkor gondolatban minden lehetséges módon leszerelünk l őrmestert. Egy őrmestert most kevesebb, mint az esetek felében szerelünk le, tehát az olyan közlegényt is, akinek egy őrmestere van. Azokat a közlegényeket,
amelyeknek
két
őrmestere
van,
a)
esetben
2l − 1 l−2
alkalommal,
b)
esetben
2l − 1 2l − 1 = alkalommal szerelünk le, e két binomiális együttható összege az összes eset felénél, l l −1 2l + 1 2l 2l 2l − 1 2l 2l − 1 ugyanis az összes eset: = + = 2 + . l l l − 1 l −1 l −1 l − 2 II. MEGOLDÁS Ehhez szükségünk lesz egy segédtételre, amit későbbi táborban szintén kitűztünk feladatként:
7. feladat Bizonyítsuk be, hogy egy véges gráfból elhagyható az élek fele úgy, hogy a maradó élek a gráf ponthalmazán egy páros gráfot alkossanak. A 7. feladat I. megoldása Ezt a feladatot az úgynevezett mohó algoritmussal lehet könnyen megoldani. A gráf pontjait sorban fogjuk kiszínezni egyes vagy kettes színűre. Az első pontot egyes színűre színezzük. Ezután sorra vesszük a pontokat. A sorra jövő pontot jelöljük x-szel. Megnézzük, hogy a már színezett pontok közül az egyes vagy a kettes színűekhez vezet-e több él x-ből. Amelyikbe kevesebb vezet, azokat az éleket elhagyjuk, és a pont színének ezt választjuk. Így minden lépés után igaz a következő: ha nézzük azokat az éleket, amelyeknek mindkét vége ki van színezve és nézzük azokat, amelyeket elhagytuk, akkor az utóbbiak legfeljebb annyian vannak, mint az előbbiek. (Minden lépésben legalább annyi él lett „színes”, mint ahányat elhagytunk és ha egy élnek mind a két vége ki van színezve, azt már nem hagyjuk el.) Ez tehát az utolsó lépés után is igaz, így legfeljebb annyi élt hagytunk el, mint ahányat teljesen kiszíneztünk, és minden teljesen színezett élnek különböző színűek a végpontjai. Ezzel a feladat állítását beláttuk. MEGJEGYZÉSEK: 1.Vegyük észre, hogy megoldásunk akkor is működik, ha a gráf nem egyszerű, többszörös éleket is megengedünk. Hurokéleket viszont nem engedünk meg. 2. Látszólag durván becsültünk, mindenesetre nagyon kényelmesek voltunk (a mohó algoritmusnál mindig kényelmesek vagyunk). A kapott állítás mégis lényegében éles. Ha ugyanis a gráf teljes gráf 2n ponton, akkor 2n2–n éle van. A legnagyobb belőle nyerhető teljes gráf élszáma n2, tehát az élek felénél alig valamivel kevesebbet tudunk elhagyni: n2–n-et n2– n/2 helyett. A 7. feladat II. megoldása Osszuk be a gráf csúcsait minden lehetséges módon két osztályba és hagyjuk el az egy osztályon belüli éleket. Azt állítjuk, hogy így átlagosan pont az élek felét hagyjuk el, amiből következik, hogy van olyan eset, amikor legfeljebb az élek felét kell elhagynunk. Hogy átlagosan az éleknek pont a felét kell elhagynunk, azt a következőképpen bizonyítjuk. Egy adott él két végpontja ugyanis ugyanannyiszor szerepel egy osztályban, mint két osztályban. Hiszen mindkét esetben rögzített e két pont helye, és a többi pontot kell tetszőlegesen besorolni a két osztályba. Ha n csúcs van, ez mindkét esetben 2n–2 lehetőség (az összes besorolás száma pedig 2n–1.)
6/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Most térjünk vissza a 6. feladatra: II. MEGOLDÁS a 6. feladatra Tekintsük azt a gráfot, amelynek pontjai az őrmesterek, két pont annyi éllel van összekötve, ahány közlegénynek e két őrmester az őrmestere. Tehát a gráf pontjai az őrmesterek, élei a „két őrmesterű” közlegények! Ez a gráf nem egyszerű, de az előző feladat után tett második megjegyzés szerint akkor is igaz, hogy elhagyható az élek legfeljebb fele úgy, hogy a maradó gráf páros legyen. Ezzel elhagytuk a „két őrmesterű” közlegényeknek legfeljebb a felét. Az őrmestereket pedig két csoportba osztottuk, A-ba és B-be. Minden él A és B között fut, tehát minden maradó közlegénynek vagy egy őrmestere van (nem szerepelt az eredeti gráfban sem), vagy egy A és egy B-beli őrmestere. Ha akár A-t, akár B-t elhagyjuk, ezeknek a közlegényeknek is egy-egy őrmestere marad. De tekintettel kell még lennünk az eredetileg egy őrmesterű közlegényekre. Ha A-t hagyjuk el, el kell hagynunk azokat közülük, akiknek őrmestere A-beli. Legyen az ilyen közlegények halmaza A’ és ugyanígy legyen B’ azoknak a közlegényeknek a halmaza, akiknek egy őrmestere van, és az B-beli. Nézzük meg, hogy A∪A’ és B∪B’ közül melyiknek van kevesebb eleme, és szereljük le az oda tartozó katonákat. Most már minden maradó közlegénynek csak egy őrmestere marad. A „két őrmesterű” közlegényeknek megmaradt legalább a fele és a többinek, tehát az őrmesterek és az „egy őrmesterű” közlegények együttes halmazának is megmaradt legalább a fele. Ezzel bebizonyítottuk a feladat állítását.
Az alábbi feladatot „feladója” valószínűleg a KöMaL-ból vette. A feladat érdekessége az, hogy bár nyilvánvalóan nem nehéz, a táborban senki nem tudta megoldani. Ezen a tapasztalaton felbuzdulva a feladatot néhány év múlva „tanári feladatként” feladtuk, mint nehéz feladatot. Az akkori résztvevők pillanatok alatt megcsinálták és nem értették, hogy mi ebben a nehéz. A „nehézségnek” tehát pszichológiai okai lehettek, hiszen a táborban igen jó feladatmegoldók is voltak, köztük versenynyertesek és olyanok, akik ma világhírű matematikusok. 8. feladat Egy pontszerű fényforrást akarunk eltakarni gömbökkel úgy, hogy egy méter távolságból sehonnan ne látszódjon. A gömbök tömörek, tehát nem nyúlhatnak egymásba és nem tartalmazhatják a fényforrást. Hány gömbre van szükségünk ehhez? MEGOLDÁS: Hogy a fényforrás nem látható, azt jelenti, hogy a belőle induló minden félegyenes beleütközik valamelyik gömb felszínébe. A kérdés tehát az, hogy hány gömbbel érhető el, hogy egy adott P pontból induló minden félegyenes beleütközzön valamelyik gömb felszínébe. Könnyen belátható, hogy három gömb nem elég (erre még azok is hamar rájöttek, akiknek a második rész nehéznek bizonyult): vegyük a három gömb középpontja által meghatározott síkot. A fényforrásból induló, erre a síkra merőleges fénynyalábot a három gömb egyike sem fogja fel. (Ez két félegyenest is jelent.) Négy gömb viszont elegendő. Ehhez először gondoljuk meg a következőket: ha találunk négy gömböt, amely együttesen eltakarja a fényforrást x méter távolságra, akkor a fényforrásból 1/x arányban kicsinyítve a négy gömböt elérhető, hogy egy méteres távolságban ne lássuk a fényt. Továbbá: nem baj, ha a gömböknek van közös része, hiszen a gömböket tetszőlegesen nagyíthatjuk a középpontból, ezzel csak azon változtatunk, hogy milyen távolról lesz láthatatlan a fényforrás. Ezek után a legközelebb levő gömböt hagyjuk változatlanul, a másodikat nagyítsuk ki úgy, hogy már ne legyen közös része az elsővel, a harmadikat nagyítsuk ki úgy, hogy ne legyen közös része az első kettő egyikével sem, végül a negyediket nagyítsuk fel úgy, hogy ne legyen közös része a másik három egyikével sem. Ezzel elértük, hogy a négy gömb nem nyúlik egymásba, és továbbra sem tartalmazza egyik sem a fényforrást. Valamilyen x távolságból továbbra is eltakarják a fényforrást. Ezután az egész rendszert a fényforrásból 1/x arányban kicsinyítve kapunk négy gömböt, amelyek együtt egy méteres távolságra láthatatlanná teszik a fényforrást. Elég plauzibilis, hogy a négy gömbnek „szimmetrikusan” kell elhelyezkednie. Ha azonban megpróbálunk négy gömböt „szimmetrikusan” elhelyezni és ezekről bebizonyítani, hogy a felszíneik felfogják a fényforrásból induló félegyeneseket, akkor a feladat nehezebbnek bizonyul, mint amilyen valójában. Ehelyett gondoljuk meg a következőt! A négy „szimmetrikusan” elhelyezkedő gömb középpontját tekinthetjük egy olyan szabályos tetraéder négy csúcsának, amelynek középpontja éppen a fényforrást jelképező P pont. A P pont nyilván el lesz takarva, ha a tetraéder minden oldallapját lefedi a négy gömb. Legyen a tetraéder bármelyik oldallapján a lap középpontjának a lapon fekvő csúcstól vett távolsága R.
7/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
R R
R
Ha a tetraéder négy csúcsa körül egy-egy R sugarú gömböt veszünk fel, akkor ezek mind a négy oldallapot lefedik, tehát nem engedik át a fénysugarakat. Vitatható még, hogy a P pontot valamelyik lapközépponttal összekötő félegyenest is letakartuk-e ezzel. Ezt a vitát megelőzendő válasszuk a négy gömb sugarát kicsit nagyobbnak R-nél. Ekkor átfedhetik ugyan egymást, de ez mint láttuk, nem okoz gondot. Végül arra kell még vigyáznunk, hogy a gömbök magát a P pontot nem tartalmazzák. Legyen a tetraéder egyik lapközéppontja S, e lap egyik csúcsa A. Ekkor az APS háromszögben S-nél derékszög van, tehát AP>AS=R. Ha tehát a gömbök sugarát R-nél nagyobbnak, de AP-nél kisebbnek választjuk, akkor ez a feltétel is teljesült. Ezzel beláttuk, hogy három gömb nem elég a fényforrás eltakarásához, de négy elég. Megjegyzés Még egyszerűbben célhoz érünk, ha a tetraéder minden lapját letakarjuk egy, a középpontját nem tartalmazó gömbbel. Ilyen gömb nyilván van.
9. feladat A feladat nehezíthető, ha nem azt kérdezzük, hogy hány gömb kell az eltakaráshoz, hanem azt, hogy hány konvex test szükséges ehhez. A gömb konvex, tehát négy konvex test elég. De nem elég-e három? (A testek most sem tartalmazhatják a fényforrást.) Feltesszük, hogy a testek korlátosak. MEGOLDÁS: Megmutatjuk, hogy három konvex testtel nem lehet eltakarni a fényforrást. Ha egy konvex test nem tartalmazza a P ponttal jelölt fényforrást, akkor van olyan sík, amely elválasztja a fényforrástól. (Ennek bizonyítását a megoldás végén közöljük.) Vegyünk tehát három tetszőleges konvex testet, amelyek egyike sem tartalmazza a P pontot. Legyen S1, S2, S3 a három sík, amely e három testet elválasztja a P ponttól. Tekintsük mindegyik síkhoz azt a félteret, amely tartalmazza P-t (tehát nem tartalmazza a megfelelő test egyetlen pontját sem). E három féltérnek tehát közös pontja P. Másrészt e három sík egy triéder belsejét alkotja, és nyilvánvaló, hogy a P pont itt helyezkedik el, akkor van egy P-ből induló teljes félegyenes is e triéder belsejében, ezt a fénynyalábot tehát nem takarja el a három test. Ha a triédernek van csúcsa, akkor az abból induló, P-n átmenő félegyenes megfelel. De ha P végtelen távoli pont, ez akkor is igaz: a három „éllel” párhuzamos, P-n átmenő egyenest tartalmazza. Azt kell még belátnunk, hogy ha egy konvex test nem tartalmazza a P pontot, akkor van olyan sík, amely a testet és P-t elválasztja. Feltehetjük ugyanis, hogy a konvex test zárt (ha nem az, lezárjuk), és tekinthetjük a testnek azt az L pontját, amely legközelebb van P-hez. Ilyen pont a korlátos zárt halmazok ismert tulajdonságai szerint van. A PL szakasz felezőmerőleges síkja nyilván elválasztja egymástól a testet és a P pontot. Ha ugyanis P oldalán lenne egy M pontja a testnek, akkor a PM szakasz egésze a testhez tartozna, mivel a test konvex. Tekintsük a PML háromszöget. Ha ebben a háromszögben M-nél nem hegyesszög van, akkor PL a legnagyobb oldal, tehát M pont közelebb volna P-hez, mint L és ez ellentmond L választásának. Ha M-nél hegyesszög van, akkor a P pontból PM egyenesre bocsátott merőleges T talppontja rajta van a PM szakaszon és közelebb van P-hez, mint L, hiszen LTP szög derékszög. Most tehát T van közelebb P-hez, mint L, s ez megint ellentmondás. Ezzel beláttuk, hogy ha egy korlátos konvex test nem tartalmazza P-t, akkor van olyan sík, amely a testet és P-t elválasztja. (Érdemes elgondolkozni azon, hogy igaz-e ez nem-korlátos konvex testre is.) Három konvex testtel tehát nem takarható el a fényforrás.
8/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Most pár olyan feladat következik, főleg a diákok által hozottak közül, amelyek egyegy jól használható ötletet követelnek. 10. feladat A H konvex hatszöget tetszőlegesen átdarabolva véges sok konvex sokszögre a sokszögek oldalszámátlaga kisebb hatnál. Erre a feladatra két olyan megoldást is bemutatunk, amelyek mindegyike egy másutt is jól használható ötletet használ. I. MEGOLDÁS Minden sokszög belsejében vegyünk fel egy pontot, a hatszögön kívül is. Két ilyen pontot akkor kötünk össze, ha a két sokszögnek van közös oldala (H külsejét tekintjük sokszögnek). A sokszögek konvexitása miatt síkbarajzolható gráfot kapunk. (Ez a másutt is használható ötlet.) Ha k sokszögre daraboltuk a hatszöget, akkor a gráf pontszáma k+1, élszáma pont fele annyi, amennyi oldala a feldaraboló sokszögeknek együttesen van, vagyis az élszám kétszerese, 2e, a sokszögek összoldalszáma. Ismert, hogy síkbarajzolható gráf élszáma legfeljebb 3(k+1)–6=3k–3, vagyis 2e/k<6, amit bizonyítani kellett. A felhasznált gráfelméleti segédtételt úgy bizonyítjuk, hogy behúzunk minden olyan élt, ami nem rontja el a síkbarajzolhatóságot, így háromszögekből álló poligonhálót kapunk. A c–e+l=2 Euler-formulában ekkor e=3l/2 (minden lapon 3 él van, minden él két lapon szerepel), s ebből következik az állítás. II. MEGOLDÁS A feldarabolás után a szögátlag minden belső pontban legfeljebb 120°, mert a konvexitás miatt minden belső pontban legalább három sokszög találkozik. A határ-hatszög csúcsaiban is, és az esetleg a határon levő csúcsokban < 120°. Ha ilyen pont nincs, akkor valamelyik csúcsban lesz < 120° a szögátlag. Tehát a szögátlag < 120°. Ha tehát k sokszög van és ezeknek rendre ni oldaluk van, akkor e sokszögek szögösszege: k
k
k
∑ (n − 2)180° < ∑ n 120°. Innen rendezés és 60°-kal való osztás után: ∑ n i =1
i
i =1
i
i =1
i
< 6k , s ez éppen azt jelenti,
hogy a sokszögek oldalszámának átlaga kisebb hatnál.
A következő feladat ismétlődő tanári feladat volt, valójában egy ismert ötlet kevésbé szembeötlő alkalmazására épül, és nagyon változó volt, hogy gyorsan, vagy nehezen oldottáke meg a diákok: 11. feladat Bizonyítandó, hogy minden háromszögben igaz a következő egyenlőtlenség: a
s−a s−b s−c +b +c ≤ s. b c a
Itt s a háromszög félkerületét, a, b, c a háromszög oldalait jelöli. MEGOLDÁS Ha a jobb oldalt a bonyolultabb
s−a s −b s−c +b +c =s a b c alakba írjuk át, akkor rögtön látszik, hogy csak azt kell megállapítanunk: azonos, vagy fordított sorrendben van-e rendezve az {a(s–a), b(s–b), c(s–c)} és az {1/a, 1/b, 1/c} számhármas. Minthogy utóbbi pedig fordítva van rendezve, mint az {a, b, c} számhármas, elég azt megállapítanunk, hogy ha a>b, akkor a(s–a) és b(s–b) közül melyik a nagyobb. Vegyük a különbségüket: a(s – a) – b(s – b) = (a – b)s – (a2 – b2) = (a – b)(s – a –b) = –(a – b)(s – c)<0, tehát az {a(s–a), b(s–b), c(s–c)} és az {a, b, c} számhármas ellentétesen van rendezve, így az {a(s–a), b(s–b), c(s–c)} és az {1/a, 1/b, 1/c} számhármas egyformán. Így a rendezési egyenlőtlenségből a feladat állítása következik. a
9/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Ahol ez a feladat nehéznek mutatkozott, ott könnyítésnek először feladtuk a következő feladatot, amelyben a rendezési egyenlőtlenség alkalmazása kézenfekvő, viszont más rutinötletre is szükség van: 12. feladat Bizonyítandó, hogy minden háromszögben igaz a következő egyenlőtlenség: s−a s −b s −c 3 + + ≥ . b c a 2
Itt s a háromszög félkerületét, a, b, c a háromszög oldalait jelöli. MEGOLDÁS Tekintsük az (s–a, s–b, s–c) és az (1/a, 1/b, 1/c) számhármasokat. Ezek egyformán vannak sorrendbe rendezve, így a rendezési egyenlőtlenség szerint a bizonyítandó egyenlőtlenség bal oldala legfeljebb akkora, mint
s−a s−b s −c 1 1 1 + + = s( + + ) − 3 . a b c a b c
Erről kell tehát belátnunk, hogy legalább másfél. A számtani és harmonikus közép közötti összehasonlításból következik, hogy
1 1 1 1 1 1 2 s ( + + ) = (a + b + c)( + + ) ≥ 9 , a b c a b c s ebből a bizonyítandó egyenlőtlenség már következik. Megjegyzés Ezt a feladatot is, az előzőt is átírhatjuk trigonometrikus egyenlőtlenségre. Az előbbi az érdekesebb. Ha az
a
s−a s −b s−c +b +c ≥s b c a
egyenlőtlenségbe beírjuk a szinus-tételt és mindkét oldalt osztjuk a beírt kör r sugarával, továbbá alkalmazzuk az ismert (s–a)/r=ctg α/2 összefüggést és a sin α = 2 sin α/2 cos α/2 addíciós tételt, akkor a következő feladathoz jutunk:
11a. feladat Bizonyítsuk be, hogy ha α,β,γ egy háromszög szögei, s a félkerülete és r a beírt kör sugara, akkor fennáll az
cos 2 α / 2 cos 2 β / 2 cos 2 γ / 2 s + + ≥ sin β sin γ sin α 2r egyenlőtlenség.
MEGOLDÁS Most is a rendezési egyenlőtlenséget használhatjuk: írjuk be a cos2α/2 = (1+cosα)/2 azonosságot az egyenlőtlenség bal oldalába. Ekkor az {1+cosα, 1+cosβ, 1+cosγ} és a {1/sinα, 1/sinβ, 1/sinγ} számhármasok egyformán vannak rendezve, tehát a bal oldal nem nagyobb, mint
cos α / 2 cos β / 2 cos γ / 2 + + = sin α sin β sin γ 2
2
2
ctg
α
2
+ ctg
β
2
+ ctg
2
s ezt kellett bizonyítani.
10/23
γ
2 = s −a + s −b + s −c = s , 2r 2r 2r 2r
Surányi László
Fazekas táborok 1987-2003
Válogatás
13. feladat
Artúr király testőrei közül minden kettőhöz van egy, aki legyőzte őket a legutóbbi lovagi tornán. Legalább hányan vannak? MEGOLDÁS Mindenki kikapott legalább három társától: ha a kikapott b-től (egy ilyen b biztos van), akkor van egy c is, akitől mindketten kikaptak. Van egy olyan d is, aki a-t is, c-t is legyőzte, és ez nem lehet b, mert b kikapott ctől. a tehát kikapott b-től, c-től, d-től. Ez azt jelenti, hogy legalább 3n csörte volt, másrészt legfeljebb n(n–1)/2 lehetett, amiből következik, hogy n legalább hét. Kérdés, hogy lehet-e hét? Nézzük meg, mi ennek a feltétele. Ha n=7, akkor pontosan 3n csörte volt, s ebből következik, hogy a pontosan három testőrtől kapott ki. De akkor pontosan hármat vert is meg. S mivel a tetszőleges testőr volt, mind a hét testőrnek három másikat kellett megvernie és háromtól kellett kikapnia. Azt már láttuk, hogy az a-t megverő b, c, d közül c megverte b-t és d megverte c-t. De kellett lennie olyan valakinek is, aki megverte a-t és d-t is, s ez nem lehet c, csak b. Tehát az a-t megverő b,c,d körbe verte egymást, s ez megint igaz bármely testőrt megverő három testőrre. Legyen most e, f, g a további három testőr. Ezeket a megverte. Másrészt b-hez, c-hez és d-hez már találtunk két-két olyan testőrt, akit megvertek: a és d, b illetve c. Tehát közülük mindegyik pontosan egyet vert meg e, f, g közül. Másrészt utóbbiak mindegyike kikapott legalább egytől b, c és d közül, mert ha például e nem mindüket megverte volna, akkor nem volna olyan testőr, aki megverte a-t és e-t. Mindebből következik, hogy b, c, d közül mindegyik pontosan egyet vert meg e, f, g közül és mindegyikük másikat vert meg. Már csak azt a három mérkőzést kell tisztáznunk, amelyeket e, f, g egymás között játszott. Eddig mindüknek két-két győzelme és két-két veresége van, tehát ők hárman körbe verték egymást. De melyik irányban? Nézzük, ki lehetett az, aki b-t is, f-et is megverte? Nem lehet a, c, e (őket b megverte) és d (f megverte). Tehát g-nek kellett megvernie f-et. Ebből már következik, hogy f megverte e-t és e megverte g-t. Így a következő irányított gráfot (tournamentet) kapjuk az a, b, c, d, e, f, g pontokon. Az élek (a győztes van előre írva): ae, af, ag, ba, bc, be, ca, cd, cf, da, db, dg, ec, ed, eg, fb, fd, fe, gb, gc, gf. Ellenőriznünk kell, hogy tényleg bármely két testőrhöz van-e egy harmadik, aki mindkettőjüket megverte. Ehhez a legjobb felírni, hogy az egyes testőrök kit vertek meg: a: e, f, g b: a, c, e c: a, d, f d: a, b, g e: c, d, g f: b, d, e g: b, c, f Azt kell megnézni, hogy minden pár előfordul-e valamelyik sorban. Ehhez érdemes felrajzolni a következő ábrát: a b c g e
d f
Aki ismeri a hét pontú projektív síkot, az rögtön látja, hogy az egyes testőrök által megvert testőröknek megfelelő pontok épp egy ilyen sík egyeneseit alkotják, és ismeretes, hogy bármely két pontot választjuk ki, van olyan egyenes, amely „összeköti” őket, tehát van olyan sor, amely a kiválasztott két testőrt tartalmazza. Aki nem ismeri a projektív sík fogalmát, az „kézi úton” is ellenőrizheti ezt. MEGJEGYZÉS: A hétpontú projektív sík mind a hét pontja pontosan három egyenesre illeszkedik, minden egyenesre a sík három pontja illeszkedik; bármely két pontra pontosan egy egyenes illeszkedik és bármely két egyenesnek pontosan egy közös pontja van (= bármely két egyenesre pontosan egy pont illeszkedik). A síkot a fenti ábra alapján képzeljük el: az „egyenesek” itt a háromszög három oldala, három súlyvonala és a három oldalfelezőpontot tartalmazó kör. Ajánló: a véges projektív síkokkal kapcsolatban lásd pld Bérczy Gergely, Gács András és Szőnyi Tamás írását az Új matematikai mozaikban vagy az interneten: http://www.typotex.hu/book/m_0071.htm vagy http://www.hik.hu/tankonyvtar/site/books/b124/ch-02.html.
11/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Most lássunk pár valószínűségszámítási feladatot a tanulók által kitűzöttek közül. 14. feladat
Mi a valószínűsége annak, hogy négy véletlenszerűen választott szakaszból mint oldalakból négyszög szerkeszthető? MEGOLDÁS Legyen a leghosszabb szakasz hossza a, akkor a másik három szakasz egy a3 térfogatú kocka pontjaival reprezentálható, és ennek a kockának az a része nem jó, amelyre x+y+z≤a, ami egy a × a × a alapélű derékszögű tetraédert vág ki a kockából, ennek térfogata a3/6, tehát a keresett valószínűség 5/6.
15. feladat
Mi annak a valószínűsége, hogy egy kettőhatvány a tízes számrendszerben egyessel kezdődik? MEGOLDÁS Elég azt megnézni, hogy n-ig a kettőhatványok hanyad része kezdődik 1-gyel. n-nél kisebb kettőhatványból [log2n] van. Minden n-nél kisebb tízhatványhoz pontosan egy megfelelő kettőhatvány van (az, ami 10k és 2·10k közé esik), kivéve esetleg a legnagyobb tízhatványt (amelyhez tartozó kettőhatvány esetleg már nagyobb n-nél). Az egyessel kezdődő kettőhatványok száma tehát [log10n] (vagy [log10n]–1). A keresett valószínűség tehát [log10n] és [log2n] hányadosának határértéke, azazlog102.
16. feladat
Van egy három oldalú dobókockánk, az oldalakon rendre 1, 2, 3. Addig dobunk, amíg a dobott számok összege legalább n nem lesz, ekkor a pontos érték n+xn. Mi xn várható értéke? Hová tart xn várható értéke? MEGOLDÁS Jelöljük an-nel annak a valószínűségét, hogy pontosan elérjük n-et, ekkor a1=1/3, a2=1/3+1/9, a3=1/3+2/9+1/27, és általában an=(an–1+a n–2+a n–3)/3. Ezt a rekurziót megoldva an=1/2+(en+fn)/4, ahol e,f két egynél kisebb abszolútértékű komplex szám (egymás konjugáltjai: e és f a 3x2+2x+1=0 egyenlet két gyöke). n-et a következő módokon érhetjük el: a) pontosan elérjük, ennek valószínűsége an és ekkor xn=0, ennek tehát 0 az „adaléka” a várhatóértékhez; b) n–1-et érjük el pontosan és utána 2-t dobunk. Ennek valószínűsége an–1/3, és ekkor xn=1; c) n–1-et érjük el pontosan és utána hármat dobunk. Ennek valószínűsége is an–1/3, és ekkor xn=2, tehát e két esetnek együtt an–1 az „adaléka” a várhatóértékhez; d) n–2-t érjük el pontosan és utána hármat dobunk. Ennek valószínűsége an–2/3, és ekkor xn=1, tehát ennek az esetnek an–2/3 az „adaléka”. Így E(xn)=an–1+an–2/3=2/3+en–1+fn–1+en–2/3+fn–2/3, ahol e és f a 3x2+2x+1=0 egyenlet két gyöke. Minthogy mindkettő egynél kisebb abszolútértékű, ezért az utolsó négy tag nullához tart, ha n a végtelenhez tart. Tehát a keresett határérték 2/3.
12/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
A következő feladat szövege is, kérdése is és a rá adandó válasz is kissé szokatlan talán, legalábbis ez derült a táborban, ahol sorra került, ezért is vált „szabad prédává”, de végül is minden csoportnak sikerült megoldania: 17. feladat
Egy fontos iratot keresünk az íróasztalban. Tudjuk, hogy p(j) anak a valószínűsége,
hogy az irat a j-edik fiókban van 1 ≤ j ≤ n,
n
j =1
∑ p( j ) = 1, és azt is tudjuk, hogy a j-edik
fiók átnézése t(j) időt vesz igénybe. Mielőtt a keresésbe fogunk, tervet készítünk, azaz megadjuk az első n természetes szám egy i(1),...,i(n) permutációját, és ebben a sorrendben fogjuk végignézni a fiókokat mindaddig, amíg az iratot meg nem találjuk. Adott p(1),...,p(j),...,p(n) és t(1), ..., t(j), ... t(n) számokhoz adjuk meg azt az i permutációt, amelyre a keresési idő várható értéke minimális. MEGOLDÁS Az a σ permutáció jó, amely a p(i)/t(i) számokat monoton csökkenő sorozatba rendezi. Ugyanis a σ permutációhoz tartozó várható érték: j
∑ p(σ ( j ))∑ t (σ (k )) . k =1
E képletben p(k)t(m) alakú szorzatok szerepelnek. k=m esetén a szorzat mindenképp szerepel, különben pontosan akkor, ha a σ permutációban m megelőzi k-t, vagyis az m-edik fiókot előbb akarjuk megnézni a kadiknál. Vagyis az a célunk, hogy ha ez elérhető, akkor minden {p(m)t(k), p(k)t(m)} párból a kisebb szerepeljen, vagyis k és m közül akkor nézzük meg az k-adik fiókot előbb, ha p(m)t(k) ≤ p(k)t(m). Eddig volt könnyű eljutni. Nem tűnt magától értetődőnek, hogy ez lehetséges, és kissé szokatlan volt az, hogy ha ezt a feltételt átfogalmazzuk, rögtön kiderül, hogy mégis lehetséges az összes feltételt egyszerre kielégíteni: ez a feltétel ugyanis ugyanazt jelenti, mint hogy p(m)/t(m) ≤ p(k)/t(k), s hogy ebből azt a feltételt nyerjük, amit a megoldás elején megadtunk. Az adott feltétel ezt valóban minden k,m számpárra biztosítja, tehát ez a permutáció (bármely ilyen permutáció) valóban a minimumot adja, más nem.
18. feladat
Az APEH két év alatt ellenőrzést végez vállalatok egy csoportjánál. A vállalatok mindegyikét p valószínűséggel az első, 1–p valószínűséggel a második évre osztják be. Egy éven belül azonos valószínűséggel kerülnek minden hónapba. Mekkora a valószínűsége, hogy egy vállalatot, amelyet az első tizenegy hónapban nem ellenőriztek, a tizenkettedik hónapban ellenőrizni fognak? MEGOLDÁS Jelölje A azt az eseményt, hogy a 12. hónapban ellenőrzik az adott vállalatot és B azt, hogy az első tizenegy hónapban nem ellenőrzik. A feladat a P(A|B) feltételes valószínűséget kérdezi. Ez a valószínűség megegyezik a P(AB)/P(B) valószínűséggel. Nyilvánvaló, hogy ha A bekövetkezik, akkor B is, tehát AB=A, így valójában a P(A)/P(B) valószínűséget kell kiszámolnunk. Nyilvánvaló, hogy P(A)=p/12. Kicsit bonyolultabb csak P(B)
kiszámolása. Ez megegyezik az 1 − P ( B ) valószínűséggel. Ennek kiszámolásához azt kell meghatároznunk, milyen valószínűséggel ellenőríznek egy adott vállalatot az első 11 hónapban. Egy adott hónapban p/12 valószínűséggel ellenőrzik, s mivel ezek az események páronként kizárják egymást, összesen 11p/12 valószínűséggel ellenőrzik az első 11 hónapban. Tehát 1 − P ( B ) = 1 − valószínűség tehát
P( A | B) =
p . 12 − 11 p
13/23
11 p 12 − 11 p = . A keresett P(A|B) 12 12
Surányi László
Fazekas táborok 1987-2003
Válogatás
19. feladat
A és B a következő játékot játssza: mindketten kiválasztanak egy számot egy adott X halmazból (választhatják mindketten ugyanazt) és leírják maguknak. Aztán megmutatják egymásnak. Ha a két szám azonos, akkor A nyer B-től annyi forintot, amennyi a két szám összege. Ha a két szám különböző, akkor B nyer A-tól annyi forintot, amennyi a két szám összege. Kinek kedvez a játék, ha X={a,b}, ahol a és b különböző? MEGJEGYZÉS: A feladat ún. játékelméleti feladat, annak egészen elemi. De a játékelméletet a tanulók nem ismerik, ezért a kitűzés után értelmezni kellett a feladatot. Feltesszük tehát, hogy mindkettőjüknek van egy véletlen stratégiája, hogy milyen valószínűséggel választják az egyik, illetve a másik számot. Ezután megnézzük, hogy hosszú távon kinek kedvez a játék, vagyis e stratégiák mellett kinek mennyi a várható nyereménye. Olyan stratégiát kell megadnunk a „nyertes” számára, amellyel játszva a másik nem tud nyerni, bárhogyan is választja/változtatja véletlen stratégiáját. MEGOLDÁS Ha A p valószínűséggel választja a-t, B pedig q valószínűséggel, akkor A várható nyereménye: 2apq + 2b(1–p)(1–q) – (a+b)((1–p)q+(1–q)p). Ezt a következő alakra hozhatjuk: 2b + 4(a+b)pq – (a+3b)(p+q). Jelöljük egyelőre u-val 4(a+b)-t és v-vel a+3b-t. Ekkor 2b + upq – v(p+q) = (up – v)(q – v/u) + 2b – v2/u. A játék akkor kedvezőtlen A számára, ha 2b–v2/u<0. Ebben az esetben ugyanis bárhogyan is játszik A, B játékonként legalább 2b–v2/u-t tud nyerni, ha q=v/u valószínűséggel választ a-t. Megmutatjuk, hogy 2b
Most pár geometriai feladatot veszünk sorra. 20. feladat
Adott a síkon néhány vektor, amelyek hosszának összege egy. Bizonyítandó, hogy kiválasztható közülük néhány, amelyek összegének hossza legalább 1/π. MEGOLDÁS Vegyük az összes vektort és mindegyiknek az ellentettjét. Rajzoljuk fel őket a hajlásszögük szerinti sorrendben egymás után. Ekkor egy zárt, középpontosan tükrös konvex sokszöget kapunk. Jelölje O a tükörközéppontot, PQ a sokszög (egyik) átmérőjét, PQ hossza legyen d. Nyilvánvaló, hogy O éppen a PQ szakasz felezőpontja (ha nem az volna, PQ az O-ra vonatkozó P’Q’ tükörképével együtt egy paralelogrammát alkot, és az egyik átló biztos hosszabb, mint PQ). Az egész sokszög benne van a PQ átmérőjű körben. (Ha ugyanis lenne O-tól d/2-nél távolabbi pont, az a tükörképével együtt egy d-nél hosszabb szakasz a sokszögben.) Mivel a sokszög kerülete a feltétel szerint 2, ezért a kör kerülete, dπ ennél nagyobb: dπ>2. Tekintsük a PQ fölötti egyik félkört, és a sokszögnek ebben futó oldalait. Ezeket osszuk két osztályba aszerint, hogy eredetileg adott vektorok, vagy azok ellentettjei. Valamelyik osztályba tartozók vetülete az átmérőn legalább az átmérő felét adják, vagyis ezek összhossza is legalább d/2>1/π.
21. feladat
Egy egységsugarú gömb felszínére π-nél rövidebb (főkörívekből álló) görbét rajzoltunk. Bizonyítandó van olyan, a gömb középpontján átmenő sík, amely a görbének egyetlen pontját sem tartalmazza. Bizonyítandó ugyanezt 2π-nél rövidebb zárt görbére is.
14/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
MEGOLDÁS Tekintsük a görbe „felezőpontját”, tehát azt a pontját, amelytől a görbe két vége egyenlő távol van, forgassuk el a gömböt úgy, hogy ez legyen az Északi Sarka. Ekkor az egyenlítőt a görbe nem metszheti, hiszen az Északi Sarok annak mindegyik pontjától π távolságra van, míg a görbe minden pontja ennél közelebb van hozzá. (Felhasználtuk, hogy a gömbön a főkörök játsszák az „egyenes” szerepét: a gömb felszínén két pont között a legrövidebb út a rajtuk átmenő rövidebb főkörív.) A 2π-nél rövidebb zárt görbe esetén vegyük annak két „átellenes” pontját, vagyis egy tetszőleges P pontját, és azt a Q pontot, amelytől a görbén mindkét irányban ugyanolyan messze van P. Legyen a gömb középpontja O és vegyük azt az S síkot, amely merőleges az OP+OQ vektorra. Tegyük fel, hogy ennek van egy M közös pontja a görbével. Tekintsük az egyik PQ görbét, és tükrözzük annak MQ ívét az S síkra. Q tükörképe legyen Q’. Ekkor Q és Q’ átellenes pontok a gömbön, és egy 2π-nél rövidebb görbe köti össze őket, ami ellentmondás.
22. feladat
Adott a síkon véges sok konvex síkidom, semelyik kettő metszete nem üres. Bizonyítandó, hogy létezik végtelen sok olyan egyenes, amely mindegyik síkidomot metszi. MEGOLDÁS Vegyünk egy tetszőleges egyenest és vetítsük rá egy adott iránnyal párhuzamosan az összes adott síkidomot. Minden síkidom vetülete egy-egy zárt szakasz és bármely két ilyen szakasznak van közös pontja, hiszen a megfelelő síkidomoknak is van. Ismeretes, hogy ha egy egyenesen adott véges sok olyan szakasz, amelyek közül bármely kettőnek van közös pontja, akkor az összesnek is van közös pontja (például annak a szakasznak az „alsó” végpontja jó, amely a legfelül kezdődik). Ha ezen a ponton át húzunk a vetítés irányával párhuzamos egyenest, ez az összes síkidomot metszeni fogja. Azt láttuk be, hogy bármely iránnyal párhuzamosan húzható minden síkidomot metsző egyenes.
23. feladat
A síkon felvettünk n>2 pontot, semelyik 3 nincs egy egyenesen. Milyen n-re igaz, hogy a sík minden P pontja, mely nincs rajta a felvett pontok által meghatározott egyenesek egyikén sem, páros sok olyan háromszög belsejében van benne, melyet az eredeti n pont közül 3 határoz meg? MEGOLDÁS Be fogjuk látni, hogy a feladat állítása pontosan a páros n-ekre igaz. Páratlan n-re ellenpélda a következő: legyen A1A2…An egy szabályos n-szög és tekintsünk benne egy olyan P pontot, amely a sokszög belsejében van, de olyan „közel” van az A1A2 oldalhoz, hogy egyetlen átló sem választja el sem A1-től, sem A2től. Vagyis P az A1A3 és az AnA2 átlók metszéspontját B-vel jelölve az A1A2B háromszög belső pontja. Ez azt jelenti, hogy P csak olyan háromszög belsejében van benne, amelyek tartalmazzák A1-et és A2-t is csúcsként, és az összes ilyen háromszög belsejében benne van. Az ilyen háromszögek száma viszont n–2, ami páratlan, mert n is az. Ha n páros, akkor a feladat állítása igaz, ezt kétféleképpen is be fogjuk bizonyítani. 1. Egy olyan P, mely az n pont konvex burkán kívül esik, nulla, azaz páros sok háromszögben van benne. Azt fogjuk belátni, hogy ha a pontot átvonszoljuk az A1A2 szakaszon, akkor az őt tartalmazó háromszögek számának paritása nem változik, ha közben más szakaszon nem vonszoltuk át. Azon háromszögek, melyeknek A1A2 oldala, mind tartalmazzák P-t, vagy P’-t, ahol P’ a P átvonszolással kapott képe, de minden ilyen háromszög csak az egyiket tartalmazza. Mivel összesen páros sok csúcs van, A1A2-nek a két oldalán levő pontok számának különbsége páros, így ezen háromszögek számának paritása nem változik. Az összes többi háromszögre igaz az, hogy akkor és csak akkor tartalmazzák P’-t, ha P-t is tartalmazzák. Most már csak azt kell belátnunk, hogy bármelyik két tartomány között van olyan „út”, mely mindig csak egy szakaszon vonszolja át Pt. Ez azért igaz, mert az egyik tartomány egy Q pontját kijelölve, és abból egyeneseket húzva a másik tartományba, azt kapjuk, hogy véges sok metszéspont van, de végtelen sok Q-ból induló egyenes, így van olyan, mely metszésponton nem megy át, így ezen P vonszolható. Ezt kellett bizonyítanunk. 2. Minden négyszögben négy háromszög van, ezek közül vagy kettő tartalmazza P-t, vagy egy sem, ha P a négyszögön kívül van. Legyen N azon négyszögek száma, mely P-t tartalmazza. Ez egész. Ekkor a P-t tartalmazó háromszögek számára 2N-et kapunk. De minden háromszöget többször számoltunk, mégpedig n–3szor, azaz páratlan sokszor. A 2N/(n–3) szám tehát páros, mivel egész. Ezt akartuk bizonyítani.
15/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
24. feladat
Szerkesszük meg a háromszöget, ha ismerjük két oldalához hozzáírt kör sugarát, valamint a harmadik oldalát: a, rB, rC. I. MEGOLDÁS
B OC
a
c
rC
b
C
a
T
A
U
rB
OB Érintse az ABC háromszög b oldalához írt kör a b oldalt a T pontban, és érintse a c oldalhoz írt kör a b oldal egyenesét az U pontban. Ismeretes, hogy ekkor TA=s–c és AU=s–b, tehát TU szakasz hossza éppen a. Ezért OB, illetve OC-vel jelölve a két hozzáírt kör középpontját, az OBTUOC törött vonal szerkeszthető (T-nél és U-nál derékszög van, de ellenkező irányban) és OBT=rB, TU=a, UOC=rC. Ezután megszerkesztjük a két kör másik közös belső érintőjét, ez lesz az AB oldalegyenes, és az egyik közös külső érintőt, ez lesz a BC oldalegyenes. Arra kell csak ügyelni, hogy a kapott B metszéspontjukat az UT egyenes elválassza az OB középpontú körtől. Ha ez teljesül, akkor a kapott háromszög megfelelő, hiszen CB=UT. MEGJEGYZÉS Az A csúcsot megkaphatjuk az OBOC és UT egyenesek metszéspontjaként is, s ebből az AB oldal egyenesét úgy kapjuk, hogy az UT egyenest tükrözzük az OBOC külső szögfelező egyenesére. II. MEGOLDÁS
Ismert, hogy a háromszög területének kétszerese rB(s–b)=rC(s–c), ahonnan akkor ismert az ennél eggyel nagyobb tört is:
s − b rC = ismert. De s − c rB
s−b s −b+ s −c a +1 = = . Ez viszont azt jelenti, hogy s−c s−c s−c
ismerjük az s–c szakasz hosszát. Ugyanígy ismerjük az s–b szakasz hosszát is. Ebből ismét meg tudjuk szerkeszteni – az első megoldás jelöléseit használva – az OBTUOC törött vonalat, de most rögtön az A csúcsot is az UT szakaszon. Az AB egyenest ismét az UT egyenes OBOC egyenesre vett tükörképeként kapjuk. A befejezés mehet az előző megoldáshoz hasonlóan a két kör külső érintőjének meghúzásával. MEGJEGYZÉS Ez a megoldás azonban befejezhető egy másik ötlettel is:
III. MEGOLDÁS Ha már ismerjük az s–b és s–c szakaszok hosszát, akkor ismerjük a b–c hosszát. Az OBTA derékszögű háromszöget megszerkesztve megkapjuk az A-nál levő szöget is. Ismerjük tehát az a oldal hosszát, a szemben levő α szöget és b–c-t. E három adatból az ismert módon szerkeszthetünk háromszöget: előbb megszerkesztjük azt a háromszöget, amelynek két oldala a és |b–c| és a-val szemben 90°+α/2 van. A harmadik oldal oldalfelező merőlegese metszi ki a b–c oldal egyeneséből a harmadik csúcsot, A-t. A szerkesztés feltétele, hogy |b–c| valóban
kisebb legyen a-nál. Ez esetünkben teljesül, mert | b − c |=| ( s − c ) − ( s − b) |=
16/23
a | rB − rC | . rB + rC
Surányi László
Fazekas táborok 1987-2003
Válogatás
25. feladat
A síknak egy önmagára való f leképezésének megvan az a tulajdonsága, hogy egységnyi távolságra levő pontok képe is ilyen pontpár. Igaz-e hogy ekkor f egybevágóság (távolságtartó)? MEGOLDÁS A megoldásban említés nélkül használni fogjuk, hogy egy ilyen leképezés egy-egyértelmű, tehát metszéspont képe metszéspont. Egységoldalú szabályos háromszög képe szabályos háromszög. Ezért egységoldalú szabályos hatszög
képe egységoldalú szabályos hatszög. Tehát 3 hosszú szakasz képe 3 hosszú szakasz és 2 hosszú szakasz képe 2 hosszú szakasz, végül felező ponté felező pont. Ebből már következik, hogy ha n,m egészek, akkor
n + m 3 hosszú szakasz képe n + m 3 hosszú szakasz, (és ha egy egyenesen egy ponttól n + m távolságra levő pontokat tekintjük, akkor a képpontok a P ponttól ugyanilyen távol vannak egy egyenesen.)
3
Belátjuk, hogy az f leképezés folytonos. Felhasználjuk, hogy az n + m 3 alakú számok „mindenütt sűrűn” helyezkednek el a számegyenesen, azaz bármilyen kis intervallumot veszünk is fel bárhol a számegyenesen, ebben az intervallumban van
n + m 3 alakú szám.
Ha PQ≤x, akkor vegyünk egy x-nél rövidebb, de x/2-nél hosszabb y = n + m 3 hosszú szakaszt és azt az R pontot, amelyre PQR háromszögben PR=RQ=y. Ennek képe egy olyan P'Q'R' háromszög, amelyben P'R'=R'Q'=y, tehát P'Q'≤2y≤x. Az f leképezés tehát folytonos. Ebből viszont következik, hogy távolságtartó, hiszen a sík egy mindenütt sűrű halmazán távolságtartó, tehát minden távolságot megtart. (A sík egy ponthalmaza akkor „mindenütt sűrű”, ha bármilyen kis kört veszünk is fel bárhol a síkon, abban van a halmaznak pontja. A sík egy tetszőleges P pontjához találunk tehát olyan pontsorozatot a halmazban, amely P- hez konvergál.)
26. feladat
Egy kört két részre osztottunk egy AB húrral, és az egyik részét elforgattuk az A pont körül α szöggel, ekkor B átment D-be. Az elforgatott AD ív felezőpontja E, a nemelforgatott AB ív felezőpontja C, a BD felezőpontja M. Bizonyítandó, hogy CME szög derékszög. MEGOLDÁS Elforgatjuk a síkot először C körül ACB szöggel, majd E körül AEB szöggel. Mivel az AEB< = 180° – ACB< (egymást 180°-ra kiegészítő kerületi szögek egyikét forgattuk AEB-be), ezért a két forgatás egymásutánja egy középpontos tükrözés. Mivel B-t D-be viszi, ezért a középpontja éppen M. A forgatások összetételére vonatkozó tétel szerint ekkor CME<=90°.
Most nézzünk pár játékokkal és algoritmusokkal kapcsolatos feladatot. 27. feladat
Két játékos a következő játékot játssza: felváltva választanak egyet-egyet az egytől nig számozott lapokból (n≥2). A nyer, ha a végén legalább az egyiküknél a számok összege prím, egyébként B nyer. Milyen n-ekre van nyerő stratégiája valamelyiküknek, mi ez a nyerő stratégia? (A kezd.) MEGOLDÁS n=2, 3 esetén mindenképp A nyer. n=4-re 1-et majd 2-t (vagy 4-t) húz és nyert. n = 5-re először 5-öt húz, másodszorra 2-t (vagy 4-et), majd ami marad és nyer. n ≥ 6 esetén írjuk fel úgy a számokat két sorba egymás alá, hogy a két sorban ugyanannyi szám legyen, vagy az elsőben eggyel több: a felső sor n = 2k esetén 1, 2, ... k, az alsó sor k+1, k+2,..., 2k; n = 2k+1 esetén a felső sor 1, 2, ..., k+1, az alsó sor k+2, k+3,..., 2k+1. B úgy játszik, hogy minden oszlopból (vagyis minden i, k+i párból, illetve minden i, i+k+1 párból) az egyik az övé legyen, a másik A-jé, ha n páratlan, akkor a szingli számot (k+1-et) is A-nak juttatja. Ha n = 2k, akkor a számok összege k(2k+1), és ez osztható k-val, másrészt a két
17/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
játékosnál levő lapszámok különbsége is osztható k-val, ebből következik, hogy mindkettőjüknél k-val, illetve páros k esetén k/2-lel osztható az összeg. Ha n = 2k+1, akkor a számok összege (2k+1)(k+1) osztható k+1-gyel, a két játékosnál levő számok különbsége k+1-gyel osztható, tehát mindkettőjüknél k+1-gyel, illetve ha ez páros, akkor (k+1)/2-vel osztható az összeg. Tehát B-nek van nyerő stratégiája. MEGJEGYZÉS Ha B-nek kell a nyeréshez prímösszeget garantálnia, akkor páratlan n-re A hasonló stratégiával nyer: először elveszi a középső számot, aztán a B által elvett szám párját. De mi van, ha n páros? Akkor is nyer: ugyanígy párokba rakja a számokat és arra vigyáz, hogy olyan páros köröket hozzon létre, amelyekben párok szerepelnek.
28. feladat
1994-en egy asztal körül n kártyával a következő játékot játsszák: kezdetben minden kártya az egyik játékos kezében van. Egy megengedett lépés van: ha valaki, akinek legalább két kártyája van, egyet-egyet ad jobb és bal oldali szomszédjának. Milyen nekre ér véget biztosan a játék? MEGOLDÁS Nyilvánvaló, hogy n ≥1994-re a játék nem ér véget. Ha n>1994, akkor minden lépésben lesz legalább egy valaki, akinek a kezében legalább két kártya van, és az tudja folytatni a játékot. n=1994 esetén csak akkor érhetne véget a játék, ha mindenkinek egy-egy kártya volna a kezében, de ekkor a helyszámszor a kezében levő kártyák számát minden játékosra összegezve páratlan számot (997) kapnánk, míg kezdetben páros szám volt (a kezdő játékosnál kezdjük a számolást!). Márpedig az eljárás során a ∑helyszám x kártyaszám összeg paritása nem változik. Marad az n ≤1993 eset. Tegyük fel, hogy nem ér véget a játék. Vegyünk két egymás melletti játékost, és tekintsük azt a pillanatot, amikor először kerül valamelyikükhöz kártya. Az első ilyen kártyát a sajátjuknak tekintik, és megfogadják, hogy a továbbiakban mindig köztük fog vándorolni. Minden szomszédpárnak legfeljebb egy kártyája van, és legfeljebb 1993 kártya van, így van olyan szomszédpár, amelynek nem jut kártya. Ez azt jelenti, hogy ez a pár nem vesz részt a játékban. Minthogy a játék végtelen, van viszont olyan pár, amely végtelen sokszor adogat egymásnak kártyát, van tehát egy olyan szomszédpár is, amely végtelen sokszor adogat kártyát egymásnak, de a mellette levő pár véges sok lépés után már nem vesz részt a játékban. De akkor van valaki, aki egyik oldalra végtelen sokszor ad kártyát, a másikra nem, ami ellentmondás. Vagy pedig van valaki, aki végtelen sokszor kap kártyát, de nem ad tovább kártyát, ami ellentmond annak, hogy véges sok kártya van. Tehát n ≤1993-ra véget ér a játék.
29. feladat
Adott egy n-pontú gráf. Van telített pontja (olyan pontja, melynek foka n–1), és van elsőfokú pontja is. Egy kérdésben megkérdezhetjük, hogy A és B pontok között van-e él. Bizonyítsuk be, hogy 2n kérdés mindig elegendő ahhoz, hogy megtudjuk, melyik a telített pont! MEGOLDÁS Mivel van elsőfokú pont, pontosan egy telített pont van.. Válasszunk ki találomra egy pontot, és kérdezzük végig az összes ponttal. Ez eddig n–1 kérdés. Ha mindegyik szomszédja, akkor ő a telített pont, ha csak egy szomszédja van, akkor az a szomszédja a telített pont. Nulladfokú nem lehet, hiszen tudjuk, hogy van telített pont. Tegyük fel tehát, hogy a találomra kiválasztott pont foka legalább kettő és legfeljebb n–2. A szomszédai legyenek a K1, K2, …, Kk pontok. A nem-szomszédai legyenek az U1, U2, …, Um pontok. Az n–1fokú pont a Ki-k között, az elsőfokú pedig az Ui-k között van. Ezután mindig kérdezzünk rá arra, hogy a legkisebb indexű Ki és a legkisebb indexű Uj között van-e él. Ha van, az Ui-t dobjuk el, és folytassuk ugyanígy, ha pedig nincs él, a Ki-t dobjuk el. Ezt addig folytatjuk, amíg a Ki-k vagy az Ui-k el nem fogynak. De az n–1fokú pontot soha nem dobhattuk ki, tehát az Ui-k fognak elfogyni. Ez azt jelenti, hogy előbb-utóbb az elsőfokút is kidobjuk. Ám az elsőfokút csak akkor dobhattuk ki, amikor a telített ponttal került párba, s utána a telített pont már minden Ui-t kidob. Mikor tehát az utolsó Ui is eltűnt, az őt kidobó Kj a telített pont. Mivel minden kérdésnél kidobunk egy pontot, itt legfeljebb n–2 kérdést tettünk fel, így összesen 2n–3 kérdést feltéve meghatároztuk azt a pontot, melynek foka n–1.
18/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
30. feladat
Egy 2n oldalú szabályos sokszög csúcspontjait csupa n jegyű számmal akarjuk megszámozni, mégpedig úgy, hogy (1) a megszámozáshoz csak az egyes és kettes számjegyeket használjuk fel; (2) különböző csúcspontokhoz különböző számok tartozzanak; (3) szomszédos csúcspontokhoz tartozó számok csak egy számjegyükben térjenek el egymástól. Lehetséges-e ez n bármely szóba jövő értéke (n=2,3,…) esetén? MEGOLDÁS A feladat átfogalmazható úgy, hogy n jegyű, egyesekből és kettesekból álló számok helyett n hosszú 0-1 sorozatokról beszélünk (a kettesek helyére 0-t írunk). Ezeket pedig elképzelhetjük egy n dimenziós kocka csúcsainak. A feladat (3)-as feltétele azt mondja, hogy a szabályos sokszög szomszédos csúcsainak a kockán is szomszédosaknak kell lennie (hiszen a kockán két csúcsot pontosan akkor köt össze él, ha pontosan egy koordinátában különböznek). Tehát a feladat kérdése úgy fogalmazható át, hogy van-e az n-dimenziós kockának Hamilton-köre? Vagyis: tekintsük az n-dimenziós kocka élhálóját egy gráf éleinek, csúcsait a gráf csúcsainak. Van-e olyan kör, amely e gráf minden csúcsát (pontosan egyszer) tartalmazza? Erre a kérdésre könnyen válaszolhatunk, ha meggondoljuk, hogyan alakítható a kétdimenziós kocka, tehát a négyzet Hamilton-köréből a háromdimenziós kocka egy Hamilton-köre: veszünk egy oldallapját és egy ezzel párhuzamos oldallapot. Mindkettőn megrajzoljuk a Hamilton-kört, majd egy-egy megfelelő élt elhagyunk e körökből és végpontjaikat a megfelelőjükkel kötjük össze a másik lapon. Ez az eljárás nyilvánvalóan ugyanígy megy akárhány dimenzióban, tehát teljes indukcióval beláttuk, hogy az n-dimenziós kocka élhálójának van Hamilton-köre. A feladat kérdésére ezzel pozitív választ adtunk.
Most ismertetünk néhány további számelméleti feladatot. 31. feladat
Jelölje k(a) a síkbeli koordinátarendszer azon (x|y) pontjainak halmazát, amelyekre 1987 1987 1≤x,y≤a és x és y egymáshoz relatív prím egészek. Határozzuk meg a ∑ k ( ) i 1 összeg értékét. MEGOLDÁS Legyen (x|y) pont jó, ha teljesíti a feladat feltételeit. Legyen P egy tetszőleges jó pont, és húzzuk meg az OP egyenest. Ha ezen az egyenesen a feladat által kijelölt négyzetben l pont van, akkor az összegben a P pontot éppen i=1,2,…,l-re számoltuk meg. Tehát vehetjük úgy, hogy a négyzet minden rácspontját pontosan egyszer számolunk meg az összegben. Vagyis annak értéke pontosan 19872.
32. feladat
Bizonyítandó, hogy végtelen sok prímszámhoz létezik végtelen sok olyan n természetes szám, hogy p|10n+3. MEGOLDÁS Először bebizonyítjuk, hogy végtelen sok prímszámnak van legalább egy 10n+3 alakú többszöröse, azaz az ilyen alakú számok összességükben végtelen sok prímmel oszthatók. Gondoljuk meg, hogyan bizonyítjuk azt, hogy végtelen sok prímszám van. Feltesszük, hogy véges sok van, összeszorozzuk őket, hozzáadunk egyet és kapunk egy olyan összetett számot, amelynek az „összes” prím közül egy sem lehet osztója. Hogyan tudnánk ezt a gondolatot átvinni a mi esetünkre? Itt hiába szorozzuk a prímeket össze, nehezen érhető el, hogy ügyes módon manipulálva a szorzatot már tízhatványt kapjunk, ráadásul olyat, amelynél hárommal nagyobb a prímjeink közül eggyel sem osztható. Amikor az eredeti bizonyítást a 6k–1 vagy 4k–1 alakú prímekre akarjuk átvinni, akkor is hasonló problémába ütközünk, ott a szorzatot megszorozzuk hattal illetve néggyel, és levonunk belőle egyet: vagyis az eredeti prímek alakjához hasonlót veszünk. A lényeg az, hogy egy olyan többszörösét keressük a prímeink szorzatának, ami nagyon hasonló a prímeink alakjához. Az ötlet az, hogy a mi esetünkben az Euler-Fermat tétel ad ilyen eszközt a kezünkbe!
19/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Tegyük fel tehát, hogy csak véges sok különböző prímosztójuk van a tízhatvány plussz három alakú számoknak, ezek szorzata legyen M, és tekintsük az N=10Φ(M) +3 számot. 10Φ(M)–1 az Euler-Fermat tétel szerint minden prímünkkel osztható, tehát N minden prímünkkel osztva négy maradékot ad. Másrészt nagyobb háromnál, tehát van más prímosztója. Ez az ellentmondás bizonyítja állításunkat. Most már csak azt kell belátnunk, hogy ha egy adott p prímhez találunk egy p-vel osztható 10n+3 alakú számot, akkor végtelen sokat is találunk. Ehhez először a következő segédtételt látjuk be: Ha p nem osztható sem kettővel, sem öttel, akkor van olyan csupa-egy N, amely osztható p-vel. Itt csupa-egynek akkor hívunk egy számot, ha a tízes számrendszerben felírva minden jegye egyes. Vegyünk ugyanis p+1 db csupa-egy számot. Ezek közül kettő ugyanazt a maradékot adja p-vel osztva, tehát különbségük osztható p-vel, másrészt a különbség egy csupa-egy szám után írt nullákkal, vagyis egy csupaegy N szám szorozva egy tízhatvánnyal. De (p,10)=1, így p biztosan N-et, a csupa-egy számot osztja. Ezzel segédtételünket bebizonyítottuk. Ha 10n+3 osztható p-vel, akkor 10n9N + 10n + 3 = (9N + 1)10n + 3 is, De 9N+1 tízhatvány, így ez a szám is egy tízhatványnál hárommal nagyobb szám. Tehát ha találunk egy p-vel osztható 10n+3 alakú számot, akkor végtelen sokat is találunk. A feladat bizonyítását ezzel befejeztük.
A következő feladat megfogalmazása sejtteti, hogy régebbi feladatgyűjteményből származik: 33. feladat
Legyen n természetes szám, k pedig egy n-hez relatív prím egész, legalább egy és kisebb n-nél. Tekintsük az M={1,2,…,n–1} halmazt. E halmaz elemeit pirosra és kékre színeztük az alábbiak figyelembe vételével: (1) minden i∈M-re i és n–i azonos színű; (2) minden k-tól különböző i∈M-re i és |k–i| azonos színű. Bizonyítassék be, hogy M minden eleme azonos színű! MEGOLDÁS Tekintsük a számokat mod n. Ekkor az első feltétel szerint egy szám (maradékosztály) és ellentettje azonos színű. De ekkor a (2) feltétel szerint i és i–k is azonos színű. Ez azt jelenti, hogy például 1-től indulva az 1, 1–k, 1–2k, …, 1–(n–1)k számok (maradékosztályok) azonos színűek. De (k,n)=1 a feltétel szerint, így e számok teljes maradékrendszert alkotnak mod n. Vagyis az összes szám (maradékosztály) azonos színű, s ezt kellett bizonyítanunk.
34. feladat
Definiáljuk az f : N→N függvényt a következő módon: Legyen f(n) az a legkisebb a szám, ami mellett választhatunk néhány különböző x1<x2<…<xk egész számot úgy, hogy x1=n, xk=a legyen és az xi számok szorzata négyzetszám legyen. Például f(1) = 1, mert az „1” szorzat négyzetszám; f(2) = 6, mert 2·3·4·6 négyzetszám, de kisebb a nem választható; f(10) pedig 18: 10·12·15·18 négyzetszám, de nincs kisebb megoldás. A kérdés: mely természetes számokat veszi fel f értékként, és hányszor? MEGOLDÁS Érdemes próbálgatni: f(2)=6 (2,3,6), f(3)=8 (3,6,8), f(4)=4 és általában minden k2 négyzetszámra a függvény értéke k2, f(5)=10 (5,8,10), és általában f(p)=2p, ha p háromnál nagyobb prím (ehhez csak azt kell meggondolni, hogy egy négynél nagyobb szám és a kétszerese közé esik egy négyzetszám kétszerese), f(6)=12 (6,8,12), f(7)=14, f(8)=15 (8,10,12,15), f(9)=9, f(10)=18, f(11)=22, f(12)=20 (12,15,20), f(13)=26, f(14)=21 (14,15,18,20,21), f(15)=24 (15,18,20,24), f(16)=16. Ha megnézzük a függvényértékeket, azt látjuk, hogy éppen a prímszámok maradnak ki, minden más – legalábbis eddig – egyszer szerepel. A prímszámok nyilván nem szerepelhetnek függvényértékként, hiszen ha xk=p prím, akkor a korábbi számok között nincs p-vel osztható, így az xi-k szorzata nem lehet p-nek egynél magasabb hatványával osztható, tehát nem lehet négyzetszám.
20/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
Most gondoljuk meg azt, hogy egy a számot sem vehet fel kétszer az f függvényértékként. Tegyük fel, hogy f(n)=f(m)=a és legyen n=x1<x2<…<xk=a és m=y1
35. feladat
Jelölje Fn az n-edik Fibonacci-számot, F0=0, F1=1 kezdőértékek mellett. Bizonyítsuk be, hogy ha p prím és 5 kvadratikus maradék mod p (tehát van olyan x egész szám, amelynek négyzete öttel azonos maradékot ad mod p), akkor p|Fp–1. I. MEGOLDÁS Ismeretes, hogy
1 5 + 1 p −1 1 − 5 p −1 1 Fp −1 = ) +( ) = p − 2 ( 2 2 5 2
p −1 2
p −1
∑ 2i − 1 5 i =1
i −1
.
Nincs olyan négyzetszám, amelynek négyzete öttel osztva kettő maradékot adna, tehát p nem kettő. Ekkor viszont elég azt belátni, hogy a szummában álló összeg osztható p-vel. Először azt állapítjuk meg, hogy a szereplő binomiális együttható mennyi maradékot ad p-vel osztva. Adjunk hozzá egyet:
p −1 ( p − 1)( p − 2)...( p − 2i + 1) + (2i − 1)! . +1 = 1.2...(2i − 1) 2i − 1 Itt a nevező nem osztható p-vel, a számláló viszont igen, mert az első szorzatban elvégezve a beszorzásokat minden tagban lesz p-es szorzó, kivéve az egyetlen (2i–1)! tagot, aminek viszont negatív lesz az előjele. S mivel tudjuk, hogy a tört értéke egész, így ez a szám osztható p-vel. Azt kaptuk, hogy az Fp–1 szummájában szereplő binomiális együtthatók mindegyike –1-et ad p-vel osztva. Az egész összeg tehát p −1 2
−∑ 5i −1 i =1
-gyel azonos maradékot ad p-vel osztva. Ezt a mértani sort összeadva eredményül
−
5
p−1 2
−1
4
adódik. Tudjuk, hogy van olyan x szám, amelyre igaz, hogy x2≡5 mod p. Ha ezt a kongruenciát (p–1)/2 hatványra emeljük, akkor azt kapjuk, hogy
21/23
Surányi László
Fazekas táborok 1987-2003
5
p −1 2
Válogatás
≡ x p −1 ≡ 1mod p
a „kis-Fermat” tétel szerint. Azt kaptuk, hogy a mértani sor eredményéül kapott számban a számláló osztható pvel. Minthogy p páratlan, az egész tört is osztható p-vel (hiszen egész). Ezzel a feladat állítását bebizonyítottuk. MEGJEGYZÉS
p − 1 binomiális együttható 1 vagy –1, attól függően, hogy i páros vagy páratlan. Ezt i p egyszerűbben is beláthatjuk. Ismeretes, hogy a binomiális együttható 1≤i≤p–1 esetén osztható p-vel (ha p i Ha p prím, akkor a
prím), hiszen a számlálóban szerepel p, tehát osztható vele, a nevező viszont nem osztható p-vel, mert ott csak pnél kisebb számok szerepelnek. Ebből viszont a Pascal-háromszög képzési szabálya szerint következik, hogy a fölötte levő sorban bármely két egymás melletti szám összege is osztható p-vel, tehát osztási maradékaik felváltva a és –a valamely a számra. Az első (és az utolsó) szám 1, tehát az osztási maradékok felváltva 1 és –1. i=0-ra 1, tehát minden páros i-re 1, a páratlanokra pedig –1. Ezzel az állításunkat beláttuk. II. MEGOLDÁS Aki tud mod p maradékosztályokkal számolni, az sokkal gyorsabban is célhoz érhet. Legyen ugyanis x olyan maradékosztály, amelyre igaz, hogy x2=5p, azaz négyzete az ötöt tartalmazó maradékosztály. Ekkor is igaz a mod p maradékosztályok közötti egyenletként, hogy
1 1+ x n 1− x n ) −( ) . Jelöljük a-val és b-vel a két számot, amelynek n-edik hatványa itt szerepel. ( 2 x 2 1 p −1 Ekkor Fp −1 = ( a − b p −1 ) . Mostmár csak azt kell észrevenni, hogy sem a, sem b nem lehet 0p, mert x nem x
Fn =
±1p. Tehát mindkettő p–1-edik hatványa 1p a „kis-Fermat” tétel szerint. MEGJEGYZÉS A feladatnak volt egy második fele is: be kellett bizonyítani, hogy ha öt nem kvadratikus maradék mod p, akkor viszont Fp+1 osztható p-vel. A I. megoldás módszerével ez nagyon hamar kijön, a második megoldás esetén még egy kicsit trükközni kell, és bővíteni a mod p maradékosztályok testét az x2–5 polinom gyökével.
Egy ilyen válogatásban képtelenség bemutatni a feladatoknak azt a változatosságát, amely a táborokra jellemző, még a témaköröket sem tudjuk lefedni. Befejezésül még két témakör egy-egy feladatát mutatjuk be. 36. feladat
m+n különböző pozitív egész közül m db páros és n db páratlan, összegük 1987. Mi 3m+4n maximuma? MEGOLDÁS
2 2 A párosokat csökkenthetjük: 2,4,6,...,2m-re, a páratlanokat 1,3,5,...,2n–1-re. Ezek összege n +m +m ≤ 2 2 1987, azaz (2n) +(2m+1) ≤ 4·1987+1. Nekünk 3m+4n-re kell felső becslést kapnunk. Kézenfekvő a CauchySchwartz-Bunyakovszkij egyenlőtlenséget használni ehhez a következő módon:
4(2n) + 3(2m + 1) ≤ 32 + 4 2 (2n) 2 + (2m + 1) 2 ≤ 5 ⋅ (4 ⋅1987 + 1) < 446. Innen 4n+3m-re felső becslésnek 221 adódik. Most már csak olyan számokat kell keresnünk, amelyre a 221 el is érhető. Ez azt jelenti, hogy a Cauchy-Schwartz-Bunyakovszkij egyenlőtlenségben nagyjából egyenlőségnek kell állnia, tehát nagyjából n:m=4:3 aránynak kell teljesülnie. Tehát nagyjából n=4x, m=3x, amiből x-re közelítőleg 9 adódik. Kis próbálgatás után megtalálhatjuk a megfelelő számokat: m=27 és n=35 és a számok: 1,3,...,69, 2,4,...52,60.
22/23
Surányi László
Fazekas táborok 1987-2003
Válogatás
37. feladat
Határozzuk meg a p(x) polinomot, ha p(12) = 12!, és minden x-re teljesül, hogy x p(x–1) = (x– 12) p(x). MEGOLDÁS A feltételbe x=0-t helyettesítve p(0)=0. Ha a–1 gyöke a polinomnak, és a≠12, akkor a is gyök. Ezért az 1, 2, 3, ..., 11 számok is gyökei a polinomnak. A megfelelő gyöktényezők kiemelése után: p(x) = x (x–1) (x–2) ... (x–11)q(x). Ezt a feltételbe helyettesítve azt kapjuk, hogy x>12-re q(x–1)=q(x), amiből következik, hogy q konstans polinom, hiszen végtelen sok helyen azonos értéket vesz fel. Az első feltételből pedig azt kapjuk, hogy értéke 1. A p(x)=x(x–1)(x–2)...(x–11) polinom valóban ki is elégíti a feltételeket.
Egy „sláger-feladattal” fejezzük be kis gyűjteményünket. Ezt a feladatot érdekes módon egy ideig szinte minden táborban feladta valaki, nem a feladat nehézsége, hanem talán meglepő eredménye miatt. 38. feladat
Egy hosszú köralakú autópályán akarunk végigmenni autónkkal, amelynek gyakorlatilag végtelen nagy a benzintartálya. Az út mellett benzinkutak vannak. Legalább mennyi benzin van a benzinkutakban összesen, ha biztosan állíthatjuk, hogy akárhogyan is oszlanak el a kutak a pálya mentén, van olyan kút, ahonnan üres tankkal elindulva és minden benzinkútnál (a kiindulásinál is) feltankolva végig tudunk menni a pályán? MEGOLDÁS Nyilván kell legalább annyi benzin, amennyire a pálya bejárásához szükség van. Megmutatjuk, hogy ha a benzinkutakban összesen ennyi benzin van, akkor van olyan benzinkút, ahonnan elindulva fennakadás nélkül végig tudunk menni a pályán. Töltsük fel annyi benzinnel a tartályunkat, amennyi benzinnel fennakadás nélkül végig lehet menni a pályán, és induljunk el egy tetszőleges kúttól. Minden kútnál töltsük tartályunkba az összes ott levő benzint. Így végigmenve a pályán pontosan annyi benzinnel fogunk célba érkezni, amennyivel indultunk. Keressük meg a pályának azt a pontját, ahol a legkevesebb benzin volt a tankunkban. Ez a pont nyilván egy benzinkútnál van. Innen indulva akkor is végig tudjuk járni a pályát, ha eredetileg üres a tankunk.
23/23
