Zasada szufladkowa - n+1 liczb niewiększych od 2n.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
bananajoe
Użytkownik
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.

Post autor: bananajoe »

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
Ostatnio zmieniony 20 sty 2008, o 20:44 przez bananajoe, łącznie zmieniany 1 raz.
Awatar użytkownika
jarekp
Użytkownik
Użytkownik
Posty: 173
Rejestracja: 7 paź 2007, o 14:40
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1 raz
Pomógł: 56 razy

Zasada szufladkowa - n+1 liczb niewiększych od 2n.

Post autor: jarekp »

Użytkownik
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.

Post autor: »

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ń.
ODPOWIEDZ