Na spotkaniu było \(\displaystyle{ 201}\) osób z pięciu państw. Wśród dowolnych sześciu osób istnieją jacyś rówieśnicy. Udowodnić, że istnieje co najmniej pięciu rówieśników z tego samego państwa i tej samej płci.
Zadanie nr 1 z finału 29. hiszpańskiej olimpiady matematycznej 1993.
... limp93.htm
Jest tam też na dole link do rozwiązań.
Moje rozwiązanie jest trochę długie:
Rozwiązanie:
Mamy \(\displaystyle{ 201}\) osób i \(\displaystyle{ 5}\) państw - z ZSD istnieje państwo, z którego pochodzi min. \(\displaystyle{ 41}\) osób. Bierzemy to państwo. Mamy \(\displaystyle{ 41}\) osób i dwie możliwe płcie - z ZSD istnieje płeć, w której jest min. \(\displaystyle{ 21}\) osób. Trzeba pokazać, że wśród tych \(\displaystyle{ 21}\) osób, które są z tego samego państwa i tej samej płci istnieje \(\displaystyle{ 5}\) osób, które są rówieśnikami. Ponumerujmy te osoby \(\displaystyle{ A_{1}}\), \(\displaystyle{ A_{2}}\), ..., \(\displaystyle{ A_{21}}\). To co piszę dalej można narysować jako graf (\(\displaystyle{ 21}\) wierzchołków, krawędź to bycie rówieśnikiem). Relacja bycia rówieśnikiem jest przechodnia, więc jeżeli mam drzewo rozpinające to mogę zrobić z niego klikę dodając wszystkie możliwe krawędzie. No a jeżeli nie chcemy robić grafu, to można myśleć o grupach rówieśników jak o zbiorach.
Bierzemy pewne \(\displaystyle{ 6}\) osób, wiemy że dwie są rówieśnikami bso. \(\displaystyle{ A_{1}A_{2}}\) są rówieśnikami. Dalej bierzemy pewne \(\displaystyle{ 6}\) z pozostałych \(\displaystyle{ A_{3}}\),\(\displaystyle{ A_{4}}\)...\(\displaystyle{ A_{21}}\) i bso \(\displaystyle{ A_{3}A_{4}}\) są rówieśnikami itd. powtarzamy konstruując pary rówieśników \(\displaystyle{ A_{5}A_{6}}\), \(\displaystyle{ A_{7}A_{8}}\), ..., \(\displaystyle{ A_{15}A_{16}}\) (potem zostaje nam \(\displaystyle{ 5}\) osób, więc nie możemy ich wziąć i zrobić pary).
Dalej bierzemy \(\displaystyle{ A_{1},A_{3},A_{5},A_{7},A_{9},A_{11}}\) z tego bso \(\displaystyle{ A_{1}A_{3}}\) się znają (mamy czwórkę \(\displaystyle{ A_{1}A_{2}A_{3}A_{4}}\) rówieśników). Bierzemy \(\displaystyle{ A_{5},A_{7},A_{9},A_{11},A_{13},A_{15}}\) z tego bso. \(\displaystyle{ A_{5}A_{7}}\) są rówieśnikami (mamy kolejną czwórkę rówieśników).
Dalej bierzemy \(\displaystyle{ A_{1},A_{5},A_{9},A_{11},A_{13},A_{15}}\). Gdyby \(\displaystyle{ A_{1}}\) lub \(\displaystyle{ A_{5}}\) był rówieśnikiem z którymś z pozostałych z tej szóstki, to mamy piątkę rówieśników wpp. bso \(\displaystyle{ A_{9}A_{11}}\) są rówieśnikami i mamy kolejną czwórkę rówieśników. Bierzmy po jednym z każdej z trzech czwórek oraz \(\displaystyle{ A_{17},A_{18},A_{19}}\) - jeżeli któryś z pierwszych trzech jest rówieśnikiem z którymś z pozostałych z tej szóstki - mamy piątkę, wpp bso niech \(\displaystyle{ A_{17}A_{18}}\) będą rówieśnikami. Analogicznie biorąc po jednym z trzech czwórek i trójkę \(\displaystyle{ A_{21},A_{20},A_{19}}\) mamy bso, że \(\displaystyle{ A_{19}A_{20}}\) są rówieśnikami. Weźmy \(\displaystyle{ A_{1},A_{5},A_{13}, A_{15},A_{17},A_{19}}\) - jeżeli \(\displaystyle{ A_{1}}\) lub \(\displaystyle{ A_{5}}\) mają rówieśnika w tej szóstce to koniec, wpp niech bso. \(\displaystyle{ A_{13}A_{15}}\) będą rówieśnikami - mamy kolejną czwórkę rówieśników. Dalej weźmy po jednym z każdej z czterech czwórek, które mamy oraz \(\displaystyle{ A_{17}A_{19}}\) - jeżeli ktoś z tej czwórki jest rówieśnikiem z którymś pozostałych z tej szóstki - koniec, wpp. \(\displaystyle{ A_{17}A_{19}}\) są rówieśnikami - mamy piątą czwórkę rówieśników. Bierzmy po jednym z każdej z tych czwórek rówieśników oraz \(\displaystyle{ A_{21}}\) - w ten sposób któraś z osób należących do pewnej czwórki musi być rówieśnikiem z kimś spoza swojej czwórki - ostatecznie mamy piątkę rówieśników, cnd.
To jest ala wzorcówka:
Rozwiązanie 2:
Jak poprzednio dochodzimy do tego, że min. \(\displaystyle{ 21}\) osób jest z tego samego państwa i ma tą samą płeć.
Wiemy, że wśród dowolnych sześciu pewne dwie są rówieśnikami. Z tego wynika, że jest co najwyżej pięć różnych wieków, które mogą mieć osoby - gdyby takich wieków mogło być min. sześć, to po podzieleniu osób na min. sześć grup o różnych wiekach i wzięciu jednej osoby z każdej z tych grup dostaniemy min. sześć osób, z których każda ma inny wiek - sprzeczność z założeniem.
Skoro tak, to wśród tych \(\displaystyle{ 21}\) osób z ZSD istnieje grupa złożona z min. pięciu osób o tym samym wieku, cnd.