Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]  

Szeretnél hozzászólni? Jelentkezz be.
[820] w2013-06-11 06:51:29

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

Előzmény: [816] nadorp, 2013-05-15 21:21:29
[819] nadorp2013-05-16 10:37:38

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.

Előzmény: [1087] Fálesz Mihály, 2013-05-16 10:05:01
[1087] Fálesz Mihály2013-05-16 10:05:01

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.

Előzmény: [816] nadorp, 2013-05-15 21:21:29
[818] Róbert Gida2013-05-15 23:17:03

É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 (1-\sqrt c)^7-tel, és akkor (1-c)7=1, a befejezés ugyanaz.

Előzmény: [816] nadorp, 2013-05-15 21:21:29
[817] nadorp2013-05-15 21:40:41

Bocs, a (3) egyenlet helyesen

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

Előzmény: [816] nadorp, 2013-05-15 21:21:29
[816] nadorp2013-05-15 21:21:29

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=pn 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 p2 elemű véges test és létezik T-ben 7-edrendű elem, akkor 7|p-1 vagy 7|p2-1, azaz p=7k\pm1 alakú.

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

7a3+7a2-1=0

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

b3-7b-7=0(1)

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

Jelölje \sqrt c~ p(x) egyik gyökét Kc-ben, és tekintsük az 1+\sqrt c,1-\sqrt c \in K_c elemeket.Ezekre

(1+\sqrt c)^7=1+21c+35c^2+7c^3+(7+35c+21c^2+c^3)\sqrt c=u+v\sqrt c

(1-\sqrt c)^7=1+21+35c^2+7c^3-(7+35c+21c^2+c^3)\sqrt c=u-v\sqrt c

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

c3+21c2+35c+7=0(2)
(c+7)3-112c+448=0(3)

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

64b3-448b-448=0

(4b)3-112.(4b)-448=0(4)

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

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

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

(1+\sqrt c)^7=(1-\sqrt c)^7

Ha 1-\sqrt c=0 lenne, akkor 1+\sqrt c=0 is teljesülne. De ekkor 2=0, azaz p=2 lenne, amit kizártunk. Tehát 1-\sqrt c\neq0. Így

\left(\frac{1+\sqrt c}{1-\sqrt c}\right)^7=1

Most már csak azt kell belátnunk, hogy \frac{1+\sqrt c}{1-\sqrt c}\neq1 és kész vagyunk, mert találtunk 7-edrendű elemet Kc-ben. Tegyük fel, hogy \frac{1+\sqrt c}{1-\sqrt c}=1. 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.

Előzmény: [811] w, 2013-05-14 16:07:25
[815] w2013-05-15 18:10:38

De Google jó barátom :-)

megrendelés

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

Előzmény: [814] w, 2013-05-15 17:44:22
[814] w2013-05-15 17:44:22

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?

Előzmény: [813] Róbert Gida, 2013-05-15 17:11:13
[813] Róbert Gida2013-05-15 17:11:13

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.

Előzmény: [810] nadorp, 2013-05-13 21:08:59
[812] w2013-05-14 16:30:01

Áprilisi feladatokból.

A.587 nem valami ügy (feltéve, hogy nem szúrtam el semmit). Vázlatosan: lebetűzzük, hogy ai 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 ai 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.2n tipp lesz, és belőle n.2n-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: (xi,xi2,xi3) (i=1,2,3). A rájuk illeszkedő sík egyenlete a1x+a2y+z+a0=0 alakú (nyilván nem vízszintes), behelyettesítve a három pont koordinátáit xi3+a2xi2+a1xi+a0=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-x1)(x-x2)(x-x3). 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>-(a1x+a2y+a0) vagy pont fordítva. Átrendezve p(x)>0 vagy p(x)<0 minden x\in{1;2;...;100}\{xi: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.

[811] w2013-05-14 16:07:25

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).

Előzmény: [810] nadorp, 2013-05-13 21:08:59
[810] nadorp2013-05-13 21:08:59

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.

Előzmény: [807] w, 2013-05-11 09:35:56
[809] w2013-05-13 16:39:23

Most már el is tűnt.

Előzmény: [808] w, 2013-05-13 16:38:26
[808] w2013-05-13 16:38:26

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.

Előzmény: [806] w, 2013-05-06 13:39:47
[807] w2013-05-11 09:35:56

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.

[806] w2013-05-06 13:39:47

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 xn szám, amely esetén ha a zseton ára xn, akkor a kaszinó várható bevétele 0 lesz? (+ Ha lehet, adjuk meg xn-et rekurzívan és explicite is.)

Előzmény: [768] w, 2013-03-14 15:25:38
[805] w2013-04-29 18:21:08

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!

[804] w2013-04-28 10:45:08

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.

[803] w2013-04-23 21:34:17

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.

[802] w2013-04-23 17:42:34

C. 1160. Mennyi a maradék, ha a 20122013+20132012 ö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:

20132012=(2012+1)20132011=2012.20132011+20132011\equiv20132011 (mod 2012.2013),

és hasonló lépésekkel 20132012\equiv20132011\equiv...\equiv2013 (2012.2013), ugyancsak

20122013=20122.20122011=(2011.2013+1).20122011\equiv20122011\equiv...\equiv2012 (mod 2012.2013).

Vagyis a maradék 2012+2013=4025.

[801] w2013-04-19 22:12:02

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.

Előzmény: [797] m2mm, 2013-04-18 01:03:39
[800] w2013-04-19 22:06:40

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.

Előzmény: [799] m2mm, 2013-04-19 20:12:23
[799] m2mm2013-04-19 20:12:23

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.

Előzmény: [798] w, 2013-04-18 08:26:04
[798] w2013-04-18 08:26:04

A.584 hogy kellett? Keveset foglalkoztam vele.

Előzmény: [797] m2mm, 2013-04-18 01:03:39
[797] m2mm2013-04-18 01:03:39

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.

Előzmény: [796] w, 2013-04-17 19:33:06

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]