Santa Claus — modified 2021-11-22 14:06 (409 days ago) — edit — reply
Obecné řešení:
Reprezentujme úlohu jako graf, ve kterém vrcholy tvoří účastníci exkluzivního večírku a hrany tvoří páry lidí, kteří si potřásli rukama.
Jestliže na party bylo $n$ párů, má graf $2n$ vrcholů. Když se pak pan Novák ptá všech ostatních lidí, a ti odpoví každý jiné čislo, znamená to, že $2n-1$ vrcholů má každý jiný stupeň.
Stupeň vrcholů na grafu může nabývat hodnot minimálně nula a maximálně $2n-1$, protože každý vrchol může sousedit maximálně s každým ostatním.
Z těchto hodnot ale musíme vyloučit tu maximální, protože kdyby se někdo pozdravil s každým ostatním, pozdravil by se i se svým partnerem, což nelze.
Máme tedy $2n-1$ vrcholů a hodnoty $0 ... 2n-2$, což jsou přesně stejně velké množiny, z principu bijekce vyplývá, že každou hodnotu přiřadíme právě jednou.
Začněme tedy budováním grafu:
1. Někdo, osoba 1, si musel s nikým rukou nepotřást.
1. Někdo další, osoba 2, si musel potřást rukou s každým, kromě sebe a svého partnera. Aby na tuto osobu zbylo dostatek rukou, musí to být partner toho, kdo si nepotřásl rukou s nikým.
1. Někdo další, osoba 3, si musel potřást rukou s jednou osobou. Určitě si potřásl ruku s osobou 2, nepotřásl si ruku tedy s nikým jiným.
1. Někdo další, osoba 4, si musel potřást rukou s každým, kromě sebe, svého partnera a jedné další osoby, osoby 1. Aby na tuto osobu zbylo dost rukou, musí to být partner osoby 3.
...
Takto můžeme pokračovat:
pro lichá $n$:
Osoba $n$ si potřese rukou s $\frac{n-1}2$ lidmi, protože nekdo takový na večírku musí existovat, osoba $n+1$ si pak musí potřást rukou s každým kromě sebe, svého partnera a $n-1$ dalších osob, musí to být partner osoby $n$.
Takto tvoříme páry, nemůžeme při tom vybrat pana a paní Novákovi, protože nakonec nám zbyde poslední číslo, a to to prostřední $\frac{2n-2}{2}=n-1$. S tolika lidmi si pak potřásli rukama pan i paní Novákovi, protože pro každou další osobu už bylo jednoznačně určeno, s kolika lidmi si potřásla rukama, a mezi sebou si partneři Novákovi navíc potřást rukou nemůžou, je i jejich počet jednoznačně dán.
Pokud byly na večírku 4 páry, potřásli si oba dva, takže i paní Nováková, rukou s $4-1=3$ lidmi.