Í skóla nokkrum eru $1000$ nemendur. Í skólanum er kenndur fjöldi tungumála.
Hver nemandi lærir í mesta lagi $5$
tungumál. Svo vill til, að í sérhverjum hópi þriggja nemenda
er hægt að finna tvo sem læra sama tungumálið.
Sýnið að hægt sé að finna að minnsta kosti $100$ nemendur sem læra allir sama tungumálið.
Lausn
Tökum einhvern nemanda $A$. Fyrst skulum við gera ráð fyrir að
ekki sé til nemandi $B$ þannig $B$ læri ekkert þeirra tungumála sem $A$
lærir. Þá lærir sérhver nemandi að minnsta kosti eitt þeirra tungumála
sem $A$ lærir. Því má skipta nemendunum í hópa, jafnmarga og tungumálin
eru sem $A$ lærir
þannig að allir nemendurnir í hverjum hópi læri eitthvert tiltekið mál
sem $A$ lærir.
Nú lærir $A$ í mesta lagi $5$ tungumál og þegar $1000$ nemendum
er skipt í hópa, $5$ eða færri, þá er gulltryggt að í einhverjum
hópnum verða að minnsta kosti $100$ nemendur.
Gerum nú ráð fyrir að til sé nemandi $B$ sem lærir ekkert þeirra
tungumála sem $A$ lærir. Þá segir skilyrðið í dæminu okkur að allir
nemendur skólans læri að minnsta kosti eitt þeirra tungumála sem $A$ og
$B$ læra. Samanlagt læra $A$ og $B$ í mesta lagi $10$ tungumál. Nú getum
við eins og áður skipt nemendunum í hópa, ekki fleiri en $10$, þannig að
allir nemendur í sama hópi læri eitthvert tiltekið tungumál sem
annaðhvort $A$ eða $B$ læra. Þá er ljóst að í
einhverjum hópnum verða að minnsta kosti $100$ nemendur.