vergadering
Opgave - USAMO 1978 vraag 5
Er zijn negen gedelegeerden op een conferentie, en éénieder spreekt maximum drie talen. Als je weet dat onder elke drie gedelegeerden er minimum twee een gemeenschappelijke taal spreken, toon dan aan dat er drie gedelegeerden zijn met een gemeenschappelijke taal.
- login om te reageren
Oplossing
Nummer de gedelegeerden van 1 t.e.m. 9.
Geval 1
Stel dat ieder koppel gedelegeerden een gemeenschappelijke taal heeft.
Dan zijn er $8$ gedelegeerden met een gemeenschappelijke taal met gedelegeerde 1.
Daar 1 slechts $3$ talen spreekt, zal er wegens het duivenhokprincipe een gemeenschappelijke taal met min. $3$ anderen zijn.
Dus zouden er $4$ personen die taal kunnen.
Geval 2
Stel dat niet ieder koppel gedelegeerden een gemeenschappelijke taal heeft.
bvb. gedelegeerde 1 en 9 hebben geen gemeenschappelijke taal .
Dan moet elke andere gedelegeerde een taal gemeenschappelijk hebben met 1 of met 9.
Er zijn $7$ gedelegeerden te verdelen (2 t.e.m. 8). Dat wil zeggen dat minstens $4$ een gemeenschappelijke taal hebben met 1 of alle vier met 9. Laten we voor het gemak zeggen dat er hiervan $4$ een taal gemeenschappelijk hebben met 1 (en anders verwissel je 1 en 9).
Dit zorgt in totaal voor $5$ personen (deze $4$+ nummer 1).
Persoon 1 kan maximaal $3$ talen spreken. Zo kan hij zorgen dat persoon 2,3 en 4 elk een taal gemeenschappelijk met hem kunnen hebben, zonder dat 3 personen eenzelfde taal spreken.
Maar volgens het ladenprincipe kunnen we de 5e persoon niet thuisbrengen zonder dat er $3$ personen eenzelfde taal spreken.
Q.E.D.