Feladat: 16.20.
Egy értekezletre két delegáció érkezik,
A és
B, mindkettőnek ugyanannyi tagja van. A két delegáció tagjai közül némelyek már ismerik egymást. Bizonyítsuk be, hogy az
A delegációból kiválasztható néhány ember (legalább egy) úgy, hogy a
B delegáció minden tagja páros sokat ismer a kiválasztottak közül, vagy úgy, hogy minden tagja páratlan sokat ismer a kiválasztottak közül.
Megoldás: 16.20
Legyen
A és
B tagszáma
n. Tekintsük
A összes nem üres részhalmazát; ezek száma
2n
-1. Minden ilyen részhalmazhoz rendeljünk hozzá egy
n hosszúságú 0-1 sorozatot: ennek
i-edik eleme 0, ha a
B delegáció
i-edik tagja a részhalmazból páros sokat ismer, és 1, ha páratlan sokat. Ha az így kapott
n hosszú 0-1 sorozatok között előfordul a csupa-0 vagy a csupa-1, akkor kész vagyunk. Ellenkező esetben van a sorozatok között két egyforma. Tartozzon a két egyforma sorozat a
C és a
D részhalmazhoz. Vegyük
C és
D szimmetrikus differenciáját, legyen ez az
E részhalmaz.
E nem üres, mert
C és
D különböző. Megmutatjuk, hogy
E megfelelő részhalmaz.
Azt fogjuk megmutatni, hogy a
B delegáció minden tagja páros sok
E-beli embert ismer.
Ha a
B delegáció
i-edig tagja
C-ből
c(i),
D-ből
d(i) embert ismer, s ebből
k(i) van
C és
D közös részében, akkor
E-ből
c(i)+d(i)-2k(i) embert ismer. De
c(i) és
d(i) paritása azonos, hiszen a
C-hez és a
D-hez tartozó 0-1 sorozat megegyezik. Ezért a
B delegáció
i-edik tagja
E-ből páros sok embert ismer. Ezt akartuk bizonyítani.