|
Cím: |
Az 57. Nemzetközi Matematikai Diákolimpia feladatainak megoldása
|
Füzet: |
2016/november,
450 - 455. oldal |
PDF | MathML |
|
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.
4. Pozitív egészek egy halmazát illatosnak nevezzük, ha legalább eleme van, és minden eleméhez található legalább egy olyan másik eleme, hogy a két elemnek van közös prímosztója. Legyen . Mi a legkisebb olyan pozitív egész érték, amihez található egy nemnegatív egész szám úgy, hogy a | | halmaz illatos?
Baran Zsuzsanna megoldása. Be fogjuk látni, hogy a legkisebb ilyen pozitív egész a . A feladat az, hogy minél kevesebb szomszédos pozitív egész számot kell találnunk úgy, hogy azok közül mindegyik -jének legyen közös prímosztója valamelyik másik elem -jével. Ehhez megvizsgáljuk, hogy közeli számok -jeinek milyen közös prímosztója lehet, azaz hogy adott kicsi pozitív egész -ekre milyen prímre lehet és ( pozitív egész). Az , 2, 3 és 4-et fogjuk megvizsgálni. Először is, mivel páros, ezért mindig páratlan, így nem lehet 2. -re:
Azaz -nek és -nek nem lehet közös prímosztója. -re:
Így csak akkor lehetséges és , ha és , így . Ilyenkor tényleg fennáll az oszthatóság: . -ra:
Így csak a jöhet szóba. Ekkor , de , így az jó, de más nem. Tehát és közös prímosztója csak a 3 lehet, mégpedig ha . -re:
Így csak a , , azaz jöhet szóba. Ez megfelelő is: . Tehát és közös prímosztója csak a 19 lehet, mégpedig ha . Most az eddigiek alapján próbáljunk létrehozni egy megfelelő 6 elemű halmazt. Szeretnénk egy olyan -t találni, hogy -nek és -nek, -nek és -nek, illetve -nak és -nak legyen közös prímosztója. Legyen és , és (ennek a kínai maradéktétel szerint van pozitív egész megoldása). Ekkor , így , míg , így , végül , így . Így a fenti mellett a halmaz mindegyik eleméhez található egy másik elem, amivel van közös prímosztója, azaz a halmaz illatos. Tegyük fel, hogy van kisebb megfelelő is, azaz létezik pozitív egész, amihez létezik pozitív egész, hogy illatos. Nem lehet vagy , mert relatív prím -hez és -hoz is. Nem lehet , mert akkor relatív prím -hez és -hoz, így -gyel kell közös prímosztója legyen, ami csak a 7 lehet ( és közös prímosztója csak a 7 lehet). Hasonlóan -nak -gyel kell közös prímosztója legyen, de ez is csak a 7 lehet. Ez viszont azt jelentené, hogy és egyaránt oszthatóak 7-tel, ami ellentmondás. Nem lehet sem, mert akkor relatív prím a szomszédjaihoz, így -gyel vagy -tel kell közös prímosztója legyen, ez a prímosztó pedig csak a 7 lehet. Ha , akkor . Eközben relatív prím a szomszédjaihoz és mivel nem osztható 7-tel, ezért relatív prím -hez is. Ekkor -tel kell közös prímosztója legyen, ami viszont csak a 3 lehet ( és közös prímosztója csak a 3 lehet). Hasonlóan -nek -gyel kell közös prímosztója legyen, ami viszont szintén csak a 7 lehet. Ekkor azonban és , ami ellentmondás. Tehát mégsem lehet , a legkisebb megfelelő szám a .
5. Felírjuk a táblára az | | egyenletet, ahol mindkét oldalon lineáris faktor szerepel. Mi az a legkisebb pozitív érték, amelyre teljesül az, hogy elhagyhatunk e közül a lineáris faktor közül pontosan darabot úgy, hogy mindkét oldalon maradjon legalább egy lineáris faktor, és az adódó egyenletnek ne legyen valós gyöke?
Nagy Kartal megoldása. Első lépésként belátjuk, hogy . Ha kevesebb, mint 2016 lineáris faktort törölnénk ki, akkor lesz egy lineáris faktor ami mindként oldalon fog szerepelni. Legyen ez az lineáris faktor. Ekkor gyöke lesz az egyenletnek, hiszen ekkor mindkét oldal 0 lenne. Most pedig megmutatjuk, hogy -ra van megoldás. Legyen ez az egyenlet:
Most nézzük a két oldalt mint két függvényt. Legyen a bal oldal , a jobb oldal . Azt fogjuk belátni, hogy minden -re . Ezt esetenként vizsgáljuk. 1. Ha , akkor mindkét oldal pozitív lesz, így elég azt nézni, hogy abszolút értéke nagy lesz -nek. Bontsuk részekre a függvényeket és hasonlítsuk azok alapján össze: | | Ezt átírhatjuk erre az alakra: . A kibontás után látszik, hogy a jobb oldal valóban nagyobb, vagyis tagjai párosíthatók tagjaival úgy, hogy mindig az -es tag legyen a nagyobb. Vagyis ezen az intervallumon . 2. Ha , akkor hasonló módon végigvihető, hogy . 3. Ha . Ha egész és vagy alakú, akkor , . Ha egész és vagy alakú, akkor , . Ha , akkor negatív, pozitív. Ha , akkor mindkét függvény pozitív. Vagyis az kell, hogy . Itt is bontsuk részekre a függvényeket:
Itt is könnyen belátható, hogy . Vagyis itt is igaz, hogy . Ha , akkor mindkét függvény negatív, ezért azt kell belátni, hogy . A részekre bontás itt így fog kinézni:
Itt könnyen belátható, hogy . Vagyis igaz, hogy , azaz . Ezzel beláttuk, hogy a jobb oldal mindig nagyobb, mint a bal oldal, azaz nem lesz gyöke az egyenletnek. A megoldás: .
6. Adott a síkon szakasz úgy, hogy bármely két szakasz keresztezi egymást, és semelyik három szakasznak sincsen közös pontja. Jeromosnak ki kell választania mindegyik szakasznak az egyik végpontját, és oda egy-egy békát elhelyezni úgy, hogy a béka a szakasz másik végpontja felé nézzen. Ezután Jeromos -szer fog tapsolni. Mindegyik tapsolásra minden béka azonnal a szakaszon található következő metszéspontra ugrik. A békák az ugrásirányukat soha nem változtatják meg. Jeromos úgy szeretné elhelyezni a békákat, hogy soha ne legyen két béka azonos időben azonos metszésponton. Bizonyítsuk be, hogy Jeromos ezt mindig meg tudja tenni, ha páratlan. Bizonyítsuk be, hogy Jeromos ezt soha nem tudja megtenni, ha páros.
Gáspár Attila megoldása. Rajzoljunk egy olyan nagy kört, ami az összes szakaszt tartalmazza a belsejében. Hosszabbítsuk meg az összes szakaszt úgy, hogy a végpontjaik a körre kerüljenek. Két szakasz legfeljebb egy pontban metszheti egymást, ezért nem jön létre új metszéspont, tehát a hosszabbítás semmit nem befolyásol. Nevezzük a szakaszvégpontokat belépési és kilépési pontoknak attól függően, hogy indul-e belőle béka, vagy nem. Nyilvánvaló, hogy db belépési és db kilépési pont van. Tegyük fel, hogy a körön van két szomszédos belépési pont. Az 1. ábrán látható, a két szakasz metszéspontig tartó részei és a köztük lévő, más pontot nem tartalmazó körív által határolt alakzat legyen . Látható, hogy mindegyik szakasz (az -et határoló szakaszokat kivéve) 0 vagy 2 pontban metszi az határvonalát, mert az konvex. A körívet egyik sem metszi, ezért mindegyik a két szakaszt fogja metszeni. A két -et határoló szakaszon így ugyanannyi metszéspont lesz, ez legyen . Mivel , ezért ugrás után a két béka összeütközik. Ez ellentmondás, tehát nem lehet két szomszédos belépési pont. Ha a békák helyett -szer ugranak, akkor a kilépési pontokba érkeznek. Ilyenkor nem történhet ütközés, ezért ez nem módosítja a feladatot. Nyilvánvaló, hogy ha a békák nem ütköztek, akkor a kilépési pontokból indulva sem ütköznének, ekkor a lépéssorozat visszafelé játszódna le. Ebből következik, hogy nem lehet két szomszédos kilépési pont. Így a körön lévő pontok felváltva kilépési és belépési pontok.
1. ábra Válasszunk ki egy végpontot, és legyen belépési pont. A többi végpont felváltva legyen kilépési és belépési pont. Egy tetszőleges szakaszt az összes többi metsz, ezért a két oldalán ugyanannyi végpont van. Összesen végpont van, ezért egy oldalon db van. Ez páros, ezért a szakasz végpontjai különböző típusúak (2. ábra).
2. ábra Tegyük fel, hogy van két béka, ami összeütközik. Legyen a 3. ábrán látható, a két szakasz metszéspontig tartó részei és a két belépési pontot összekötő, a két szakasz kilépési pontját nem tartalmazó körív által határolt alakzat . Az konvex, ezért minden szakasz 0 vagy 2 pontban metszi az határvonalát. A két béka ütközik, ezért a két szakasz határvonalán ugyanannyi metszéspont van. A köríven páratlan számú végpont van, mert két belépési pont között vannak. Így összesen páratlan számú pontban metszik a szakaszok az határvonalát. Ez ellentmondás, tehát a békák nem ütköznek.
3. ábra Tegyük fel, hogy lehetséges. Egy szakasz egyik oldalán végpont van. Ez páratlan, ezért a szakasz két végpontja ugyanolyan típusú. Ez ellentmondás (4. ábra).
4. ábra Az első nap feladatainak megoldását az októberi számban közöltük. |
|