Stránka 2628

Re: Dobrá hádanka? Vánoční

PříspěvekNapsal: stř 23. pro 2015 1:22:19
od voki8
alkaatch píše:Devět kamarádů si předává dárky k Vánocům, každý z nich dá dárek třem různým kamarádům. Ukažte že není možné, aby každý dostal dárky právě od těch kamarádů, kterým dárky sám dal.


Odkud to máš,tohle se mi zdá jsem viděl někde v souvislosti s teorií grafů,ale už si nemůžu vzpomenout kde to bylo :angry:

Re: Dobrá hádanka?

PříspěvekNapsal: stř 23. pro 2015 2:02:38
od SirPotkanus
Nevim tak nejak logicky se mi udelaj 2 skupiny po 4 a jeden zustava plonkovej...ale asi v tom neco bude:))

Re: Dobrá hádanka?

PříspěvekNapsal: stř 23. pro 2015 15:20:48
od Charlie579
Darky nosi Jezisek a ne kamaradi :)

Re: Dobrá hádanka?

PříspěvekNapsal: stř 23. pro 2015 20:59:16
od alkaatch
Voki: ano je to typická grafová úloha, ale dá se řešit i bez teorie grafů celkem snadno.
SirPotkanus: není to těžké, asi máš pravdu, ale jde o to nějak jednoznačně odpověděť aby to z toho prostě bylo vidět (nebo taky můžeš vyzkoušet všechny kombinace na počítači, ale to do hádanek nepatří :) ) )
Charlie579: myslíš tenhle Ježíšek?

Re: Dobrá hádanka?

PříspěvekNapsal: čtv 24. pro 2015 12:08:00
od Pal1n0
tak ja som si original na to spravil tabulku a nejak logicky mi vyšlo toto

[Ukázat] Spoiler:
vlavo su ludia označení číslom a vpravo šú čísla, ktorým daruje darček,

hadanka.PNG
hadanka.PNG (3.59 KiB) Zobrazeno 455 krát


každý každému vrátil darček, ale ostalo jedno voľné miesto, to znamená, že ta deviatka by si musela dať darček sam sebe aby to bola pravda, resp. bude tam na 100% jeden človek, ktorý daruje darček niekomu, kto mu to dať naspeť nemôže, lebo už svoje voľby vyčerpal ... resp, aspon jeden musí dostať 4 darčeky aby to sedelo

ale teraz by ma zaujímal ešte nejaký matematický dôvod, ak vôbec existuje :D ... ale asi budu existovať kombinácie kedy to vyjde pekne

Re: Dobrá hádanka?

PříspěvekNapsal: čtv 24. pro 2015 14:55:09
od alkaatch
Chtělo by to ještě nějakej argument typu "přípustnou permutací se vlastnosti tabuljy nezmění", ale asi ok :)

Zdůvodnění: když by každý dostal dárek od toho komu dal, tak by se dárky daly uspořádat do dvojic (dal-dostal) a tudíž by jich byl sudý počet. Ale my víme že jich je 3*9=27 a to je liché číslo :idea:

Re: Dobrá hádanka?

PříspěvekNapsal: čtv 24. pro 2015 16:06:38
od pepiksevcu
A co treba takhle: kdyby byli 3 a davali jeden darek, tak je jasne ze to nejde a pak se oboje jen vynasibi 3. Ale nevim zda je to korektni.

Re: Dobrá hádanka?

PříspěvekNapsal: čtv 24. pro 2015 17:59:20
od Pal1n0
to s permutiaciami som myslel, že to už logicky z tejto tabuľky vychádza, tak ma to nenapadlo doplniť, ale inak máš pravdu, ak by to malo byť úplne, tak ten komentár tam nesmie chýbyť ...

a bol som si vedomý, že môj systém zisťovania či je to možne je prinajmenšom nepraktický .. a presne nejaké take matematicke vysvetlenie, ktoré sa da generalizovať na ľubovľný počet ľudí a darčekov som nejak nevedel nájsť ... a pritom to je tak logické :D

Re: Dobrá hádanka?

PříspěvekNapsal: čtv 24. pro 2015 22:05:40
od alkaatch
A co treba takhle: kdyby byli 3 a davali jeden darek, tak je jasne ze to nejde a pak se oboje jen vynasibi 3. Ale nevim zda je to korektni.

Musel bys nějak dokázat že násobení neničí tu vlastnost. Třeba liché číslo se vynásobením změní na sudé, proč násobení třema musí zachovat vlastnost "nejde...".

Re: Dobrá hádanka?

PříspěvekNapsal: pát 25. pro 2015 0:58:18
od pepiksevcu
alkaatch píše:
A co treba takhle: kdyby byli 3 a davali jeden darek, tak je jasne ze to nejde a pak se oboje jen vynasibi 3. Ale nevim zda je to korektni.

Musel bys nějak dokázat že násobení neničí tu vlastnost. Třeba liché číslo se vynásobením změní na sudé, proč násobení třema musí zachovat vlastnost "nejde...".


Ktere liche cislo se nasobenim cisla 3 zmeni na sude ? Nepolemizuji, jen jsem to myslel pro tuhle konkretni hadanku, ne obecne pro n pandulaku. Dokazovat ze nasobenim neznicim vlastnost samozrejme ...nedam. V tyhle hadance mi to vyslo, ale chapu ze dukaz je neco jineho, ono asi "je jasne " taky neni matematicky pojem.

Re: Dobrá hádanka?

PříspěvekNapsal: pát 25. pro 2015 10:21:48
od alkaatch
Liché samozřejmě vynásobením dvěma, jde o to, že obecně násobením N se může něco zkazit...
Tady je hlubší problém, přidáním lidí/dárků můžou vzniknout struktury (to jsou ty grafy o kterých psal Voki), které v menším počtu vzniknout nemůžou, při třikrát větším počtu dárků/lidí je počet kombinací jakými si můžou dárky předat mnohem větší než trojnásobný.

Re: Dobrá hádanka?

PříspěvekNapsal: úte 08. bře 2016 22:09:46
od voki8
Odesílám někam náhodnou zprávu a v ní můžu posílat jen nulu a jedničku.

Šance,že odešlu 0 je 0,5 (50%)
Šance,že odešlu 1 je 0,5

Ale během přenosu zprávy občas dojde k chybě.

Přijetí 0 za podmínky,že byla odeslána 0 = 0,9
Přijetí 1 za podmínky,že byla odeslána 1 = 0,8

Z toho se odvodí i pravděpodobnosti chybného přenosu (odešlu 0,přijmu 1 nebo odešlu 1,přijmu 0)

Bude tedy platit toho:

0 -> 0 ....P = 0,9
0 -> 1 ....P = 0,1
1 -> 0 ....P = 0,2
1 -> 1 ....P = 0,8

A teď zprávu budeme posílat stále dále a dále.
Jaká je pravděpodobnost přijetí nuly a přijetí jedničky po n přenosech? Samozřejmě uvažujeme i chybné přenosy.
Co se stane,když se n bude blížit k nekonečnu. (A platí,že n ∈ N)
Vlastně stačí spočítat jen pravděpodobnost přijetí nuly.Pravděpodobnost jedničky pak bude jen doplňěk do 100%.

Už jsem v řešení docela pokročil,ale stále se mi nedaří najít vztah mezi P(n) v závislosti na pravděpodobnostech ze zadání.
A když n půjde k nekončenu,je jasné,že nul budu příjimat stále víc (Některé 0 se změní po cestě na 1 a obráceně,ale 1->0 se stane častěji,takže je jasné,že jedniček bude ubývat a nul přibývat,ale netuším jestli pořád až do 100% a nebo se to bude limitně blížit k nějaké hodnotě.

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 22:26:32
od voki8
[Ukázat] Spoiler:
voki8 píše:Odesílám někam náhodnou zprávu a v ní můžu posílat jen nulu a jedničku.

Šance,že odešlu 0 je 0,5 (50%)
Šance,že odešlu 1 je 0,5

Ale během přenosu zprávy občas dojde k chybě.

Přijetí 0 za podmínky,že byla odeslána 0 = 0,9
Přijetí 1 za podmínky,že byla odeslána 1 = 0,8

Z toho se odvodí i pravděpodobnosti chybného přenosu (odešlu 0,přijmu 1 nebo odešlu 1,přijmu 0)

Bude tedy platit toho:

0 -> 0 ....P = 0,9
0 -> 1 ....P = 0,1
1 -> 0 ....P = 0,2
1 -> 1 ....P = 0,8

A teď zprávu budeme posílat stále dále a dále.
Jaká je pravděpodobnost přijetí nuly a přijetí jedničky po n přenosech? Samozřejmě uvažujeme i chybné přenosy.
Co se stane,když se n bude blížit k nekonečnu. (A platí,že n ∈ N)
Vlastně stačí spočítat jen pravděpodobnost přijetí nuly.Pravděpodobnost jedničky pak bude jen doplňěk do 100%.

Už jsem v řešení docela pokročil,ale stále se mi nedaří najít vztah mezi P(n) v závislosti na pravděpodobnostech ze zadání.
A když n půjde k nekončenu,je jasné,že nul budu příjimat stále víc (Některé 0 se změní po cestě na 1 a obráceně,ale 1->0 se stane častěji,takže je jasné,že jedniček bude ubývat a nul přibývat,ale netuším jestli pořád až do 100% a nebo se to bude limitně blížit k nějaké hodnotě.




Zkusím tady nějak popsat svůj postup,myslím,že jsem na to už přišel,ale nejsem si úplně jistý na 100%.

Nejdřív si napíšu pravděpodobnosti,že přijmu 0 a 1 po prvním přenosu a z toho budu vycházet.
Řekněme,že P(Xn) bude pravděpodobnost přijetí nuly po n přenosech a P(Yn) to samé pro přijetí 1.

0 -> 0 = 0,5 * 0,9 = 0,45
1 -> 0 = 0,5 * 0,2 = 0,1
1 -> 1 = 0,5 * 0,8 = 0,4
0 -> 1 = 0,5 * 0,1 = 0,05

P(X1) = 0,45 + 0,1 = 0,55
P(Y1) = 0,4 + 0,05 = 0,45

A teď když to budu posílat dále...0 se změní na nulu s pravděpodobností 0,9 a jednička se změní na nulu s pravděpodobností 0,2.

Musí tedy platit :
P(Xn) = P(Xn-1) * 0,9 + P(Yn - 1) * 0,2

Teď je ale problém vyjádřit P(Xn) v závislosti na P(X1)
Pokračoval jsem takto :

P(Xn) = P(Xn-1) * 0,9 + [1 - P(Xn-1)] * 0,2
P(Xn) = 0,9*P(Xn-1) + 0,2 - 0,2*P(Xn-1)
P(Xn) = 0,7*P(Xn-1) + 0,2
P(Xn) = 0,7* [0,7*P(Xn-2) + 0,2] + 0,2
P(Xn) = 0,7^2*P(Xn-2) + 0,7*0,2 + 0,2 atd

Nakonec když budu pořád opakovat stejnou úpravu dojdu ke konečnému výsledku
P(Xn) = 0,7^(n-1) * P(X1) + 0,2* [ 0,7 + 0,7^2 + 0,7^3 + ... + 0,7^(n-2) ] + 0,2
P(Xn) = 0,7^(n-1) * 0,55 + 0,2* [ 0,7 + 0,7^2 + 0,7^3 + ... + 0,7^(n-2) ] + 0,2

Je toto správně?
A co teď s limitou když n se bude přibližovat nekonečnu?
Možná vlastně bude stačit prostě dosadit vysoké číslo a bude to cca dobře.

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 22:57:13
od Kubex
Co myslíš tím montecarlo? Jako nasimulovat pár členů?

Když zadám:
[Ukázat] Spoiler:
for n=2:30
A=A+ 0.7^(n-2);
P = 0.7^(n-1)*0.55 + 0.2*A + 0.2;
dat = [dat,P];
end


Tak to vyplivne:

[Ukázat] Spoiler:
voki.jpg
voki.jpg (18.54 KiB) Zobrazeno 368 krát


Tos myslel?

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 23:02:28
od voki8
Kubex píše:Co myslíš tím montecarlo? Jako nasimulovat pár členů?

Když zadám:
[Ukázat] Spoiler:
for n=2:30
A=A+ 0.7^(n-2);
P = 0.7^(n-1)*0.55 + 0.2*A + 0.2;
dat = [dat,P];
end


Tak to vyplivne:

[Ukázat] Spoiler:
voki.jpg


Tos myslel?



JJ,to asi není přesně montecarlo,jsem nevěděl jak to pojmenovat.
Ale přesně to jsem myslel,díky :poklona:
Teď to vypadá,že limita bude někde u 0,87.

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 23:06:38
od Kubex
Jo jo, jak n bude víc než 100 tak už se to měnit skoro nebude

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 23:09:35
od Kubex
Jen pro představu, pro n=200000 ani nevidíš ten začátek.

[Ukázat] Spoiler:
voki.jpg
voki.jpg (17.25 KiB) Zobrazeno 363 krát

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 23:35:48
od voki8
Jjj,to bude ono.
Jen mi ještě ta hodnota nějak nesedí,zdá se mi,že je to moc vysoké číslo,zamyslím se nad tím zápisem ještě...

Re: Dobrá hádanka?

PříspěvekNapsal: úte 22. bře 2016 23:41:37
od voki8
Jo já tam mám chybu v tom původním řešení.
Tedy je to možná dobře od n > 2

Když to napíšu takto,mělo by to sedět.
Zmizí nám ten poslední člen 0.2 a celé řešení bude 0,67 místo 0,87.

P(Xn) = 0,7^(n-1) * 0,55 + 0,2* [0.7^0 + 0,7^1 + 0,7^2 + 0,7^3 + ... + 0,7^(n-2)]

Re: Dobrá hádanka?

PříspěvekNapsal: stř 23. bře 2016 1:26:01
od alkaatch
Na to co řešíš je celá teorie, tzv Markovských řetězců. Celej proces si můžeš napsat jako matici 2x2, která u tebe vypadá takhle:
Kód: Vybrat vše
0.9   0.1
0.2   0.8

A vizuálně to je pak tohle:
Kód: Vybrat vše
http://setosa.io/markov/index.html#{%22tm%22%3A[[0.9%2C0.1]%2C[0.2%2C0.8]]}


Ty máš výchozí rozdělení (50%,50%) a rozdělení po N krocích je (0.5,0.5)x N-tá mocnina té matice. Obecně platí, že po N krocích udává stav systému (respektive pravděpodobnosti kde se to nachází) N-tá mocnina matice. To co hledáš není limita, ale limitní rozdělení, prostě jaké jsou pravděpodobnosti při N jdoucím nade všechny meze. To bude nějaké rozdělení typu (a%,100%-a%). To obecně nemusí existovat (může to různě oscilovat), ale pro tvůj případ platí, že existuje a shoduje se tzv stacionárním rozdělením, které je řešením rovnice x=xP, kde P je ta matice. Z toho vychází řešení (2/3,1/3). To nezávisí ani na výchozím stavu, takže ať na začátku pošleš cokoliv, tak na konci to bude s pravděpodobností 2/3 nula a s pravděpodobností 1/3 jednička.

Všimni si, že když do toho "hodíš" nulu s pravděpodobností 2/3 a jedničku s pravděpodobností 1/3, tak ti to vypadne se stejnejma pravděpodobnostma...
0 :arrow: 0 2/3*90%
1 :arrow: 0 1/3*20%
dohormady 180%/3 + 20%/3 = 200%/3=2/3 * 100% = 2/3
a analogicky u jedničky.

Proto se to jmenuje stacionární rozdělení. Ale to, že se bude stacionární a limitní rozdělení shodovat je už složitější, každopádně tady je to pravda protože máš "hezkej" řetězec.

Dá se to taky spočítat napřímo přes mocniny té matice, nebo podobně jako jsi to dělal ty, což je převod na diferenční rovnice, ale to je obojí o dost složitější, než řešit soustavu x=xP (dvě rovnice a dvě neznámé).
Ale vyřešils to dobře koukám, napoprvé jsem to dělal taky tak :) Pak jsem se naučil řešit obecné diferenční rovnice a pak jsem se naučil, že to vůbec nepotřebuju, protože to jde přes ty stacionární rozdělení :cool: