Tämä menee nyt vähän kyllä matikan puolelle, mutta ongelma taitaa olla tuttu kuitenkin niille, jotka ovat tietotekniikkaa lukeneet. Eli miten ratkaistaan diskreetin matematiikan tehtävä tuttavuusrelaatiosta: Osoita että missä tahansa n > 1 henkilön ryhmässä on ainakin kaksi jäsentä, jotka ovat tuttuja tasan yhtä monen ryhmään kuuluvan henkilön kanssa. Omaa itseä ei lueta tuttujen joukkoon ja tuttavuusrelaatio on symmetrinen, niin että jos a on b:n tuttu on myös b a:n tuttu. Kyyhkyslakkaperiaatetta pitäisi käyttää mutta miten?
Tuttavuusrelaatio
Matikka
1136
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 1
Vanhimmat
Jos n 1 esinettä sijoitetaan umpimähkään n:ään laatikkoon, tulee johonkin laatikkoon vähintään kaksi esinettä.
Tai hieman monimutkaisemmin (jos k > 1):
Jos kn 1 esinettä sijoitetaan umpimähkään n:ään laatikkoon, tulee johonkin laatikkoon vähintään k 1 esinettä.
Periaatetta voi havainnollistaa kuvittelemalla vaikkapa 201 palloa, jotka tulee sijoittaa sataan laatikkoon mahdollisimman tasapuolisesti. 200 pallon jälkeen jokaisessa laatikossa on kaksi palloa, ja yksi pallo on vielä sijoittamatta. Johonkin laatikkoon siis välttämättä tulee kolme palloa. Jos pallot sijoitetaan umpimähkään, voi tilanne olla mikä hyvänsä (esim. kaikki pallot voivat joutua samaan laatikkoon), mutta aina löytyy laatikko, jossa on vähintään kolme palloa.