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.

[399] Káli gúla

2008-06-12 20:27:43

A. 452. Egy 2n csúcsú egyszerű gráfnak n²+1 éle van. Igazoljuk, hogy az élek legalább n háromszöget határoznak meg.

Bizonyítás. Ha n=2, akkor az állítás igaz. Tegyük fel, hogy igaz n-re, és legyen G=(V,E) egy 2n+2 csúcsú gráf n²+2n+2 éllel. Jelöljük $\delta$ (u)-val az u csúcs fokát és t(G)-vel a G-beli háromszögek számát. Legyen e=(u,v) egy olyan él, amelyre $\delta$ (u)+ $\delta$ (v)-1 minimális, és legyen a minimum értéke m.

(1) Ha m>2n+1, akkor u-nak és v-nek van közös szomszédja, vagyis e egy háromszögben van, és ugyanez igaz az összes többi élre is, hisz azok végpontjaiból is együtt legalább m él indul. Tehát G minden éle benne van egy háromszögben, ezért 3t(G) $\ge$ n²+2n+2>3(n+1).

(2) Ha m=2n+1, akkor az u, v csúcsokat és a belőlük induló 2n+1 élt elhagyva egy 2n csúcsú G₁ gráfot kapunk, amelyben n²+1 él marad, így az indukciós feltevés szerint t(G₁) $\ge$ n. Még egy háromszöget tudunk G-ben találni, vagy úgy, ha (I) akár az u, akár a v szomszédai között megy él (így u ill. v csúcsú háromszöget kapunk), vagy úgy, ha (II) u-nak és v-nek van közös szomszédja (így u, v és a közös szomszéd alkot háromszöget). E két lehetőség egyikének be kell következni, különben az u és a v csúcs szomszédai a G₁ gráf csúcsainak két színnel színezését adnák, vagyis G₁ páros gráf volna, ellentétben azzal, hogy t(G₁) $\ge$ n.

(3) Ha m<2n+1, akkor az u, v csúcsokat és a belőlük induló m élt elhagyva a kapott G₁ gráfban most legalább n²+2 él marad. Vegyünk G₁-ben az indukciós feltevés szerint létező háromszöget, és töröljük az egyik élét. Tudjuk, hogy a megmaradt n²+1 él is legalább n háromszöget határoz meg. Visszahúzva a törölt élt, megkapjuk az n+1-edik háromszöget.

[398] Káli gúla

2008-06-12 20:25:55

A. 454. Létezik-e olyan konstanstól különböző valós együtthatós p polinom, amelyre minden x valós szám esetén p²(x)-1=p(x²+1) teljesül?

Nem létezik. (1) Először lássuk be, hogy minden n>0 esetén pontosan egy n-edfokú p(x) polinom létezik, amelyre $\matrix{}{\rm deg}\big(p(x^2+1)-p^2(x)\big)<n$ . Bizonyítás. Ilyen p polinom csak a főtaggal azonos paritású x hatványokat tartalmazhat, egyébként p²(x)-ben n-nél nem kisebb páratlan kitevős tag is adódna, ami $p(x^2+1)=\sum b_{2k}x^{2k}$ miatt lehetetlen. Legyen $p(x)= \sum a_i x^{n-2i}$ , ekkor a követelmény szerint:

$\matrix{} (a_0 x^n + a_1 x^{n-2} + . . . + a_k x^{n-2k}+ . . .)^2 + R_n(x) ~=~ a_0 (x^2+1)^n + a_1 (x^2+1)^{n-2} + . . . + a_k (x^2+1)^{n-2k} + . . . ,$

ahol R_n(x) foka kisebb, mint n. Innen az a₀, a₁, . . . értékeket egymás után megkaphatjuk, ha az x²ⁿ, x^2n-2 . . . együtthatóit a két oldalon összehasonlítjuk. Így a₀=1, $a_1=\frac{n}{2}$ , $a_2=\frac{n^2}{8}$ , $a_3=\frac{n^3-16n}{48}$ . . . Általában, ha i<k indexekre már ismerjük az a_i értékeket, akkor az x^2n-2k együtthatója a bal oldalon 2a_k+ $\phi$ (a₁,...a_k-1), a jobb oldalon pedig $\psi$ (a₁,...a_k-1) lesz, ahonnan a_k egyértelműen kiszámolható.

(2) Jelöljük a fentiek miatt egyértelműen meghatározott n-edfokú polinomot H_n-nel, a maradékát R_n-nel, azaz legyen $\matrix{}H_n(x^2+1)=H_n^2(x)+R_n(x)$ , ahol deg R_n<n. Ekkor $\matrix{}H_n((x^2+1)^2+1)=H_n^2(x^2+1)+R_n(x^2+1)$ is teljesül, azaz H_2n, R_2n egyértelműsége és $\matrix{}{\rm deg~} R_n(x^2+1)<2n$ miatt azt kapjuk, hogy $\matrix{}H_{2n}(x)=H_n(x^2+1)$ és $\matrix{}R_{2n}(x)=R_n(x^2+1)$ . Tehát a kiinduló állítást elég páratlan fokú p polinomokra igazolni, hiszen $\matrix{}R_{2n}(x)\equiv -1$ -ből $\matrix{}R_{n}(x)\equiv -1$ is következne.

(3) Indirekt tegyük fel, hogy p(x) páratlan fokú és teljesül rá a $\matrix{}p^2(x)-1= p(x^2+1)$ azonosság. Írjuk át ezt a $\matrix{}q_1(t)=t^2+1$ és $\matrix{}q_2(t)=t^2-1$ jelölésekkel $\matrix{}q_2\circ p=p\circ q_1$ alakba. Teljes indukcióval (a q-kat egymás után "áthúzva" p-n) azonnal adódik, hogy

$\matrix{}q_2^{(k)}\circ p = p\circ q_1^{(k)}$

Vizsgáljuk a két oldalt az x=0 helyen k $\to$ $\infty$ esetén! A jobb oldalon q₁^(k)(0) $\ge$ k, hiszen indukcióval $\matrix{}q_1^{(k+1)}(0)=\big[q_1^{(k)}(0)\big]^2+1 \ge k+1$ , ezért $\lim_{k\to\infty} p\circ q_1^{(k)} (0) =\infty$ . A bizonyítás elején tett megjegyzés szerint p(0)=0, mert p minden tagja páratlan fokú, ezért a bal oldal x=0-ban egy kettő hosszúságú ciklusba van zárva, vagy 0, vagy -1, mert $\matrix{}q_2(0)=-1$ és $\matrix{}q_2(-1)=0$ . Ez az ellentmondás igazolja az állítást.

Megjegyzés. Ugyanígy látható be, hogy a $\matrix{}p^2(x)-2= p(x^2+1)$ azonosság sem teljesülhet semmilyen p polinomra, csak ekkor az utolsó képlet bal oldalán a q₂(t)=t²-2 polinom iteráltjai nem oszcillálnak, hanem azonosan 2 értékűek a 0 helyen, de ez is lehetetlen végtelenbe tartó jobb oldal mellett.

[397] jenei.attila

2008-06-12 10:29:26

Az előzőhöz javítás: "Figyelembe véve, hogy t_n=0, azaz u_n=8" helyesen: Figyelembe véve, hogy t₃=0, azaz u₃=8.

A 2.a.) ponthoz kiegészítés: itt azt állítom, hogy a PP' átmérő pontosan akkor döfi át a maradék n pont által meghatározott konvex burkot, ha az n pont husszúsági koordinátáiból az egyenlítő mentén képződő n oldalú sokszög tartalmazza a gömb középpontját. Elég ezt belátni n=3 esetén, ugyanis ha PP' átdöfi a burkot, akkor az n pontból kiválasztható 3, amelyek által alkotott háromszöglemezt szintén átdöf. Fordítva, ha ilyen háromszöhlemezt átdöf, akkor a burkot is. Mindez a konvex burok tulajdonsága miatt van így. Ha pedig egy háromszög lemezt átdöf az átmérő, akkor nyilván a három pont hosszúsági koordinátáiból az egyenlítő mentén képződő háromszög tartalmazza a gömb középpontját. Ez esetben maga az egyenlítő mentén keletkező n szög is tartalmazza a gömb középpontját. Továbbá az is világos, hogy a szóbanforgó 3 ponthoz hozzávéve vagy a P, vagy a P' pontot, a keletkező tetraéderek pontosan egyike fogja tartalmazni a gömb középpontját, hiszen a három pontból, és a P és P'-ből álló 5 pontú konvex burok teljes egészében tartalmazza a PP' átmérőt (és ezzel együtt a gömb kp.-ját is).

[396] jenei.attila

2008-06-11 22:32:35

Az A.453 feladatra írok egy megoldást. A gömbfelületen egymástól függetlenül véletlenszerűen kiválasztunk n pontot. Mi a val.-ge, hogy a kiválasztott pontok konvex burka tartalmazza a gömb középpontját?

Megoldás: Válasszuk ki a pontokat a következőképpen. Először adjunk meg n véletlenszerűen választott átmérőt. Egy átmérő a gömbfelületet két pontban döfi, amelyek egyikét választjuk pontként. Így az átmérők kijelölése után 2ⁿ lehetőség van a pontok kiválasztására. Össze fogjuk számolni, hogy a 2ⁿ lehetőségből hány olyan van, amikor a kiválasztott pontok konvex burka tartalmazza a gömb középpontját (mint látni fogjuk, ez független az átmérők helyzetétől). Jelöljük ezt t_n-nel, ekkor a keresett val.-ég $\frac{t_n}{2^n}$ . t_n+1-re egy rekurzív összefüggést adunk meg. Jelöljük ki az egyik átmérőt (PP'), és vizsgáljuk ennek, valamint a maradék n pont által meghatározott konvex buroknak a helyzetét. Három esetet különböztetünk meg:

1.) A maradék n pont konvex burka tartalmazza a gömb középpontját.

2.a.) A maradék n pont konvex burka nem tartalmazza a gömb középpontját, és nincs közös pontja a PP' átmérővel.

2.b.) A maradék n pont konvex burka nem tartalmazza a gömb középpontját, de a PP' átmérő döfi a burkot.

Az 1.) esetben akár a P, akár a P' potot választjuk a már kiválasztott n pont mellé, az új konvex burok szintén tartalmazni fogja a gömb kp.-ját. Tehát az ebből adódó kedvező esetek száma 2t_n.

A 2.a.) eset akkor állhat fenn, ha a maradék n pont "hosszúsági koordinátáiból" az egyenlítő mentén keletkező n oldalú sokszög nem tartalmazza a gömb kp.-ját (PP'-őt tekintjük forgástengelynek, az erre merőleges főkör az egyenlítő). Tehát meg kell oldani az analóg síkbeli feladatot: a körben véletlenszerűen kiválasztva n átmérőt, majd az egyes átmérők egyik végpontját kijelölve, hány esetben nem fogja tartalmazni a kör kp.-ját a kijelölt pontokból álló n oldalú sokszög (vagyis mikor esnek egy félkörre)? Erre a válasz 2n, ami könnyen belátható. Tehát a 2.a.) pontnak megfelelő esetek száma 2n. Ezen esetekben a P vagy P' hozzávételekor keletkező konvex burok sem tatalmazza a gömb kp.-ját.

A 2.b.) esetek száma nyilván az összes esetek száma - 1.)esetek száma - 2.a.) esetek száma, vagyis 2ⁿ-t_n-2n. A 2.b.) esetben, azonban a P vagy P' (kizáró vagy) hozzávételével a keletkező konvex burok tartalmazni fogja a gömb kp.-ját, hiszen PP' átdöfi a maradék konvex burkot. Tehát az összes kedvező esetek száma:

t_n+1=2t_n+2ⁿ-t_n-2n=2ⁿ+t_n-2n

. Ezzel a feladat tulajdonképpen meg van oldva, már csak a t_n-re adunk egy zárt képletet. Legyen u_n:=2ⁿ-t_n, vagyis azon esetek száma, amikor a konvex burok nem tartalmazza a gömb kp.-ját. Tehát

u_n+1=2ⁿ⁺¹-t_n+1=2ⁿ-t_n+2n=u_n+2n

Figyelembe véve, hogy t_n=0, azaz u_n=8, kapjuk, hogy

u_n=n²-n+2

. Vagyis a feladatra a válasz:

$1-\frac{n^2-n+2}{2^n}$

annak a valószínűsége, hogy a gömb kp-ja benne lesz a véletlenszerűen választott n pont által meghatározott konvex burokban.

[395] rizsesz	2008-05-26 09:58:57
Egyszerűen nem kell reagálni a hozzászólásaira, a feladataira, azt hiszem ez a legegyszerűbb megoldás.
Előzmény: [394] Sirpi, 2008-05-26 08:35:33

[394] Sirpi	2008-05-26 08:35:33
Ha gondolkodtál volna kicsit, mielőtt megint fröcsögsz, akkor rájöttél volna, hogy a feladat nincs elszúrva. Senki nem mondta, hogy minden N-re kell lennie ilyen színezésnek. Ha nincs, akkor arra az N-re az állítás üres. A stílusod viszont nem nagyon fejlődik...
Előzmény: [393] Róbert Gida, 2008-05-26 00:58:52

[393] Róbert Gida

2008-05-26 00:58:52

"A.448. helyett új példát tűztek ki."

No igen. De ezt is sikerült elszúrniuk: "A. 448. Az 1,2,...,N számokat kiszíneztük 3 színnel úgy, hogy mindegyik szín legfeljebb $\frac{N}{2}$ -ször szerepel."

N=1-re egy lehetséges színezést azért megnéznék...

Előzmény: [389] Róbert Gida, 2008-05-08 16:58:43

[392] Python	2008-05-18 17:56:28
Legyen PD₁ felezőpontja G₁, PD₂ felezőpontja G₂! Mivel A felezi PQ-t, AG₁ középvonal PQD₁ hároszögben, így AG₁ párhuzamos QD₁-el. Hasonlóan AG₂ párhuzamos QD₂-vel. Tegyük fel, hogy QD₁-merőleges PF₁-re! Ekkor AG₁ is merőleges PF₁-re. Mivel PD₁ merőleges AD₁-re, így F₁PD₁ $\angle$ és G₁AD₁ $\angle$ szögek megegyeznek (merőleges szárú szögek). Így F₁PD₁ és G₁AD₁ háromszögek hasonlóak, mivel a szögeik megegyeznek. Így $\frac{AD_1}{PD_1}=\frac{G_1D_1}{F_1D_1}$ , de így, mivel PD₁=2G₁D₁ és D₁B₁=2F₁D₁, $\frac{AD_1}{PD_1}=\frac{PD_1}{B_1D_1}$ , ami azt jelenti, hogy AD₁P és PD₁B₁ derékszögű háromszögek is hasonlóak. Így pl. D₁PB₁ $\angle$ =D₁AP $\angle$ =90^o-D₁PA $\angle$ , és emiatt B₁PA $\angle$ =90^o, ami azt jelenti, hogy AP a háromszög A-ból induló magassága, P a magasságtalppont B₁B₂-n (mivel a háromszög hegyesszögű, ez B₁B₂ szakaszon van). Innen visszfelé ugyanez elmondható a másik oldalon, ami miatt teljesül a feladat állítása. (APB₂ $\angle$ =90^o, így AD₂P és PD₂B₂ hasonló, mivel PAD₂ $\angle$ =90^o-APD₂ $\angle$ =D₂PB₂ $\angle$ , így AD₂G₂ és PD₂F₂ is hasonló ( $\frac{AD_2}{PD_2}=\frac{G_2D_2}{F_2D_2}$ miatt), de ekkor G₂AD₂ $\angle$ =F₂PD₂ $\angle$ , és ebből, valamint PD₂ és AD₂ merőlegességéből következik, hogy AG₂ merőleges PF₂-re, így QD₂ merőleges PF₂-re, és ezt kellett igazolni.) A lényeg az, hogy ha van két hasonló háromszögünk, és mindkettőt "félbevágjuk" egymásnak megfelelő csúcsaikból induló súlyvonalakkal, akkor a megfelelő részháromszögek is hasonlóak lesznek. Ezt itt csak derékszögű háromszögekre igazoltam és használtam fel.

Előzmény: [390] S.Ákos, 2008-05-17 09:21:05

[391] BohnerGéza	2008-05-17 16:58:02


Előzmény: [390] S.Ákos, 2008-05-17 09:21:05

[390] S.Ákos	2008-05-17 09:21:05
Valaki tudna mutatni egy elemi geometriai megoldást a B.4088-as feladatra?

[389] Róbert Gida	2008-05-08 16:58:43
A.448. helyett új példát tűztek ki.
Előzmény: [382] Róbert Gida, 2008-03-27 01:02:18

[388] rizsesz

2008-04-16 14:22:44

Nagyon szép megoldás, kedves Ákos (bár eléggé adta magát a kis Fermat-tétel :)).

Néhány gondolat amúgy eszembe jutott a kitűzött K problémákkal kapcsolatban.

A K. 167. ugyanabba a hibába esik, mint a K. 90.

Azt kérte ott ugyanis a feladat, hogy adjunk meg minél több megoldást, míg maximális pont arra járt, ha igazoltad, hogy két megoldás van és nincsen több. Érdemes lenne ezt a javítóknak most is figyelembe venni, és ilyen hibába nem beleesni újra.

A másik a K. 168. Ennek második része pedig már korábban tárgyalt B feladat (azt hiszem 2002 - 2003 májusi). Ez persze nem először fordul elő, de úgy gondolom, hogy ilyenekre érdemes lenne ügyelni.

Üdv, rizs

[387] S.Ákos	2008-04-16 12:20:38
helyesen: (n,a-1) $\ge$ p>1
Előzmény: [386] S.Ákos, 2008-04-16 12:19:37

[386] S.Ákos

2008-04-16 12:19:37

B.4078. Legyen p n legkisebb prímosztója, k pedig a rendje mod p. Ekkor a feltételek alapján (i) (p,a)=1 (ii)k|n és (iii)k<p (ez a Kis-Fermat tételből és (i)-ből következik, mivel ekkor p|a^p-1-1). Mivel p n legkisebb prímosztója, így a [2;p-1] intervallumban nem oszthatja egy szám sem, mivel ez ellentmondana p minimalitásának. $\implies$ k=1, így p|a-1 $\implies$ (a-1,n)=p>1

[385] kdano	2008-03-30 23:06:35
Ez sem igaz. Laci n=5-ig küldött ellenpéldát. n=8-tól viszont már igaz az állítás.
Előzmény: [383] rizsesz, 2008-03-27 08:23:15

[384] rizsesz	2008-03-27 08:23:36
2ⁿ-1-et.

[383] rizsesz	2008-03-27 08:23:15
de n>3-ra már jó, csak akkor nem A-nak való ez a feladat. (bár lehet, hogy van olyan konstrukció, ami még jobban szűkíti a 2ⁿ/2-t.
Előzmény: [382] Róbert Gida, 2008-03-27 01:02:18

[382] Róbert Gida

2008-03-27 01:02:18

Javítás: rossz volt az ellenpélda:

n=1-re: S=A, teljesíti a feltételeket, de |S|=1<3*1, ellentmondás. Megjegyzem, hogy n=1 esetén S más nem is lehet, hogy teljesítse a feltételeket, az |S|=3 álom.

n=2-re: a legkisebb S ellenpélda: S=AA,AB,BA, erre |S|=3<2*3, ellentmondás.

n=3-ra egy ellenpélda (lehet, hogy nem a legkisebb): S=AAA,AAB,ABA,ABB,BAA,BAB,BBA (látszik a minta?), itt |S|=7<3*3, ellentmondás.

Sokat nem foglalkozott a példával a kitűző, vagy csak sajtóhiba. Ezt gondolom a Fazekasban egyből kiszúrták.

Előzmény: [381] Róbert Gida, 2008-03-27 00:39:19

[381] Róbert Gida

2008-03-27 00:39:19

A.448

AHA, igazad van. Ilyen rossz feladatot régen olvastam. n=1-re biztosan nem igaz: Legyen S="B","C" ez teljesíti a feltételeket, de |S|=2<3, ellentmondás.

Egyébként amit én kb. 5 perc alatt találtam: n>12-re az állítás biztosan igaz! Sőt az alsó korlát ultragyenge. Ok: 1 darab n hosszú S-beli szó 3ⁿ darab szót tilt le W-ből, hiszen 1 pozicióra 3 lehetőség van és n pozició van, Így legfeljebb |S|*3ⁿ darab szót tudunk letiltani, aminek nagyobb vagy egyenlőnek kell lennie, mint -1+4ⁿ, hiszen ennyien vannak az n hosszú szavak, a csupa "A" nélkül. Azaz |S|*3ⁿ $\geq$ -1+4ⁿ, tehát $|S|\geq \frac {4^n-1}{3^n}$ . Ez pedig n>12-re indukcióval belátható, hogy legalább 3*n, ami kellettt, sőt a becslés szerint S-nek exponenciálisan sok eleme van, így a feladat lineáris becslése nudli.

Előzmény: [380] kdano, 2008-03-26 21:21:43

[380] kdano	2008-03-26 21:21:43
Annak a feladatnak az állítása nem igaz..
Előzmény: [379] ik68, 2008-03-26 13:50:06

[379] ik68	2008-03-26 13:50:06
Ha lenne valakinek egy megoldasa az A.448.-as feladatra, örömmel venném. Köszönöm!

[378] nadorp	2008-03-21 15:26:41
Igaz. A vége nem kell, elbonyolítottam.
Előzmény: [377] Lóczi Lajos, 2008-03-21 14:28:20

[377] Lóczi Lajos	2008-03-21 14:28:20
De miért kell integrálra hivatkozni? Nem elég az, hogy ha egy függvény deriváltja nemnegatív, akkor a függvény nemcsökkenő?
Előzmény: [376] nadorp, 2008-03-21 10:20:26

[376] nadorp

2008-03-21 10:20:26

A.447

A feladat következő általánosítását bizonyítjuk be:

Legyenek a₁,...,a_n tetszőleges valós számok és b₁,...,b_n tetszőleges pozitív valós számok. Ekkor $\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{a_ia_j}{b_i+b_j}\geq0$ Bizonyítás:

Legyen $g(x)=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{a_ia_j}{b_i+b_j} x^{b_i+b_j}$ (x $\geq$ 0). Azt kell bizonyítani, hogy g(1) $\geq$ 0

Nyilván g(0)=0. Továbbá a függvény deriváltjára

g^'(x) $=\sum_{i=1}^{n}\sum_{j=1}^{n}a_ia_jx^{b_i+b_j-1}= \frac1x\sum_{i=1}^{n}\sum_{j=1}^{n}(a_ix^{b_i})(a_jx^{b_j})= \frac1x\left(\sum_{i_1}^{n}a_ix^{b_i}\right)^2$

Mivel $\alpha$ >-1 esetén $\int_0^1x^\alpha dx$ létezik , ezért b_i+b_j-1>-1 miatt g^' integrálható a [0;1] intervallumon és a fentiek miatt g^'(x) $\geq$ 0. Tehát

$g(1)=g(1)-g(0)=\int_0^1g^{'}(x)dx\geq0$ , hiszen nemnegatív függvény integrálja is nemnegatív.

[375] sakkmath	2008-03-18 17:16:02
A B. 4056. feladat itt olvasható rapid megoldásával kapcsolatban megjegyzem, hogy létezik tisztán elemi geometriai megoldás is, amely - esetleg - érdekesebb fordulatokat ígér...

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