podzielność, liczby względnie pierwsze

[kolegasafeta]

Udowodnij, że wśród \(\displaystyle{ n+1}\) liczb wybranych spośród liczb \(\displaystyle{ 1,2,...,2n}\) znajdują się

a) co najmniej dwie liczby względnie pierwsze
b) co najmniej dwie liczby, z których jedna dzieli drugą.

Jak się za to zabrać?

[Cutlass]

To może podpowiedź. Tych par liczb poszukaj spośród \(\displaystyle{ n+1}\) ostatnich liczb:
\(\displaystyle{ n+0, n+1, n+2, \dots, n+n}\).

[yorgin]

Cutlass, Twoja podpowiedź na nic się przyda. Wybierasz dowolne spośród liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 2n}\) i wśród nich szukasz spełniających warunki zadania.

kolegasafeta, niewątpliwie trzeba użyć zasady szufladkowej.

Ukryta treść:    

Dla podzielności: Niech \(\displaystyle{ xRy}\) wtedy, gdy obie liczby \(\displaystyle{ x ,y}\) mają ten sam największy czynnik nieparzysty, lub inaczej, \(\displaystyle{ \frac{x}{y}}\) jest potęgą dwójki. Szufladkami niech będą klasy \(\displaystyle{ R}\). Ile jest szufladek? Ile liczb wrzucamy do szufladek?

[Cutlass]

Ups, sorry. Że wśród dowolnych \(\displaystyle{ n+1}\) liczb? No tak, to by było za proste.

EDIT: Na pewno wiadomo, że wybierając więcej niż połowę liczb znajdziemy tam dwie sąsiednie liczby naturalne, więc względnie pierwsze, ale z podzielnością to już jest większy problem.

[kolegasafeta]

Racja, te liczby względnie pierwsze- załatwione. Zostaje drugi podpunkt

[yorgin]

EDIT: Na pewno wiadomo, że wybierając więcej niż połowę liczb znajdziemy tam dwie sąsiednie liczby naturalne, więc względnie pierwsze, ale z podzielnością to już jest większy problem.

To rozumowanie powinno się jeszcze sformalizować.

Co do podzielności - dałem wskazówki w poprzedniej wiadomości. Pełne rozwiązanie znajduje się na wazniaku.

[Cutlass]

Dobra, to wybieramy podzbiór \(\displaystyle{ L=\{ l_0, l_1, \dots l_n \}}\) zbioru \(\displaystyle{ N= \{1,2\dots 2n \}}\). Rozważmy przypadek, że \(\displaystyle{ 1 \notin L}\). Wiemy, że dla wszystkich \(\displaystyle{ k \in \{0, 1, \dots n\}}\) zachodzi \(\displaystyle{ l_k-1 \in N}\), gdyby jednocześnie dla wszystkich \(\displaystyle{ k \in \{0, 1, \dots n\}}\) zachodziło \(\displaystyle{ l_k-1 \notin L}\), to dopełnienie \(\displaystyle{ L'}\) w zbiorze \(\displaystyle{ N}\) posiadałoby \(\displaystyle{ n+1}\) elementów, a zatem \(\displaystyle{ N}\) miałoby \(\displaystyle{ 2n+2}\) elementów - sprzeczność. Natomiast gdy w \(\displaystyle{ L}\) jest jedynka to z czymkolwiek innym będzie względnie pierwsza.