[Kombinatoryka] Przyjaciele finalistów

[Utumno]

W finale LXIII Olimpiady Matematycznej uczesniczy 104 finalistów. Udowodnij, że istnieje takich dwóch, którzy mają parzystą liczbę wspólnych znajomych.

[timon92]

warunki zadania spełniają Marcin Fryz i Adam Baranowski - istotnie, nie mają oni kolegów, zatem liczba ich wspólnych znajomych jest równa \(\displaystyle{ 0}\), więc jest parzysta

[Utumno]

Rozwiązanie też oceniam na parzyste zero

[adamm]

jak dla mnie 6p

[kaszubki]

warunki zadania spełniają Marcin Fryz i Adam Baranowski - istotnie, nie mają oni kolegów, zatem liczba ich wspólnych znajomych jest równa \(\displaystyle{ 0}\), więc jest parzysta

Ale w treści jest mowa o znajomych, a to nie jest to samo.

[Marcinek665]

jak dla mnie 6p

No ja bym dla zasady ściął do 5p.

[adamm]

odłożę moze na chwilę życie forumowego celebryty i wrzucę jednak jakieś rozwiązanie egzystencjalne.
Weźmy se jakąkolwiek parzystą ilość finalistów. Przez \(\displaystyle{ P(A)}\) będę oznaczał zbiór przyjaciół finalisty \(\displaystyle{ A}\). Najpierw lemacik jeśli \(\displaystyle{ 2\nmid |P(A) \cap P(B)|}\) dla dowolnych różnych OMowców A i B to każdy OMowiec ma parzystą liczbę znajomych. Dla dowodu ustalmy sobie jakiegoś finalistę A i rozpatrzmy zbiór P(A), a teraz graf G indukowany przez P(A) i dowolnego znajomego B naszego finalisty A. Przekrój P(A) i P(B) ma zgodnie z założeniami nieparzystą ilosć elementów, ale w takim razie z twierdzenia o usciskach dłoni Eulera mamy, że nasz indukowany graf ma parzystą liczbę wierzchołków co po rozciągnięciu na wszystkie grafy indukowane w ten sposób kończy dowód lematu.
Dobra zatem załóżmy, że nasza teza nie zachodzi, więc z lematu wiemy, że każdy omowiec ma parzystą liczbę znajomych. Weźmy sobie znowu jakiegoś finalistę A, oznaczmy przez Q(A) zbiór finalistów których A nie zna. Łatwo zauważyć że zgodnie z naszym załozeniem nie wprost Q także musi mieć nieparzystą liczbę elementów. Weźmy sobie teraz jakiegoś finalistę \(\displaystyle{ B\in P(A)}\), mamy \(\displaystyle{ P(B)=(P(B) \cap P(A)) \cup (P(B) \cap Q(A)) \cup \{A\}}\) zbiory które sumujemy są rozłączne, więc \(\displaystyle{ |P(B)|=|(P(B) \cap P(A)) |+|(P(B) \cap Q(A)) |+| \{A\}|}\), a więc można zauważyć, że \(\displaystyle{ |P(B) \cap Q(A)|}\) jest liczbą parzystą. Rozpatrzymy sobie teraz zbiór E znajomości (krawędzi) pomiędzy zbiorem P(A) i Q(A). Z jednej strony mamy rozkład na sumę parami rozłącznych podzbiorów \(\displaystyle{ E= \bigcup_{C\in P(A)}(P(C) \cap Q(A))}\), a więc E jako suma rozłącznych parami, parzystej mocy zbiorów też musi mieć parzystą moc. Policzmy jednak także E z drugiej strony \(\displaystyle{ E= \bigcup_{C\in Q(A)}(P(C) \cap P(A))}\), znowu mamy sumę parami rozłącznych zbiorów, ale zgodnie z przyjętą wcześniej nieparzystością mocy przekrojów P(A) i P(B) dla różnych osob A,B, mamy powyżej (po przejściu na sumowanie po mocach) sumę iluś tam liczb nieparzystych, ale E jak już ustaliliśmy ma parzystą moc, więc musimy zsumować te liczby nieparzyste parzystą ilość razy, ale skoro sumujemy po elementach \(\displaystyle{ Q(A)}\) to oznacza to, ze \(\displaystyle{ |Q(A)|}\) jest parzyste, sprzecznośc z założeniem .

[Utumno]

To oceniam na parzyste 6p.