liczności przecięć, zasada szufladkowa

[kolegasafeta]

Zad: W pewnej szkole \(\displaystyle{ 64}\) uczniów bierze udział w pięciu olimpiadach przedmiotowych. W każdej z tych olimpiad uczestniczy co najmniej \(\displaystyle{ 19}\) uczniów tej szkoły, żaden nie jest uczestnikiem więcej niż trzech olimpiad. Udowodnij, że jeżli każde trzy olimpiady mają wspólnego uczestnika, to pewne dwie mają ich co najmniej pięciu.

Poproszę o jakąś wskazówkę.

[robertm19]

Każde trzy mają wspólnego uczestnika, oznacza to że 10 z uczniów startuje w trzech olimpiadach. Oznacza to także, że każde dwa mają 6 uczestników przy czym 3 wspólnych, bo np. \(\displaystyle{ A_{1} \cap A_{2} \cap A_{3} =\{a_{1}\}}\), \(\displaystyle{ A_{1} \cap A_{2} \cap A_{4} =\{a_{2}\}}\) oraz \(\displaystyle{ A_{1} \cap A_{2} \cap A_{5} =\{a_{3}\}}\). Wystarczy pokazać, że jeszcze dwóch jest wspólnych.
Rozmieszczamy pozostałych 54 uczniów w 5 olimpiadach, każdego do jednej i po równej liczbie. (jeżeli na tym etapie będziemy przypisywać więcej niz jedną olimpiadę to problem się upraszcza. ).
Po rozmieszczeniu otrzymujemy 17 uczniów w olimpiadach oznaczonych \(\displaystyle{ A_{i}}\), i=1,2,3,4 oraz 16 w \(\displaystyle{ A_{5}}\). W zadaniu jest warunek, że conjamniej 19 uczniów bierze udział w olimpiadzie, więc musimy dobrać kilku uczniów z te 54 osobowej grupy i przypisać im druga olimpiadę. (te 10 pierwszych osób już uczestniczy w trzech ).
Do \(\displaystyle{ A_{5}}\) dobieramy siedemnastego uczestnika, przy czym on już uczestniczy w olimpiadzie \(\displaystyle{ A_{1}}\) lub \(\displaystyle{ A_{2}}\) lub \(\displaystyle{ A_{3}}\) lub \(\displaystyle{ A_{4}}\). Weźmy tego z \(\displaystyle{ A_{1}}\)( bso) wtedy \(\displaystyle{ A_{5}\cap A_{1}}\) ma już 4 wspólnych.
Do \(\displaystyle{ A_{1}}\) dobieramy osiemnastego uczestnika. Bierzemy go z \(\displaystyle{ A_{2}}\) lub \(\displaystyle{ A_{3}}\) lub \(\displaystyle{ A_{4}}\). Jeśli byłby z \(\displaystyle{ A_{5}}\) to już byśmy mieli 5 wspólnych. Weźmy go z \(\displaystyle{ A_{2}}\). Więc \(\displaystyle{ A_{1}\cap A_{2}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{2}}\) postępując analogicznie dobierzmy z \(\displaystyle{ A_{3}}\). Więc \(\displaystyle{ A_{2}\cap A_{3}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{3}}\) postępując analogicznie dobierzmy z \(\displaystyle{ A_{4}}\). Więc \(\displaystyle{ A_{3}\cap A_{4}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{4}}\) postępując analogicznie dobierzmy z \(\displaystyle{ A_{5}}\). Więc \(\displaystyle{ A_{4}\cap A_{5}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{5}}\) postępując analogicznie dobierzmy z \(\displaystyle{ A_{2}}\). Więc \(\displaystyle{ A_{2}\cap A_{5}}\) ma 4 wspólnych.
Teraz zaczynamy dobierać dziewiętnastego uczestnika.
Do \(\displaystyle{ A_{1}}\) dobierzmy z \(\displaystyle{ A_{3}}\). Więc \(\displaystyle{ A_{1}\cap A_{3}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{2}}\) dobierzmy z \(\displaystyle{ A_{4}}\). Więc \(\displaystyle{ A_{2}\cap A_{4}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{3}}\) dobierzmy z \(\displaystyle{ A_{5}}\). Więc \(\displaystyle{ A_{5}\cap A_{3}}\) ma 4 wspólnych.
Do \(\displaystyle{ A_{4}}\) dobierzmy z \(\displaystyle{ A_{1}}\). Więc \(\displaystyle{ A_{1}\cap A_{4}}\) ma 4 wspólnych.
Zauważ, że w tym momencie wszystkie \(\displaystyle{ A_{i}\cap A_{j}}\) mają już 4 elementy wspólne a do \(\displaystyle{ A_{5}}\) trzeba dodac jeszcze jednego uczestnika. Więc wybierając dowolnego z pozostałych 44 uczniów któraś dwie olimpiady będą miały 5 wspólnych uczestników.

[Kamaz]

bo np. \(\displaystyle{ A_{1} \cap A_{2} \cap A_{3} =\{a_{1}\}}\),

Moim zdaniem treść zadania mówi, że ten zbiór jest co najmniej jednoelementowy a nie dokładnie jednoelementowy.

Rozmieszczamy pozostałych 54 uczniów w 5 olimpiadach, każdego do jednej i po równej liczbie.

A to w ogóle nie wynika z treści zadania.

Zastosujmy wzór włączeń i wyłączeń:

\(\displaystyle{ |A_1\cup A_2\cup A_3\cup A_4\cup A_5|=\sum_i|A_i|-\sum_{i,j}|A_i\cap A_j|+\sum_{i,j,k}|A_i\cap A_j\cap A_k|,}\)

\(\displaystyle{ \sum_{i,j}|A_i\cap A_j|=\sum_i|A_i|+\sum_{i,j,k}|A_i\cap A_j\cap A_k|-|A_1\cup A_2\cup A_3\cup A_4\cup A_5|\ge\\\\\ge5\cdot19+10\cdot1-64.}\)

Dalej wystarczy skorzystać z zasady szufladkowej.

[robertm19]

bo np. \(\displaystyle{ A_{1} \cap A_{2} \cap A_{3} =\{a_{1}\}}\),

Moim zdaniem treść zadania mówi, że ten zbiór jest co najmniej jednoelementowy a nie dokładnie jednoelementowy.

Rozmieszczamy pozostałych 54 uczniów w 5 olimpiadach, każdego do jednej i po równej liczbie.

A to w ogóle nie wynika z treści zadania.

No tak może być więcej niż jeden, ale w najgorszym wypadku jest jeden w innych łatwo jest wykazać. To samo tyczy sie 54 uczniów. Rozważyłem "najgorszy" przypadek, czyli przypadek w którym jest tylko jedna taka dwójka i ma dokładnie 5 elementów.
Ale przyznam że twoje rozwiązanie jest klarowne i krótkie

[kolegasafeta]

Świetny pomysł, żeby użyć do tego wzoru włączeń i wyłączeń : ) To już będzie czepianie się szczegółów, ale to się chyba nazywa "uogólniona zasada szufladkowa Dirichleta".