Mamy zbiór liczb \(\displaystyle{ x = {1,2,3,4....n}}\)
W zbiorze \(\displaystyle{ x}\) jest dokładnie \(\displaystyle{ m}\) liczb pierwszych.
Wybieramy dowolne \(\displaystyle{ (m+1)}\) liczb ze zbioru \(\displaystyle{ x}\).
I musimy udowodnić, że wśród tych wybranych \(\displaystyle{ m+1}\) liczb istnieje conajmniej jedna, która jest dzielnikiem iloczynu powstałych liczb.
Wybór liczb ze zbioru
-
Elek112
- Użytkownik
- Posty: 165
- Rejestracja: 15 wrz 2010, o 09:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 28 razy
Wybór liczb ze zbioru
Ostatnio zmieniony 4 mar 2012, o 18:15 przez loitzl9006, łącznie zmieniany 1 raz.
Powód: Nie stosuj wyrażeń matematycznych w nazwie tematu.
Powód: Nie stosuj wyrażeń matematycznych w nazwie tematu.
-
Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Wybór liczb ze zbioru
Lemat: Zauważmy, że dla całkowitych dodatnich x,y,z spełniających \(\displaystyle{ x,y > [\frac{z}{2}]}\) zachodzi \(\displaystyle{ x+y > z}\) (dowód łatwy, zostawiam jako ćwiczenie). Oznaczmy nasze \(\displaystyle{ m+1}\) liczb jako \(\displaystyle{ a_1,a_2,...,a_{m+1}}\), jeżeli któraś z nich jest równa 1, to teza zachodzi (1 dzieli dowolną liczbę całkowitą), dodatkowo jeżeli pewne dwie liczby są takie same to teza oczywiście również zachodzi, możemy więc założyć, że wszystkie spośród danych liczb są parami różne i różne od 1. Oznaczmy:
\(\displaystyle{ a_1\cdot a_2\cdot ... \cdot a_{m+1} = p_1^{b_1}\cdot p_2^{b_2} \cdot ... \cdot p_k^{b_k} (*) , p_i \in \mathbb_{P}}\) \(\displaystyle{ , b_i \in \mathbb_{Z_+}}\)
Teza jest równoważna pokazaniu, że wśród naszych \(\displaystyle{ m+1}\) liczb istnieje taka \(\displaystyle{ a_j}\), że \(\displaystyle{ a_j = p_1^{c_1} \cdot p_2^{c_2} \cdot ... \cdot p_k^{c_k}}\), gdzie \(\displaystyle{ c_1 \le [\frac{b_1}{2}] \wedge c_2 \le [\frac{b_2}{2}] \wedge ... \wedge c_k \le [\frac{b_k}{2}]}\)
(Wówczas w iloczynie pozostałych m liczb odpowiednie wykładniki przy liczbach pierwszych będą nie mniejsze niż wykładniki odpowiednich liczb pierwszych w liczbie \(\displaystyle{ a_j}\), czyli inaczej mówiąc liczba \(\displaystyle{ a_j}\) będzie dzieliła iloczyn pozostałych liczb, a oto nam chodzi), załóżmy nie wprost, że tak nie jest, czyli przynajmniej jeden z wykładników przy którejś liczbie pierwszej w każdej z liczb \(\displaystyle{ a_1,a_2,...,a_{m+1}}\) jest większy, niż odpowiednia cecha, tj:
\(\displaystyle{ a_1 = p_{x_{\lbrace1,1\rbrace}}^{d_{x_{\lbrace1,1\rbrace}}} \cdot p_{x_{\lbrace 1,2\rbrace}}}^{d_{x_{\lbrace 1,2\rbrace}}} \cdot ... \\ \\ a_2 = p_{x_{\lbrace2,1\rbrace}}^{d_{x_{\lbrace 2,1\rbrace}}}\cdot p_{x_{\lbrace2,2\rbrace}}^{d_{x_{\lbrace2,2\rbrace}}}\cdot ... \\ \\ ... \\ \\ a_{m+1} = p_{x_{\lbrace m+1,1\rbrace}}^{d_{x_{\lbrace m+1,1\rbrace}}} \cdot p_{x_{\lbrace m+1,2\rbrace}}^{d_{x_{\lbrace m+1,2\rbrace}}} \cdot ...}\)
gdzie \(\displaystyle{ d_{x_{\lbrace1,1\rbrace}} > [\frac{b_{x_{\lbrace1,1\rbrace}}}{2}] \wedge d_{x_{\lbrace2,1\rbrace}} > [\frac{b_{x_{\lbrace2,1\rbrace}}}{2}] ... \\ \\ d_{x_{\lbrace m+1,1\rbrace}} > [\frac{b_{x_{\lbrace m+1,1\rbrace}}}{2}]}\)
Zauważmy jednak, że zbiór \(\displaystyle{ \lbrace x_{\lbrace1,1\rbrace} , x_{\lbrace2,1\rbrace} , ... , x_{\lbrace m+1,1\rbrace}\rbrace}\) nie może posiadać parami różnych elementów (wówczas mielibyśmy m+1 liczb pierwszych, a z założenia jest ich m) czyli wymnażając \(\displaystyle{ a_1 \cdot a_2 \cdot ... \cdot a_{m+1}}\) dostaniemy w wykładniku pewnej liczby pierwszej sumę co najmniej dwóch liczb, które są większe niż cecha połowy odpowiedniego wykładnika liczby pierwszej z \(\displaystyle{ (*)}\) co na mocy lematu będzie większe niż dana liczba, sprzeczność.
\(\displaystyle{ a_1\cdot a_2\cdot ... \cdot a_{m+1} = p_1^{b_1}\cdot p_2^{b_2} \cdot ... \cdot p_k^{b_k} (*) , p_i \in \mathbb_{P}}\) \(\displaystyle{ , b_i \in \mathbb_{Z_+}}\)
Teza jest równoważna pokazaniu, że wśród naszych \(\displaystyle{ m+1}\) liczb istnieje taka \(\displaystyle{ a_j}\), że \(\displaystyle{ a_j = p_1^{c_1} \cdot p_2^{c_2} \cdot ... \cdot p_k^{c_k}}\), gdzie \(\displaystyle{ c_1 \le [\frac{b_1}{2}] \wedge c_2 \le [\frac{b_2}{2}] \wedge ... \wedge c_k \le [\frac{b_k}{2}]}\)
(Wówczas w iloczynie pozostałych m liczb odpowiednie wykładniki przy liczbach pierwszych będą nie mniejsze niż wykładniki odpowiednich liczb pierwszych w liczbie \(\displaystyle{ a_j}\), czyli inaczej mówiąc liczba \(\displaystyle{ a_j}\) będzie dzieliła iloczyn pozostałych liczb, a oto nam chodzi), załóżmy nie wprost, że tak nie jest, czyli przynajmniej jeden z wykładników przy którejś liczbie pierwszej w każdej z liczb \(\displaystyle{ a_1,a_2,...,a_{m+1}}\) jest większy, niż odpowiednia cecha, tj:
\(\displaystyle{ a_1 = p_{x_{\lbrace1,1\rbrace}}^{d_{x_{\lbrace1,1\rbrace}}} \cdot p_{x_{\lbrace 1,2\rbrace}}}^{d_{x_{\lbrace 1,2\rbrace}}} \cdot ... \\ \\ a_2 = p_{x_{\lbrace2,1\rbrace}}^{d_{x_{\lbrace 2,1\rbrace}}}\cdot p_{x_{\lbrace2,2\rbrace}}^{d_{x_{\lbrace2,2\rbrace}}}\cdot ... \\ \\ ... \\ \\ a_{m+1} = p_{x_{\lbrace m+1,1\rbrace}}^{d_{x_{\lbrace m+1,1\rbrace}}} \cdot p_{x_{\lbrace m+1,2\rbrace}}^{d_{x_{\lbrace m+1,2\rbrace}}} \cdot ...}\)
gdzie \(\displaystyle{ d_{x_{\lbrace1,1\rbrace}} > [\frac{b_{x_{\lbrace1,1\rbrace}}}{2}] \wedge d_{x_{\lbrace2,1\rbrace}} > [\frac{b_{x_{\lbrace2,1\rbrace}}}{2}] ... \\ \\ d_{x_{\lbrace m+1,1\rbrace}} > [\frac{b_{x_{\lbrace m+1,1\rbrace}}}{2}]}\)
Zauważmy jednak, że zbiór \(\displaystyle{ \lbrace x_{\lbrace1,1\rbrace} , x_{\lbrace2,1\rbrace} , ... , x_{\lbrace m+1,1\rbrace}\rbrace}\) nie może posiadać parami różnych elementów (wówczas mielibyśmy m+1 liczb pierwszych, a z założenia jest ich m) czyli wymnażając \(\displaystyle{ a_1 \cdot a_2 \cdot ... \cdot a_{m+1}}\) dostaniemy w wykładniku pewnej liczby pierwszej sumę co najmniej dwóch liczb, które są większe niż cecha połowy odpowiedniego wykładnika liczby pierwszej z \(\displaystyle{ (*)}\) co na mocy lematu będzie większe niż dana liczba, sprzeczność.