Matematyka.pl

Spośród liczb \(\displaystyle{ 1,2,3,...,199,200}\) wybrano \(\displaystyle{ 101}\) liczb. Dowieść, że wśród nich są dwie takie, że jedna jest dzielnikiem drugiej.

Jak to zrobić? Może mi ktoś pomóc?

Ok, czy to się opiera na tym, że do zbioru tych \(\displaystyle{ 101}\) liczb należy przynajmniej jedna liczba parzysta. I do tego zbioru \(\displaystyle{ 101}\) liczb należy też przynajmniej jedna liczba, która jest dzielnikiem tej liczby parzystej? O to chodzi?

Każda liczba całkowita dodatnia \(\displaystyle{ n}\) jednoznacznie zapisuje się w postaci \(\displaystyle{ s \cdot 2^k}\), gdzie \(\displaystyle{ s}\) jest nieparzyste. Jeśli \(\displaystyle{ 1 \le n \le 200}\), to \(\displaystyle{ s \in \{ 1, 3, 5, \ldots, 199 \}}\). Zatem z zasady szufladkowej dwie spośród wybranych liczb mają to samo \(\displaystyle{ s}\).

Dasio11 pisze: 14 sie 2023, o 20:18 Każda liczba całkowita dodatnia \(\displaystyle{ n}\) jednoznacznie zapisuje się w postaci \(\displaystyle{ s \cdot 2^k}\), gdzie \(\displaystyle{ s}\) jest nieparzyste.

Zaskoczyłeś mnie tym faktem, wczoraj na dobranoc to zauważyłem, nie znałem tego faktu (no cóż, może po wieczne czasy będę odkrywał podstawy matematyki ).

Uogólniłem dzisiaj ten fakt, zastępując dwójkę, dowolną pierwszą, a warunek 'bycia liczbą nieparzystą' można zastąpić równoważnym warunkiem '\(\displaystyle{ 2}\) nie dzieli tej liczby', i ten fakt uogólniłem.

Tzn. udowodniłem, że:

Jeśli \(\displaystyle{ n}\) jest liczbą naturalną różną od zera, a \(\displaystyle{ p \in \mathbb{P}}\) jest dowolną liczbą pierwszą, to liczbę \(\displaystyle{ n}\) można przedstawić jednoznacznie w postaci: \(\displaystyle{ n=m \cdot p ^{k}}\), gdzie \(\displaystyle{ k,m \in \NN}\), i \(\displaystyle{ p}\) nie dzieli \(\displaystyle{ m}\).

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ p \in \mathbb{P}}\) będzie dowolną liczbą pierwszą.

Szukamy liczb naturalnych \(\displaystyle{ m}\) i \(\displaystyle{ k}\) spełniających warunki zadania.

Jeśli \(\displaystyle{ p\not|n}\), to bierzemy \(\displaystyle{ m=n}\) i \(\displaystyle{ k=0}\), i otrzymujemy:

\(\displaystyle{ m \cdot p ^{0}= m= n,}\)

i \(\displaystyle{ p\not| \left( m=n\right).}\)

W przeciwnym przypadku rozważmy zbiór:

\(\displaystyle{ S= \left\{ k \in \NN: \ p ^{k}|n \right\}.}\)

I zastosujmy do niego zasadę maksimum dla liczb naturalnych.

Niewątpliwie \(\displaystyle{ S \subset \NN}\), i jest to zbiór niepusty, gdyż \(\displaystyle{ 0 \in S}\), bo \(\displaystyle{ 1= p ^{0}|n}\).

Łatwo jest pokazać indukcyjnie, że dla \(\displaystyle{ k \in \NN}\) mamy nierówność: \(\displaystyle{ k \le p ^{k}.}\) A zatem, u nas:

Dla \(\displaystyle{ k \in S}\), mamy \(\displaystyle{ p ^{k}| n}\), a zatem:

\(\displaystyle{ k \le p ^{k} \le n}\),

(bo \(\displaystyle{ n \neq 0}\)),

a zatem \(\displaystyle{ k \le n}\), i \(\displaystyle{ n}\) jest ograniczeniem górnym zbioru \(\displaystyle{ S}\).

Na mocy zasady maksimum dla liczb naturalnych zbiór \(\displaystyle{ S}\) ma liczbę największą \(\displaystyle{ k \in S}\). Ponieważ \(\displaystyle{ k \in S,}\) więc \(\displaystyle{ p ^{k}|n.}\) A zatem, z definicji podzielności : \(\displaystyle{ n= p ^{k} \cdot m}\), gdzie \(\displaystyle{ k \in \NN}\) i \(\displaystyle{ m \in \NN}\).
Pozostaje pokazać, że: \(\displaystyle{ p\not|m}\).

Gdyby byłoby \(\displaystyle{ p|m}\), to \(\displaystyle{ m=p \cdot l}\), gdzie \(\displaystyle{ l \in \NN}\). A wtedy:

\(\displaystyle{ n= p^{k} \cdot m= p ^{k} \cdot \left( p \cdot l\right)=}\)

co jest równe, na mocy łączności mnożenia liczb naturalnych, więc to jest równe:

\(\displaystyle{ = p ^{k+1} \cdot l,}\)

a zatem \(\displaystyle{ p ^{k+1}|n}\), a zatem, ponieważ \(\displaystyle{ (k+1) \in \NN}\), więc, z definicji zbioru \(\displaystyle{ S}\): \(\displaystyle{ \left( k+1\right) \in S}\), a ponieważ \(\displaystyle{ k}\) jest liczbą największą w \(\displaystyle{ S}\), więc możemy wnioskować, że: \(\displaystyle{ k+1\le k}\)-sprzeczność.

Wobec czego \(\displaystyle{ p\not|m}\) i \(\displaystyle{ n= p ^{k} \cdot m}\), gdzie \(\displaystyle{ k \in \NN}\), a więc takie liczby \(\displaystyle{ k}\) i \(\displaystyle{ m}\) istnieją.

Pozostaje pokazać, że są one jedyne.

Jeśli \(\displaystyle{ n= m_1 \cdot p ^{k_1}}\) i \(\displaystyle{ n= m_2 \cdot p ^{k_2}}\), są dwoma takimi przedstawieniami liczby \(\displaystyle{ n}\), to:

Jeśli \(\displaystyle{ m_1 \neq m_2}\), to te dwie liczby naturalne mają różne rozkłady na czynniki pierwsze ( w przeciwnym razie te dwie liczby byłyby równe ), a wtedy liczba \(\displaystyle{ n}\) ma dwa różne rozkłady na czynniki pierwsze- sprzeczność.

Jeśli \(\displaystyle{ m_1=m_2}\), to z jednoznaczności rozkładu liczby \(\displaystyle{ n}\) na czynniki pierwsze otrzymujemy:
\(\displaystyle{ k_1=k_2}\). A więc te liczby \(\displaystyle{ m}\) i \(\displaystyle{ k}\) są jedyne.

A więc są one wyznaczone jednoznacznie.\(\displaystyle{ \square}\)

Jeśli natomiast \(\displaystyle{ p \in \left\{ 2,3,\ldots\right\}}\), i \(\displaystyle{ p}\) jest liczbą złożoną: \(\displaystyle{ p=a \cdot b}\), to liczby \(\displaystyle{ n:=a}\) nie da się przedstawić w powyższy sposób; bo wtedy byłoby: \(\displaystyle{ a=m \cdot \left( a \cdot b\right) ^{k}}\), i, rozpisując rozkład, z jednoznaczności rozkładu liczby naturalnej na czynniki pierwsze otrzymamy sprzeczność.\(\displaystyle{ \square}\)


Dodam jeszcze pewne spostrzeżenie (które zaświtało mi w głowie, już gdy byłem w gimnazjum), że dowolne dwie różne liczby pierwsze \(\displaystyle{ p_1,p_2 \in \mathbb{P} }\) są względnie pierwsze.

No bo skoro liczba \(\displaystyle{ p_1}\) jest pierwsza, to ma dokładnie dwa dzielniki: \(\displaystyle{ 1}\) i \(\displaystyle{ p_1}\). Podobnie liczba \(\displaystyle{ p_2}\) ma dwa dzielniki: \(\displaystyle{ 1}\) i \(\displaystyle{ p_2}\). Ponieważ \(\displaystyle{ p_1 \neq p_2}\), to jedynym ich wspólnym dzielnikiem jest \(\displaystyle{ 1}\), a stąd liczby \(\displaystyle{ p_1}\) i \(\displaystyle{ p_2}\) są względnie pierwsze.\(\displaystyle{ \square}\)

O, mam pomysł jak udowodnić nierówność:

\(\displaystyle{ x+y \le x \cdot y}\),

w liczbach naturalnych \(\displaystyle{ x,y \ge 2}\). A zasadę szufladkową, tzn.:

Jeśli mamy \(\displaystyle{ n \ge 1, n \in \NN}\) szufladek, i \(\displaystyle{ m>n}\)( \(\displaystyle{ m \in \NN}\)) przedmiotów, i chcemy je rozmieścić w tych szufladkach, to zasada szufladkowa głosi, że wtedy istnieje szufladka w której są co najmniej dwa przedmioty.

Można to łatwo udowodnić dowodem nie wprost:

PROSTY DOWÓD TEGO FAKTU:

W przeciwnym razie, w każdej szufladce byłby co najwyżej jeden przedmiot, a więc łącznie byłoby co najwyżej:
\(\displaystyle{ \underbrace{1+1+\ldots+1}_{n \hbox{ razy}}=n}\) przedmiotów, a wszystkich przedmiotów jest \(\displaystyle{ m>n.\square}\)

Na koniec dodam jeszcze jeden dowód z ważniaka:

Wykażemy teraz, że dla każdego \(\displaystyle{ n}\) naturalnego \(\displaystyle{ n \ge 1}\), mamy podzielność: \(\displaystyle{ 4| 3 ^{2n-1} +1.}\)

Idea tej obserwacji:

Rozważmy reszty z dzielenia przez \(\displaystyle{ 4}\) kolejnych naturalnych dodatnich potęg liczby \(\displaystyle{ 3}\). Otrzymujemy ciąg :
\(\displaystyle{ \left( 3,9\mod 4=1,3\cdot 1=3,9\mod 4=1, \ldots\right). }\)

Skoro dla nieparzystych potęg mamy resztę \(\displaystyle{ 3}\), to takie potęgi powiększone o jeden będą podzielne przez cztery, a to odpowiada tezie zadania. Nie zastępuje to dowodu tego faktu. Oto:

DOWÓD TEGO FAKTU:

Dla \(\displaystyle{ n=1}\), mamy: \(\displaystyle{ 3 ^{2 \cdot 1-1}+1 = 4}\) jest podzielne przez cztery, spełniona jest więc podstawa indukcji.

Krok indukcyjny:
Załóżmy, że podzielność zachodzi dla pewnego \(\displaystyle{ n \ge 1}\).
Wykażemy, że: \(\displaystyle{ 3 ^{2\left( n+1\right) -1}+1}\) jest podzielne przez cztery.

Mamy:

\(\displaystyle{ 3 ^{2\left( n+1\right)-1 }+1= 3 ^{2n-1+2} +1= 9 \cdot 3 ^{2n-1}+1= 9 \cdot \left( 3 ^{2n-1}+0 \right)+1= 9 \cdot \left( 3 ^{2n-1} +\left( 1-1\right) \right) +1=\\= 9 \cdot \left( 3 ^{2n-1}+1 \right) - 9+1= 9 \cdot \left( 3 ^{2n-1}+1 \right)-8,}\)

zarówno \(\displaystyle{ 9 \cdot \left( 3 ^{2n-1}+1 \right)}\) jest podzielne przez cztery (na mocy założenia indukcyjnego), jak i \(\displaystyle{ 8}\) jest podzielne przez cztery, więc ich różnica również jest podzielna przez cztery.

W ten sposób udowodniliśmy krok indukcyjny; i, na mocy zasady indukcji, fakt jest prawdziwy dla każdego \(\displaystyle{ n \ge 1. \square }\)

A mam jeszcze parę innych spostrzeżeń związanych z podzielnością, np. dla \(\displaystyle{ n \ge 1}\), mamy \(\displaystyle{ 5| 4 ^{2n-1}+1}\), będzie można to udowodnić.

Dasio11 powinien się wstydzić, że przywołuje fakty wymagające tak skomplikowanych dowodów.
Dzięki JG za oświecenie

max123321 pisze: 12 sie 2023, o 19:41 Spośród liczb \(\displaystyle{ 1,2,3,...,199,200}\) wybrano \(\displaystyle{ 101}\) liczb. Dowieść, że wśród nich są CO NAJMNIEJ dwie takie, że jedna jest dzielnikiem drugiej.

Wydaje mi się, że niezbędne jest CO NAJMNIEJ?
A gdyby podejść do tematu od "d..py" strony.
Ile można wybrać liczb z których żadna nie jest dzielnikiem drugiej?
Pierwsze co się narzuca to \(\displaystyle{ 46}\) liczb pierwszych - nie bardzo wystarcza.
Znalazłem takie rozwiązanie.
Wszystkie liczby pierwsze od \(\displaystyle{ 11}\) do \(\displaystyle{ 199}\) - szt.\(\displaystyle{ 42}\)
wszystkie iloczyny tych liczb pierwszy przez pozostałe pierwsze \(\displaystyle{ 2}\) do \(\displaystyle{ 7}\) ale \(\displaystyle{ <=200}\) - jest ich \(\displaystyle{ 48}\)
dodatkowo
wszystkie kwadraty pierwszych \(\displaystyle{ 2}\) do \(\displaystyle{ 7}\) + iloczyny par \(\displaystyle{ 2}\) do \(\displaystyle{ 7}\) - jest ich \(\displaystyle{ 9}\)
razem \(\displaystyle{ 99}\)