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]  

Szeretnél hozzászólni? Jelentkezz be.
[397] jenei.attila2008-06-12 10:29:26

Az előzőhöz javítás: "Figyelembe véve, hogy tn=0, azaz un=8" helyesen: Figyelembe véve, hogy t3=0, azaz u3=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.attila2008-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 2n lehetőség van a pontok kiválasztására. Össze fogjuk számolni, hogy a 2n 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 tn-nel, ekkor a keresett val.-ég \frac{t_n}{2^n}. tn+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 2tn.

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 2n-tn-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:

tn+1=2tn+2n-tn-2n=2n+tn-2n

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

un+1=2n+1-tn+1=2n-tn+2n=un+2n

Figyelembe véve, hogy tn=0, azaz un=8, kapjuk, hogy

un=n2-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] rizsesz2008-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] Sirpi2008-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 Gida2008-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] Python2008-05-18 17:56:28

Legyen PD1 felezőpontja G1, PD2 felezőpontja G2! Mivel A felezi PQ-t, AG1 középvonal PQD1 hároszögben, így AG1 párhuzamos QD1-el. Hasonlóan AG2 párhuzamos QD2-vel.

Tegyük fel, hogy QD1-merőleges PF1-re! Ekkor AG1 is merőleges PF1-re. Mivel PD1 merőleges AD1-re, így F1PD1\angle és G1AD1\angle szögek megegyeznek (merőleges szárú szögek). Így F1PD1 és G1AD1 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 PD1=2G1D1 és D1B1=2F1D1, \frac{AD_1}{PD_1}=\frac{PD_1}{B_1D_1}, ami azt jelenti, hogy AD1P és PD1B1 derékszögű háromszögek is hasonlóak. Így pl. D1PB1\angle=D1AP\angle=90o-D1PA\angle, és emiatt B1PA\angle=90o, ami azt jelenti, hogy AP a háromszög A-ból induló magassága, P a magasságtalppont B1B2-n (mivel a háromszög hegyesszögű, ez B1B2 szakaszon van).

Innen visszfelé ugyanez elmondható a másik oldalon, ami miatt teljesül a feladat állítása. (APB2\angle=90o, így AD2P és PD2B2 hasonló, mivel PAD2\angle=90o-APD2\angle=D2PB2\angle, így AD2G2 és PD2F2 is hasonló (\frac{AD_2}{PD_2}=\frac{G_2D_2}{F_2D_2} miatt), de ekkor G2AD2\angle=F2PD2\angle, és ebből, valamint PD2 és AD2 merőlegességéből következik, hogy AG2 merőleges PF2-re, így QD2 merőleges PF2-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éza2008-05-17 16:58:02
Előzmény: [390] S.Ákos, 2008-05-17 09:21:05
[390] S.Ákos2008-05-17 09:21:05

Valaki tudna mutatni egy elemi geometriai megoldást a B.4088-as feladatra?

[389] Róbert Gida2008-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] rizsesz2008-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.Ákos2008-04-16 12:20:38

helyesen: (n,a-1)\gep>1

Előzmény: [386] S.Ákos, 2008-04-16 12:19:37
[386] S.Ákos2008-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|ap-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] kdano2008-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] rizsesz2008-03-27 08:23:36

2n-1-et.

[383] rizsesz2008-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 2n/2-t.

Előzmény: [382] Róbert Gida, 2008-03-27 01:02:18
[382] Róbert Gida2008-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 Gida2008-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ó 3n darab szót tilt le W-ből, hiszen 1 pozicióra 3 lehetőség van és n pozició van, Így legfeljebb |S|*3n darab szót tudunk letiltani, aminek nagyobb vagy egyenlőnek kell lennie, mint -1+4n, hiszen ennyien vannak az n hosszú szavak, a csupa "A" nélkül. Azaz |S|*3n\geq-1+4n, 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] kdano2008-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] ik682008-03-26 13:50:06

Ha lenne valakinek egy megoldasa az A.448.-as feladatra, örömmel venném. Köszönöm!

[378] nadorp2008-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 Lajos2008-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] nadorp2008-03-21 10:20:26

A.447

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

Legyenek a1,...,an tetszőleges valós számok és b1,...,bn 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\geq0). Azt kell bizonyítani, hogy g(1)\geq0

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 bi+bj-1>-1 miatt g' integrálható a [0;1] intervallumon és a fentiek miatt g'(x)\geq0. 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] sakkmath2008-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...

[374] nadorp2008-03-16 11:30:21

A.443

Nevezzük a p kerületű hatszöget H-nak, csúcsai legyenek A,B,C,D,E,F és nevezzük az oldalfelező pontok által meghatározott hatszöget H1-nek az Fi ( i=1...6) csúcsokkal. Húzzuk be az AC,BD,...,FB átlókat. Ezen átlók metszéspontjai H belsejében egy olyan H2 hatszöget határoznak meg, melynek oldalai nyilván párhuzamosak H1 egy-egy oldalával ( melyek középvonalak), tehát H2 szögei szintén 120o-sak. Ebből következik, hogy az AEC és BDF háromszögek minden szöge 60o, tehát ezek a háromszögek szabályosak. Mivel H2 szemközti oldalai nyilván párhuzamosak is, ezért H csúcsait úgy kaphatjuk meg, hogy H2 oldalaira kifelé egy-egy szabályos háromszöget állítunk. Legyenek H2 oldalai a1,...,a6 hosszúak. Ekkor

p_1=\frac{a_1+a_2+a_3}2+\frac{a_2+a_3+a_4}2+...+
\frac{a_6+a_1+a_2}2=\frac32\sum_{i=1}^6{a_i}.

Másrészt AB=\sqrt{a_1^2+a_1a_2+a_2^2}=\sqrt{\frac{3(a_1+a_2)^2+
(a_1-a_2)^2}4}\geq\frac{\sqrt3}2(a_1+a_2)

Ha ezt elvégezzük H mindegyik oldalára akkor az kapjuk, hogy

p\geq\frac{\sqrt3}2(a_1+a_2+...+a_6+a_1)=
\sqrt3\sum_{i=1}^6{a_i}=\frac2{\sqrt3}p_1

[373] S.Ákos2008-03-15 22:15:42

A B. 4055.-ös feladatnál (Bizonyítsuk be, hogy minden n!-nál nem nagyobb pozitív egész szám felírható az n! legfeljebb n darab különböző osztójának összegeként.) elég könnyen kijön indukcióvan, h n>1 esetén n-1 db tag is elég. Az lenne a kérdésem, hogy ez mindig szükséges-e, vagy lehet tovább csökkenteni?

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