Fórum: Lejárt határidejű KÖMAL feladatokról

Nagyon köszönöm én is az érdekes megoldásodat. Sikerült kb. megérteni. Igazad volt, felraktak hiv. megoldást is.

Kedves Mihály,

Köszönöm a kiegészítést, erre nem gondoltam. A poén az, hogy amikor először "nekiestem" a feladatnak, akkor én is próbálkoztam ezzel a körosztási polinommal, de nem jutottam dűlőre, egészen másfelé kalandoztam el.

Szia Péter,

Köszi, hogy leírtad.

Szerintem azért legbelül a két megoldás lényege ugyanaz: találunk egy hetedrendő elemet (ha tetszik, hetedik egységgyököt) \(\displaystyle GF_{p^2}\)-ben.

Ha a Kearnes-Kiss-Szendrei cikket követjük, akkor az \(\displaystyle \Phi_7(x)=1+x+x^2+x^3+x^4+x^5+x^6\) körosztási polinom egyik gyökét keressük. Ha \(\displaystyle p\ne7\), akkor \(\displaystyle \Phi_7(1)\ne0\), így a \(\displaystyle \Phi_7\) gyökei tényleg hetedrendűek.

Mivel \(\displaystyle \Phi_7\) páros fokú palindrom polinom, a szokásos módon eloszthatjuk \(\displaystyle x^3\)-bel, és átírhatjuk \(\displaystyle x+\frac1x\) polinomjává:

\(\displaystyle \frac{\Phi_7(x)}{x^3} = x^3+x^2+x+1+\frac1x+\frac1{x^2}+\frac1{x^3} = \left(x+\frac1x\right)^3+\left(x+\frac1x\right)^2-2\left(x+\frac1x\right)-1 = \Psi_7\left(x+\frac1x\right). \)

Ha \(\displaystyle \Psi_7\)-nek van egy \(\displaystyle u\) gyöke \(\displaystyle GF_p\)-ben, akkor \(\displaystyle \Phi_7\)-nek is van (0-tól különböző) gyöke \(\displaystyle GF_{p^2}\)-ben: az \(\displaystyle x^2-ux+1\) polinom gyökei ilyenek.

Ha pedig van hetedrendű elem, akkor a multiplikatív csoport rendje, \(\displaystyle p^2-1\) osztható az elem rendjével, \(\displaystyle 7\)-tel.

* * *

A feladatban szereplő polinom a \(\displaystyle \Psi_7\) egy transzformáltja:

\(\displaystyle 7x(x+1)^2-1 = (x+1)^3 \Psi_7\left(2-\frac1{x+1}\right). \)

Ha \(\displaystyle 7a(a+1)^2-1\equiv 0~(\mod~p)\), akkor \(\displaystyle p\ne7\), \(\displaystyle GF_p\)-ben \(\displaystyle a\ne-1\), és \(\displaystyle 2-\frac1{a+1}\) gyöke \(\displaystyle \Psi_7\)-nek.

* * *

Mindkét megoldásban úgy kerestük a hetedik egységgyököket, hogy először felírtunk egy harmadfokú polinomot, aminek valamilyen szorosabb köze van a \(\displaystyle \cos\frac{2k\pi}7\) számokhoz (a Te esetedben \(\displaystyle c=\tg^2\frac{k\pi}7=\frac{1-\cos\frac{2k\pi}7}{1+\cos\frac{2k\pi}7}\)), ennek volt egy modulo \(\displaystyle p\) gyöke, és ebből egy másodfokú egyenlet adott egy hetedik egységgyököt \(\displaystyle GF_{p^2}\)-ben.

Érdekes megoldás, és még kis p<225 prímekre sem kell az ellenőrzés.

"Szorozzuk meg (1) mindkét oldalát 64-gyel ( ez megtehető, mert p páratlan)", ha p=2, akkor is megteheted.

A végén be is lehetett volna szorozni -tel, és akkor (1-c)⁷=1, a befejezés ugyanaz.

Bocs, a (3) egyenlet helyesen

(c+7)³-112(c+7)+448=0

A588

A lenti megoldás nem teljesen elemi, de úgy látom, nincs összefüggésben a hivatalos megoldásban hivatkozott cikkel.

Azt fogjuk felhasználni, hogy a q=pⁿ elemű ( p prím, n pozitív egész) T véges testben minden 0-tól különböző elem rendje osztója (q-1)-nek. Speciálisan, ha T p vagy p² elemű véges test és létezik T-ben 7-edrendű elem, akkor 7|p-1 vagy 7|p²-1, azaz p=7k1 alakú.

Legyen "a" pozitív egész és tegyük fel, hogy a p prímszámra p|7a²(a+1)-1. Ekkor nyilván p páratlan és p7. Ha K jelöli a mod p maradékosztályok testét, akkor a feltétel szerint létezik aK, hogy

7a³+7a²-1=0

Jelölje b az a multiplikatív inverzét K-ban, azaz ab=1. Ekkor

Legyen cK egyelőre tetszőleges és tekintsük a p(x)=x²-c polinom K feletti K_c felbontási testét. Ha c egy K-beli elem négyzete, akkor K=K_c, azaz K_c p elemű. Ha c nem áll elő semmilyen K-beli elem négyzeteként, akkor p(x) irreducibilis K felett, tehát K_c másodfokú bővítése K-nak, azaz ekkor K_c p² elemű. Azt fogjuk belátni, hogy c alkalmas megválasztásával K_c-ben létezik 7-edrendű elem. Ebből már, mint láttuk, következik a feladat állítása.

Jelölje p(x) egyik gyökét K_c-ben, és tekintsük az , elemeket.Ezekre

Próbáljuk meg megválasztani c értékét úgy, hogy v=0 teljesüljön, azaz

Szorozzuk meg (1) mindkét oldalát 64-gyel ( ez megtehető, mert p páratlan)

64b³-448b-448=0

Összeadva (3)-at és (4)-et

(c+7)³+(4b)³-112(c+7+4b)=0

A fenti egyenletből c+7+4b kiemelhető, tehát c=-4b-7K megoldása (2)-nek, azaz ebben az esetben v=0.Azt kaptuk tehát, hogy a c=-4b-7 választás mellet

Ha lenne, akkor is teljesülne. De ekkor 2=0, azaz p=2 lenne, amit kizártunk. Tehát . Így

Most már csak azt kell belátnunk, hogy és kész vagyunk, mert találtunk 7-edrendű elemet K_c-ben. Tegyük fel, hogy . Ekkor c=0 kell hogy legyen, de mivel c gyöke (2)-nek, azt kapnánk, hogy 7=0, azaz p=7, amit kizártunk.

De Google jó barátom :-)

megrendelés

Ha rákeresünk a cikkre, akkor az is megvan (ingyen).

De legalább elemi.

Egyébként ha már kétszer is hivatkozik feladat a megjegyzésben leírt cikkre, jó volna elektronikusan is hozzáférni. Tudjátok-e, hogy kapható-e olyan régi Kömal?

Fent van a megoldás, bár elég aktívan változik a szövege, és még mindig van benne legalább 2 hiba.

Áprilisi feladatokból.

A.587 nem valami ügy (feltéve, hogy nem szúrtam el semmit). Vázlatosan: lebetűzzük, hogy a_i között melyik mod 4 maradéknak mennyi a gyakorisága, kifejezzük belőle az összeghalmaz maradékait, és a kapott egyenletrendszert "ügyesen" megoldjuk. Szokatlanul egyszerű az eredmény, az jön ki, hogy n egy negyedik hatvány kell legyen, és ha a maradékok rendben vannak, akkor az összegek eltérése elintézhető, az a_i számoknál minden új számot az összes többi összegénél nagyobbnak választjuk.

B.4540. Ez egy érdekes feladat. Az n=2 esetnél k=1 (könnyű), ezért adott n-re k=[n/2] elérhető (párbaállítás). Ennél több nem lehet. Valóban, egy adott rab tévedési esélye 1/2, ezért minden lehetséges sapkakiosztásra eljátszva a stratégiát n^.2ⁿ tipp lesz, és belőle n^.2^n-1 talált. Skatulya-elv miatt lesz olyan kiosztás, melyre max. n/2 jó tipp van, tehát készen vagyunk.

B.4541. Vegyünk három pontot: (x_i,x_i²,x_i³) (i=1,2,3). A rájuk illeszkedő sík egyenlete a₁x+a₂y+z+a₀=0 alakú (nyilván nem vízszintes), behelyettesítve a három pont koordinátáit x_i³+a₂x_i²+a₁x_i+a₀=0 (i=1,2,3). Ez olyan gyanús polinom alakú (persze, mert úgy írtam fel a sík egyenletét :-) ). Ez a polinom nem más, mint p(x)=(x-x₁)(x-x₂)(x-x₃). Tudjuk, hogy az {1;2;...;100} tartományon minden más x-re a hozzá tartozó pont e sík felett van, már ha az a sík K része. Akkor z>-(a₁x+a₂y+a₀) vagy pont fordítva. Átrendezve p(x)>0 vagy p(x)<0 minden x{1;2;...;100}\{x_i:i=1,2,3} esetén. A gyöktényezős felbontásból ez összesen 196 módon lehet. Továbbá mivel K minden lapja ily módon háromszög, 294 él és (Euler) 100 csúcs lesz.

Szerintem biztos egyetemi anyagra van szükség, és hivatalos megoldást nem fognak felrakni. Ettől függetlenül kíváncsi volnék a megoldásodra, vagy akár egy vázlatra (a megértéshez van nálam szakirodalom).

A588-ra van viszonylag egyszerű megoldásom, de egyetemi anyagot - véges testek, testbővítés - is használ. Várnék a hivatalos megoldásra, lehet, hogy van elemi bizonyítás is.

Most már el is tűnt.

A B.4515-ről szóló hozzászólásommal valami baj van, nem tudom, hogy ezt Ti is látjátok-e. A k*szin* szóhoz nem raktam semmiféle linket sem, viszont érdekes módon valamilyen robot egy reklámoldalt rakott be hozzá. Ha pl. válaszolunk rá, akkor pedig a link eltűnik. A jelenséget érdemes volna eltüntetni. Válaszokat előre is köszönök.

A B4539 szép megoldásáért (ha van), vagy valamelyik A-jelű feladat megoldásáért cserébe felraknám a B4540, B4541 vagy A587 megoldását.

A B.4515 feladat mintájára kitűzném a következő feladatot.

Egy kaszinó egy speciális új játékautomatát vett. Zsetonnal működik, és a zsetont előre meg kell venni adott áron. A következőképpen működik. Zseton bedobása után egy legfeljebb két körös játék indul meg. Az automata véletlenszerűen választ egy egész számot 1 és n között (n rögzített), és megmutatja. Ha a látható számmal elégedett a játékos, felveszi nyereményét, ami a látható számmal megegyező számértékű pénz, és a játék véget ér. Ha a játékos szerencsésnek érzi magát, akkor még egy zsetont bedob, folytatva a játékot; a gép újra generál egy számot 1-től n-ig, és ekkor a nyeremény a két szám szorzata lesz. Melyik az az x_n szám, amely esetén ha a zseton ára x_n, akkor a kaszinó várható bevétele 0 lesz? (+ Ha lehet, adjuk meg x_n-et rekurzívan és explicite is.)

Jó, hogy így egyedül vezetem a témát. Kíváncsi volnék, még talán marcius8 kedvéért is, hogy az A.585-ös szép "magyar passziánsz"-remineszenciát hogy lehetett megfogni (ugyebár ő terjesztette elő a problémakört). Előre is köszönöm az esetleges válaszokat!

A C.1162 feladat kiírt megoldása hibás. Idézem: "Tehát a paralelogramma összes szöge hegyesszög."

Emellett még hibás a C.1145 feladat hiv. megoldása: "Írjuk fel két tetszőleges négyzetszám különbségét. Ez valahány egymás utáni négyzetszám összege lesz."

Aki alaposan meggondolta a feladatot, annak ezek az elírások nem okoznak gondot, de biztosan akad olyan, akinek igen nehéz megérteni a megoldást, ha kíváncsi, hogy a kitűzők hogyan oldották meg.

B.4530 megoldása szebben.

Használva az ábra jelöléseit, nagyítsuk FGD-t C körül kétszeresére --> BAR háromszög. Itt CPRQ paralelogr., hisz kposan tükrös. Azt fogjuk igazolni, hogy ABR hasonló BCP-hez, egy további stratégiával: azt mutatjuk meg, hogy BR:BA=BP:BC és AR:AB=AQ:AC. Vegyük észre, hogy ABC, RBP és ARQ hasonló háromszögek! Pl. ABC és ARQ hasonló: AQR<=ACB< (szögszámítás) és AQ:QR=AQ:CP, ami AC:CB a hasonlóság miatt. Ugyanígy ABC hasonló RBP, tehát készen is vagyunk.

C. 1160. Mennyi a maradék, ha a 2012²⁰¹³+2013²⁰¹² összeget elosztjuk 2012^.2013-mal?

A hiv. megoldás binomiális tétellel készült. A versenykiírás szerint azonban "egy hónapon belül a kisebb sorszámú feladatokat ajánljuk a fiatalabb versenyzőknek". Ennek megfelelően az általános iskolás megoldás:

2013²⁰¹²=(2012+1)2013²⁰¹¹=2012^.2013²⁰¹¹+2013²⁰¹¹2013²⁰¹¹ (mod 2012^.2013),

és hasonló lépésekkel 2013²⁰¹²2013²⁰¹¹...2013 (2012^.2013), ugyancsak

2012²⁰¹³=2012^2.2012²⁰¹¹=(2011^.2013+1)^.2012²⁰¹¹2012²⁰¹¹...2012 (mod 2012^.2013).

Vagyis a maradék 2012+2013=4025.

A.570 hiperbola nélkül is megoldható: GEOMETRIA Fálesz 1645-46. Az a benyomásom, hogy direkt szép elemi szerkesztést akartak kerestetni a versenyzőkkel.

Kösz a tippet. Még azt is be lehetne látni, hogy a K és C(K) ekcentritásai egymás reciproka: (16) és (17) között van leírva a cikkben. Azért ez nem egyszerű feladat B.4450 nélkül.

Mondjuk olvasd el ennek a cikknek az alján levő három estere való írását:

http://www.komal.hu/cikkek/dandelin/dandelin.h.shtml

Utána mondjuk lásd be, hogy a kúp C csúcsának az ellipszis síkjára vett merőleges vetülete az AB nagytengelyen van, innen pedig azt lásd be, hogy CAB háromszög minden oldalát érinti a cikkben leírt beírt gömb. Innen B.4450. és adódik(persze itt nem csak az egyik hiperbolaíven lesznek pontok, mert a két fókuszpont bármelyikére bármelyik oldalra vehetjük a beírt gömböt), hogy a kérdéses pontok halmaza egy hiperbolán van, minek síkja merőleges az ellipszisére, és fókuszpontjai az ellipszis nagytengelyének végpontjai etc.

A többi kúpszeletre, ha érdekel nézd végig hasonlóan.

A.584 hogy kellett? Keveset foglalkoztam vele.

Ahogy én tapasztaltam A és B példák közti egyik fő különbség, hogy A-nál valami nagyobb, hatásosabb eszközt/módszert tudsz felfedezni magadtól/gyakorolni, míg a B-példák puzzle-ként kijönnek ált. max. 2 lépésben ha az ismert apró trükköket helyes sorrendben kihasználod.

Mostanában nincs időm nagyon A-kat nézegetni, B-k meg már nem mondanak újat, így

B.4525-öt sem oldottam meg, azaz nem tudom eldönteni A-ba való-e, ránézésre nem. Pláne mert a konstrukció(legalábbis a tied) nem igényel komolyabb hátteret, mint ld. pl. A.524.

Az általad említett A.542.-re én teljesen különböző megoldást találtam, de az is és a hiv. megoldás is azt mutatja hogy váratlanul "egyszerű" a megoldása általában egy komb. példának.

Nehézségre A.584. se valami nagy ügy, de Dandelin-gömb és B.4450 alap hozzá, B-be nem berakható. Mondjuk B.4450. előkerül A.570 megoldásánál is (bár vele csak az jön ki, hogy mi a megszerkesztendő pont valójában, onnan kell kicsi számolás a szerkesztéshez, de annak a feladatnak amúgy sem a szerkesztés kéne hogy legyen a lényege, csak a pont ily módon való meghatározása, de ez csak egyéni vélemény)

De a megoldáshoz nem kell ezeket tudni, arra is van az A-példa, hogy aki nem ismeri az magától rájöjjön ezekre. Mint ahogy pl. a Sawayama-lemmát se kell ismerned, az A-példák arra vannak hogy részeredményként belásd, aztán hiv. megoldásból tudod, hogy ezt így hívják.