Matematické Fórum

Rovněž mě nenapadá řešení tohoto zadání, mohl by prosím někdo poradit. Děkuji

↑ Kondr:
Chtěl bych se zeptat na toto tvrzení:Vedle Petra sedí Martin a Honza, jeden z nich určitě taky zná Karla. Jak si přišel na to, že jeden z nich zná určitě Karla? A ještě píšeš, že to co chceme získáme dosazením za k=25, myslím si, že to ale není nutné, když dokážu, že lze dosadit správně Karla.

Taky by mě to zajímalo jsem z toho v pasti...

Ale nevím jak to dokázat pro těch 25 lidí... A taky ještě dotaz když je dvojce lidí tak může jeden z nich znát třeba 5 z 5ti lidí a ten druhý nikoho ale bude sedět mezi známími?

↑ mexx:Když jsme to dokázali pro obecné k, platí to i pro k=25.

Ta situace, že někdo nikoho nezná, nastat nemůže. Když vyberu dva lidi, tak jeden z nich zná jeho, takže on zná jednoho z nich (to je ta symetrie).

↑ Kondr:
Jasne, ale porad nechapu proc to nejde pro 3 lidi? Kdyz vyberu libovolne dva, tak dohromady musi znat zbytek lidi (zbyva pouze jeden, a toho znaji oba dva).

A----B           A----D            A     B     C     D            z te tabulky vidim kdo se s kym zna
|      |           |      |           --------------------            (A se zna s B a s D)
D----C           B----C            B     A      B     A
                                         D     C      D     C
D----A           D----C
|      |           |      |
C----B           A----B

C----D           C----B
|      |           |      |
B----A           D----A

B----C           B----A
|      |           |      |
A----D           C----D


Kdyz vemu 4 lidi, je 8 moznosti jak je mohu rozesadit?


"Pro k=4 rozebereme několik možností, nějak nám to musí vyjít "

tady porad nechapu co se po me chce :D

Jo, vzdyt jsem to vlastne napsal, jen jsem reagoval na to, ze nahore Kondr napsal, že pro 3 lidi nelze splnit zadani.

No to jsme na tom podobne, jako jak to funguje chapu, ale nevim co bych tam mel napsat no

Pro 3 lidi narazíme. Graf známostí může vypadat takto:

Petr------Karel-------Honza

Petr s Karlem znají honzu, Honza s Karlem Petra, Petr s Honzou Karla, ale Honza nikdy nebude sedět mezi známýma.

Co se týče čtyřky je potřeba to zdůvodnit pro všechny možnosti. Tzn. zdůvodnit, že tři hrany nestačí, pět hran vždy stačí a pro čtyři hrany jsou dva možné grafy (až na izomorfizmus)

o---o
|     |
o---o

     o
     |  \
o--o---o

Pro ten první vždy rozesazení provést jde, pro ten první není splněna podmínka, že každá dvojice zná všechny zbylé

Indukce je popsaná v ↑ Kondr:.

Pokud byste chtěli hledat cyklus v grafu, ukažte nejdřív, že každý vrchol má stupeň alespoň 23 (pro každého člověka existuje max. jeden jiný člověk, který ho nezná). Pak to nějak půjde, ale rozepisovat se mi to nechce.

↑ mexx:Přesněji řečeno chceme ukázat, že každý graf
* nesplňuje podmínku, že každá dvojice dohromady zná zbytek
nebo
* lze ty lidi rozsadit kolem kruhového stolu.
Když nám protivník dá graf, tak ho musíme být schopni zařadit do jedné z těchto škatulek.

Díky indukčnímu kroku nám to stačí ukázat pro grafy na čtyřech vrcholech. A nenašl jsem elegantnější způsob, než si nakreslit všechny grafy na 4 vrcholech a ukázat, že každý patří do jedné škatulky.

↑ mexx:Dvojice zná podle zadání *alspoň* dva, v tom problém není. Máš pravdu v tom, že tento graf nevyhoví zadání, protože A a C dohromady neznají B.