Matematické Fórum

deadfak · 29. 11. 2018 10:09

Zdravím, potřebuji pomoci s touto úlohou.

Káždý ze svatebních hostů se zná

1. s více než polovinou
2. s alespon polovinou

ostatních hostů. Dokažte v obou případech, že se hosté mohou posadit kolem kulatého stolu tak, aby se každí dva sousedé znali.

Alespon nějaké rady z čeho začit, protože úplně nevím jak na to.

Děkuju za cokoliv.

check_drummer · 30. 11. 2018 15:12

ahoj, z 2. plyne 1., tak buď vyřešit jen 2 a nebo nejdřív 1 a s pomocí ní 2.

krakonoš

↑ check_drummer:
Ahoj.
Já myslím,že
v případě 2. je použito slovo aspoň ve smyslu polovina nebo více. Vše závisí na volbě N.Pokud je např N rovno 9,stačí pak polovina přesně ,ale bude třeba dokázat,že i ta polovina stačí pro rozesazení kolem stolu.Pokud tedy každý se zná přesně s polovinou ostatních,aspoň doufám,že navzájem,tak musí být počet dvojic N.(N-1)/4 po odbourání pořadí,musí být ale zaručena dělitelnost.Jinak musí znát víc jak polovinu.No a u stolu je to aspoň 2.N/2 po odbourání pořadí.
Tak to aspoň vidím já,ale diskrétní matiku jsem nikdy nestudovala.

check_drummer · 02. 12. 2018 00:36

Tak pro 4 hosty to neplatí. Pokud je označíme A,B,C,D a A se zná s B,C a D se zná s A,B, tak je musím uspořádat cyklicky jako A,B,D,C,A (aby měl A sousedy B,C), ale pak bude D sousedit s C, kterého nezná..

zdenek1 · 02. 12. 2018 08:41

↑ check_drummer:
Nemáš splněnu podmínku: C se zná jen s A.

krakonoš

↑ check_drummer:Ja si myslim,ze
Pro 4 hosty je sice N.(N-1) delitelne ctyrmi,ale neni (N-1) delitelne dvema.
Takze musim uvazovat o tom,ze kazdy zna vic jak polovinu.
Ono to zadani je vlastne svym zpusobem blbost,protoze pojmu vic jak polovina vyhovuje i ze se zna kazdy s kazdym,a pak je rozesadim podle pravidel vzdy.Tady je zajimavejsi prave vysledovat tu zakonitost,kdy staci polovina,a kdy to musi byt vic. V pripade,ze staci prave polovina, musi byt delitelne N-1 dvema,pak ale N neni delitelne dvema a je liche.Takze musi byt N-1 delitelne ctyrma. To vyhovuje pak i tomu , ze pocet vsech znamych dvojic je roven nebo vetsi nez pocet znamych dvojic u stolu.Aspon tak to vidim ja.

check_drummer · 02. 12. 2018 23:39

↑ zdenek1:
Ahoj, nevypsal jsem všechny dvojice známých, ale jen ty "podstatné". C se kromě A zná i s B.

misaH · 02. 12. 2018 23:46 — Editoval misaH (02. 12. 2018 23:48)

No neviem.

Keby sme všetci hostia boli traja - poznám sa s 1 (polovicou zvyšných), tak ako sa posadíme, aby sa vždy každí dvaja susedia poznali?

krakonoš

↑ misaH:
Ahoj.Ale 3-1 jsou 2 .To je delitelne 2,ale ne 4ma.Ten vyse uvedeny postup plati az od N rovno 5 ,pokud se dobre pamatuji,pri porovnani tech dvou cisel t.j. N.(N-1)/4 -N je rovno vetsi nez 0.
Takze u 3 lidi musis znat proste vic jakpolovinu.

Matematické Fórum

#1 29. 11. 2018 10:09

Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#2 30. 11. 2018 15:12

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#3 01. 12. 2018 12:06 — Editoval krakonoš (01. 12. 2018 16:56)

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#4 02. 12. 2018 00:36

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#5 02. 12. 2018 08:41

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#6 02. 12. 2018 11:09 — Editoval krakonoš (02. 12. 2018 11:39)

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#7 02. 12. 2018 23:39

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#8 02. 12. 2018 23:46 — Editoval misaH (02. 12. 2018 23:48)

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

#9 03. 12. 2018 14:26 — Editoval krakonoš (03. 12. 2018 14:45)

Re: Kombinatorika - Stirlingovo číslo prvního druhu - důkaz - indukce

Zápatí