Dirichlet Za mała szufladka: Zadanie z zasady szufladkowej: Jest n drużyn piłkarskich. Każde dwie mają rozegrać jeden mecz. Wykorzystując zasadę szufladkową wykaż, że w dowolnym momencie rozgrywek istnieją co najmniej dwie drużyny, które rozegrały już tę samą liczbę meczów. Moje rozumowanie: Jest n drużyn więc każda rozegra n−1 meczów(każda gra 1 mecz z każdą). Więc mamy od <0,n−1> szufladek. Jak mam teraz to ugryźć? Jak wykorzystać tu tę zasadę?

kochanus_niepospolitus: Ja bym to wykazał w ten sposób. Skoro mamy 'n' drużyn i każda musi gra jeden mecz z każdą inną drużyną (czyli maksymalnie rozgrywa (n−1) meczy), to jedyna możliwość aby minimum dwie drużyny nie miały takiej samej liczby rozegranych meczy jest wtedy gdy: 1 drużyna ma 0 meczy, 2 drużyna ma 1 mecz, 3 drużyna ma 2 mecze, ... n−1 drużyna ma n−2 mecze, n drużyna ma n−1 mecze rozegrane. Skoro n'ta drużyna ma rozegrane n−1 meczy, to znaczy że grała z każdą pozostałą drużyną, w tym także z 1 drużyną. Więc 1 drużyna nie może mieć 0 spotkań na koncie. Sprzeczność. Dodatkowo należy uzasadnić dlaczego to jest jedyna sytuacja kiedy n drużyn może mieć inną ilość rozegranych meczy.

Za mała szufladka: Dzięki znalazłem też rozwiązanie w kisążce Biggsa, ale co masz na myśli pisząc "uzasadnić dlaczego to jest jedyna sytuacja kiedy n drużyn może mieć inną ilość rozegranych meczy", przecież skoro szufladek jest <0,n−1> i drużyn jest n czyli tyle samo ile szufladek to inny rozkład, drużyn z inną ilością rozegranych meczy jest niemożliwy.

kochanus_niepospolitus: i to jest właśnie to uzasadnienie