Miło by było jakby mi ktoś to zadanie rozwiązał i mniej więcej wytłumaczył co i jak Z góry dziękuje
Załóżmy, że danych jest n+1 różnych dodatnich liczb całkowitych mniejszych bądź równych 2n. Pokaż, że :
1) istnieje para liczb, których suma liczb wynosi 2n+1
2) muszą istnieć dwie liczby, które są względnie pierwsze (tj. nie maja wspólnego dzielnika większego od 1)
3) istnieje liczba, która jest wielokrotnością innej liczby
Zasada szufladkowa - n+1 liczb niewiększych od 2n.
-
- Użytkownik
- Posty: 7
- Rejestracja: 20 sty 2008, o 16:34
- Płeć: Mężczyzna
- Lokalizacja: Inowrocław
Zasada szufladkowa - n+1 liczb niewiększych od 2n.
Ostatnio zmieniony 20 sty 2008, o 20:44 przez bananajoe, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Zasada szufladkowa - n+1 liczb niewiększych od 2n.
W linkowanym wątku nie ma rozwiązania zadania trzeciego, które zresztą istotnie jest trudniejsze od pozostałych z tej serii.
Zapiszmy każdą liczbę ze zbioru \(\displaystyle{ \{ 1,2, \dots, 2n \}}\) jako \(\displaystyle{ 2^k p}\), gdzie \(\displaystyle{ p}\) jest nieparzyste. Ponieważ dla dowolnej liczby musi być \(\displaystyle{ p \{ 1,3, \dots, 2n-1 \}}\), a ten zbiór ma \(\displaystyle{ n}\) elementów, to jeśli wybierzemy \(\displaystyle{ n+1}\) liczb ze zbioru wyjściowego, to pewne dwie będą miały równe \(\displaystyle{ p}\), czyli będą postaci \(\displaystyle{ 2^n p}\) i \(\displaystyle{ 2^m p}\). To zaś oznacza, że jedna musi dzielić drugą, co kończy dowód.
Podobno to zadanie dawał Paul Erdös swoim podopiecznym na początku współpracy, by przetestować ich zdolności twórczego myślenia .
Pozdrawiam.
Qń.
Zapiszmy każdą liczbę ze zbioru \(\displaystyle{ \{ 1,2, \dots, 2n \}}\) jako \(\displaystyle{ 2^k p}\), gdzie \(\displaystyle{ p}\) jest nieparzyste. Ponieważ dla dowolnej liczby musi być \(\displaystyle{ p \{ 1,3, \dots, 2n-1 \}}\), a ten zbiór ma \(\displaystyle{ n}\) elementów, to jeśli wybierzemy \(\displaystyle{ n+1}\) liczb ze zbioru wyjściowego, to pewne dwie będą miały równe \(\displaystyle{ p}\), czyli będą postaci \(\displaystyle{ 2^n p}\) i \(\displaystyle{ 2^m p}\). To zaś oznacza, że jedna musi dzielić drugą, co kończy dowód.
Podobno to zadanie dawał Paul Erdös swoim podopiecznym na początku współpracy, by przetestować ich zdolności twórczego myślenia .
Pozdrawiam.
Qń.