Matematyka.pl

Załóżmy że danych jest \(\displaystyle{ n+1}\) różnych liczb ze zbioru \(\displaystyle{ \left\{ 1,2,3...2n\right\}}\)Udowodnij ze wsrod tych liczb istnieja dwie liczby względne pierwsze.
ma ktoś pomysł?

Ja bym do tego podszedł tak: jeśli wśród tych liczb znalazła się liczba \(\displaystyle{ 1}\), to teza jest oczywista. Powiedzmy, że nie wybraliśmy jedynki. Wówczas mamy \(\displaystyle{ n+1}\) liczb ze zbioru \(\displaystyle{ \left\{ 2, \ldots 2n\right\}}\) i przypuśćmy nie wprost, że nie ma wśród nich dwóch liczb względnie pierwszych. Ponieważ \(\displaystyle{ \NWD(k, k+1)=1}\), zatem jeśli wybrano liczbę \(\displaystyle{ k}\), to nie mogła zostać wybrana liczba \(\displaystyle{ k+1}\). Wybraliśmy też co najmniej \(\displaystyle{ n}\) liczb mniejszych od \(\displaystyle{ 2n}\) i dla każdej z nich wykluczamy jej następnik – w ten sposób wykluczamy \(\displaystyle{ n}\) spośród liczb \(\displaystyle{ 2, \ldots 2n}\). Mamy więc \(\displaystyle{ n}\) wybranych mniejszych niż \(\displaystyle{ 2n}\) i \(\displaystyle{ n}\) wykluczonych spośród \(\displaystyle{ \left\{ 2\ldots 2n\right\}}\), czyli łącznie \(\displaystyle{ 2n}\), ale w zbiorze \(\displaystyle{ \left\{ 2, \ldots 2n\right\}}\) jest tylko \(\displaystyle{ 2n-1}\) liczb, sprzeczność.-- 23 kwi 2018, o 20:38 --A indukcyjnie to potrafię zrobić tylko korzystając z Twierdzenia o Dowodzie przez Założenie Tezy.

Jeżeli nie chcesz za pomocą indukcji to :
Załóżmy, że nie wybraliśmy \(\displaystyle{ 1}\).
Oznaczmy te liczby jako \(\displaystyle{ 2 \le x_{1} < x_{2} < ... , x_{n+1}}\), jeżeli liczby te mają wspólny dzielnik, oznaczmy \(\displaystyle{ k \ge 2}\), to zachodzi \(\displaystyle{ x_{i} = ky_{i}}\) dla \(\displaystyle{ i = 1 , 2, ... , n + 1}\), gdzie \(\displaystyle{ 1 \le y_{1} < ... < y_{n+1}}\). W takim wypadku zachodzi \(\displaystyle{ y_{n+1} \ge n + 1}\), skąd \(\displaystyle{ x_{n+1} = ky_{n+1} \ge 2\left( n + 1\right) > 2n}\), co daje sprzeczność.

Zahion, nie rozumiem niestety Twojego rozwiązania. Przecież takie sformułowanie, jakie podałeś, sugeruje, że zakładasz nie wprost, iż \(\displaystyle{ \NWD(x_1, \ldots x_n)=k>1}\), a to jest coś o wiele mocniejszego niż założenie, że dla każdych dwóch spośród liczb \(\displaystyle{ x_1, \ldots x_n}\) ich \(\displaystyle{ \NWD}\) przekracza \(\displaystyle{ 1}\), i jak na mój gust nie prowadzi to do tezy zadania.
Np. \(\displaystyle{ \NWD(2,3,6)=1}\), ale wśród liczb \(\displaystyle{ 2,3,6}\) nie ma pary liczb względnie pierwszych.
Ale pewnie znowu to ja czegoś nie pojmuję.

Pokaz, że wśród wybranych liczb muszą być co najmniej dwie kolejne.

Premislav, tak, niestety kilka razy z rzędu zmieniałem wersje, włącznie z usunięciem wiadomości ze względu na pośpiech i niedociągnięcia, ale pierwotnie ( po modyfikacji ) wyszedłem od \(\displaystyle{ \left( x_{j}, x_{j+1} \right) = 2}\) w przeciwnym wypadku sprzeczność ze względu na szacowanie \(\displaystyle{ x_{n+1}}\) ( a z powyższego właśnie \(\displaystyle{ \left( x_{1}, ... x_{n+1} \right) \ge 2}\) ), chociaż już szacowanie \(\displaystyle{ x_{j+1} - x_{j} \ge 2}\) ( nie mogą być kolejne ) daje \(\displaystyle{ x_{n+1} \ge x_{1} + 2n}\), a tutaj miałem obliczeniowy, więc obrałem pierwotną drogę.

Kombinacje, kombinacje,...

Dzielimy liczby na pary: \(\displaystyle{ (1,2)}\), \(\displaystyle{ (3,4)}\), ..., \(\displaystyle{ (2n-1,2n)}\).

Par jest \(\displaystyle{ n}\) liczb jest \(\displaystyle{ n+1}\), wiec przynajmniej dwie z nich muszą należeć do jednej pary. Te właśnie są względnie pierwsze.