2002 personen
Opgave - APMC 2002 dag 3 vraag 3
Een verzameling $P$ van 2002 personen is gegeven. De familie van deelverzamelingen van $P$ die precies 1001 personen bevatten heeft de volgende eigenschap: het aantal koppels dat elkaar kent in iedere deelverzameling is gelijk (in de veronderstelling dat elkaar kennen een symmetrische relatie is). Vind het minimum aantal koppels personen die elkaar kennen in de verzameling $P$, als er minstens 1 zo'n koppel is.
- login om te reageren
Oplossing
Ofwel bestaat er een groep van 1001 mensen waarin niemand $A$ kent, ofwel bestaat er een groep van 1001 mensen waarin iedereen $A$ kent. Stel het eerste en noem die verzameling $U$.
Neem een $S\subset U$ van 1000 mensen. A heeft geen kennissen in die groep, dus geen enkel van de andere elementen heeft een kennis in die groep, dus ook niet het 1001-de element. Herhalen we dit voor alle $S\subset U$ krijgen we dat $U$ geen kennisrelaties bevat, dus iedereen heeft 0 kennissen.
In het tweede geval krijgen we analoog dat iedereen elkaar kent. De opgave zegt dat er minstens 1 kenniskoppel is, dus we zitten in dat 2e geval, dus minimaal $\binom{2002}{2}$ kennissenkoppels. :cool: