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]    [46]    [47]    [48]  

Szeretnél hozzászólni? Jelentkezz be.
[72] jenei.attila2004-08-17 14:24:27

Én is a rekurzió karakterisztikus egyenletéből kaptam a zárt alakot, amelynek komplex gyökei vannak, és a komplex számok hatványozására vonatkozó Moivre képletből (azt hiszem így hívják) adódik a zárt alak. Közvetlenül felismerni pedig szerintem nagyon nehéz lenne. A Csebisev polinomokkal való összefüggést esetleg észre lehet venni, de azok koszinuszos előállítását is ismerni kell.

Előzmény: [71] Kós Géza, 2004-08-17 14:13:35
[71] Kós Géza2004-08-17 14:13:35

A nevezőből az következik, hogy an értéke sohasem lesz pontosan 1, mert soha sem lesz egész szám.

A koszinuszos alak nem igazán kerülhető ki. El lehet mondani persze a megoldást úgy, hogy csak titokban tudjuk, hogy koszinuszokról van szó, de az ugyanaz.

A kérdés inkább az, hogy mennyire lehet kitalálni a koszinuszos alakot. Aki nem ismeri fel közvetlenül, az még kezelheti a sorozatot lineáris rekurzív sorozatként is, abból is kiderül. De erről inkább valaki olyan nyilatkozzon, aki meg is oldotta a feladatot. :-)

Előzmény: [70] jenei.attila, 2004-08-17 13:39:49
[70] jenei.attila2004-08-17 13:39:49

Igaz. Ezek szerint az an=cos(n*arccos(1/3)) összefüggésből azonnal következik a feladat állítása. Az igaz, hogy a rekurzióból kiolvasható hogy an nevezője 3n, de ebből hogyan következik a feladat állítása? Van -e olyan megoldás, ami nem használja fel a koszinuszos zárt alakot?

Előzmény: [69] Kós Géza, 2004-08-17 12:57:07
[69] Kós Géza2004-08-17 12:57:07

Szia Attila,

A feladat megoldásához nem szükséges bebizonyítani, hogy {\rm arc~cos}\frac13 irracionális. Ha racionális lenne, akkor az (an) sorozatban végtelen sokszor szerepelne az 1, és az állítás akkor is igaz volna.

Abban igazad van, hogy a Csebisev-polinomok egy kis kerülőt jelentenek. A rekurzióból --- ami a feladat szövegében is szerepelt --- közvetlenül kiolvasható, hogy an nevezője 3n.

Előzmény: [68] jenei.attila, 2004-08-17 11:00:07
[68] jenei.attila2004-08-17 11:00:07

Szia Géza!

Bocs, előbb valami hiba történt.

Köszi a megoldást. Egyébként a B.3740-es feladatról volt szó, ugyanis az ott szereplő rekurzív sorozat zárt alakja: an=cos(n*arccos(1/3)). Mivel arccos(1/3) irracionális, ezért cos(n*arccos(1/3)) tetszőlegesen közel kerülhet 1-hez. Én is a csebisev polinomokra gondoltam, csak már nem emlékeztem rá, hogy a cos(n*arccos(x)) polinomban nem 1 -e a főegyüttható (de ezek szerint nem). Egyébként a feladat viszonylag ártalmatlannak néz ki ahhoz, hogy a Csebisev polinomokat kellene bevetni. Van ennek valami egyszerűbb megoldása is? Persze a rekurzióból leolvasható, hogy an=Tn(1/3), és esetleg meg sem kell említeni, hogy itt a Csebisev polinomokról van szó, mégis ha valaki nem ismeri, elég nehezen jön rá, hogy pont egy ilyen polinom sorozatot definiáljon.

Előzmény: [66] Kós Géza, 2004-08-17 08:55:37
[67] jenei.attila2004-08-17 10:57:36

Szia Géza!

Köszi a megoldást. Egyébként a B.3740-es feladatról volt szó, ugyanis az ott szereplő rekurzív sorozat zárt alakja:

Előzmény: [66] Kós Géza, 2004-08-17 08:55:37
[66] Kós Géza2004-08-17 08:55:37

A {\rm arc~cos}\frac13 szám irracionális.

Jelöljük az n-edik Csebisev polinomot Tn-nel; ez az a polinom, amelyre cos n\alpha=Tn(cos \alpha). Például T0(x)=1, T1(x)=x, T2(x)=2x2-1, T3(x)=4x3-3x.

A Tn polinomokra sok érdekes összefüggés ismert, például Tn+1(x)=2xTn(x)-Tn-1(x). Ebből a rekurzióból máris leolvasható az a két tulajdonság, amire most szükségünk lesz:

a) A Tn polinom pontosan n-edfokú és mindegyik együtthatója egész;

b) A fő együtthatója 2n-1.

Ha \alpha={\rm arc~cos}\frac13 fokban kifejezve mégis racionális lenne, akkor lenne olyan n\alpha többszöröse, ami egész és még 360 fokkal is osztható. Erre az n számra legyen Tn(x)=2n-1xn+an-1xn-1+...+a1x+a0; ekkor

3nTn(1/3)=Tn(cos \alpha)=3ncos n\alpha=3n,

2n-1+3an-1+9an-2+...+3na0=3n.

Minden tag osztható 3-mal, kivéve a 2n-1-t, ez pedig lehetetlen.

Előzmény: [65] jenei.attila, 2004-08-16 17:33:56
[65] jenei.attila2004-08-16 17:33:56

Egy KÖMAL feladattal kapcsolatban merült fel a következő kérdés: vajon arccos(1/3) fokban kifejezve irracionális -e?

[64] Káli gúla2004-07-05 12:15:08

Sziasztok! Kedves nadorp!

Az an és az 1/n harmonikus közepe helyett elég a minimumról belátni, hogy divergens. Ha A-val jelöljük azt a halmazt, ahol 1/n\leqan, akkor feltehetjük, hogy ezen az A halmazon \sum 1/n konvergens, és azt is, hogy \sum a_n divergens. Mivel an monoton és az A halmaz kicsi, ezért a \sum a_n sor az A komplementerén --ahol a \sum \min (a_n, 1/n) sorral azonos-- még inkább divergens lesz.

Előzmény: [63] nadorp, 2004-06-30 07:48:30
[63] nadorp2004-06-30 07:48:30

Sziasztok !

Ha valamilyen apró ötletet tudtok adni az A 348. feladathoz, azt nagyon megköszönném.

N.P.

[62] Pach Péter Pál2004-06-09 22:27:45

A B. 3699.-es feladat egyben a "Kavics Tanár Úr Pályázat" 2. feladata is volt. A lapban közölt megoldásnál szerintem elegánsabb megoldást olvashattok itt.

[61] Hajba Károly2004-06-04 10:45:00

Kedves Géza!

Túlzottan nem csodálkozom, hogy nem értesz mindent, mivel a fejemben sem állt még össze a kép teljesen, s a sok firkámat nem tudtam hirtelen feldolgozni, hogy érthetőbb legyen, amit gondoltam.

Hozzászólásodból kisejlik, hogyha jó is az elképzelésem, nagyon-nagyon izadtságszagú és lenne elegánsabb megoldás is.

Ha lesz egy kis időm, mindenképpen szeretnék még foglakozni vele.

Üdv: HK

Előzmény: [60] Kós Géza, 2004-06-04 10:25:03
[60] Kós Géza2004-06-04 10:25:03

Őszintén szólva, nem minden részletet értek... :-)

Az viszont biztos, hogy félreérthetően fejezhettem ki magam korábban. Én lényegében két különböző megoldást ismerek. Az egyik megoldás közvetlenül, a hurkok átrendezése nélkül bizonyítja, hogy minden hurok belseje páratlan számú négyzetből áll.

A másik megoldás a végtelen leszállás; ez minden teljesen kitöltött hurokból konstruál egy még kisebbet. (Lehetséges, hogy a paritás is kiderül, ha a megoldást kicsit ügyesebben mondjuk el.)

* * *

A feladatot a versenyben összesen ketten oldották meg, mindketten a végtelen leszállást találták meg.

Előzmény: [59] Hajba Károly, 2004-06-03 23:24:30
[59] Hajba Károly2004-06-03 23:24:30

Kedves Géza!

Míg ki nem hűl a forró nyom, folytatom. Tudom, még nem teljes, de leírom az újabb elgondolásomat, hogy legyen mire reagálva újabb információmorzsát adnod a továbblépésemhez. :o)

Ha a hurok rajzolatában találok két azonos törésvonalat úgy, hogy egy-egy törésvonal csak kétszer messe a hurkot, akkor a köztük levő idomokat és hiányokat kivéve egymáshoz illeszthetem, s egy rövidebb hurkot kapok. (Ha többször metszi, akkor az eljárás szükség szerint ismételhető.)

1) Ezen eltolás mindkét koordináta irányban csak páros lehet, mivel az azonos irányultságú idomhatároló szakaszok távolsága 2 egység többszöröse.

2) Az azonos állású szakaszok között páros számú elem lehetséges, mivel a vonallánc egyszer az egyik irányba, utána pedig a másik irányba dőlt szakaszon halad át.

3) (2)-ből következően a hurok hossza legalább 4, de mindenképpen páros egységgel csökken.

4) Két szabályosan egymáshoz illesztett idom azonos irányultságú szakaszainak felező pontjait összekötő vonal vízszintesen vagy függőlegesen két páratlan számosságú részre, míg ferdén két páros számosságú részre osztja.

5) A kivágott hurokszakasz és a törésvonalak közötti terület (1) miatt páros nagyságú; az összetartozó szakadási pontok közötti s ezzel a vonallal elvágott idomrészek területe páros (4) miatt. Így ha páros összterületből páros idomterületet levonunk, páros hiányterületet kell kapjunk.

Tehát, a fenti hurokhossz csökkentő módszerrel mindenképpen páros számmal csökken a bezárt hiány számossága.

Nos egyelőre ennyit, tudva, hogy ha ez is a jó megoldás, néhány részletet még ki kell zárni vagy megoldani.

HK

Előzmény: [58] Kós Géza, 2004-06-02 21:45:38
[58] Kós Géza2004-06-02 21:45:38

Ez már tényleg forró. :-)

Előzmény: [57] Hajba Károly, 2004-06-02 18:52:31
[57] Hajba Károly2004-06-02 18:52:31

Kedves Géza!

Talán a következők szerint már forró nyomon vagyok, de még mindig bizonyítás nélkül. (Most nem tudtam több időt erre szakítani, de ami késik nem múlik.)

Tehát a sejtésem, hogy a hurok által körbezárt lefedetlen négyzetek száma páratlan, s így mindig kell legalább egynek lennie. Gondolkodom a bizonyításán.

HK

Előzmény: [56] Kós Géza, 2004-06-02 13:14:26
[56] Kós Géza2004-06-02 13:14:26

Kedves Károly,

Az ilyen belebonyolódások elkerülésére jó a végtelen leszállás módszere. Tegyük fel, hogy mégis létezik egy olyan hurok, aminek a belsejében -- a görbedarabok által határolt részben -- nincs lefedetlen terület. Ha ki tudnánk találni egy olyan módszert, ami minden ilyen hurkot egy rövidebb hurokká alakít át, kész lenne a megoldás, mert az algoritmus még a legrövidebb huroknál is rövidebbet találna.

Visszatérve az előző próbálkozáshoz, az igaz, hogy minden hurok belsejében marad lefedetlen terület, de ennél egy kicsit erősebbet is lehet mondani. Az erősebb állítást pedig sokszor könnyebb bebizonyítani, mint a gyengébbet.

Géza

Előzmény: [55] Hajba Károly, 2004-06-02 02:22:27
[55] Hajba Károly2004-06-02 02:22:27

Kedves Géza!

Sok ötletet felvetettem, de mindegyikkel van egy kis bibi, így még nem állt össze a kép, de a legkomolyabbnak tűnőt leírom:

Ahhoz, hogy a hurokban ne legyen hiány, minden azonos szinű nem csatlakozópontú mezőnek kell lennie legalább egy sarokkal érintkező másik szomszédjának, melyen szintén átmegy ugyanaz a hurok. Tekintsünk ezek közül egy olyan párt, melynek egyik oldalán lévő hurokszakaszon nincs hiány, s nézzük meg, hogy a másik oldalon milyen továbbfolytatási lehetőségek vannak. A vizsgált elempárnak két darab csatlakozópontú szomszédja van, melyeknek ellentétes az iránya. A hurok két vonala vagy párhuzamosan megy tovább vagy szétágazik. Össze nem mehet, mivel az csak szabálytalan (átfedő) elrendezéssel lehetséges.

A széttartásnál két lehetőség van. Vagy egy hiányt kerül ki vagy egy oldalág indul és a szomszédjában visszatér a hurok. Ha ebben az oldalágban nincs hiány akkor a vizsgálati pontunkat eggyel arrább helyezhetjük, hogy az oldalág a hiánymentes oldalon legyen.

Mivel a párhuzamos folytatás nem mehet a végtelenségig és a hiánnyal nem rendelkező oldalágakat rendre áttesszük a másik oldalra, csak a hiány maradhat fenn.

Remélem nem túl zavaros így késő éjjel :o)

HK

Előzmény: [54] Kós Géza, 2004-06-01 17:35:16
[54] Kós Géza2004-06-01 17:35:16

Kedves Károly,

Nagyon jó helyen keresgélsz. A sejtésed igaz, de a hideg-forró játékban ez még nem a "forró" sejtés lenne, hanem csak a "meleg". :-)

(Nem akarok ennél többet mondani, minden segítség csökkenti a megoldás megtalálásának örömét.)

Előzmény: [53] Hajba Károly, 2004-06-01 17:07:40
[53] Hajba Károly2004-06-01 17:07:40

Kedves Géza!

Megbukott az elképzelésem, ugrott a túró rudi :o(

Talán a hurkoknál kell keresgélni? Az tiszta, hogy mindenképpen hurok keletkezik, elágazás kizárva. Így az tapasztalom, nem tudok úgy hurkot képezni, hogy ne maradjon legalább egy hiány körülzárva. Ha ezt bizonyítani tudom, akkor kész a feladat bizonyítása is. Ha jól sejtem :o)

HK

Előzmény: [52] Kós Géza, 2004-06-01 16:18:48
[52] Kós Géza2004-06-01 16:18:48

A kapcsolódási pontok egy hurkon belül azonos színűek. De ezt csak egy hurkon belül tudjuk. Előfordulhat, hogy az egyik hurokban a fehér mezők a kapcsódási pontok, egy másik hurokban pedig a feketék.

Előzmény: [51] Hajba Károly, 2004-06-01 15:50:18
[51] Hajba Károly2004-06-01 15:50:18

Kedves Géza!

Akkor pontosítok. Tehát a téglalap négy sarokpontjába csak olyan rész kerülhet, ami nem kapcsolódási pont, azaz legyen ez a sakktábla fehér szine, míg a kapcsolódási pontok helyei legyenek a fekete szinűek.

Így ha a tábla valamely oldalhossza páros, akkor ha a kezdeti sarkunk fehér és páratlan, a másik sorokba fekete színnek azaz kapcsolódási pontnak kellene esnie, ez pedig nem lehetséges. A tábla négy sarkának fehér színűnek kell lennie, ez pedig csak mindkét oldalán páratlan hosszúságú tálba esetén lehetséges. Ekkor pedig a területe páratlan és lefedettsége hiányos azaz nem lehet az idommal egy téglalapot hiánytalanul kirakni.

HK

Előzmény: [50] Kós Géza, 2004-06-01 14:29:21
[50] Kós Géza2004-06-01 14:29:21

Kedves Károly,

A láncpontok paritásáig OK. Az 5. résszel viszont nem értek teljesen egyet.

(Én a paritás helyett jobban szeretem a sakktáblaszerű színezést -- ami persze ugyanaz --, hadd színezzem inkább ki a rácsnégyzeteket pirosra és kékre, a bal alsó sarok legyen mondjuk piros.)

Ha jól értem, arra gondolsz, hogy minden csempe tartalmaz egy teljes rácsnégyzetecskét -- ennek a közepét nevezed sarokpontnak -- és két fél négyzetet. Az valóban igaz, hogy egy-egy láncon belül a ferde oldalak azonos színű mezőket vágnak ketté. A bal alsó sarkot tartalmazó hurokban tehát minden csempe egy teljes piros négyzetből és két fél kék négyzetből áll.

Ha a téglalap sarkai ugyanabban a láncban vannak, akkor működik az a gondolat, amit írtál: a téglalap mindegyik sarka piros, a téglalap területe pedig páratlan. Ha viszont a téglalap sarkai különböző hurkokhoz tartoznak, akkor lehetnek közöttük kékek is.

Előzmény: [49] Hajba Károly, 2004-06-01 10:45:05
[49] Hajba Károly2004-06-01 10:45:05

Kedves László!

Gyanítom, hogy több módon is meg lehet oldani a feladatot. Először én is a különböző továbbépítési lehetőségek ill. lehetetlenségeket kerestem, de elvesztem benne.

Utána a két átlós oldalt összekötő vonalból képzett láncokat vizsgáltam, melyből egy szakaszt bemutatok az ábrán is. Feltételeztem, hogy a kirakhatósághoz összefüggő és egy irányban haladó vonallánc kell, de nem tudtam kizárni az egyéb lehetőségeket.

Végül is arra lettem figyelmes, s ez megfelelő nagy ábrán szépen ki is jön, hogy az átlós oldalak érdekes és nagyon szabályos mintázatot adnak. Nos ebben az irányban indultam el, s talán ez visz el a megoldáshoz. Tehát:

1. Egy elem területe 2 egység, így a kirakandó téglatest legalább egyik oldalhosszának páros számúnak kell lennie.

2. A téglalap konvex, így ennek sarkában az idom az ábra szerinti bal alsó sarokban lesz és az egész értékű oldalai lesznek a vízszintes és függőleges irányban. Elképzelhető tükörkép is, de a lényegen nem változtat. Azaz kizárhatjuk a 45°-os elforgatásos eset vizsgálatát a konkáv rész miatt.

3. Az átlós oldalaknak mindig kell lennie szomszédjának, ez értelemszerűen egy másik idom átlós oldala. Tehát az átlós oldalak, mint kapcsolódási pontok egy vagy több, önmagukba visszazárt (hurok) lánccá szervezik a beillesztett idomokat. Ezen átlós szakaszok középpontját nevezzük kapcsolódási pontnak és legyen irányultsága 0 vagy 1.

4. Az idom sajátosságából következik, hogy két szomszédos láncpont koordinátakülönbsége \pm1 és irányultsága és koordinátájának paritása ellentétes. (Lásd az ábrát.)

5. Mivel sarokpont nem lehet kapcsolódási pont, olyan téglalapokat kell keresnünk, melynek sarokpontjainak paritása megegyezik. Mivel a bal alsó sarokpont paritása: páratlan-páratlan, így a páros eltolás miatt a két szomszédos sarok paritása is páratlan-páratlan, s ebből következően az átellenes sarok paritása is páratlan-páratlan. Ezen téglatest mindkét oldalhossza páratlan, így páratlan egységből áll, ezt pedig nem lehet hiány vagy többlet nélkül kirakni a 2 egység területű idomból.

HK

Előzmény: [48] lorantfy, 2004-06-01 09:01:33
[48] lorantfy2004-06-01 09:01:33

Kedves Károly és Fórumosok!

Nagyon jó kis feladat, engem érdekel! Elsőre a következő megoldás vázlatra gondoltam:

Az idom egy négyzetből és két egyenlő szárú derékszögű háromszöből áll. Nevezzük a háromszögeket röviden fogaknak. Ha az idomokból (4 elforgatott és 4 tükrözött elfogatott változat, összesen 8 féle) téglalapot akarunk kirakni, akkor nem maradhat egyedülálló fog. Minden fognak meg kell találnia a párját.

Tegyük fel, hogy már n idomot egymáshoz illesztettünk és vannak pár nélküli fogak. Azt kell belátni, hogy az n+1-dik idomot nem lehet úgy hozzáileszteni, hogy mindkét foga párt képezzen és igy csökkenjen a pár nélküli fogak száma.

Ha ezt beláttuk akkor már világos, hogy a fogak száma nem csökkenhet és igy nem rakható ki téglalat.

Az állítás belátásához hozzuk létre azt a kiegészítő felületet, amelyhez illesztve az eredeti idom mindkét foga párt tud képezni. Azt kell belátni, hogy ilyen felület nem hozható létre a 8 idom felhasználásával.

(e és f félegyenes többféle helyzetű lehet!)

Előzmény: [47] Hajba Károly, 2004-05-29 14:01:52

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