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.
[3874] jonas2014-03-13 21:14:40

Úgy értem, az (a) és (b) feladat az, hogy mennyi a lépések számának várható értéke, és miért független ez a stratégiától.

Előzmény: [3873] jonas, 2014-03-13 21:13:23
[3873] jonas2014-03-13 21:13:23

Helyes, a véges várható érték. Akkor most jön a megoldás trükkösebb része.

Rögztsük a játékos egy stratégiáját. Jelölje Fn a játék állapotát n lépés után. Ez tartalmazza a játékos által kiválasztott két golyót és a játékvezető érmedobását az első n lépésben.

Legyen Xn az a szám, ahányféleképpen a játékos megválaszthatná a két különböző golyót az (n+1)-edik lépésében. Azért számozom így, mert Xn az Fn függvénye. Nyilván X0=n(n-1), mivel a kezdőhelyzetben bármely két golyó különböző. Feltéve, hogy a játék n lépés után még nem ért véget, számoljuk ki az E(Xn+1-Xn|Fn) feltételes várható értéket!

Ha ez megvan, akkor alkalmazzuk a martingál megállási tételt egy megfelelő martingálra, és ezzel oldjuk meg az (a) és (b) feladatot.

Előzmény: [3872] Róbert Gida, 2014-03-13 17:22:28
[3872] Róbert Gida2014-03-13 17:22:28

Nem jött megoldás, így lelövöm. Kezdetben n szín van, a játék véget ér, ha egy szín marad. Tetszőleges n2 egymásutáni fordulóban (1 forduló amikor 2 golyót a játékvezetőnek adunk és 2-t visszakapunk) van olyan szín ami legalább n-szer szerepel az odaadott golyószínek között (skatulyaelv, sőt van ami legalább 2n-szer), és legfeljebb persze n2-szer (mindez stratégiától függetlenül igaz). Ha ezen fordulók mindegyikében pont a másik színből adott vissza a játékvezető, akkor ebből a színből több nem marad (és később sem jöhet "vissza" a szabályok miatt). Ennek valószínűsége legalább r=\frac{1}{2^{n*n}}. Nézzünk n-1 egymásutáni blokkot, azaz n2 hosszú fordulót, ha minden blokkban vesztünk egy színt, akkor a játék természetesen véget ér, ennek a valószínűsége legalább q=rn-1. Azaz annak a valószínűsége, hogy n2(n-1) fordulóban befejeződik a játék legalább q, így annak a valószínűsége, hogy nem fejeződik be a játék legfeljebb s=1-q<1.

Ebből már készen vagyunk, mert ekkor Pr2(m)=Pr(játék m lépésben nem fejeződik be)<c*pm, ahol c>0,p<1 (Miért is? Bontsuk fel az m fordulót n2(n-1) hosszú fordulókra, bármelyiket is választjuk legfeljebb s<1 valószínűséggel nem ér benne véget a játék, így m forduló után is játszunk legfeljebb s^{\frac {m}{n^2(n-1)}-1}<c*p^m valószínűséggel .)

Legyen Pr1(m)=Pr(játék pontosan m lépésben ér véget), ekkor E=\sum_{m=1}^{\infty}m*Pr1(m)=\sum_{m=0}^{\infty}Pr2(m)<\sum_{m=0}^{\infty}c*p^m=\frac{c}{1-p}, azaz véges a várható érték, stratégiától függetlenül.

Sőt itt valamivel többet is beláttam, hiszen c,p csak n-től függött (de a stratégiától nem), azaz létezik v(n) véges szám, hogy a várható érték kisebb, mint v(n). Itt v(n) egyébként ki is számolható.

Előzmény: [3871] jonas, 2014-03-12 10:10:43
[3871] jonas2014-03-12 10:10:43

Hadd szedjem külön a feladat első részét.

(c) Lássuk be, hogy bármilyen stratégiával játszol is, a lépések számának várható értéke véges.

Előzmény: [3870] jonas, 2014-03-11 21:03:52
[3870] jonas2014-03-11 21:03:52

Ezt a feladatot nem volt jó ötlet ezen a fórumon feladnom, mert a megoldásához túl sok előismeret kell. A középiskolás fórumozóktól ezért elnézést kérek.

Előzmény: [3861] jonas, 2014-03-09 16:36:46
[3869] jonas2014-03-11 17:42:59

Aha, értem! Bocsánat, hogy nem fogalmaztam egyértelműen. Valóban, a játékvezető nem adja vissza a két golyót, amit odaadtál neki, így minden lépés után pontosan n golyó lesz nálad.

Előzmény: [3868] Róbert Gida, 2014-03-11 17:28:14
[3868] Róbert Gida2014-03-11 17:28:14

Jó a megoldásom, csak egy másik feladatra. Az persze számomra nem volt világos, hogy a játékvezető a két golyót lenyúlja amit odaadsz neki, így persze nálad mindig n golyó lesz, az én feladatomban pedig minden lépés után 2-vel több.

Előzmény: [3867] jonas, 2014-03-11 11:46:28
[3867] jonas2014-03-11 11:46:28

A számok, amiket megadtál, szerintem nem stimmelnek. n=3 esetén az első lépés után három golyóból két egyforma színű, és egy különböző lesz. Ez után minden további lépés után 1/2 valószínűséggel nyertél, 1/2 valószínűséggel visszajutsz egy hasonló állapothoz, csak most a másik színből van két golyód, mint az előbb. Így aztán biztosan legalább 2 lépés kell a nyerésig, nem 1, mint a táblázatban mutatod. Nem nehéz belátni, hogy a lépések várható száma pontosan 3.

Látható, hogy n=3 esetén még lényegében nincs választásod a játék során. A következő, n=4 esetben már van választásod. Például ha az első lépés után két fehér, egy sárga, és egy piros golyód van, akkor kétféleképpen dönthetsz. Odaadhatod a játékvezetőnek a sárga és a piros golyót, ez a kevésbé kockázatos stratégia, mert ekkor legközelebb biztosan két fehér és két másik azonos színű golyód van. Vagy kockáztathatsz, odaadva a játékvezetőnek egy fehér és egy sárga golyót, ekkor 1/2 valószínűséggel már három fehér golyód lesz, amivel közelebb jutottál a nyeréshez; de 1/2 valószínűséggel két sárga, egy fehér és egy piros golyód lesz, amivel helyben maradtál.

Te választod meg a stratégiát, de a feladat kitűzésében azt állítottam, hogy a lépések számának várható értéke bármely stratégia esetén ugyanannyi.

Előzmény: [3864] Róbert Gida, 2014-03-10 21:20:33
[3866] Róbert Gida2014-03-10 21:47:50

Nagyobb n-ekre megnézve látszik, hogy \frac {a(n)}{n} tart 1-hez, ami nagyon igaznak tűnik. Például a(1000) kb. 974.7749818216391980931583112 .

Előzmény: [3865] Róbert Gida, 2014-03-10 21:39:02
[3865] Róbert Gida2014-03-10 21:39:02

Optimális stratégiával a sorozat első 20 tagja (Neil adatbázisában nincs benne a számlálók sorozata, a nevezők 2 hatványok)

1 0

2 1

3 1

4 5/2

5 5/2

6 33/8

7 33/8

8 93/16

9 93/16

10 965/128

11 965/128

12 2379/256

13 2379/256

14 11333/1024

15 11333/1024

16 26333/2048

17 26333/2048

18 480429/32768

19 480429/32768

20 1079775/65536

Előzmény: [3864] Róbert Gida, 2014-03-10 21:20:33
[3864] Róbert Gida2014-03-10 21:20:33

"Minden lépésben megnézed a golyókat"

"A várható érték miért ugyanannyi függetlenül attól, hogy melyik golyókat választod?"

Játszhatok egy stratégia szerint, vagy véletlenül kell a golyókat kiválasztanom? Optimális stratégiával O(n) lesz a válasz: mindig a két eddig legtöbbet kihúzott színt választom (ha több lehetőség van, akkor véletlenül döntök a leggyakoribbak közül), ez persze mese eddig, hogy miért is ez lenne az opt. Várható értéket sem mutatja, de sokkal könnyebben kiszámítható ezzel a várható érték.

Míg hülyén játszva O(n2). Teljesen véletlenül játszva is érdekes (lehet) a feladat.

Előzmény: [3861] jonas, 2014-03-09 16:36:46
[3863] jonas2014-03-10 07:35:16

Igen, veheted úgy, hogy a játékvezető csukott szemmel választ egyet. Én úgy képzelem, hogy egy golyót a játékvezető jobb kezébe adsz, egyet a bal kezébe. Ezután ha a játékvezető fejet dob, akkor két olyat ad vissza, amilyen a bal kezében van, ha írást, akkor két olyat, ami a job kezében van.

Előzmény: [3862] BohnerGéza, 2014-03-10 03:13:18
[3862] BohnerGéza2014-03-10 03:13:18

Nem értem biztosan a feladatot. Ki dönti el, melyik az egyik illetve másik? Azt akarja jelenteni, amit így kapunk?

... A két kiválasztott közül csukott szemmel választ egyet és két ilyen színű kerül vissza. ...

n=1 esetén 0, n=2 esetén 1 a várható érték. A többi néhány esetet ehhez jobban értőkre bízom!

Előzmény: [3861] jonas, 2014-03-09 16:36:46
[3861] jonas2014-03-09 16:36:46

Itt van egy valószínűség-számítás feladat.

Legyen n egy természetes szám. Kapsz n különböző színű golyót. Minden lépésben megnézed a golyókat, majd ki kell választanod két különböző színű golyót, és odaadnod a játékvezetőnek. Ezután a játékvezető feldob egy érmét, ha fej jön ki, akkor ad neked két olyan színű golyót, mint az egyik, amit adtál neki; ha írás jön ki, akkor két olyan golyót kapsz, mint a másik golyó a kettő közül. Ha n egyforma golyó van nálad, akkor a játék véget ér, nyertél.

Mennyi a várható értéke a lépések számának? A várható érték miért ugyanannyi függetlenül attól, hogy melyik golyókat választod?

[3860] nyerek012014-03-06 19:54:41

(de valószínűleg hagyom és nem OFF-olok itt róla)

Előzmény: [3859] nyerek01, 2014-03-06 19:49:08
[3859] nyerek012014-03-06 19:49:08

Nem teljesen értem a hozzászólásodat, csak azért kérdeztem itt az elliptikus görbékről, mert suliban hallottam róla és gondoltam, hogy érdemes annyi figyelmet szentelnem neki, hogy egy egyszerű Java programban implementáljam. Nekünk a titkosítást említették mint felhasználási módot.

Előzmény: [3857] csábos, 2014-03-05 23:03:34
[3858] Loiscenter2014-03-06 01:48:22

Köszönönöm a segitséget!

Előzmény: [3851] w, 2014-03-03 20:48:18
[3857] csábos2014-03-05 23:03:34

Bakchausz Tibi, Zábrádi Gergely, Maga Péter, Harczos Gergely, Bodor Bertalan

Mi kellene róluk?

Előzmény: [3856] nyerek01, 2014-03-04 21:47:34
[3856] nyerek012014-03-04 21:47:34

Más: Elliptikus görbékhez ért valaki? Titkosításhoz kéne, ha megértem akkor lehet hogy írok ilyen programot.

[3855] w2014-03-04 20:59:30

Ahogy mondod.

Előzmény: [3854] nyerek01, 2014-03-04 20:22:20
[3854] nyerek012014-03-04 20:22:20

Na de a minimális várakozási idő kéne, ami akkor jön ki beleszámoljuk azt is hogy lejátszás közben is tölt, tehát nem az Össz. idő és a betöltési sebesség hányadosa a jó megoldás.

Előzmény: [3853] w, 2014-03-04 16:54:46
[3853] w2014-03-04 16:54:46

Ömm, 82 perc az 82.60=4920 másodpercben a 28 másodperc 175-ször van meg, így 350 másodpercig bufferol, ha azok a feltételek. Azaz én 5 perc 50 másodpercre állítanám meg, de ember a kb. 6 perc időtartamot szerintem könnyebben bírja érzékelni. :-) Ha ilyen formában kérdezed meg, csak egy maradékos osztásról van szó.

Előzmény: [3852] nyerek01, 2014-03-04 10:46:59
[3852] nyerek012014-03-04 10:46:59

Sziasztok. Egy 82 perces YouTube videó 28 másodpercenként megáll bufferelni 2 másodpercre, akkor hány másodpercre kell megállítani, hogy bebuffereljen elég tartalmat ahhoz, hogy utána akadásmentesen végig lehessen nézni.

Nem tudom mennyivel lenne bonyolultabb álltalánosítva, tehát ha X perces videó, N másodpercenként M sec-et bufferel. (Nyilván a "matekos" része a lényeg, nem az informatikai, tehát minden ideális, nincs szerver leállás, sávszél. ingadozás stb.)

[3851] w2014-03-03 20:48:18

554. feladat. Adott x2+2y2=1 esetén mennyi \sqrt{2x+1}+\sqrt{2y+1} maximuma?

(Nem kell az egész TeX tanfolyamot elvégezni ahhoz, hogy ezt be bírd gépelni, csak rámész és kikeresed, hogy hogy lehet hatványt és gyökjelet írni. Sokkal jobban néz ki, nem?)

Van rá egy bonyolult elemi megoldásom, egy saját módszerrel, ami nagyon hatékonyan működik.

Egy bizonyos becsléssorozatot fogok végrehajtani, de egyelőre nem tudom, hogy mik lesznek a súlyok. Legyenek tehát A és B később meghatározandó pozitív valós konstansok.

A kéttagú számtani és mértani közepek közötti egyenlőtlenség szerint

\sqrt{2x+1}=\frac1{A}\cdot\sqrt{A^2(2x+1)}\le\frac{A^2+2x+1}{2A},(1a)
\sqrt{2y+1}\le \frac{B^2+2y+1}{2B}.(1b)

A két becslést összeadva becslést kapunk \sqrt{2x+1}+\sqrt{2y+1}-re, amit ezáltal egy \frac{2x}{2A}+\frac{2y}{2B} plusz konstans típusú kifejezéssel majoráltunk.

Ezután pedig a Cauchy-egyenlőtlenséget alkalmazzuk:

\frac xA+\frac yB\le\sqrt{(x^2+2y^2)\left(\frac{1}{A^2}+\frac1{2B^2}\right)},(2)

ami már fix érték.

Ahhoz, hogy ezek a becslések működjenek, kizárólag arra van szükségünk, hogy egyenlőséget is garantálhassunk. Egyenlőség a következő esetekben áll fenn: 2x+1=A2 az (1a)-ban, 2y+1=B2 az (1b)-ben, illetve x2.A2=2y2.2B2 (2)-ben, végül pedig az, hogy erre az x,y párra x2+2y2=1 fenn is álljon. A kapott egyenletrendszert megoldva (negyedfokú egyenletre vezet, amit ez megold, és hát reménykedhetünk abban, hogy van valós megoldása). Ha nem probléma én ezt most nem fejezném be.

Előzmény: [3850] Loiscenter, 2014-03-03 09:55:25
[3850] Loiscenter2014-03-03 09:55:25

Legyenek x, y nem negativ számok, továbbá x*2 + 2.y*2 = 1. Határozzuk meg (2x+1)*1/2 + (2y+1)*1/2 maximum és minimum értékét ! ( * hatványt jelent)

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