Egy 16 fős társaságban 8 fiú és 8 lány található. A 16 fiatal pontosan 8 párt alkot, minden fiú pontosan egy lánnyal alkot párt, és minden fiú más és más lánnyal alkot párt. A feladatunk a párok meghatározása!

Jól látható, hogy összesen 64 lehetséges pár van, ám ebből csak 8 adja meg a megoldást.

A párokat úgy kell kitalálni, hogy egy másik személy információkkal lát el minket. Egy-egy információ azt tartalmazza, hogy egy adott fiú egy adott lánnyal NEM alkot párt. Nevezzük ezt az információt elemi kizárásnak, hiszen a 64 lehetséges párból egyet zárunk ki egy-egy ilyen információval.

Természetesen a megadott információk alapján lehetséges, hogy további párokat már logikai úton mi magunk is ki tudunk zárni, ezeket azonban NEM tekintjük elemi kizárásnak!

- Mennyi az elemi kizárások azon minimális száma, amellyel megoldható ez a feladat 8 fiú és 8 lány esetén? Indoklással! (7 pont)
- Minden esetben megoldható-e a feladat az előző kérdésben megadott számú elemi kizárás megadásával, ha semmi más információnk nincsen? Ha igen, bizonyítsuk be; ha nem, adjunk meg egy ellenpéldát! (3 pont)