Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Surányi László: Válogatás a Fazekas tábor feladataiból (1987-2003)

Surányi László

Válogatás a Fazekas táborok feladataiból (1987-2003)

Készült a Közoktatási Modernizációs Közalapítvány (KOMA) támogatásával


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.

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

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 szer­ke­zet 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 (BB’).

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/

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:

.

Megoldás

Az összeget átrendezzük és minden i-re összeadjuk a négy megfelelő tagot. A négytagú összeget felülről becsülhetjük az  összeggel. Tehát a feladatban szereplő összeget felülről becsülhetjük a  összeggel. Természetesen a feladatban az összes, egynél magasabb k-ra vehetjük a k-adik hatványok reciprokösszegét, így összegük pontosan egyhez tart. S mivel összetett k-ra a k-adik 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.

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:

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 szereljük le, ha a) mindkét őrmesterét leszereltük, b) egyik őrmesterét sem szereltük le. a) eset  alkalommal következik be, b) eset alkalommal következik be. A két binomiális együttható értéke megegyezik, másrészt könnyen belátható, hogy . Vagyis az ilyen közlegényt az eseteknek 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  alkalommal, b) esetben  alkalommal szerelünk le, e két binomiális együttható összege az összes eset felénél, ugyanis az összes eset: .

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 2n2n é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: n2n-et n2n/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.)

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 AA’ és BB’ 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.

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.

Most pár olyan feladat következik, főleg a diákok által hozottak közül, amelyek egy-egy 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:  Innen rendezés és 60°-kal való osztás után: , 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ák-e meg a diákok:

11. feladat Bizonyítandó, hogy minden háromszögben igaz a következő egyenlőtlenség:

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

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(sa), b(sb), c(sc)} é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(sa) és b(sb) közül melyik a nagyobb. Vegyük a különbségüket:

a(s a) – b(s b) = (a b)s (a2b2) = (a b)(sab) = –(a b)(s c)<0,

tehát az {a(sa), b(sb), c(sc)} és az {a, b, c} számhármas ellentétesen van rendezve, így az {a(sa), b(sb), c(sc)} é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.

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:

.

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 (sa, sb, sc) é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

.

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

,

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

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 (sa)/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

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

,

s ezt kellett bizonyítani.

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 c-tő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:

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: itt a háromszög három oldala, három súlyvonala és a három oldalfelezőpontot tartalmazó kör jelöli.

Ajánló: A véges projektív síkokkal kapcsolatban lásd 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.

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+za, 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.

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  é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:

.

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 k-adikná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,mstyle='text-transform:uppercase'> 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

 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

.

A keresett P(A|B) valószínűség tehát

.

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ő?
Előzetes 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 + upqv(p+q) = (upv)(qv/u) + 2bv2/u.

A játék akkor kedvezőtlen A számára, ha 2bv2/u<0. Ebben az esetben ugyanis bárhogyan is játszik A, B játékonként legalább 2bv2/u-t tud nyerni, ha q=v/u valószínűséggel választ a-t.

Megmutatjuk, hogy 2b<v2/u, azaz 8(a+b)b<(a+3b)2. A műveletek elvégzése és rendezés után:

0<b2–2ab+a2=(ba)2. A feladat kikötése volt, hogy a és b különböző, tehát ez az egyenlőtlenség valóban fennáll.

Ha tehát B (a+3b)/4(a+b) valószínűséggel választja a-t és (b+3a)/4(a+b) valószínűséggel b-t, akkor A várható nyereménye stratégiájától függetlenül pozitív, így neki kedvez a játék.

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 vonat­kozó PQ’ 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 rajzol­tunk. 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.
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 A2-tő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 P-t. 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–3-szor, azaz páratlan sokszor. A 2N/(n–3) szám tehát páros, mivel egész. Ezt akartuk bizonyítani.

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 É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=sc és AU=sb, 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(sb)=rC(sc), ahonnan

 ismert. De akkor ismert az ennél eggyel nagyobb tört is:

.

Ez viszont azt jelenti, hogy ismerjük az s–c szakasz hosszát. Ugyanígy ismerjük az sb 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 sb és sc szakaszok hosszát, akkor ismerjük a bc 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 bc-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 |bc| és a-val szemben 90°+α/2 van. A harmadik oldal oldalfelező merőlegese metszi ki a bc oldal egyeneséből a harmadik csúcsot, A-t. A szerkesztés feltétele, hogy |bc| valóban kisebb legyen a-nál. Ez esetünkben teljesül, mert

.

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  hosszú szakasz képe  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  hosszú szakasz képe  hosszú szakasz, (és ha egy egyenesen egy ponttól  távolságra levő pontokat tekintjük, akkor a képpontok a P ponttól ugyanilyen távol vannak egy egyenesen.)

Belátjuk, hogy az f leképezés folytonos. Felhasználjuk, hogy az  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  alakú szám.

Ha PQx, akkor vegyünk egy x-nél rövidebb, de x/2-nél hosszabb  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'≤2yx. 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 nem-elforgatott 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 n-ig 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 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 n-ekre é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–1-fokú 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–1-fokú 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.

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 1≤x,ya és x és y egymáshoz relatív prím egészek. Határozzuk meg a

 ö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!

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. (φ az Euler-féle "fí" függvény, tehát φ(M) az M számnál kisebb M-hez relatív prím pozitív egészek száma) 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 csupa-egy 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 iM-re i és ni azonos színű;
(2) minden k-tól különböző iM-re i és |ki| 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 ik 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: NN 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.

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<y2<...<yl=a a két sorozat, amelyre az xi-k és az yj-k szorzata is négyzetszám. Tegyük fel, hogy például n<m. Tekintsük az összes xi és az összes yj szorzatát és hagyjuk el azokat a számokat, amelyek mindkét sorozatban szerepelnek. Így továbbra is négyzetszámot kaptunk, hiszen két négyzetszám szorzatát négyzetszámokkal osztottuk. Másrészt ebben a szorzatban már nem szerepel az a és továbbra is szerepel n, hiszen n az összes szereplő szám közül a legkisebb. Vagyis találtunk egy olyan n-nel induló számsorozatot, amelynek tagjait összeszorozva négyzetszámot kapunk és a legnagyobb tagja is kisebb a-nál. Tehát f(n)<a, ami ellentmond feltevésünknek.

Ezzel beláttuk, hogy az f függvény minden értéket legfeljebb egyszer vesz fel.

A most látott (és máshonnan is ismert) ötlet kis továbbfejlesztésével már azt is beláthatjuk, hogy ha a összetett szám, akkor szerepel f értékkészletében. Ha a négyzetszám, akkor f(a)=a, mint említettük. Tegyük fel, hogy a=p1p2...prb2, ahol a pi számok különböző prímek. Feltehetjük, hogy nagyság szerint vannak indexelve. Ha x1=p1, ... xi=pi,...,xr=pr, xr+1=a választással kapunk egy olyan, p1-gyel kezdődő számsorozatot, amelynek legnagyobb tagja a és tagjainak szorzata négyzetszám (p1p2...prb négyzete). Ha f(p1)=a, akkor kész vagyunk. Ha nem, akkor f(p1)=a’<a. Legyen y1=p1<y2<...<ys=a’ az a sorozat, amelyre az yi-k szorzata négyzetszám. Most is szorozzuk össze az összes xi-t és az összes yj-t és hagyjuk el a mindkettőben szereplő számokat. Most is négyzetszámot kapunk. A különbség az, hogy most a legkisebbet, p1-et biztosan elhagyjuk, hiszen mindkettőben szerepel, és a, a legnagyobb biztosan megmarad, hiszen csak az xi-k között szerepel.

Így kapunk egy olyan számsorozatot, amelynek tagjait összeszorozva négyzetszámot kapunk, legnagyobb tagja továbbra is a, de első tagja nagyobb, mint p1, vagyis nagyobb az eredeti sorozatunk első tagjánál. Ezt az eljárást tehát mindaddig folytathatjuk, amíg a kapott sorozat legkisebb tagjához f az a-nál kisebb függvényértéket rendel (nagyobbat nem rendelhet). Az eljárás egyszer befejeződik, hiszen a legkisebb tag mindig nő és kisebb a-nál. De csak akkor fejeződhet be, ha a legkisebb taghoz tartozó függvényérték éppen a. Ezzel beláttuk, hogy ha a összetett, akkor f felveszi értékként. (Érdemes meggondolni, hogy hol használtuk ki, hogy a összetett szám.)

Ezzel beláttuk, hogy az f függvény minden összetett számot és az egyet veszi fel értékként, és ezeket az értékeket pontosan egyszer veszi fel.

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

.

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:

.

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

-gyel azonos maradékot ad p-vel osztva. Ezt a mértani sort összeadva eredményül

 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

 a „kis-Fermat” tétel szerint. Azt kaptuk, hogy a mértani sor eredményéül kapott számban a számláló osztható p-vel. 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 Ha p prím, akkor a  binomiális együttható 1 vagy –1, attól függően, hogy i páros vagy páratlan. Ezt egyszerűbben is beláthatjuk. Ismeretes, hogy a  binomiális együttható 1≤ip–1 esetén osztható p-vel (ha p prím), hiszen a számlálóban szerepel p, tehát osztható vele, a nevező viszont nem osztható p-vel, mert ott csak p-né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

 Jelöljük a-val és b-vel a két számot, amelynek n-edik hatványa itt szerepel. Ekkor . Mostmár csak azt kell észrevenni, hogy sem a, sem b nem lehet 0p, mert x nem ±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 A párosokat csökkenthetjük: 2,4,6,...,2m-re, a páratlanokat 1,3,5,...,2n–1-re. Ezek összege n2+m2+m ≤ 1987, azaz (2n)2 +(2m+1)2 4·1987+1.  Nekünk 3m+4n-re kell felső becslést kapnunk. Kézenfekvő a Cauchy-Schwartz-Bunyakovszkij egyenlőtlenséget használni ehhez a következő módon:

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.

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.


Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.