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: Érdekes matekfeladatok

  [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]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]  

Szeretnél hozzászólni? Jelentkezz be.
[2652] Sirpi2008-05-19 10:47:20

A rendes 13-as totón a pontosan k találat darabszáma:

\binom {13}k \cdot 2^{13-k}

Hiszen kiválasztjuk azt a k meccset, amit eltalálunk, azok kitöltése egyértelmű, a többinél pedig mindenhol 2 lehetőségünk van, hogy oda rosszat írjunk. Ha fix meccsek is vannak, akkor a képletben mindkét 13-ast cseréld ki tetszőleges kisebb számra (mondjuk az nem teljesen világos, hogy a fix találatokat miért nem számolod a találatok közé, mert azt írod, hogy 12-ből maximum 12 találatod lehet, de mivel így szeretnéd értelmezni, ennek megfelelően adtam meg a képletet).

Előzmény: [2651] Lajosz, 2008-05-19 10:40:06
[2651] Lajosz2008-05-19 10:40:06

Ismétléses variáció:

A totón, ha minden esetet megjátszunk, (3 a 13-on ), mennyi 0, 1, 2,...11, 12, 13. találatunk lesz, hogyan kell kiszámítani?

Ugyanezt hogyan számítjuk, ha 1 fix mérkőzés mellett (3 a 12-en) eredményt megjátszunk, mennyi 0, 1, 2,...11, 12. találatunk lesz?

etc...

[2650] Róbert Gida2008-05-16 12:57:13

Ez lényegében meg Lajos eredeti konstrukciója, csak tekergetések nélül megoldva, de az is 2/3-os megvalósítás.

Előzmény: [2649] Sirpi, 2008-05-16 01:37:44
[2648] Sirpi2008-05-16 02:27:20

És hogy ez miért optimális:

A közlekedőutat tekintsük egy gráfnak (a csúcsok az üres mezők, az élek az élszomszédos mezőket kötik össze). Erről a gráfról kell belátni, hogy ha nem is mindig összefüggő, de néhány autó átpakolásával mindig azzá tehető. Hiszen ha van út, ami nincs összeköttetésben a bal felső sarokkal (az ábrán a sárga tartomány), akkor az annyit jelent, hogy egy vagy több autó blokkolja az utat a bal felső sarokig. Vegyünk egy ilyen autót (piros), és toljunk rajta egyet, rá a belső útra (kék helyzet). Az autó az új helyzetében nem blokkolhat másik autót, hiszen az autók hiába hajtanak a belső útra, onnan nem tudnak kijutni, csak ha az eredeti helyükre visszamennek, tehát a kék mező érintése nélkül is ki tudnak jutni, ha eddig ki tudtak. A kék autó pedig szintén kijut (egyet előremegy, és onnan már a feltételezésünk szerint kijut). Ezzel a tolással a belső út hossza 1-gyel csökkent, így ilyen lépések véges sorozatával felszámolható az összes belső út (jelen esetben a kék autót még 1-gyel lejjebb tolva a belső út összekapcsolódik a "fő" úthálózattal, vagyis több lépésre nincs is szükség).

Így a továbbiakban feltehető, hogy a közlekedőutak hálózata összefüggő, álljon k mezőből. Ekkor legalább k-1 belső kapcsolódása van (az összefüggő gráfnak legalább k-1 éle van). Minden belső kapcsolódás 2-vel csökkenti a közlekedőhálózat kerületét, tehát az összkerület legfeljebb 4k-2(k-1)=2k+2. Minden él a kerületen egy autónak ad lehetőséget, hogy felhajtson az úthálózatra, és így eljusson a bal felső sarokba (egy autó több élen át is megteheti ezt). Sőt, a bal felső mező két sarokéle nem segít egy autónak sem, vagyis legfeljebb 2k autó lehetséges k mezőből álló úthálózat esetén. Tehát a mezők számának legfeljebb 2/3-án lehetnek autók, és ez az arány aszimptotikusan (az előző hsz. ábrája alapján) el is érhető.

Megj.: Sőt, az út "meglátogatja" a másik 3 sarkot is, hiszen egy sarok és két szomszédja közül nem állhat mind a 3-on autó, vagyis k mezőből álló úthálózat esetén legfeljebb 2k-3 autó lehetséges (hiszen minden határélnél vesztünk egy autót) - feltéve, hogy a parkoló mindkét oldalának hossza legalább 4, mert ilyenkor a sarkokkal szomszédos mezők nem eshetnek egybe.

Előzmény: [2649] Sirpi, 2008-05-16 01:37:44
[2649] Sirpi2008-05-16 01:37:44

Ez a konstrukció pedig 2/3-os (66,67%) határértéket ad, ráadásul elég egyszerű is, nem kell mozaikba pakolni (bár épp azt is lehet).

Előzmény: [2647] Sirpi, 2008-05-16 01:18:30
[2647] Sirpi2008-05-16 01:18:30

Nem kell azt az egy autót se kitörölni, kis átszervezéssel elérhető a 28/49\approx57,143%. Viszont 6×6-asra tudtam egy kicsit jobbat is csinálni, csak a bal felső (pirosra festett) autót kell kiszedni. De egyetlen autó kivétele nem befolyásolja a határértéket, ami jelen esetben 21/36\approx58,333%.

Ja, és a határszám megtalálásához nem kell feltétlenül négyzet alakú területeket használni, ha esetleg egy téglalap jobb eredményt ad.

Előzmény: [2646] Róbert Gida, 2008-05-15 23:35:28
[2646] Róbert Gida2008-05-15 23:35:28

Szerintem nem adható rá explicit képlet tetszőleges n-re. Programozási versenyen volt egy hasonló példa axb-es téglalapra, de úgy, hogy alul és felül is ki lehet jutni, gyakorlatilag végignézték az összes esetet a megoldásoknál.

Ha az első ábrában a hatodik sor első pozicióján nem autó van, és ilyen 7x7-es blokkokat rakunk egymásra, akkor tetszőleges autó fel tud jutni a legfelső sorba. Ha a nagy négyzet felső sorából töröljük az autókat, így már mindenki kijut, ez (7k)x(7k)-asra müködik, ha n nem ilyen alakú, akkor legyen k=floor(n/7). Az autók száma aszimptotikusan \frac{28-1}{49}n^2=\frac{27}{49}n^2.

Felső becslés pedig: egy autónak van van legalább egy nem autó szomszédja, hogy esélye legyen kijutni (kivéve, ha n=1 és 1 autó van az ábrán), továbbá egy nem autó hely maximum 3 autónak lehet szomszédja, ami kijutásra használja, ellenben minden szomszéd autó, de akkor nem tudna kijutni, ha odamenne. Így #autó<=3*#nemautó, azaz

#auto<=3*(n2-#auto), innen \frac{#auto}{n^2}\leq \frac 34 teljesül, ha n>1.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46
[2645] Sirpi2008-05-15 22:39:14

Szerintem ezt a négyzetfelosztást mindig meg lehet csinálni akkor is, ha a két kis négyzet (egész) oldalhosszát előírjuk (a és b). Hiszen ekkor egy ab(a2+b2) oldalhosszú négyzet biztos kitölthető, méghozzá úgy, hogy a felső részében vannak az a oldalhosszú kis négyzetek (b(a2+b2a db.), alatta pedig a b oldalúak (a(a2+b2b db.). Sőt, gyakran kevesebb is elég lehet, pl. ha a és b nem relatív prím. Viszont azt nem tudom, hogy ennél kevésbé rendezett megoldások is vannak-e kisebb elemszámmal.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46
[2644] jonas2008-05-15 22:23:31

A négyzetes nem nehéz.

Egyszerűen választunk egy (s,a,x) számhármast, amelyre 1<s,x és 0<x<a2, és a2-x=s2x. Ezután egy nagy négyzetet felosztunk a2 közepes négyzetre, majd x darab közepes négyzetet egyenként s2 darab kis négyzetre.

Több megfelelő számhármas is van, az ábra a (2,5,5)-nek megfelelő megoldást mutatja, de jó például a (2,10,20),(3,10,10),(7,10,2),(2,15,45),(4,17,17),(2,20,80),(3,20,40),... is.

Ha 4s2\lex, akkor megtehetjük azt is, hogy egy (vagu több) közepes négyzetet kis négyzetek közé fáziseltolással csempészünk be, ahogy a második ábra mutatja.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46
[2643] Lóczi Lajos2008-05-15 21:51:46

Hát akkor tűzzük ki :) Az is érdekes kérdés, hogy határértékben mi a fekete/fehér kockák aránya, az optimális esetben, ha a négyzetrács mérete végtelenhez tart. Amúgy ezt a feladatot idén adták fel orosz 6.-osoknak, egy olimpiai előkészítőn. A közölt megoldás is 28-at ad meg (egyébként Python ábráján a jobb szélsőt), persze nem bizonyítja az optimalitást. (A feladat pontozása érdekes: aki 25 autót rak be, 1 pontot kap, ezen felül viszont minden újabb autó plusz 2 pontot ér :-)

A másik, hasonlóan érdekes feladat: osszunk fel egy négyzetet kétféle méretű négyzetre, úgy, hogy a két fajtából egyforma számú darab szerepel. Kíváncsi vagyok, hogy van-e lényegében másfajta elrendezés, mint amit közöltek.

(A többi 4 feladat triviális volt ezekhez képest.)

Előzmény: [2642] Python, 2008-05-15 19:55:25
[2642] Python2008-05-15 19:55:25

A 28 nálam is megvan és szerintem nincs ennél jobb, mivel elég sokat szórakoztam, és 28-at többfélét találtam, de annál jobbat nem (3 példányt felteszek ábrában). Érdekes lenne a feladatot általánosabban is kitűzn, tehát n×n-es parkolóra.

Előzmény: [2640] Káli gúla, 2008-05-15 14:50:44
[2641] Róbert Gida2008-05-15 16:48:03

Jók a számok. Lehet találni egy formulát, ami ilyen számokat állít elő, feltéve, hogy néhány szám prím a formulában. Ez hasonló a Carmichael számokat gyártó képlethez, ami persze nem véletlen, hiszen ahogy írtad ezek mind azok. Ha egy ikerprím sejtéshez hasonló sejtés igaz, akkor máris végtelen sok ilyen szám van.

Előzmény: [2638] Enkidu, 2008-05-15 12:41:43
[2640] Káli gúla2008-05-15 14:50:44

1-et tudtam javítani (27 -> 28), nem tudom, lehet-e jobbat csinálni.

Előzmény: [2639] Sirpi, 2008-05-15 13:06:23
[2639] Sirpi2008-05-15 13:06:23

A példaábrához képest (ami elsőre optimálisnak tűnt számomra) 3-at tudtam javítani (24 -> 27), nem tudom, lehet-e jobbat csinálni.

Előzmény: [2637] Lóczi Lajos, 2008-05-13 12:14:17
[2638] Enkidu2008-05-15 12:41:43

Ha jól számoltam az első két szám: 1729 és 2465 (a harmadik a 15841). A "bizonyításom" egy program, ami végigfut a Carmichael-számokon (csak ilyenek lehetnek a feladatban kitűzött számok).

Hogy miért éppen a Carmichael-számok?! Azok az n számok, melyekre minden lnko(a,n) = 1 esetén an-1\equiv1(modn) azok éppen a prímek és a Carmichael-számok. Prímek esetén viszont van olyan a<n, amely primitív gyök, erre az a-ra nem teljesülhet a feladatban kitűzött egyenlőség.

Most hirtelenjében csak azokon a számokon fut a progi, amik beleférnek a szabvány 16-bites (max 32000) egész szám fogalmába. Arra nem merek tippelni, hogy véges, vagy végtelen sok ilyen szám van.

Üdv!

Előzmény: [2633] Róbert Gida, 2008-04-28 19:11:45
[2637] Lóczi Lajos2008-05-13 12:14:17

Egy 7x7-es autóparkolóba legfeljebb hány darab autót helyezhetünk el, ha azt akarjuk, hogy bármelyik ki tudjon jönni a többitől függetlenül? (A kijárat bal fölül van, és egyszerre mindig csak 1 autó mozog. 1 autó 1 teljes négyzetet foglal el és csak a négyzetrács mentén mozoghatnak függőlegesen vagy vízszintesen.)

[2636] Róbert Gida2008-05-12 02:06:51

Ah, megvan a pontos érték: 1-\frac {\Pi ^2}{12} Érdemes felbontani az integrált y<x és y>x részekre. Mivel az integrálandó x,y-ban szimmetrikus ezért elég az egyiket kiszámolni, például y<x-et, ekkor az egyik tag persze: frac(y/x)=y/x, a másik miatt viszont a [0,x] intervallumot fel kell osztani. Végén kapunk egy kellemes szummát, amit egy apró trükkel lehet explicit alakban felírni. Bár a \Pi2 gondolom így sokat segít.

Előzmény: [2635] Róbert Gida, 2008-05-12 01:35:06
[2635] Róbert Gida2008-05-12 01:35:06

Ha valaki ki akarná számolni: Monte Carlo módszere kb. 0.177-et ad az integrálra, 1 millió pontot használva az egységnégyzetből, ez így kb. 1/sqrt(1000000)=1/1000-ed pontosságot jelent.

Előzmény: [2634] Gyöngyő, 2008-05-12 00:58:33
[2634] Gyöngyő2008-05-12 00:58:33

Mennyi a következő integrál értéke: Ahol a kapcsos zárójel törtrészt jelent:


\int_0^{1} \int_{0}^{1} \left\{ \frac{x}{y} \right\} \left\{ \frac{y}{x} \right\} dx dy

Üdv.: Zsolt

[2633] Róbert Gida2008-04-28 19:11:45

Találjuk meg a két legkisebb pozitív egész 1-nél nagyobb páratlan N számot, melyre teljesül, hogy: minden lnko(a,N)=1 esetén a^{\frac {N-1}{2}}\equiv 1 mod N teljesül! Mi a sejtésünk: végtelen vagy véges sok ilyen N szám van?

[2632] Róbert Gida2008-04-28 18:32:20

Fazekas felvételi feladatsora a 6 osztályos spec. mat. tagozatra.

[2631] Róbert Gida2008-04-27 00:52:00

Egy megoldás rá: Legyen s=a1+an rögzített, ekkor, ha s fix, akkor a jobb oldal is fix. De mi lesz a bal oldal maximuma (rögzített s esetén)? Legyen x=a2...ak és y=an-k+1...an-2, a bal oldalon elég az első és utolsó tagot nézni:

max(a1*x+y*an)=max(x,y)*s, ha s=a1+an, és a maximum felvétetik olyan helyen (is), ahol a1=0 vagy an=0, ezt beírva az eredeti feladatot kapjuk meg csak n tag helyett (n-1) taggal. Azaz leszállhatunk, egészen n=k-ig, ami a triviális eset, hiszen ez éppen a számtani-mértani egyenlőtlenség.

Egyenlőség viszont sokféleképpen lehet, például k=1-nél mindig egyenlőség van. n=3,k=2-nél pontosan akkor, ha a1-a2+a3=0

Előzmény: [2630] Gyöngyő, 2008-04-26 22:06:26
[2630] Gyöngyő2008-04-26 22:06:26

Szisztok!

Legyen k és n pozitiv egészek és k=<n, és legyen a1,a2,...an nemnegativ valós számok. Bizonyítsuk be,hogy


a_1a_2...a_k + a_2a_3....a_{k+1} + ... + a_{n-k+1}a_{n-k+2}...a_{n} \leq \left(\frac{a_1 + a_2 + ... +a_n}{k}\right)^k

[2629] Ratkó Éva2008-04-21 13:16:07

Kedves CD iránt érdeklő és tájékozott fórumozók! Az, hogy a KöMaL eltűnt a sulinet honlapról, sajnos nem a mi hatáskörünk: higgyétek el, mi is azt szeretnénk, ha még mindig ott lenne. Volt velük egy ötéves szerződésünk, melyet a lejárta után nem óhajtottak megújítani, és jelenleg is ez az állapot áll fenn. Valóban, szkennelt formában elérhetőek a számok a mi honlapunkon, teljesen ingyen. (Itt egy másik oldal is, ahol elérhetők, méghozzá oldalanként: db.komal.hu/scan ) Ahhoz, hogy a) vagy egy hasonlóan működő honlapot gyártsunk b) a CD-t frissítsük vagy internetes vagy új CD-kiadás formájában, egy jó programra és ehhez pénzre van szükségünk. A HEFOP pályázat arról szólt, hogy adatokkal feltöltjük az adatbázisunkat.

Egyébként a pályázatnak 2006 decemberében vége volt, azóta még nem kaptuk meg az általunk kifizetett pénz 20%-át. Tehát adott egy egész szépen feltöltött adatbázis, amivel még 2 teendő van - ez folyik most- : 1.) a szöveghez az ábrákat bevinni - ezt elkezdték, de nem fejezték be - 2.) ellenőrizni kell, hogy tényleg jók-e a bevitt szövegek - ugyanis az adatbevitelkor sok hiba keletkezhetett.

Valóban eladtunk kb. 500 Cd-t, ebből számoljátok ki hány ember fizetése (minimálbér) finanszírozható!? Hány hónapig? (persze a CD nyomása és elkészítése és az azt működtető valóban nem egészen felhasználóbarát program megíratása sem volt ingyen - amúgy épp ezért szándékoznánk valami mai igényeknek megfelelőbb feldolgozást) Szóval elnézést, de ma csak itt tartunk. Egyébként teljesen igazatok van, már rég működnie kéne ennek az archívumnak valamilyen formában. A jó hír az, hogy legalább a KöMaL kiadására és a KöMal-honlap és FÓRUM működtetésére épp hogy futja a MATFUND (és az adófizetők) pénzéből :-)

Oláh Vera

Előzmény: [2626] Cogito, 2008-04-13 14:11:36
[2628] sakkmath2008-04-13 16:17:36

Szia Gyöngyő!

Úgy tűnik, az első öt jól felírt sorozattag után a sok szám és vessző között eltévedtél, s talán ezzel magyarázható, hogy több hibával írtad fel a sorozat hátralévő tagjait. Megpróbálom hiba nélkül leírni a sorozat első 11 tagját, remélem, sikerül: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211, 11131221133112132113212221, ...

Végül nézzük a rekurziós képzési szabályt; hogyan kapjuk a 11. tagot a tizedikből: 1db 1, 1db 3, 1db 2, 2db 1, 1db 3, 3db 1, 1db 2, 1db 3, 2db 1, 1db 3, 2db 1, 2db 2, 2db 1.

Üdv: sakkmath

Előzmény: [2627] Gyöngyő, 2008-04-13 14:36:32

  [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]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]