[111] Kós Géza | 2004-11-11 11:48:11 |
Nem nehéz 5 olyan pontot találni, amire nem lehet szinuszgörbét illeszteni:
A(0,0), B(1,0), C(2,0), D(3,0), E(3,1).
Tételezzük fel, hogy egy szinuszgörbe átmegy az A,B,C pontokon. A görbét középpontosan tükrözve B-re, a tükörkép is átmegy A-n és C-n. Ha B nem a görbe tengelyén van, akkor a görbe és a tükörkép közös pontjai periodikusan helyezkednek el (lásd az ábrát), ezért az AC egyenesnek párhuzamosnak kell lenni a tengellyel. Ugyanez elmondható a B,C,D pontokra is. Ha B és C is a tengelyen van, akkor az ABCD egyenes maga a tengely. Tehát, az ABCD egyenes mindenképpen párhuzamos a tengellyel.
A DE egyenes merőleges a tengelyre, tehát legfeljebb egy pontja lehet a görbén.
|
|
Előzmény: [110] Strenner Balázs, 2004-11-10 14:11:56 |
|
[110] Strenner Balázs | 2004-11-10 14:11:56 |
A következő probléma valószínűleg elég nehéz, pár napja vetődött fel bennem, és gyanítom, hogy a megoldása meglehetősen bonyolult, feltéve ha van.
Hallottam egy feladatot, miszerint egy szinuszgörbét kell illeszteni 3 pontra. (A szinuszgörbét egy olyan függvény grafikonjaként értelmezem, ahol a koordináta-rendszer a síkban tetszőleges helyzetű, és f(x)=asin (bx) ahol a és b nem 0. Könnyen belátó, hogy van olyan szinuszgörbe, amelyik mindhárom ponton átmegy. Gondoltam, megnézem, mi van 4 pontra. Itt már csak addig jutottam, hogy négyzetre találtam szinuszt, általánosságban azonban nem jutottam semmire. Aztán az is felvetődött, hogy ha 4-re is igaz az állítás, akkor van-e olyan n, hogy n pontot elhelyezve a síkon ne létezzen olyan szinuszgörbe, amelyre mindegyik pont illeszkedik.
Akinek van ötlete, vagy valamit valamit hozzá tud szólni, tegye meg. Köszönöm
|
|
|
|
|
[106] Gubbubu | 2004-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] Csimby | 2004-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-12*(-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ény | 2004-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 |
|
|
[102] Gubbubu | 2004-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éza | 2004-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éza | 2004-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] Sirpi | 2004-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))0.
(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ény | 2004-10-10 20:07:32 |
A 2. feladatra n=2004+(1002!)2 jon ki,ugyanis n-2004 felbomlik 2004 kulonbozo egesz szorzatara 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] Csimby | 2004-10-10 19:50:37 |
Hú, de szép! Köszi.
|
|
[96] Kemény Legény | 2004-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] Csimby | 2004-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] nadorp | 2004-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 tökéletes szám.Így
, ezért az állításból következne, hogy véges sok Mersenne-prím van.
|
|
[93] Gubbubu | 2004-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ál | 2004-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ál | 2004-04-05 23:05:17 |
Szerintem a 10. feladat [24] mindhárom kérdésére nemleges a válasz.
A. Legyen nN. Ha A(n)={x:f(x)=n} nem megszámlálható számosságú, akkor A(n)-re a feltétel nem teljesül.
n:A(n) megszámlálható É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 yR. 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).
Válasszuk meg úgy k-t, hogy „jó nagy” legyen: , ahol pi-k a prímszámok.
Ismert, hogy ha s-et elég nagynak választjuk, akkor pl. . Ebből már következik, hogy a feladat állítása nem igaz.
|
|
[90] Sirpi | 2004-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,m2.
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] Sirpi | 2004-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] nadorp | 2004-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.
|
|
|