A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A 2011. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
1. Adott pozitív egészeknek egy végtelen sorozata, amelyre teljesül, hogy tetszőleges , pozitív egészek esetén osztható az és számok legnagyobb közös osztójával. Mutassuk meg, hogy bármely esetén osztható -gyel.
Megoldás. A binomiális együtthatók mintájára legyen | | (1) | Az szerinti indukcióval bizonyítjuk, hogy egész szám. A és esetekben az állításunk triviális, hisz . Ez a megfigyelés egyúttal az esetet is bizonyítja. Tegyük fel tehát, hogy , és teljesül minden értékre. Az (1) definícióból láthatjuk, hogy | | (2) |
A feladat feltétele szerint az szám osztható és legnagyobb közös osztójával. Ezért vannak olyan , egész számok, amelyekre . Ezt beírva (2)-be,
Az indukciós feltevés szerint a jobb oldalon álló számok egészek, így is egész.
Megjegyzések. 1. Az sorozatra triviálisan fennáll a kívánt feltétel. A feladat erre a konkrét sorozatra éppen a a binomiális együtthatók egész tulajdonságát állítja. A kitűzött feladat tehát arra mutat rá, hogy a szorzatok hányadosának egész tulajdonsága már egy, az sorozatról kikötött jóval gyengébb feltételből is következik. 2. Több versenyző próbálkozott annak becslésével, hogy egy prím milyen kitevőn osztja a számlálót, illetve a nevezőt. Nem nagyon nehéz megmutatni, hogy tetszőleges prímhatványnak legalább annyi többszöröse van az számok között, mint az számok között. Ebből a megfigyelésből pedig könnyen adódik a feladat megoldása.
2. Legyen pozitív egész. Jelölje az olyan felbontások számát, ahol és a sorozat minden tagjára a pozitív egész kitevős hatványa. Jelölje az olyan felbontások számát, ahol minden tag pozitív egész és az utolsó kivételével minden -re teljesül. Igazoljuk, hogy .
Megoldás. Tetszőleges olyan felbontást, amit az -ben számolunk meg, kódoljunk az alábbi módszerrel. Minden -re írjuk fel az kettes számrendszerbeli alakját (az -edik sorba -t írva) úgy, hogy a legnagyobb helyiértéken álló számjegyek egymás alá kerüljenek. Mivel a szám kettes számrendszerbeli alakja pontosan db egyesből áll, a kapott felírásban kizárólag egyesek fognak szerepelni, és az egyesekből álló sorok hossza lefelé haladva nem csökken. Ebben a felírásban minden egyeshez egy jól meghatározott érték tartozik: ha egy egyestől jobbra további egyes található, akkor az adott egyes értéke pontosan . A felírásból adódóan a kódolásból úgy olvasható ki az , hogy az -edik sorban álló egyesek értékét összeadjuk. Ha a most felírt kódolásban oszloponként adjuk össze a felírt egyesek értékét, akkor egy felbontást kapunk, ahol jelöli a jobbról az -edik oszlopban álló egyesek összértékét. Világos, hogy , hiszen minden egyesétől balra áll egy -hez tartozó egyes, ami pontosan kétszer annyit ér, mint a tőle jobbra álló. Ez azt jelenti, hogy az felbontást -ben számoltuk meg. Azt kaptuk, hogy minden -ben leszámolt felbontáshoz tartozik egy jól meghatározott -ben leszámolt felbontás. A továbbiakban azt igazoljuk, hogy a fenti transzformáció kölcsönösen egyértelmű megfeleltetés a kétféle típusba tartozó felbontások között. Ezt pedig úgy mutatjuk meg, hogy minden -ben leszámolt felbontáshoz konstruálunk egy -ben leszámolt felbontást, amit a fenti transzformáció pontosan az felbontásba visz. Legyen tehát adott egy -ben leszámolt felbontás. A jobb szélső oszlopban helyezzünk el db egyest egymás felett. Ha már elkészítettünk oszlopot, akkor ezektől balra úgy konstruáljuk meg az -edik oszlopot, hogy az -edik oszlop minden egyese mellé balról írunk egy egyest, továbbá még további egyest írunk ezen egyesek fölé. Ez miatt mindig megtehető. Világos, hogy ha most minden egyesnek a fent definiált értéket adjuk, akkor a -edik oszlopbeli egyesek összértéke pontosan lesz minden értelmes -re. Ha pedig a felírt egyeseket soronként olvassuk ki kettes számrendszerbeli számokként, akkor ezen számok az -nek egy -ben leszámolt felbontását adják, amit (a konstrukció miatt) a fent leírt transzformáció pontosan az felbontásba visz. Mi pedig éppen ezt akartuk bizonyítani.
Megjegyzés. A megoldás rámutat arra is, hogyan keletkezett a feladat. A jól ismert Ferrers-diagram konjugálásának mintájára teremtünk bijekciót a kétféle partíciótípus között azzal a különbséggel, hogy míg a Ferrers-diagramban minden jel értéke , ez a feladatban egy kettőhatvány, ami a diagramból egyértelműen kikövetkeztethető. Ha tehát Ferrers-diagramként (azaz ,,egyes számrendszerben'') értelmezzük az reprezentációt, akkor az a partíciót jelenti, aminek konjugáltja a Ugyanez a diagram a feladatbeli kódolás szerint az -ben leszámolt partíciót kódolja, amihez a -ben leszámolt partíció tartozik.
3. Adott a síkon pont és egyenes. Bizonyítsuk be, hogy van a síkon olyan pont, hogy -nek a egyenestől való távolságainak összege kisebb, mint -nek a ponttól való távolságainak összege.
Megjegyzés. A megoldáshoz vezető alábbi ötletre sokan rájöttek. Ha igaz az állítás, akkor annak úgy is teljesülnie kell, ha az adott egyenesek mindegyike ugyanazon az ponton halad át, és ugyanez a metszéspont van multiplicitással megadva. Ha ekkor egy -tól különböző pont rendelkezik a kívánt tulajdonsággal, akkor az félegyenes bármely pontja ilyen tulajdonságú. Márpedig, ha ,,kellően messziről'' nézünk rá a síkra, akkor az egyenesek és a pontok ,,nagyon közel'' lesznek ehhez az állapothoz. Az utolsó ötlet pedig az, hogy ha nagyon sok egyenes van adva, és azok egy szabályos oldalú sokszög átmérői, akkor -nek az egyenesektől mért össztávolsága ,,nagyjából'' arányos lesz az távolsággal. Tehát ha az állítás igaz, akkor annak már egy véletlenül választott pontra is pozitív valószínűséggel kell teljesülnie. Ezeket a gondolatokat bontjuk ki az alábbi megoldásban.
Megoldás. Válasszunk egy olyan kört a síkon, amiből a egyenes mindegyike olyan húrt metsz ki, amihez legalább nagyságú középponti szög tartozik. Könnyen látható, hogy létezik ilyen kör: válasszuk a kör középpontját tetszőlegesen, sugara pedig legyen, ahol az adott egyeneseknek az -tól mért távolságai közül a legnagyobb. Ha egy, a körbe írt szabályos hatszög és a megadott egyenesek egyike, akkor azt mondjuk, hogy jó -hez, ha -nak csúcsa esik mindkét partjára, azaz a két átellenes oldalát metszi. A választása folytán az olyan szabályos hatszögek csúcsai, amik nem jók -hez a körnek hat ívét alkotják, és mindegyik ívhez legfeljebb nagyságú középponti szög tartozik. Mivel ilyen ív nem fedheti a kört, ezért található olyan -ba írt szabályos hatszög, ami a megadott egyenes mindegyikéhez jó. Sőt, még az is feltehető, hogy a egyenes egyike sem merőleges a hatszög egyetlen oldalára sem. Azt állítjuk, hogy a , , , , , pontok valamelyike rendelkezik a feladatban leírt tulajdonsággal. Ehhez elegendő megmutatni, hogy e hat pontnak a megadott ponttól vett távolságösszege több, mint a egyenestől vett távolságösszege, hiszen ekkor nem lehetséges hogy mindegyik -nek a pontoktól mért távolságösszege legalább akkora legyen, mint az egyenesektől való. Legyen tehát a megadott pontok valamelyike. A háromszög-egyenlőtlenség miatt | | hisz és az sugarú kör átellenes pontjai. Hasonló okból | | tehát | | A megadott pontok mindegyikére összeadva a fenti becslést azt kapjuk, a pontoknak a megadott ponttól vett távolságösszege legalább . A bizonyítás befejezéséhez az alábbiakban azt igazoljuk, hogy a pontoknak az egyenesektől mért távolságösszege kisebb -nél. Legyen a megadott egyenes valamelyike. Feltehetjük, hogy a és oldalakat metszi, azaz egyik partján a , és , míg a másikon a , és pontok vannak. Világos, hogy a és pontoknak az egyenestől mért távolságainak összege megegyezik a szakasznak egy -re merőleges egyenesre vett merőleges vetületének hosszával.
Hasonlóan, a és , illetve a és pontok -től mért távolságösszege a , illetve a szakaszok -re vett merőleges vetületének hossza. Márpedig a merőleges vetület hossza sosem nagyobb a vetített szakaszénál, jelen esetben pedig szigorúan kisebb annál, ugyanis a hatszöget úgy választottuk, hogy nem merőleges -re. Tehát a kérdéses távolságösszeg szigorúan kisebb, mint e három szakasz összhossza, azaz , hiszen a szabályos hatszög oldalhossza megegyezik a köré írt kör sugarával, míg az átellenes csúcsokat összekötő húr a kör átmérője. Azt kaptuk, hogy a -knek a megadott egyenestől a távolságösszege kisebb, mint . Nekünk pedig pontosan ezt kellett bizonyítanunk.
Megjegyzés. A feladatbelinél erősebb állítás is igaz. Ha nem csak egy szabályos hatszög csúcsaival dolgozunk, hanem egy megfelelően nagy körön egyenletes eloszlással választott véletlen pontra számítjuk ki a kérdéses távolságösszegek várható értékeit (ehhez a kör mentén kell integrálni), akkor az is könnyen igazolható, hogy tetszőleges pont és egyenes esetén, ahol , mindig létezik olyan pont a síkon, hogy -nek a pontoktól vett távolságösszege legalább akkora, mint -nek az egyenesektől mért távolságainak összege.
|
|