KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Játékszabályok
Technikai info
TeX tanfolyam
Regisztráció
Témák

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Fórum - Nehezebb matematikai problémák

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Ön még nem jelentkezett be.
Név:
Jelszó:

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]  

Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[107] nadorp2004-11-03 16:50:43

Szia Csimby !

A megoldás teljesen jó és be is fejezhető. Legyen k=4m+3, ahol m\geq1, azaz k\geq127. Vizsgáljuk a számokat modulo 7. Mivel 24m+3-1=8.16m-1\equiv2m-1mod(7), ezért 7|4+23n+2-1 és 7|4.49+23n-1 miatt csak m=3n+1 jöhet szóba, azaz k=12n+7. Ekkor viszont

212n+7-1=128.212n-1\equiv(-2).1-1\equiv-3mod(13) miatt 13|4*4+212n+7-1 is teljesül, azaz nem lesz prímszám. Így a feladatnak csak a p=3,7 a megoldásai.

Előzmény: [105] Csimby, 2004-10-30 13:42:01
[106] Gubbubu2004-11-02 18:27:00

A "megváltozik" szót úgy értve, hogy az input invariáns sem lehet, hanem kifejezetten más a végén, mint kezdetben... Nem mintha azt várnám, hogy bárki is válaszol erre nekem, de fő a pontosság...

Előzmény: [102] Gubbubu, 2004-10-16 10:32:42
[105] Csimby2004-10-30 13:42:01

A.350. Adjuk meg az összes pozitív egészt, melyre a 4x2+p polinom a 0,1,...,p-1 helyeken prím értéket vesz fel.

p(x)=4x2+p

p(x)=4x2+p+(4px2-2p-1)-(4px2-2p-1)

p(x)=(p+1)(4x2-1)-(4px2-2p-1)

p(x)=(p+1)(2x-1)(2x+1)+(p+1)-4px2+p

p(x)=(p+1)(2x-1)(2x+1)+(p+1)+p(1-2x)(1+2x)

p csak prím lehet, ellenkező esetben x=0-ra p(x) összetett szám. p=2 nem jó, mert x=1-re p(x)=6, ami összetett. Tehát p páratlan, p+1 páros.

p(x)-et 3 tag összegére bontottuk fel melyek közül az 1. és a 3. osztható 2x+1-gyel. A 2. tag p+1, akkor oszthaó 2x+1-gyel, ha van páratlan osztója, hiszen 2x+1 az x=0,1,...p-1 értékeket veszi fel, vagyis minden páratlan értéket p-ig. Tehát ha p+1-nek van páratlan osztója, akkor van olyan x, hogy p+1 is osztható lesz 2x+1-gyel, tehát p(x) összetett lesz. Az nem jó nekünk amikor p+1-nek csak az 1, a páratlan osztólya illetve az, ha 2x+1=p(x), de ezt kizárhatjuk, hiszen 2x+1<p(x).

Hogyha p+1-nek nincsen 1-en kívül páratlan osztója, akkor p+1=2k, tehát p egy 2k-1 alakú prím, azaz Mersenne-prím. Ismert, hogy ekkor k is prím kell, hogy legyen. Ha k=2, akkor p=3, ez egy jó megoldás. A többi esetben k=4m+1 vagy pedig k=4m-1 alakú. Hogyha k=4m+1, akkor:

p=24m+1-1=2*(22)2m-1\equiv2*(-1)2m-1=1 (mod5)

Tehát x=1-re p(x) osztható lesz 5-tel, hacsak nem p(x)=5, akkor ez azt jelenti, hogy p(x) összetett (ha p(x)=5, az x=1, helyen, akkor p=1, ami nem prím, ez tehát nem jó).

Maradt az az eset amikor k=4m-1 és ez az ami miatt írtam, mert hogy innen nem tudok tovább menni (lehet, hogy zsákutca?). Hogyha valaki megoldotta másképpen, vagy innen tovább tud menni, az írja be, mert nagyon érdekelne.

Megjegyzés: p=7 is jó megoldás, ahol k=3.

[104] Kemény Legény2004-10-24 11:20:20

Kedves Bálint!Az ellenpéldád rendkivül meggyőző,és minden további nélkül el is fogadom,azonban ezuton egésziteném ki a megoldást azzal,hogy két kék szomszédos pont között 0 hosszuságu piros sorozatokat definiálunk....

Előzmény: [103] Ureczky Bálint, 2004-10-23 22:34:07
[103] Ureczky Bálint2004-10-23 22:34:07

Hát a 3mal való oszthatóság állandósága sajnos nem igaz... Pl:

Előzmény: [96] Kemény Legény, 2004-10-10 19:22:46
[102] Gubbubu2004-10-16 10:32:42

20. feladat Egy kis algoritmikus kombinatorika:

Van-e "éles" becslés adott n-elemű véges abc feletti k állapotú klasszikus (egyszalagos, egy I/O-fejes, jobbra/balra/helyben lépegető, determinisztikus) Turing-gépek számának felső határára?

Ezek közül hány Turing-gép olyan, ami csinál is valamit, azaz van olyab véges input, amelyre ráeresztve a gépet az megváltozik a számítási eljárás során (nem kell, hogy az eljárás szabályosan érjen véget, az úgy elég nehéz lenne!).

[101] Kós Géza2004-10-12 12:14:26

Várhatóan péntek körül, amikor már beérkeztek a vidéki dolgozatok, a megoldásokból megint csinálok egy web-oldalt.

Addig is gyűjthetjük a megoldásokat, mert én biztos nem ismerem az összeset. :-)

Az 1. feladatra tudtok szép elemi megoldást?

Előzmény: [95] Csimby, 2004-10-10 01:08:18
[100] Kós Géza2004-10-11 16:49:44

A feladat annak igazolása, hogy az f(x)ig(x)j alakú polinomok közül kiválasztható néhány, ami lineárisan összefüggő.

Legyen n olyan pozitív egész, ami f és g fokánál is nagyobb. (Azért kell ilyen furcsán fogalmazni, hogy a konstans polinomokból ne lehessen kellemetlenség.)

Tekintsük azokat az fi(x).gj(x) polinomokat, amikre i,j<2n. Ez össesen 4n2 darab polinom. Mindegyik foka legfeljebb 2(2n-1)(n-1)<4n2-1. A kiválasztott polinomok tehát többen vannak, mint az általuk kifeszített tér dimenziója...

Előzmény: [99] Sirpi, 2004-10-11 15:37:09
[99] Sirpi2004-10-11 15:37:09

19. feladat: Adott két valós együtthatós polinom: f(x) és g(x). Bizonyítsuk be, hogy ezekhez mindig létezik olyan h(y,z) kétváltozós, nem az azonosan nulla polinom, melyre h(f(x),g(x))\equiv0.

(Saját ötlet, úgy érzem, meg is oldottam, de a megoldásom nem túl szép és vannak benne picit ködös pontok is. Azért tűzöm ki, hátha valaki ad rá egy frappáns megoldást)

[98] Kemény Legény2004-10-10 20:07:32

A 2. feladatra n=2004+(1002!)2 jon ki,ugyanis n-2004 felbomlik 2004 kulonbozo egesz szorzatara \implies n-2004 legalabb (-1002)(-1001)..(-1)(1)..(1001)(1002).(Erre van is polinom, -(x-1002)...(x-1)(x+1)...(x+1002)+2004+(1002!)2),ez x=0-ra 2004,x=-1002,...,-1,1,...1002-re pedig eppen n).

Előzmény: [95] Csimby, 2004-10-10 01:08:18
[97] Csimby2004-10-10 19:50:37

Hú, de szép! Köszi.

[96] Kemény Legény2004-10-10 19:22:46

Keves Csimby!A 3. feladatnal a piros sorozatok hosszanak valtakozo elojelu osszegenek a harommal valo oszthatosaga nem valtozik egy lepes soran(ellenorizd le,ha nem hiszed).2 kekre ez 0 oszthato 3-mal,mig 2 pirosrara +-2 nem oszthato 3-mal.Igy nem elerheto. A megoldas nem sajat:Molnar Andristol(11.o.)szarmazik.

Előzmény: [95] Csimby, 2004-10-10 01:08:18
[95] Csimby2004-10-10 01:08:18

Valami okos ember beírhatná a Kürschák példák megoldásait, szerintem sokan kíváncsiak rá...

[94] nadorp2004-04-09 07:58:34

Sziasztok !

Gubbubu 12. feladatát [27] ugyan nem oldottam meg ( Péter ellenpéldája alapján nem is igaz), most csak arra szeretnék egy egyszerű példát adni, hogy az álítás milyen messzire vezet(ne).

Legyen q=2p-1 Mersenne-prím. Ekkor S_q=\frac{q(q+1)}2=2^{p-1}(2^p-1) tökéletes szám.Így

\frac{\sigma(S_q)}{S_q}=\frac{2S_q}{S_q}=2, ezért az állításból következne, hogy véges sok Mersenne-prím van.

[93] Gubbubu2004-04-06 13:50:14

Kedves Pach Péter Pál!

A 12. feladatot én - Gubbubu tűztem ki. Először is nagyon köszönöm, hogy foglalkoztál vele. Másodszor csak annyit mondtam, hogy az állítás "valószínűleg" igaz. A Derive program szerint ugyanis igaz. Jónak tűnik amit írtál - hétvégén, ha hozzájutok, részletesebben is átnézem - úgyhogy a tanulság az: ne bízzunk meg feltétlenül a számítógépes programokban, különösen ha határértékszámításról van szó.

Üdv.: G.

Előzmény: [91] Pach Péter Pál, 2004-04-05 23:05:17
[92] Pach Péter Pál2004-04-05 23:06:56

Fazekas-pályázat feladatok voltak:

18. feladat

a) Van-e olyan nem konstans folytonos függvény, amelynek minden helyen helyi szélsőértéke van?

b) Van-e olyan függvény, amely pontosan a racionális pontokban folytonos?

(c) Van-e olyan függvény, amely pontosan az irracionális pontokban folytonos? – Csak gyakorlásnak, a másik kettőnél lényegesen könnyebb.)

[91] Pach Péter Pál2004-04-05 23:05:17

Szerintem a 10. feladat [24] mindhárom kérdésére nemleges a válasz.

A. Legyen n\inN. Ha A(n)={x:f(x)=n} nem megszámlálható számosságú, akkor A(n)-re a feltétel nem teljesül.

\foralln:A(n) megszámlálható \implies ÉT is megszámlálható, ellentmondás

B. Most még egy feltétel van, de már A-hoz sincs megfelelő függvény.

C. Legyen y\inR. Ha A(y)={x:f(x)=y} nem megszámlálható, akkor A(y)-ra nem teljesül a feltétel. Ha A(y) megszámlálható (vagy véges), akkor R\A(y)-ra nem teljesül a feltétel, ellentmondás.

A 12. feladatot [27] is nehezen tudom értelmezni, valamit nagyon elnézhetek benne. Legyen pl. n=2k, ekkor Sn=k(2k+1).

(k,2k+1)=1 \implies \frac{S_n}{n}=\frac{\sigma(k(2k+1))}{k(2k+1)}=\frac{\sigma(k)}{k}\frac{\sigma(2k+1)}{2k+1}\ge\frac{\sigma(k)}{k}

Válasszuk meg úgy k-t, hogy \frac{\sigma(k)}{k} „jó nagy” legyen: k=\prod_{i=1}^s{p_i}, ahol pi-k a prímszámok.

\frac{\sigma(k)}{k}=\frac{\prod_{i=1}^s(1+p_i)}{\prod_{i=1}^s{p_i}}=\prod_{i=1}^s{\left(1+\frac{1}{p_i}\right)}\ge \sum_{i=1}^s{ \frac{1}{p_i}}

Ismert, hogy ha s-et elég nagynak választjuk, akkor pl. \sum_{i=1}^s{ \frac{1}{p_i}}>4. Ebből már következik, hogy a feladat állítása nem igaz.

[90] Sirpi2004-03-25 10:25:44

Sziasztok!

Elnézést a hosszú szünetért, de pár dolog közbejött...

Most viszont mutatok egy konstrukciót arra, hogy minden n, m pozitív egészre meg lehet adni úgy m+n-d-1 számot, hogy bármely egymás utáni n összege pozitív, bármely egymás utáni m összege pedig negatív legyen.

Ezt elég relatív prímekre bizonyítani, mert ha n=dn', m=dm', és (n',m')=1, valamint az n',m' párra van n'+m'-2 hosszú megoldás, akkor ezt 0-kkal felhigítva: az első szám elé, az utolsó mögé, és minden két szám közé is d-1 nullát beiktatva, (n'+m'-2)+(d-1)(n'+m'-1)=d(n'+m'-1)-1=n+m-d-1 hosszú sorozatot kapunk, és könnyű látni, hogy ez az n,m párra jó megoldást ad.

Innentől kezdve tehát feltehető, hogy n és m relatív prím, ilyenkor n+m-2 a konstruálandó hossz. Ha valamelyik szám, például m=1, akkor könnyű a dolgunk, mert ekkor n-1 hosszú sorozat kell, a csupa-(-1) megfelel a célnak. Tegyük fel ezért, hogy n,m\geq2.

Az eredeti állítás helyett azt fogom bizonyítani, hogy ki lehet az első m+n-2 számot két színnel (pirossal és kékkel) színezni úgy, hogy bármely szomszédos n szám között ugyanannyi (0<c<n) piros legyen, és bármely m szomszédos között ugyanannyi (0<d<m) piros legyen. Ugyanis ha ez sikerül, akkor a piros számokba P-t, a kékekbe K-t írunk értékként úgy, hogy cP+(n-c)K>0 és dP+(m-d)K<0 teljesüljön.

Ha n és m relatív prím, akkor ennek mindig van egész megoldása, például vesszük a cP+(n-c)K=1 és dP+(m-d)K=-1 lineáris egyenleteket (P-re és K-ra), relatív prím esetben ennek egyértelmű a megoldása, sőt racionális. A megoldásként kapott P és K nevezőjének legkisebb közös többszörösével megszorozva a számokat, egész megoldást kapunk.

Most már csak a tényleges konstrukció van hátra. Az alapötlet az euklídeszi algoritmus.

Legyen n>m és tegyük fel, hogy szeretnénk n+m-2 hosszú piros-kék színezést. Ha lenne n-m,m-re (n-m)+m-2 hosszú jó színezésünk, akkor állítom, annak az utolsó m elemét még 1x a színezett számok után rakva jó színezést kapnánk.

Legyen az n-m,m párra bármely szomszédos n-m között c piros, és bármely m között d piros (0<c<n-m, 0<d<m). Ekkor a kibővített sorozatban is bármely egymás utáni m között c piros lesz, és bármely egymás utáni n=(n-m)+m között pedig c+d. Ezeket könnyű látni, ha nem baj, akkor nem megyek bele részletesen.

Ezzel a módszerrel a feladatot mindig kisebb és kisebb számokra kell megoldani, kérdés, hogy mikor állunk le. Előbb-utóbb eljutunk az 1,k párhoz valamilyen k-ra, de ne itt álljunk meg, hanem 1 lépéssel előbb. A legelső 1,k pár előtt csak k+1,k lehetett az előző számpár. Erre pedig könnyen megy a konstukció, mert k+(k+1)-2=2k-1 hossz kell. Ha most a középső elemet pirosra színezzük, a többit meg kékre, akkor c=1 és d=1 lesz könnyen látható módon, tehát a színezés megfelel a feltételeknek.

Ennyi a bizonyítás dióhéjban, remélem, nem volt túl hosszú, és nem voltam túl szűkszavú bizonyos helyeken, de ha bárkinek van kérdése, akkor nyugodtan kérdezzen. Ja, és bocs, hogy ennyit kellett várni :-)

Sirpi

[89] Sirpi2004-02-27 13:29:15

Szia Nadorp!

Köszi a megoldást, teljesen jó. Amúgy ez az alapötlete az én konstrukciómnak is, amit mondjuk hétfőn beírok, ha addig nem csap le rá senki (hétvégén síelek :-) ).

S

Előzmény: [88] nadorp, 2004-02-27 10:47:48
[88] nadorp2004-02-27 10:47:48

Felső korlát megadása Sirpi [75] feladatára.

Legyenek m,n pozitív egészek és legyen (m,n)=d. Ekkor legfeljeb m+n-d-1 darab valós szám adható meg úgy, hogy közülük bármely szomszédos n darab összege pozitív és bármely szomszédos m darab összege negatív.

Tegyük fel, hogy az állítással ellentétben létezik m+n-d darab, a feltételeknek megfelelő szám. Legyenek ezek x1,x2,...xn+m-d.Előrebocsátunk két nyilvánvaló észrevételt:

1, Ha létezik a feltételeknek megfelelő sorozat, akkor olyan is létezik,amelyben bármely n darab szomszédos összege negatív és bármely m darab szomszédos összege pozitív ui. csak minden elemet meg kell szorozni -1-gyel.

2, n nem osztója m-nek és viszont

Az 1. észrevétel miatt feltehető, hogy n<m.Osszuk el m-et maradékosan n-nel:

m=nx1+r1    0<r1<n,    d|r1

Mivel az első m szám összege negatív, de bármely n szomszédos összege pozitív, ezért

x1+x2+...xr1<0. Teljesen hasonlóan

x2+x2+...xr1+1<0

...

xn-d+1+...xn+r1-d<0

Azt kaptuk, hogy létezik n+r1-d darab szám, hogy közülük bármely r1 szomszédos összege negatív és bármely szomszédos n összege pozitív, de ekkor az 1.észrevétel miatt létezik n+r1-d darab szám, hogy közülük bármely r1 szomszédos összege pozitív és bármely szomszédos n összege negatív.

A fenti gondolatmenetet most a r1,n számokra alkalmazva,ha

n=r1x2+r2    0<r2<r1,    d|r2

akkor létezik r1+r2-d darab szám, hogy közülük bármely r2 szomszédos összege pozitív és bármely szomszédos r1 összege negatív.

A fenti folyamat vég nélkül nem folytatható, ezért lesz egy olyan k index, hogy

rk-1=rkxk+1+rk+1    0<rk+1<rk,    d|rk+1

rk=rk+1xk+2+d

és létezik rk+1+d-d=rk+1 darab szám, hogy bármely szomszédos d összege pozitív és az rk+1 összege negatív. Ez viszont a 2. észrevétel miatt ellentmondás.

[87] nadorp2004-02-26 15:28:01

Teljesen jó.

Előzmény: [86] Sirpi, 2004-02-26 14:48:53
[86] Sirpi2004-02-26 14:48:53

Ha bonyi a bizonyításod egy része, akkor írd le csak a felső becslése(i)d bizonyítását. Amit én adtam megoldást a felső korlát élességére, az konstruktív, és aránylag egyszerű, ha nem lesz más megoldó, akkor azt a részt beírom én. Jó lesz így?

Sirpi

Előzmény: [85] nadorp, 2004-02-26 14:43:47
[85] nadorp2004-02-26 14:43:47

Szia Sirpi !

Kösz a segítséget, így már könnyebb volt (0...0). Én is próbálkoztam a relatív prím megoldásba "beszúrkálni", csak az volt a baj, hogy két elem közé d darab elemet és a maradék d-1 elemet meg valahogy elosztogatni.

A megoldást nem tudom, érdemes-e közölni, mert szerintem egy picit hosszú a fórumhoz. A másik baj az vele, hogy relatív prímekre felhasználtam egy kis lineáris algebrát (rezultáns) és csak egzisztenciát bizonyít, tehát nem konstruktív.

N.P.

Előzmény: [84] Sirpi, 2004-02-26 10:31:48
[84] Sirpi2004-02-26 10:31:48

Szia nadorp!

Gratulálok, lényegében megoldottad a feladatot! Az n+m-d-1 valóban éles korlát minden n,m-re (a d=1 esetre is jó). Az, hogy a korlát elérhető nem relatív prím esetben, nem olyan nehéz. Legyen (n,m)=d, n=dn', m=dm', és tegyük fel, hogy a relatív prím n',m'-re már van n'+m'-2 hosszú jó sorozatunk.

Ezt kellene "felduzzasztani", pl. bármely két elem közé, sőt, legelőre és leghátulra is d-1 új elemet (de vajon mit?) betenni, ekkor ugyanis n'+m'-2+(n'+m'-1)(d-1)=n'd+m'd+d-1=n+m-d-1 elemű lesz a felduzzasztott sorozat. Remélem, így már összeáll a teljes bizonyítás.

Sirpi

Előzmény: [83] nadorp, 2004-02-26 09:09:55
[83] nadorp2004-02-26 09:09:55

Szia Sirpi !

Az általad kitűzött példához részeredményein vannak, de egyelőre nem tudom eldönteni, hogy jó helyen kereskedek-e. Jelölje S a maximális elemszámot. Ekkor

1, Ha n=1,m=1, akkor nincs megoldás

2, Ha n|m, akkor S=m-1 ( ugyanez igaz fordítva)

3, Bizonyítottam, hogy S\len+m-2

4, Bizonyítottam, hogy m és n relatív prímek, akkor S=n+m-2 ( ez a bizonyítás sajnos nem teljesen elemi )

5, Bizonyítottam, hogy ha (m,n)=d és d\ge2, akkor S<=m+n-d-1

6, Egyelőre még nem látom, hogy az 5-ben levő felső korlát elérhető-e.

Üdv

N.P.

Előzmény: [75] Sirpi, 2004-02-17 08:51:41

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]  

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley