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]  

Szeretnél hozzászólni? Jelentkezz be.
[711] m2mm2012-10-12 13:39:38

Szándékos is lehetett, letesztelni ki az akit lehet tanítani, nem csak vegetál szakkörökön, illetve ki az aki a nehéznek tűnő feladatokat bemisztifikálja és esélytelen emiatt egy IMO 3 vagy 6-ra...

Előzmény: [710] Róbert Gida, 2012-10-12 00:56:00
[710] Róbert Gida2012-10-12 00:56:00

Lejárt A567. megoldása.

Ritkán ad a szerkesztő (Kós Géza) segítséget egy akkor még élő feladathoz. Az olimpiai szakkör második feladatának (1988/6) megoldásában ugyanaz a trükk van, mint az egyébként pont a Pelikán által kitűzött A567-ben.

Egyszerre oldom meg az a,b, részét a feladatnak, legyen e=5 vagy 3. A feladat szerint a|b2-e, és b|a2-e és a,b relatív prímek, így ab|a2+b2-e is teljesül, sőt ez megfordítva is igaz (kivéve az, hogy relatív prímek lesznek). Nagyszerű, a két oszthatósági feltételből egyet csináltam.

Ha ab|a2+b2-e, akkor a2+b2-e=kab teljesül valamilyen k egészre (k lehet negatív is). Az a,b szerepe szimmetrikus, így feltehető, hogy a\leb. Rendezve: b2-kab+a2-e=0, azaz x=b megoldása az x2-kax+a2-e=0 másodfokú egyenletnek. Végtelen leszállás (méthode de descente infinie) következik, majd felszállás.

Tegyük fel, hogy a>2 teljesül. Ha az egyenletnek az egyik megoldása 'b', akkor a másik b2=ka-b (gyökök és együtthatók közti összefüggés) és a,b2-re teljesül, hogy a2+b22-e=kab2, sőt a,b2 relatív prímek, hiszen lnko(a,b2)=lnko(a,ka-b)=lnko(a,b), továbbá b2 egész (trivi), és pozítiv, hiszen b_2=\frac{a^2-e}{b}>0, mert a2-e\ge9-5=4>0 és b>0. Már csak az kell, hogy "kisebb" megoldást találtunk, valóban: b_2=\frac{a^2-e}{b}<\frac{a^2}{b}\le a (utóbbi azért, mert a\leb volt). Azaz a (b2,a) pár megoldás, ahol b2<a, így az (a,b) párnál a rendezésben kisebb megoldást kaptunk.

Leszállás addig működik, amíg az a>2 feltétel teljesül. Mikor akadunk el e=3 esetben: ha a=1, akkor b=1 vagy b=2, míg az a=2 eset nem ad megoldást. Így (még a (2,1) páron kívül) nincs más megoldás, hiszen a felszálláshoz szükséges b>2 feltétel egyikre sem teljesül. Ha e=5, akkor a=1 esetén b=1,2,4 és a=2 nem ad megoldást. Végtelen felszállás működik, de csupán az (1,4) párra, hiszen ott b>2. Figyeljük meg, hogy k értéke egy sorozat mentén konstans, itt k=3. Azaz az összes megoldás (1,1),(1,2) és legyen a0=1;a1=4;an=3an-1-an-2, ekkor (an,an+1) megoldás, illetve ezek felcserélésével kapott párok. És nincs több megoldás. Ehhez még elsüthetjük azt, hogy a fel/leszállás adott megoldásból kiindulva egyértelmű, hiszen a másodfokú egyenletnek két gyöke van.

[709] Róbert Gida2012-05-10 23:56:19

Tavalyi B. 4364. megoldásához:

Legyen c=z;b=y+z;a=x+y+z ahol x,y,z nemnegatív a feltételek miatt. Behelyettesítve és rendezve az egyenlőtlenséget bal oldalra minden tag együtthatója pozitív lesz. Nagyon olcsó példa.

A Mathematica is bebizonyítja (Simplify elég hozzá).

[708] Róbert Gida2012-04-11 17:11:59

(lejárt) A557.

Solution. Define a1=3,an+1=(an2+1)/2. Paint the numbers in the interval Ai=[ai,ai+1) in the color i mod 3. The number 1 painted in color 2, number 2 - as you like. Now consider any x,y,z(x<y) such that x+y=z2 and z lies in Ai. Then it is easy to see that y is either Ai+1, or Ai+2, ie, y and z have different colors. Equality 1+3=22 is also not suitable.

A megoldás az internetről jön. Oroszból lefordítva a google translate segítségével (tex-be áttéve és a mat.jeleket újra beírva). 5 perc alatt találtam meg, google és google translate kellett hozzá. Kezdő internetezőnek talán érdekes lehet, hogy nulla orosz tudással egy orosz lapon levő zip-elt file-ban levő orosz nyelvű feladatot és megoldást miért is lehet egyáltalán megtalálni. Kömal kiírásból: "Többször előfordult már, hogy egy-egy feladat szerepelt valamely példatárban, vagy megtalálták az interneten...Célunk továbbra is versenyzőink problémamegoldó képességének feljesztése, nem pedig a keresőprogramok tesztelése", de itt nem pusztán kereső kellett hozzá. És ez nem az első Kolmogorov kupás feladat volt az A jelűek között, talán érdemes lenne kitűzés előtt az interneten rákeresni, hogy a megoldás fent van-e. Megjegyzem nem minden megoldást tettek fel a Kolmogorov kupáról, de például az A545 és az A539 Kolmogorov kupás feladatok megoldásai ugyanitt megtalálhatóak. 15 ingyen pont kicsit sok az A pontversenyben 1 tanév alatt, nem?

[707] m2mm2012-04-11 13:47:52

A. 558. feladatot valaki megoldotta a fórumosok közül? Érdekelne a megoldása.

[706] nadorp2012-03-14 00:45:26

2. megoldás az A556 feladatra:

Legyen f(t)=\sum_{i=1}^n|\sin(t-a_i)|. Ha n=1, akkor t=a1 választással a feladat állítása nyilván teljesül, ezért a továbbiakban feltesszük, hogy n\geq2.

Mivel az f(t) függvény \pi-szerint periodikus, ezért az állítást elegendő abban az esetben bizonyítani, amikor

0\leqt<\pi és 0\leqai<\pi ( 1\leqi\leqn), sőt az általánosság megsértése nélkül az is feltehető, hogy

(1)0\leqt<\pi , 0\leqa1\leqa2\leq...\leqan<\pi

. Ekkor

(2)|\sin(t-a_i)|=\left\{\matrix{\sin(t-a_i)&ha&t>a_i\cr \sin(t-a_i+\pi)&ha&t\leq a_i}\right.

Szükségünk lesz még a következő azonosságra

(3)\sum_{k=1}^{n-1}\sin\frac{k\pi}n=\ctg\frac\pi{2n}

Valóban

\sum_{k=1}^{n-1}\sin\frac{k\pi}n=\sum_{k=1}^{n-1}\frac{2\sin\frac{k\pi}n\sin\frac\pi{2n}}{2\sin\frac\pi{2n}}=\sum_{k=1}^{n-1}\frac{\cos(k-\frac12)\frac\pi{n}-\cos(k+\frac12)\frac\pi{n}}{2\sin\frac\pi{2n}}=\frac{\cos\frac\pi{2n}-\cos(n-\frac12)\frac\pi{n}}{2\sin\frac\pi{2n}}=\ctg\frac\pi{2n}

Rátérve a feladat bizonyítására, azt fogjuk belátni, hogy az (1) feltételek mellett \frac1n\sum_{i=1}^nf(a_i)\leq\ctg\frac\pi{2n}. Ebből már következik a feladat állítása, hiszen ha f(a_k)=\min_{1\leq 
 i\leq n}f(a_i), akkor f(a_k)\leq\ctg\frac\pi{2n} is teljesül.

\sum_{i=1}^nf(a_i)=\sum_{i=1}^n\sum_{j=1}^n|\sin(a_i-a_j)|=\sum_{k=1}^{n-1}\sum_{i-j\equiv k~mod(n)}|\sin(a_i-a_j)|

Itt felhasználva (2)-t és hogy a sinus függvény a [0,\pi] intervallumon konkáv

\sum_{i-j\equiv k~mod(n)}|\sin(a_i-a_j)|=\sin(a_1-a_{n-k+1}+\pi)+...+\sin(a_k-a_n+\pi)+\sin(a_{k+1}-a_1)+...+\sin(a_n-a_{n-k})\leq

\leq n\sin\frac{(a_1-a_{n-k+1}+\pi)+...+(a_k-a_n+\pi)+(a_{k+1}-a_1)+...+(a_n-a_{n-k})}n=n\sin\frac{k\pi}n

tehát (3) alapján

\sum_{i=1}^nf(a_i)\leq\sum_{k=1}^{n-1}n\sin\frac{k\pi}n=n\ctg\frac\pi{2n}

Megjegyzés: Az f(t) függvény minimumára adott felső becslés általában már nem javítható, ugyanis a_k=\frac{(k-1)\pi}n (1\leqk\leqn) esetén f(t)\geq\ctg\frac\pi{2n} teljesül és egyenlőség t=ak+m\pi ( m egész) esetén van

[705] jenei.attila2012-03-13 09:14:30

Szép feladat volt ez, és nagyon szép megoldásokat adtatok rá. Különösen az első tetszett, de Fálasz Mihályé is igen elegáns. A harmadik a vektorok használatának erejét mutatja, az is nagyon ügyes. Grat mindkettőtöknek.

Előzmény: [702] HoA, 2012-03-09 10:49:57
[704] HoA2012-03-09 14:43:39

A szemléletes megoldások után jöjjön egy mechanikus, vektoralgebrai. Jelöljük a \vec V vektor 90 fokos pozitív elforgatottját \vec {V_n} -nel, \vec V és \vec {V_n} összegét \vec {V_d} -vel . \vec {V_d} a \vec V -vel 45 fokos szöget bezáró, \sqrt 2 |\vec V | hosszúságú vektor. Könnyen belátható, hogy tetszőleges \vec U és \vec V vektorokra ( \vec U + \vec V)_n =  \vec {U_n}  + \vec {V_n}

Legyen  \vec{CA} =  \vec a ,  \vec{CB} =  \vec b . Ekkor  \vec {NL} = 1/2  \vec a ,  \vec {NM} = 1/2  \vec {( a - b )} ,  \vec {LO} = 1/2  \vec {( a - b )_n}  ,  \vec {NO} = 1/2  ( \vec a +   \vec {( a - b )_n } ) . Hasonlóan  \vec {MO} = 1/2  ( \vec b +   \vec {( a - b )_n } )

 \vec {NO} = 1/2  (\vec a + \vec a_n - \vec b_n ) = 1/2  (\vec {a_d} - \vec {b_n} ) . Mivel  \vec {a_d} és  \vec {b_n} adott hosszúságú vektorok, különbségük abszolút értéke akkor lesz a legnagyobb, ha egy egyenesbe esnek és ellentétes irányúak.  \vec {a_d}  \vec a - hoz képest 45 fokra áll, tehát  \vec {b_n} 225 fokra és így  \vec b 135 fokra. Hasonlóan adódik, hogy  \vec {MO} is akkor a leghosszabb, ha  \vec a és  \vec b 135 fokos szöget zár be.

Előzmény: [703] Fálesz Mihály, 2012-03-09 13:37:29
[703] Fálesz Mihály2012-03-09 13:37:29

B. 4408. Az ABC háromszögben AC és BC oldalak hossza rögzített, a C-nél levő szög pedig változik. Az AC oldal felezőpontja M, a BC oldal felezőpontja N, az AB oldalra kifelé állított négyzet középpontja pedig O. Hogyan kell az ACB szöget megválasztani ahhoz, hogy az OM és ON távolságok összege a lehető legnagyobb legyen?

Megoldás. Legyen az AB oldal felezőpontja K, ekkor persze CMKN paralelogramma, és megjelölt szögek egyállású szögek. Az AOK és BOK háromszögek egyenlő szárú derékszögű háromszögek.

Írjuk fel a Ptolemaiosz-tétel egyenlőtlenség alakját az OAMK négyszögre: OM.AK\leOA.MK+OK.AM; ebből


OM \le \frac{OA}{AK} \cdot MK + \frac{OK}{AK} \cdot AM
= \sqrt2 \cdot \frac{BC}2 + 1 \cdot \frac{AC}2
= \frac{\sqrt2}2 BC + \frac12 AC. (1)

Egyenlőség akkor van, ha OAMK húrnégyszög. Mivel AOK\angle=45o, ez ekvivalens azzal, ha KMA\angle=135o, azaz BCA\angle=135o.

Ha a Ptolemaiosz-tételt az OBNK négyszögre írjuk fel, akkor azt kaphatjuk, hogy


ON \le \frac{\sqrt2}2 AC + \frac12 BC, (2)

és egyenlőség most is akkor van, ha BCA\angle=135o.

Az (1) és (2) becslések összeadásával


OM+ON \le \frac{1+\sqrt2}2(AC+BC).

Az OM és ON összege tehát legfeljebb \frac{1+\sqrt2}2(AC+BC), és ez az érték akkor áll elő, ha BCA\angle=135o.

Előzmény: [702] HoA, 2012-03-09 10:49:57
[702] HoA2012-03-09 10:49:57

B. 4408. Az ABC háromszögben AC és BC oldalak hossza rögzített, a C-nél levő szög pedig változik. Az AC oldal felezőpontja M, a BC oldal felezőpontja N, az AB oldalra kifelé állított négyzet középpontja pedig O. Hogyan kell az ACB szöget megválasztani ahhoz, hogy az OM és ON távolságok összege a lehető legnagyobb legyen?

Az 1. ábrán MNPQ és ABRS négyzetek, L az AB oldal felezőpontja. \vec{OM} = \vec{OL} + \vec{LM} =  \vec{PN} + \vec{NC} = 1/2 ( \vec{RB} + \vec{BC}) = 1/2 \vec{RC} és hasonlóan \vec{ON} = 1/2 \vec{SC} Így feladatunkkal egyenértékú, ha az RC és SC távolságok összegének maximumát keressük, ahol ABRS az AB oldalra kifelé állított négyzet.

Rögzítsük a háromszög AC oldalát. ( 2. ábra ) Ekkor B a C körüli r1=a sugarú k1köríven mozoghat, 90 fokos C-nél levő szöghöz tartozó helyzete legyen B0 , egy másik helyzete B1 . Legyen ACGH az AC egyenes B0 -t tartalmazó olalán állított négyzet. S-et úgy kapjuk, hogy B-t A körül óramutató járás irányában ( negatív irány ) 90 fokkal elfordítjuk, S rajta van a H középpontú a sugarú k2 körön, B0-nak ill. B1 -nek megfelelő helyzete S0 ill. S1 . R-et B-nek A körüli 45 fokos \sqrt 2 nagyítású nyújtva forgatásával kapjuk, R rajta van a G középpontú \sqrt{2}a sugarú k3 körön, B0-nak ill. B1 -nek megfelelő helyzete R0 ill. R1 . RC akkor a leghosszabb, ha R k3 és a CG egyenes R* metszéspontjába kerül. Ekkor R0GR* szög 45 fokos, ez B-nek arra a B* helyzetére fordul elő, ha a B0CB* szög 45 fokos, vagyis az ACB szög 135 fokos. Hasonlóan SC akkor a leghosszabb, ha S k2 és a CH egyenes S* metszéspontjába kerül. Ekkor S0HS* szög 45 fokos, tehát SC is akkor a leghosszabb, ha B B* -ban van. Ezért az RC és SC távolságok összegének maximuma az ACB szög 135 fokos értékénél adódik. Ez a maximális távolságösszeg az ábrából leolvashatóan l_{max} = a + \sqrt 2 b  + \sqrt 2 a + b= ( a + b ) ( 1 + \sqrt 2 ) . Eredeti feladatunk maximális távolságösszege ennek a fele.

Előzmény: [701] elrond16, 2012-02-27 16:33:37
[701] elrond162012-02-27 16:33:37

Sziasztok!

Engem nagyon erdekelne a B.4408-as feladat megoldasa. Ha esetleg valaki beirna, vagy elkuldene nekem a megoldasat nagyon orulnek! Koszi

[700] Róbert Gida2012-02-15 01:12:29

Ok, így már értelek. Amúgy lényegében ugyanez az én bizonyításom is, csak kissé hosszabban elmondva.

Előzmény: [699] Fálesz Mihály, 2012-02-14 23:31:01
[699] Fálesz Mihály2012-02-14 23:31:01

Az A.545. megoldása két becslésből áll:

 \frac{a^2-b^2}2 \le [a+b,a-b] \le b^2-1.

Mindkét egyenlőtlenség onnan jött, hogy a kisebbik szám osztója a nagyobbiknak. Ha valamelyik esetben nincs egyenlőség, akkor az arány legalább 2, és az is igaz, hogy a2-b2\leb2-1.

Előzmény: [697] Róbert Gida, 2012-02-14 17:46:12
[698] Róbert Gida2012-02-14 18:51:01

Javítás: (a+b,a-b)=e.

Előzmény: [697] Róbert Gida, 2012-02-14 17:46:12
[697] Róbert Gida2012-02-14 17:46:12

Hát nem látható. Két feladatot összetéve: b\sqrt 3 -1<a<b\sqrt 3, illetve még azt is bizonyította, hogy a2\le3b2-2, de még ezekből sem következik, hogy a2=3b2-2 lehet csak.

De valóban kijön egy kis munkával: A545. megoldásából: b2-1 többese [a+b,a-b]-nek, így alkalmas pozitív g egésszel: b2-1=g*[a+b,a-b], továbbá (a+b,a-b)=2 miatt az is igaz, hogy [a+b,a-b]=\frac {a^2-b^2}{e}. Azaz a kettő egyenletből: \frac{b^2-1}{g}=\frac{a^2-b^2}{e}. Itt e=1,2 lehet csupán A545 szerint.

e=1 esetén kapjuk: b2-1=g(a2-b2), ebből: a^2=\frac {g+1}{g}b^2-\frac {1}{g}<2b^2, amiből: a<b\sqrt 2, ami ellentmondás lesz a>b\sqrt 3-1-gyel, ha b>3.

e=2-nél hasonlóan, 2(b2-1)=g(a2-b2), amiből: a^2=\frac {g+2}{g}-\frac {2}{g}<2b^2, ha g>1, ami megint ellentmondás. Ha g=1, akkor meg 2(b2-1)=a2-b2, azaz a2-3b2=-2, és pont ezt kellett bizonyítani. (A551 miatt ez mindig megoldás).

A végtelen leszállást meg úgy értettem, hogy a feladatot végtelen leszállással bizonyítsuk be, hogy még az is kijöjjön, hogy nincs más megoldás.

Előzmény: [696] Fálesz Mihály, 2012-02-14 09:21:43
[696] Fálesz Mihály2012-02-14 09:21:43

Azok az (a,b) párok jók, amikre b=1, vagy a2-3b2=-2. Ez az egyik irányban leolvasható az A. 545. megoldásából, a másik irányban az A. 551. megoldásából.

A végtelen leszállás a szokásos módon működik, az a'+b'\sqrt3 = (a+b\sqrt3)(2-\sqrt3), azaz a'=2a-3b, b'=2b-a képletekkel.

Előzmény: [695] Róbert Gida, 2012-02-14 01:48:18
[695] Róbert Gida2012-02-14 01:48:18

Azt senki nem gondolta végig, hogy a megadottakon kívül miért nincs más megoldás? Egy lehetséges út lenne végtelen leszállást alkalmazni, voltak hasonló olimpiai példák is. Itt nem látom, hogy lehetne ilyet csinálni, ráadásul itt két oszthatósági feltétel is van.

Előzmény: [694] Róbert Gida, 2012-02-11 12:48:17
[694] Róbert Gida2012-02-11 12:48:17

Lejárt A551. megoldása:

Az ezer alatti megoldások géppel könnyen megkaphatóak, ezek: (5,3),(19,11),(71,41),(265,153),(989,571). Tehát az "a", illetve "b" sorozat: 5,19,71,265,989 és 3,11,41,153,571 Ezek a sorozatok Neil Sloane adatbázisában benne vannak (előkelő helyen): A001834 és A001835. Én legalábbis nem lepődök meg, hogy a Pell egyenletekhez van közük a sorozatoknak, de az ismert tételeket a Pellből nem fogom használni.

(a*b+1)/(a+b) és (a*b-1)/(a-b) (egész elemű) sorozatra is érdemes rákeresni, ez valójában egy sorozat: A001075. Az explicit képleteket is megadja Neil, ezeket használom:

f(n) = ((1+\sqrt{3})^{2n-1}+(1-\sqrt{3})^{2n-1})/2^n

g(n) = ((3+\sqrt{3})^{2n-1}+(3-\sqrt{3})^{2n-1})/6^n

h(n) = ((2+\sqrt{3})^n + (2-\sqrt{3})^n)/2

Pell helyett: megfelelő lineáris rekurziót teljesítik a sorozatok (kezdőtagok is jók), így a sorozat tagjai egész számok (ez karakterisztikus polinomokkal is kijön). Legyen a=f(n) és b=g(n). Ekkor bizonyítható a képlettel, hogy a2-3*b2=-2, ebből pedig a>b\sqrt{3}-1.

a*b+1=(a+b)*h(n-1)

a*b-1=(a-b)*h(n)

is teljesül, ezeket is az explicit képlettel láthatjuk be, ehhez célszerű minden tagot s*tn alakban felírni. Ami kellett (az (f(n),g(n)) számpárok különbözőek, így ez végtelen sok megoldást ad).

[693] m2mm2012-01-18 22:18:11

A.549. (Többször elég vázlatos lesz)

Lemma: UVW háromszög VW oldal belső P pontjára tekintsük UVP és UPW háromszögek O1, O2 középpontú beírt köreit, e két kör közös belső érintője nyilván UP. Ekkor a másik közös belső érintő VW oldalt a beírt kör E érintési pontjában metszi(ha a két kör érinti egymást, akkor a két belső érintő egybeesik, ezesetben ez megy át a kérdéses ponton).

Ez könnyen bizonyítható csupán az érintőszakaszok felírásával, ezt most nem részletezem.

Innen az érintő egyenesek miatt adódik egyszerűen, hogy O1PO2\angle=90°=O1EO2\angle, azaz O1O2PE húrnégyszög.

Mivel ABCD érintőnégyszög, ezért ABC és CDA beírt körei AC-t egy pontban érintik (\frac{AB+AC-BC}{2}=\frac{AD+AC-DC}{2}, mivel AB+DC=AD+CB), mondjuk F-ben.

Legyen ABE, BCE, CDE, DAE háromszögek beírt köreinek középpontja rendre O1,O2,O3,O4. Előbbiekből jön, hogy O1O2EF és O3O4EF húrnégyszögek.

Van az az eset, amikor E,F egybeesik, de ekkor kisakkozható, hogy ABC és CDA beírt körei érintik egymást, azaz ami a lényeg és megjegyezzük, hogy O1O2E és O3O4E körök hatványvonala AC.

Monge szerint(három hasonlósági pont tétele...) ABD és BCD háromszögek beírt köreinek külső hasonlósági K pontja AC-re illeszkedik, ha a harmadik körnek ABCD beírt körét vesszük.(két külső hasonlósági pont a háromból A és C...) ABD beírt körének középpontja nyilván BO1-en rajta van(belső szögfelezője ABD-nek...) és hasonlóan BDC beírt körének középpontja BO2-n. Mivel a belső hasonlósági pont közös belső érintőn van, továbbá két kör kp-ja és hasonlósági pontjai harmonikus pontnégyes + van egy Papposz-Steinerünk, ezért BO1,BE,BO2 egyeneseket tekintve BE harmonikus társa BK.

De ABE és BEC beírt köreinek középpontja és hasonlósági pontjai is harmonikust hat. meg, így e két kör R külső hasonlósági pontjára BR BE-nek harmonikus társa BO1,BO2,BE tekintetében. Mivel R és K nyilván AC-n van, így ebből az adódik, hogy R=K.

Ezt eljátszva O3,O4-re az adódik, hogy O1O2 és O3O4 R-ben metszik egymást, ergo AC-n. Mivel AC hatványvonala volt két körünknek anno, így innen triviális a húrnégyszögség.

[692] Róbert Gida2012-01-12 16:33:32

http://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A550&l=hu azt hiszem az én megoldásom az egyszerűbb. A hivatalos megoldást végigszámolva a kínai 5093338546785390*k+1400926917841815 sorozatot nézi, míg én a 38*k+21 számtani sorozatot.

Előzmény: [691] Róbert Gida, 2012-01-11 14:15:23
[691] Róbert Gida2012-01-11 14:15:23

Lejárt A550. megoldása: Teljesen trivi becsléssel nem jön ki: nézzük meg hány szám áll elő n-ig! n-ig van legfeljebb (1+\epsilon)\frac {n}{\log n} prím és \frac {\log n}{\log {(phi)}}+c Fibonacci szám, ahol phi=\frac {1+\sqrt 5}{2}. Így n-ig van kb. \frac {n}{\log (phi)}=2.078n darab nem feltétlenül különböző előállítás (ez azért igaz, mert ugyan a prímek viszonylag sűrűn vannak, de a Fibonacci számok már ritkán.) Itt \epsilon>0 tetszőlegesen kicsinek választható, ha n nagy, illetve c (korlátos) konstans. Ez a becslés viszont már mutatja, hogy az állítás valószínűleg hamis lesz.

Amiben reménykedhetünk, hogy egy adott maradékosztálynál már kevés előállítás van. Itt a sűrűséget ki tudjuk számolni: Fibonacci számok m-mel vett osztási maradéka periodikus, a prímeké ugyan nem, de ott van a számtani sorozatok prímszámtétele (nagyágyú): ha gcd(r,m)=1, akkor a prímek \frac {1}{\varphi (m)}-ed részére p\equivr mod m. Ha r és m nem relatív prím, akkor legfeljebb egy ilyen prím van.

Géppel: m=34;r=17 a legkisebb jó választás! Nézzünk egy másikat amit bizonyítok: m=38;r=21, ekkor a Fibonacci számok periodikusak mod 38, és a periódus 18. Tekintsük a fibonacci(i)+p=38k+21\len megoldásszámát, ahol p prím. i mod 18 szerint nézzük az egyenletet. Ekkor az i választható \frac {\log n}{18\log (phi)}+c-nek, ha i mod 18 rögzített, akkor p\equiv21-fibonacci(i) mod 38. Számtani sorozatokra vonatkozó prímszámtételből tudjuk, hogy hány ilyen prím van n-ig.

Kapjuk a megoldásszámra (felső) becslést: \sum _{i=0}^{17} (\frac {\log n}{18\log (phi)}+c)*#(p: p\le n; p\equiv 21-fibonacci(i) mod 38)< (\frac {\log n}{18\log (phi)}+c)*\{i:i=0..17;gcd(38,21-fibonacci(i))=1\}*(1+\epsilon)*\frac {n}{\varphi(38)\log n}= (\frac {\log n}{18\log (phi)}+c)*4*(1+\epsilon)*\frac {n}{\varphi(38)\log n}<
0.0257n<\frac {n}{38}, ami kellett. (Többit az olvasóra bízom. Ezt még ki kéne rendesen epszilonozni , illetve még belevenni azon maradékosztályokat, ahol legfeljebb egy prím van, de ez már nem változtat sokat az előállítások számán.)

[690] m2mm2011-12-03 13:41:44

B. 4380. m=0 esetén n függvényében legfeljebb mennyi lehet az egyenlő hosszú szakaszok száma?

[689] Róbert Gida2011-11-15 20:16:18

Igen, de az nem derül ki belőle, hogy ez a hamis érme megnevezésére is vonatkozik-e. Egy nem ortdox érempakolással akár egy méréssel is az összes hamis érmét megtalálhatjuk.

Előzmény: [688] Fálesz Mihály, 2011-11-15 18:56:54
[688] Fálesz Mihály2011-11-15 18:56:54

A megoldás(vázlat) szövegében ez áll:

"... a véletlen választásokat tartalmazó eljárások esetén minden véletlen döntésnél előre előírhatjuk az adott választást."

Előzmény: [687] Róbert Gida, 2011-11-15 16:49:29
[687] Róbert Gida2011-11-15 16:49:29

Lejárt októberi A542. hivatalos megoldásához: a hamis érem megnevezésének is determinisztikusnak kell lennie, mert előfordulhat, hogy egyszerre több hamis érmét is találunk. Továbbá a kiegészítések igenekkel elhagyhatóak, elég annyi, hogy a játékfának max. 512 levele lesz a legfeljebb 9 kérdés után.

  [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]