verkiezingen
Opgave - CanMO 1972 vraag 8
Tijdens een verkiezingscampagne worden er $p$ verschillende beloftes gemaakt door de verschillende politieke partijen ($p>0$). Terwijl verscheidene partijen dezelfde beloftes mogen maken, hebben elke twee partijen op zijn minst één belofte gemeenschappelijk. Er zijn ook geen twee partijen met exact dezelfde verzameling beloftes. Bewijs dat er niet meer dan $2^{p-1}$ partijen zijn.
- login om te reageren
Oplossing
Veronderstel dat er meer dan $2^{p-1}$ partijen zijn.
Bekijk dan de beloftes van $2^{p-1}+1$ verschillende partijen samen met de voorstellenbundel ("antibundels" ) met exact de tegenovergestelde voorstellen.
Dan hebben we minimaal $2^p+2$ voorstellenbundels, terwijl er slechts $2^p$ mogelijkheden waren.
Volgens het duivenhokprincipe zijn er dus $2$ bundels gelijk.
Deze kunnen niet beide van een partij zijn of beide "antibundels" zijn wegens de voorwaarden.
Dus volgt dat een bundel van de ene partij gelijk zal zijn aan de antibundel van de andere en dus hebben ze geen enkel voorstel gemeenschappelijk.