Rozsazení ke stolkům

Úloha číslo: 3434

Mějme skupinu \(n=3k\) lidí a \(k\) stolků po třech. Kolikrát je třeba rozsadit tuto skupinu ke stolkům tak, aby se každá dvojice potkala právě jednou?

Můžete předpokládat, že vhodný plán rozesazení je možný, i když to v obecnosti nemusí být pravda. Např. lze plán rozesazení najít pro sudý počet stolků? Zobecněte svoji úvahu pro \(n\)-člennou skupinu, stolky s \(s\) místy a \(t\)-tice lidí, kteří se mají potkat právě jednou.

  • Řešení

    Zvolme libovolného člena skupiny \(x\), potom je třeba zbytek skupiny rozdělit do dvojic tak, aby \(x\) zasedal s každou takovou dvojicí právě jednou. Počet potřebných rozsazení je tedy \(\frac{n-1}2\). Odtud také plyne, že \(n\) je lichý násobek tří, tedy \(k\) je liché.

    Alternativní úvaha: je třeba, aby se sešlo \(\binom{n}{2}\) dvojic, zatímco při jednom rozsazení se u každého stolku potkají tři dvojice, čili u všech stolků se během jednoho rozesazení potká celkem \(3\frac{n}3=n\) dvojic. Počet rozesazení je nyní dán podílem \(\frac{\binom{n}{2}}{n}=\frac{n-1}2\)

    Obecně se při jednom sezení u \(s\)-místného stolku sejde \(\binom{s}{t}\) \(t\)-tic, za jedno sezení u všech \(\frac{n}{s}\) stolků jde o \(\binom{s}{t}\frac{n}{s}\) \(t\)-tic. Všech \(t\)-tic je \(\binom{n}{t}\).

    Počet možných zasedacích plánů roven: \( \frac{\binom{n}{t} s}{\binom{s}{t} n}\), což nemusí vyjít celé (pak žádný vhodný plán rozsazení neexistuje).

     

    Poznámka na okraj: Jde o tzv. Steinerův systém trojic s paralelismem neboli Kirkmanův systém trojic. Ten existuje pro všechny liché násobky tří, jak bylo ukázáno v roce 1965.

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze