Zasada szufladkowa

Hnoss · Post autor: **Hnoss** » 8 gru 2007, o 15:45

Witam,

mam problem z rozwiazaniem nastepujacych 2 zadan :
1. W klasie jest 30 uczniow. Janek w dyktandzie popełnił 13 błędów a pozostali mniej niż on. Wykazać, że w klasie jest co najmniej trzech uczniow ktorzy popelnili w dyktandzie tyle samo bledow.
2. W pola tablicy rozmiaru n na n wpisano liczby : -1,0,1 w sposob calkowicie dowolny. Czy moze sie zdazyc, ze wszystkie sumy liczb liczone pionowo, poziomo i po przekatnych sa różne?

Bylbym bardzo wdzieczny za pomoc.

UNIX_admin · Post autor: **UNIX_admin** » 8 gru 2007, o 16:23

przyjemne zadanka

1. kazda z 29 osob popelnila 0, 1, ... lub 12 bledow w najbardziej zrownowazonym przypadku 2 uczniow popelnilo 0 bledow, 2 popelnilo 1 blad, ..., 2 popelnilo 12 bledow, co daje 26 uczniow, pozostali trzej musieli osiagnac wynik z zakresu 0..12, wiec bedzie szuflada, w ktorej znajdzie sie wiecej niz 2 uczniow. zadanie jest poprawne nawet dla 28 uczniow.

2. sum jest 2n+2 bo n w pionie, n w poziomie i 2 na skos. natomiast wartosci sum mog abyc z zakresu -n .. 0 .. n, a zatem jest ich 2n+1, zatem przynajmniej jedna musi sie powtorzyc.

Hnoss · Post autor: **Hnoss** » 8 gru 2007, o 19:27

Serdecznie dziekuje za odpowiedz, jednak chodzilo mi bardziej o formalne wyprowadzanie, tj. takie przy pomocy odpowiedniego wzoru i warunku. Jesli moglbym o takie cos poprosze

Undre · Post autor: **Undre** » 8 gru 2007, o 21:21

odpowiedniego wzoru i warunku ? daj może jakieś wzorcowe rozwiązanie, bo niezbyt wiem o co biega ... no chyba, że takie coś cię zadowoli :

Dzielimy m=29 studentów pomiędzy n=13 grup pod kątem ilości błędów.
Ponieważ m>2n, na mocy zasady szufladkowej Dirichleta musi wystąpić taka grupa, której przyporządkowanych będzie co najmniej trzech studentów.