Egy n tagú társaságban senki sem ismeri a másikat. Meg lehetne-e ismertetni egymással néhány embert úgy, hogy bárhogyan is választunk ki három embert a társaságból, ezeknek ne legyen ugyanannyi ismerősük? Levezetné a megoldást nekem valaki?

Ez csak akkor lehetséges, ha mindenki különböző számú embert ismer (mivel ha lenne 2 olyan, akiknek azonos az ismerettségszáma, akkor azt a két embert kiválasztva már lesz olyan, hogy nem lesznek különbözőek). Egy n tagú társaságban egy ember maximum n-1 embert ismerhet (mivel önmagát ugyan mindenki ismeri, de a feladatban úgy kezeljük az ismeretséget, hogy az két ember között áll fenn). Ez azt jelenti, hogy 0-tól n-1-ig ismerheti egy ember a társaság többi tagját; 0-tól n-1-ig viszont pontosan n darab szám van, tehát mindegyik számot hozzá kell rendelnünk valamelyik emberhez.

Most jön a csavar: így lesz egy olyan ember, aki senkit sem ismer, és egy olyan, aki mindenkit, már pedig senki se ismerhet mindenkit, mivel valaki senkit sem ismer (így őt sem ismerik). Tehát 1 eshetőség lehetne arra, amit a feladat kér, az viszont nem valósul meg, tehát a kérdésre a válasz az, hogy nem.