Riešky tábor - Milí naši Rieškari, ako je už zvykom, aj tento rok sme si pre Vás pripravili Letný tábor Riešok. Je to desaťdňová akcia počas ktorej sa zabavíte, niečo naučíte a hlavne … Prejsť na článok
×10. príklad - Vzorové riešenie
Zadanie
Raz, keď išiel domov, zbieral po ceste minerály, ktoré našiel na zemi. Keď prišiel domov, spočítal ich a roztriedil ich podľa farieb. Teraz by ich rád uložil do krabíc takým spôsobom, aby zostali čo najroztriedenejšie ako sa dá.
Hutton nazbieral n^2 minerálov najviac n rôznych farieb (ale nie nutne n minerálov z každej farby). Chce ich rozmiestniť do n krabíc. Dokážte, že vie do každej krabice dať n minerálov tak, aby v každej krabici boli minerály najviac dvoch rôznych farieb.
Vzorové riešenie
Vo vzorovom riešení budeme využívať rozšírený Dirichletov princíp. Ak máme n pretmetov k typov, tak existuje nejaký typ, že ho je najviac \lfloor \frac{n}{k} \rfloor predmetov a nejaký typ, ktorého je aspoň \lceil \frac{n}{k} \rceil predmetov.
Ďalej budeme predpokladať, že kameňov je presne n rôznych farieb, pričom ak by ich v skutočnosti bolo menej ako n, tak môžene doplniť farby, ktoré budú mať 0 kameňov.
Pozrime sa na farbu A, ktorej je najmenej kameňov, počet týchto kameňov je najviac n, lebo máme n^2 kameňov a n farieb. Ďalej sa pozrime na farbu B, ktorej kameňov je najviac, počet týchto kameňov je aspoň n, lebo máme n^2 kameňov a n farieb. Teraz vložíme všetky kamene farby A a všetky voľné miesta doplníme kameňmi farby B. Toto bude vždy možné, lebo kapacita jednej krabice je n a kameňov farby A je najviac n a kameňov farby B je aspoň n.
Zbavili sme sa n kameňov, 1 farby a 1 krabice, takže nám ostáva n(n-1) kameňov, n-1 farieb a n-1 krabíc. Znovu môžeme zopakovať popísaný proces, lebo farby, ktorej kameňov je najmenej je najviac n a farby, ktorej je najviac kameňov je aspoň n kameňov. Znovu sa zbavíme n kameňov, 1 farby a 1 krabice, ostane nám n(n-2) kameňov, n-2 farieb a n-2 krabíc.
Tento proces môžeme opakovať kým sa nám neminú všetky kamene, lebo po vykonaní tohto procesu k-krát budeme mať n(n-k) kameňov, n-k farieb a n-k krabíc. Teda stále bude platiť, že farby ktorej kameňov je najmenej je najviac n a farby, ktorej je najviac kameňov je aspoň n kameňov. Takže stále sa budeme môcť pomocou každej krabice zbaviť n kameňov a jednej farby.