Kategórie:
5
6
7
8
9

Zadanie

6 vedúcich sa ide rozhodovať hlasovaním medzi 2 možnosťami, pričom každý musí všetkými svojimi hlasmi hlasovať za práve jednu z týchto možností. Na sústredku bude 7 družiniek a každá z nich má ako družinkového vedúceho práve jedného z týchto šiestich vedúcich (jeden vedúci môže byť družinkový vedúci aj viacerých družiniek). Každý vedúci má toľko hlasov, koľkým družinkám je družinkový vedúci. Navyše ale tí, ktorí nie sú vedúci žiadnej družinky, majú jeden hlas. Vedia sa vždy rozdeliť na dve skupinky tak, aby v každej skupinke malo každé možné hlasovanie jednoznačný výsledok?

Vzorové riešenie

Opravovali: Jakub26, JakubLecak, MartinŠ

Dôležitá vec, ktorú si na začiatok môžeme všimnúť je, že celkový počet hlasov sa mení podľa toho, koľko ľudí má a koľko nemá družinku (pre každého, čo nemá družinku je o jeden hlas viac).

V príklade nás zaujíma, že kedy je hlasovanie jednoznačné, takže sa pozrime najprv na to, hlasovanie je jednoznačné, keď sa v skupinke hlasy nevedia rozdeliť na dve polovice s rovnakým počtom hlasov. Napríklad sa nevedia rozdeliť keď je niekto sám, alebo je celkový počet hlasov v skupinke nepárny.

Teraz by bolo pekné vedúcich rozdeliť na 2 takéto skupinky. Toto by pekne vyšlo ak by sme pri párnom súčte hlasov odobrali jedného s nepárnym počtom a pri nepárnom počte jedného s párnym počtom hlasov, tieto prípady si teda môžeme rozobrať detailnejšie:

Keď je celkový počet hlasov párny, tak si uvedomíme, že musí existovať vedúci s jedným hlasom, lebo ak by neexistoval, tak každý vedúci by musel mať aspoň dva hlasy, teda keďže je celkovo 6​ vedúcich tak by muselo byť najmenej 12 hlasov a teda 12 družiniek, čo je v rozpore so zadaním. 

Potom vieme dať vedúceho s jedným hlasom do jednej skupinky. Keďže celkový počet hlasov je párny a do jednej skupinky sme dali vedúceho s nepárnym počtom hlasov, tak v druhej bude počet hlasov tiež nepárny a teda hlasovanie bude vždy rozhodné.

Keď je celkový počet hlasov nepárny, tak si uvedomíme, že musí existovať vedúci s párnym počtom hlasov, lebo ak by mal každý vedúci nepárny počet hlasov, tak keďže je ich 6​ tak by celkový počet hlasov bol párny (párny\ počet\ vedúcich \cdot nepárny\ počet\ hlasov\ každého = párny\ súčet), a to sme už vyššie vyriešili. 

Potom vieme dať vedúceho s párnym počtom hlasov samého do skupinky, a keďže celkový počet hlasov je nepárny, tak v druhej skupinke bude počet hlasov nepárny, a teda hlasovanie bude vždy rozhodné.

Odpoveď: 

Vieme vždy rozdeliť vedúcich do dvoch skupiniek, tak aby bolo vždy rozhodné hlasovanie v oboch skupinkách.