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.

[495] Csimby

2009-11-27 03:02:32

Szívesen!

Olvasd el ezt! A lap alján található Lagrange-tételből könnyen beláthatod, hogy minden elem rendje osztja a csoport rendjét.

Előzmény: [494] bily71, 2009-11-26 22:07:07

[494] bily71	2009-11-26 22:07:07
Kösz a segítséget! Sok helyen olvastam, de most már nagyjából értem is, hogy mit jelent: minden elem rendje osztja a csoport rendjét.
Előzmény: [493] Csimby, 2009-11-26 15:09:51

[493] Csimby

2009-11-26 15:09:51

Ellenpélda: legyen b=6 és p=7.

b² $\equiv$ 1 (mod p) nagyon-nagyon-nagyon nem csak p=3 esetén teljesül.

A modulo p maradékosztályok a 0-t kivéve a szorzásra nézve p-1 rendű csoportot alkotnak. És csak annyit állíthatunk, hogy minden elem rendje osztja a csoport rendjét. Tehát b² $\equiv$ 1(mod p)-ből csak az következik, hogy p páratlan.

Előzmény: [492] bily71, 2009-11-26 09:57:26

[492] bily71	2009-11-26 09:57:26
A második részhez még annyit, hogy b² $\equiv$ 1(mod p) már csak azért sem teljesülhet, mert feltételeztük,hogy b² $\equiv$ 0(mod 3), tehát 3\|b, és b² $\equiv$ 1(mod p) csak p=3 esetén teljesül, így teljesülne a b² $\equiv$ 1(mod 3) kongruencia is, ami ellentmondás.
Előzmény: [491] bily71, 2009-11-26 09:46:20

[491] bily71

2009-11-26 09:46:20

És most jöjjön egy másik lehetséges megoldás a B.4026. feladatra:

Minden p>3 prim felírható p=6k $\pm$ 1alakban.

A binomiális tétel értelmében

$(6k\pm1)^n=\binom{n}{0}(6k)^n(\pm1)^0+\binom{n}{1}(6k)^{n-1}(\pm1)^1+...+\binom{n}{n}(6k)^0(\pm1)^n,$

ahol a jobb oldali összeg utolsó tagja

$\binom{n}{n}(6k)^0(\pm1)^n=\pm1.$

Mivel az összeg minden tagja az utolsó kivételével osztható 6-tal, ezért

(6k $\pm$ )ⁿ $\equiv$ $\pm$ 1(mod 6).

Tételezzük fel indirekt módón, hogy a

p^k+p^m=a²

egyenlőség teljesül, ahol a pozitív egész, mivel négyzetszámon egy egész szám második hatványát értjük.

1. eset: 0<k $\le$ m, és k és m paritása megegyezik. Ebben az esetben

a² $\equiv$ $\pm$ 2(mod 6),

de ez csak úgy lehetséges, ha az

a² $\equiv$ $\pm$ 2(mod 3)

kongruencia is teljesül. Ez pedig nem teljesülhet, mert az Euler-Fermat-tétel miatt

$a^{\varphi(n)}\equiv1(\mod{n}),$

ha a és n relatív prímek, és mivel $\varphi$ (3)=2, ezért, ha 3|a, akkor a² $\equiv$ 1(mod 3), ha pedig 3|a, akkor a² $\equiv$ 0(mod 3), így az a² $\equiv$ $\pm$ 2(mod 3) kongruencia nem teljesülhet.

2. eset: 0<k<m, és k és m paritása ellentétes. Ekkor

p^k+p^m=p^m(p^k-m+1)

p^m(p^k-m+1)=a²,

ez csak úgy lehetséges, ha 2|m. Osszunk le p^m-mel, legyen $\frac{a^2}{p^m}=b^2$ , és k-m=x, ekkor

p^x+1=b².

Mivel p^x $\equiv$ $\pm$ 1(mod 3), ezért vagy a b² $\equiv$ 2(mod 3), vagy a b² $\equiv$ 0(mod 3) kongruencia teljesül. Az előbbi nem teljesülhet az 1.-ben tárgyaltak miatt. Nézzük az utóbbit:

p^x+1 $\equiv$ 1(mod p),

ebből következik, hogy

b² $\equiv$ 1(mod p).

Ez viszont azt jelentené, mivel az Euler-Ferma-tétel megfordítása is igaz, hogy p=3, vagy 3|p, de egyik sem lehetséges, mert a feladat szerint p>3 és p $\in$ P, azaz prím.

3. eset: k=m=0, ekkor a² $\equiv$ 2(mod 3), mivel p^k=p^m=1, de ez a kongruencia nem teljesülhet az 1.-ben részletezett okok miatt. Több lehetőség nincs.

[490] R.R King	2009-11-24 18:42:27
Szerintem nem kell aggódnod, mert már most többet tudsz, mint a felvételizők többsége:) Hidd el sokat változott a színvonal 20 év alatt. A másik topicban tett hibás gondolatmeneteidről meg annyit, hogy ki tudja, talán egyszer valaki hasonló nyomon indulva bizonyít be valamit a láncszemeket megfelelően helyretéve.. Vajon hány tétel született úgy, hogy előtte 100 rossz utat végigjárt a megoldó??? A legtöbben pedig, akik bírálnak 2-3 matektanártól tanulták amit tudnak, önállóan még nem sokat tettek le az asztalra..Akinek nem inge, ne vegye magára.
Előzmény: [489] bily71, 2009-11-24 17:52:53

[489] bily71	2009-11-24 17:52:53
Nemcsak szerencsésebb, hanem helyesebb is. Amit én írtam, csak k=2 esetén lehet igaz. Hirtelen nem is jutott eszembe, hogy k bármilyen egész lehet, annyira a négyzetszámokra koncentráltam. Azt hiszem, nem lesz egyszerű visszaülni 20 év után az iskolapadba, egy kicsit össze kell szednem magam, hogy sikerüljön a felvételi:)
Előzmény: [488] R.R King, 2009-11-24 16:46:04

[488] R.R King	2009-11-24 16:46:04
A 3. rész végén talán szerencsésebb azt mondani, egy prímhatvány csak úgy bontható egészek szorzatára, ha a tényezők maguk is ugyanannak a prímnek a hatványai. Jelen esetben a a+1 és a-1 különbsége 2, így ezek nem lehetnek, mert p>3, még az sem lehet hogy az egyik tényező 1 a másik pedig maga p a k-on(leellenőrizhető!)
Előzmény: [487] bily71, 2009-11-24 16:00:25

[487] bily71

2009-11-24 16:00:25

Sokan bírálták (jogosan) eddigi működésemet, ezért jöjjön egy lehetséges megoldás egy, a tudásszintemhez méretezett feladatra:

B.4026. Legyen p>3 prímszám, k és m pedig nemnegatív egész számok. Igazoljuk, hogy p^k+p^m nem lehet négyzetszám.

Megoldás:

p^k+p^m=a², ahol a nemnegatív egész, ugyanis négyzetszám definició szerint csak egy egész szám második hatványa lehet. Négy eset lehetséges:

1. k=m=0, ekkor

p^k=p^m=1

p^k+p^m=2

2=a²

$\sqrt2=a$ ,

ami nem lehet, mert a a feladat szerint egész.

2. k=m>0, ekkor

p^k=p^m

p^k+p^m=2p^m

2p^m=a²,

ami nem lehet, mert egy négyzetszám prímtényezős felbontásában minden hatványkitevő páros, a baloldali 2-es kitevője pedig páratlan.

3. k>m=0, ekkor

p^m=1

p^k+p^m=p^k+1

p^k+1=a²

p^k=a²-1

p^k=(a+1)(a-1),

ami nem lehet, mert (a+1) $\ne$ (a-1), és egy prímhatvány szorzótényezős felbontásában nem szerepelhet két különböző szám.

4. k>m>0, ekkor

p^k+p^m=p^m(p^k-m+1)

p^m(p^k-m+1)=a²,

ami csak úgy lehetséges, ha 2|m, osszuk le az egyenletet p^m-el. Legyen $\frac{a^2}{p^m}=b^2$ , és k-m=x, b és x nemnegatív egészek, ekkor

p^x+1=b²

p^x=b²-1

p^x=(b+1)(b-1),

ez pedig nem lehet a 3. esetnél részletezett okok miatt. Több lehetőség nincs.

[486] jenei.attila	2009-11-16 20:31:59
Tényleg elszámoltam.
Előzmény: [485] nadorp, 2009-11-16 16:27:18

[485] nadorp	2009-11-16 16:27:18
Szerintem elszámoltad, nálam 0,68 k=3 esetén
Előzmény: [484] jenei.attila, 2009-11-16 13:13:36

[484] jenei.attila	2009-11-16 13:13:36
Nem fordítva áll az eredeti feladatban az egyenlőtlenség jel? Ha $a=3, b=\sqrt{3}, c=1$ , akkor a baloldali kifejezés értéke nagyobb mint 3/4. Vagy valamit elszámoltam?
Előzmény: [481] m2mm, 2009-10-19 21:01:55

[483] m2mm

2009-11-11 14:24:35

B. 4211. Mutassuk meg, hogy nincs olyan racionális együtthatós polinom, amely pontosan egy egész helyen vesz fel nem egész értéket. Létezik-e ilyen tulajdonságú valós együtthatós polinom?

Megoldás: Mint ismert, ha egy p(x) valós együtthatós polinom k-adfokú, akkor tetszőleges valós a-ra $\sum_{i=0}^{k+1}(-1)^i\binom{k+1}{i}p(a-i)=0$ .

Ha véges sok a-ra lesz p(a) nem egész(p foka k), akkor vegyük a legkisebbet, mondjuk b-t. Ekkor $-p(b)=\sum_{i=1}^{k+1}(-1)^i\binom{k+1}{i}p(b-i)$ . A bal oldal nem egész, a jobb viszont igen:ellentmondás, nem létezik ilyen val. együtthatós polinom.

[482] nadorp

2009-10-20 16:18:08

Az biztos, hogy az állítás n=2 esetén nem mindig igaz. Pontosabban:

1.) $3-2\sqrt2\leq k\leq3+2\sqrt2$ esetén a maximum valóban $\frac2{k+1}$

2.minden más k-ra a maximum $\frac{k+1}{2\sqrt k|k-1|}$

Szerint n>2 esetén is valami hasonló lesz a helyzet. Nem számoltam még végig, de szerintem az a_i-k legfeljebb 2-féle értéket vehetnek fel maximum esetén, pontosabban bizonyos k esetén az összes egyenlő, a másik esetben pedig két különböző érték

Előzmény: [481] m2mm, 2009-10-19 21:01:55

[481] m2mm

2009-10-19 21:01:55

Üdv! Talált valaki a B. 4201.-re olyan megoldást, ami alkalmazható a_i>0, i=1,2,...n (a_n+1=a₁)és adott k>0 esetén

$\sum_{i=1}^n \frac{a_ia_{i+1}}{a_i^2+ka_{i+1}^2}\le \frac{n}{k+1}$ bizonyítására(ha ez igaz)?

[480] Tibixe

2009-10-13 21:39:44

Lényegesen egyszerűbb nem hiszem hogy lenne.

A te 2. lemmádból szerintem elég sokféleképpen be lehet fejezni, de hallottam azt elkerülő megoldásról is.

A. 487. meglett neked?

Előzmény: [479] S.Ákos, 2009-10-13 19:45:59

[479] S.Ákos

2009-10-13 19:45:59

A. 486. Eléggé vázlatosan:

Lemma1: $\nu$ (2n)- $\nu$ (n)=n. Egyszerű teljes indukció n-re

Lemma2.: $\nu$ (n)+ $\tau$ (n)=n, ahol $\tau$ (n) az 1-esek száma n 2-es számrendszerbeli alakjában. Itt felhasználjuk az első segédtételt, és azt, hogy $\tau$ (2n+1)= $\tau$ (n)+1; $\tau$ (2n)= $\tau$ (n), teljes indukcióval.

Lemma3.: Minden n-re van végtelen sok olyan a₁<a₂<a₃<... egész szám, hogy (2^a_i-1,n)=1, és 2^a₁-1 $\equiv$ 2^a₂-1 $\equiv$ ...(modn). $n:=2^s k=2^s {p_1}^{\alpha _1}{p_2}^{\alpha _2}\cdot...\cdot {p_k}^{\alpha_k}$ , k páratlan. Legyen q olyan prím, amire q>Max(o_{p_i}(2),s). Ezzel a választással p_i|2^q-1 nem állhat a rend tulajdonságai miatt, 2-vel nem osztható. Másrészt $2^{\varphi (k)}\equiv 1 (k)$ , így q+l $\varphi$ (k) alakú számok megfelelnek, a_i:=q+i $\varphi$ (k)

Megmutatjuk, hogy a következő számok: A₁=2^a₁,A₂=2^a₁+2^a₂,...,A_m=2^a₁+2^a₂+...+2^a_m teljes maradékrendszer mod m. Az A_i szám 2-es számrendszerbeli felírásában i darab 1-es van, így a 2-ik lemma alapján: $\nu(A_i)=A_i-i=\sum 2^{a_i}-1\equiv i(2^{a_1}-1) (mod$ m). De (2^a₁-1,m)=1, így ez az m szám teljes maradékrendszert alkot mod m

Valaki tud mutatni egyszerűbbet?

[478] rizsesz	2009-05-21 14:49:20
Annak idején amúgy lényegesen több jó megoldás volt :) Nem mellesleg az ottani megoldás tartalmazza a diszkussziót: http://www.komal.hu/verseny/2002-01/B.h.shtml (a legutolsó mondat, persze azt ki kell fejteni).
Előzmény: [477] m2mm, 2009-05-21 14:44:22

[477] m2mm

2009-05-21 14:44:22

Hát igen. A 3 pontosok többsége, de nem mindenki megtalálta, ezt kaptam:

Javító (az összes versenyzőnek), 2009/05/09 19:36

Kedves Versenyzők!

A feladat lényegében egyezik a B.3521. korábbi feladattal, de ott sajnálatos módon rossz megoldás szerepel, mely csupán 3 pontot ér. Ha észrevettétek, hogy 1 vagy $\frac{p}{(1-p)}$ a jó valószínűség, az még bizonyításra szorul, hogy $p\le \frac 12$ esetén $\frac{p}{(1-p)}$ lesz a jó megoldás, ez folytonossággal, határértékszámítással vagy teljes indukcióval könnyen igazolható.

Egy további probléma: aki ezt a levelet megkapta, az feltehetően megnézte, márcsak kíváncsiságból is azt a B.3521.-es feladatot.

A fölötte levő B. 3515. feladat:

Bizonyítsuk be, hogy a $\big[\sqrt2\cdot n\big]$ alakú számok között végtelen sok 2-hatvány van. (4 pont)

Magyarán az 5 pontos áprilisi feladatra lesz pár másolt megoldás, mivel ehhez hasonlóan meg lehet oldani (lehet hogy kicsit nehezebb a mostani, de a módszer ugyanaz). Úgy gondolom, a javítóknak erre vigyázni kéne.

Előzmény: [476] rizsesz, 2009-05-21 11:22:34

[476] rizsesz	2009-05-21 11:22:34
A baktériumos b-t meg már kitűzték annak idején a B-ben (2002 januárjában :))

[475] rizsesz

2009-05-21 11:22:06

C. 976. Adjuk meg azt a legszűkebb intervallumot, ahová három pozitív szám összegének és a reciprokaik összegének szorzata eshet.

Itt amúgy nem szükséges annak bizonyítása, hogy bármilyen értékhez van megfelelő a, b, c hármas?

[474] Blinki Bill	2009-05-19 20:54:27
Az A.479. megoldásában nem úgy van helyesen, hogy "...és (3) csak d>6 esetén teljesülhet..."?

[473] Tibixe	2009-05-18 19:02:23
A480-at hogy kellett volna megoldani? Kinek sikerült?

[472] Kós Géza

2009-05-14 16:56:27

Valóban kimaradt egy + jel. Kijavítottam.

$\sum_{i=1}^{n-1} a_ia_{i+1} \le \left( \sum_{i\equiv0~(2)} a_i \right) \left( \sum_{j\equiv1~(2)} a_j \right) \le \left(\frac{ \left( \sum_{i\equiv0~(2)} a_i \right) + \left( \sum_{j\equiv1~(2)} a_j \right) }2\right)^2=\frac14$

Előzmény: [469] Tibixe, 2009-05-13 22:57:20

[471] Csimby	2009-05-14 15:22:41
Szerintem az nem kell. Úgy 1 jönne ki $\frac14$ helyett. Számtani mértani közepet használ az A="páros indexű tagok összege" és B="páratlan indexű tagok összege" számokra.
Előzmény: [470] Lóczi Lajos, 2009-05-14 07:33:58

Már regisztráltál?
Új vendég vagy?