Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1 2
Ahoj. Mám dva příklady:
1. Kombinatorika
Kolika různými způsoby lze na šachovnici rozestavit
(a) 8 věží tak, aby se žádné dvě neohrožovaly?
(b) k věží, 1≤k≤8, tak, aby se žádné dvě neohrožovaly?
(c) zobecněte vzorec pro k věží a šachovnici o rozměrech n×m.
2.Teorie grafů
Nechť V(G) grafu G je množina všech dvouprvkových podmnožin množiny [1,5] a nechť jsou vrcholy x,y sousední právě tehdy, když x a y jsou množiny disjunktní. Jakou délku má nejkratší cyklus v tomto grafu? Své tvrzení dokažte!
ad1.)
Někde na foru už tento příklad byl, ale nějak se mi nezdálo řešení. Počítal jsem to tedy tak:
a) Věže jsou stejné. Počet možností umístění první věže je 64 (šachovnice 8x8), další věž můžu umístit kamkoli mimo stejný řádek a sloupec umístěné první věže, tedy 49 atd.. Výsledek by tedy měl být (8^2)*(7^2)*(6^2)*(5^2)*(4^2)*(3^2)*(2^2)*(1^2).
b) (8^2)* ..... * [(k-8)+1]^2
c) musí platit: m,n >= k;
(m*n) * ( (m-1)*(n-1) ) * ...... * ( (m-(k-1)) * (n-(k-1)) )
ad2.) vůbec netuším
Je ta jednička dobře? Předem dík za každou radu
Offline
1. (a) jak sam rikas, veze jsou nerozlisitelne. Ty jsi je ale pocital jako rozlisitelne, cili kazdou z moznosti jsi zapocital prave 8! ("osm faktorial") krat.
Kdyz veze ocislujeme, jedno rozestaveni muze vypadat treba takto
1xxxxxxx
x2xxxxxx
xx3xxxxx
xxx4xxxx
xxxx5xxx
xxxxx6xx
xxxxxx7x
xxxxxxx8
To je ale to same, jako napriklad tohle:
2xxxxxxx
x1xxxxxx
xx3xxxxx
xxx4xxxx
xxxx5xxx
xxxxx6xx
xxxxxx7x
xxxxxxx8
Je to jedno a totez rozestaveni, nebot nezalezi na poradi vezi. Existuje jeste dalsich 40318 rozestaveni s vezemi na hlavni diagonale. Vsechna jsou stejna, tedy by se vsechny mely pocitat jako jedna moznost, tys je ale zapocital jako 40320 moznosti.
2. Rozmysleme si, jaky muze byt nejkratsi cyklus. Muze mit delku tri? (odpoved zni ne, proc?)
Sel by cyklus delky ctyri? (sel, zkus ho najit)
Offline
ad1)
Takže pokud to chápu, stačí spočítat pro první věž na kolik míst v řádku ji lze umístit a následující věž bude vybírat z řádku kratšího o jeden sloupec? Výsledek by tedy vypadal: 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 => tedy 8!
Offline
Presne tak. Lze take postupovat tak, ze si uvedomime, ze jsme kazdou moznost zapocitali vicekrat, a potom tvuj vyraz (8^2)*(7^2)*(6^2)*(5^2)*(4^2)*(3^2)*(2^2)*(1^2) jednoduse vydelime timto cislem, tedy v tomto pripade vyrazem 8*7*6*5*4*3*2*1, coz po vydeleni vyjde skutecne 8!.
Offline
ad1 b)
Pokud tedy budu počítat umístění pro k věží (k může být 1-8), spočetl bych to takto: spočtu kombinaci k možných řádků na kterých se budou věže nacházet, tedy (8 nad k) a vynásobím to možnými umístěními věži, které bych asi vyjádřil 8! / (8-k)! a vynásobil počtem věží
Výsledek: k* [ (8 nad k) * ( 8! / (8-k)! ) ]
Offline
Z jakeho duvodu se to cele nasobi poctem vezi? Ten vzorecek by mel samozejme platii i pro k=8. V zadani a) jsme zjistili, ze pro k=8 je pocet moznosti 8!. Po dosazeni k=8 do tveho vzorce ale vyjde 8*8!.
Offline
Aha. To by asi platilo pro různé šachy. ad1 c) - Mohl by tedy obecný vyorec vypadat takto? (pokud mam sachovnici o m*n polich, kde m bude pocet prvnku v radku a n pocet sloupcu) (n nad k) * ( m! / (m-k)! )
Offline
"Pocet prvku v radku" a "pocet sloupcu" je totez. Tvuj vzorecek plati pro 'n' - pocet radku, 'm' - pocet sloupcu, 'k' - pocet vezi.
Offline
Ahoj mam stejne zadani, ktere je zde jiz uvedeno. Reseni prvniho prikladu jsem pochopil. Ale ten druhy priklad mi neni moc jasny. Jsem se ho pokousel resit a dospel jsem, ze v nejkratsim cyklu musim projit 5 hran. Mohl bys mi snim poradit. Diky.
Offline

Cyklus délky 3 vyloučit umíme.
Řekněme, že by existoval cyklus délky 4: {a,b} -> {c,d} -> {e,f} ->{g,h}. Kdyby {e, f} bylo disjunktní s {a, b}, byly by prvky a, b, c, d, e, f různé, což nelze. Proto bez újmy na obecnosti a=e. Prvky c,d,g,h nesmí být rovny a,b,d, mohou tedy nabývat pouze dvou hodnot, takže {c,d}={g,h}, spor.
Pro délku pět už cyklus najdeme (1,2) -> (3,4) -> (1,5) -> (2,3) -> (4,5).
Offline
Podle mě to za ad 1) A není dobře,protože TY VĚŽE jsou všechny naprosto stejné!!! Tedy nezáleží na pořadí a PERMUTACI záleží.Tudíž to podle mě 8!(osm faktoriál) není dobře. Nezapomeňte,že se tady bavíme o rozestavení a ne o proházení.To co jste udělali vy je to,že jste v jedné diagonále proházely mezi sebou věže.Každopádně jdu zítra na konzultace,takže napíšu jak jsem dopadl... pisnu ...
Offline
Samozrejme nemohu rict, ze moje odpovedi jsou vzdy bezchybne. To se tyka i te moji mystifikace ohledne nejkratsiho cyklu. Za toto se samozrejme omlouvam, mel jsem si to nakreslit misto toho, ze jsem si to jen predstavil. Ohledne te sachovnice, podivejme se, co se stane v pripade, kdy mame sachvnici mensi. Napriklad 3x3. Vypisme vsechna mozna rozestaveni vezi:
voo
ovo
oov
voo
oov
ovo
ovo
voo
oov
ovo
oov
voo
oov
voo
ovo
oov
ovo
voo
Je jich tedy 3!, coz by souhlasilo s mym vypoctem. Pro vyssi pocet policek postupujeme naprosto analogicky. Cili za timto vysledkem bych si stal.
Offline

Vyřeším zde pouze (c), dosadit už zvládne každy. Tož tedy: "zobecněte vzorec pro k věží a šachovnici o rozměrech n×m".
Pro jednodušší popis řekněme, že n je řádků a m je sloupců.
Pokud je k>n nebo k>m, je tento počet nula.
V opačném případě vybereme
řádků, v nichž budou věže umístěny. Do prvního z těchto řádků umístíme věž m způsoby, do dalšího m-1, do dalšího m-2,.... pro zvolenou k-tici řádků tedy
.
Podle pravidla součinu je celkový počet možností
. Finální verze vzorce nám dává jistou kontrolu správnosti tím, že je symetrická vzhledm k záměně pojmů řádek a sloupec. Navíc vede k jinému možnému řešení: nejdříve (n nad k)*(m nad k) způsoby vybereme "podšachovnici" k x k, na niž pak věže umístíme k! způsoby.
Takže pokud máte někdo protipříklad, máte smůlu, protože moderátoři mají dva důkazy :o) Tím chci říct, že jsem dost silně přesvědčen o správnosti svého i Lishaakova postupu, ale pokud čemukoliv nebylo rozumět, tak dotazy vítáme :o)
Offline
↑ Lishaak:
Já si to než jsem se dostal zase na fórum také zkusil a musí uznat svou chybu.Omluvám se,opravdu mi také vyšlo 3! pro případ 3x3.Dal jsem si tu práci a nakreslil všechny možnosti pro 4x4 a světe div se,opravdu vyšlo 24,což je 4!(čtyři fatoriál). Omlouvám se Lishaakovi a všem,které jsem svým tvrzením nějak znejistěl nebo uvedl v další tápání... :)
Offline
ja bych se taky primlouval jeste k reseni toho grafu... ja si totiz nedokazu predstavit ani ten graf podle vety: "Nechť V(G) grafu G je množina všech dvouprvkových podmnožin množiny [1,5]"
Offline
↑ Kauf:
takze spravny vypočet 1a) je tedy P(8)=8! = 40320 ?????? nebo je to výpočet pomocí nějaké kombinace?! :)
1b) s t9mhle výpočtem bych aji souhlasil :) přesněji ten (8^2)* ..... * [(k-8)+1]^2 co myslite ?! :)
1c) si myslim ze reseni od kondr je spravne :)
ale 2 tu teorii grafu tu fakt nevim :(
Offline
↑ radovanek:
ad1a) Já byl dneska na konzultaci a došli jsme k tomu,že výsledek 8! faktoriál je správně,avšak nechtěl mi říct, jestli je to permutace nebo něco jiného...Každopádně si osobně myslím,že permutace to nebudou :-)
Tak jsou to kombinace :) už jsem na to přišel :-)
Offline
↑ Kauf:
Jen tak na okraj, mozna by nebylo od veci zduraznit jednu vec, kdyz uz je tento priklad ve vysokoskolskem foru. Ne vsechny priklady z kombinatoriky lze rozskatulkovat na variace, permutace, kombinace apod. Tyto pojmy jsou v podstate jenom urcite pomucky, ktere nam maji usnadnit premysleni. Pokud se ale clovek snazi je napasovat na kazdy priklad, zacne ho to pozdeji strasne omezovat. Ja tuto terminologii pouzivam v podstate jen tehdy, kdyz neco vesvetluju stredoskolakum. Jinak se bez ni kdykoliv obejdu a nemusim si uvedomovat, do ktere skatulky ten ktery priklad patri.
Namyslim si, ze by tento priklad byl v nektere z vyse zminenych skatulek. V nejobecnejsi verzi c) se uplatni jak variace, tak kombinace a klidne i permutace.
Offline
↑ Kondr:
neni mi jasne jak mam vyloucit cyklus delky 3? Muzes prosim to rozepsat?
V podstate v dalsi fazi vylucujes cyklus 4 a nachazis cyklus 5 coz je vysledek tohodle prikladu, chapu to zpravne?
Offline

↑ marros11:Ano, to chápeš správně. A cyklus délky 3 se vyloučí velmi podobně: kdyby cyklus procházel množinami
{a,b},{c,d},{e,f}, musely by každé dvě být disjunktní, tzn. prvky a až f různé, 6 různých prvků ale nemáme.
Offline

↑ Kauf:Lishaak má pravdu. Ani "kombinace", ani "variace" ani "permutace" nejsou typy příkladů. Jsou to pouze prostředky k jejich řešení. Existují různé postupy řešení té úlohy. Jeden využívá kombinace a permutace, jiný variace a permutace, možná by šlo vymyslet nějaký, které by využívalo jenom kombinace. Ale ve vysokoškolské matematice neexistuje nic jako "příklad na kombinace". Určitě se hodí ty pojmy znát, protože to usnadní vyjadřování (imho nejen v textech pro středoškoláky), ale primární je chápat, jak se tyto prostředky dají k řešení úloh využít.
Offline
Stránky: 1 2