Własność Podzbioru
-
mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Własność Podzbioru
Udowodnić, że istnieje podzbiór \(\displaystyle{ E}\) o \(\displaystyle{ 2^{n-1}+n}\) elementach, zbioru \(\displaystyle{ \{ 1,..., 2^n \}}\) taki, że jeśli \(\displaystyle{ x,y }\) są jego różnymi elementami \(\displaystyle{ E}\), to \(\displaystyle{ x+y}\) nie dzieli \(\displaystyle{ xy}\).
Ostatnio zmieniony 5 cze 2022, o 21:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Interpunkcja.
Powód: Interpunkcja.
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Własność Podzbioru
W tym zadaniu trzeba było się najpierw zastanowić jakie liczby spełniają tę zadaniową cechę podzielności, czyli kiedy:
(*) \(\displaystyle{ x+y|xy}\)
Potem starałem się rozwiązać to równanie diofantyczne:
\(\displaystyle{ xy=ax+ay}\)
Założyłem, że: \(\displaystyle{ x<y}\)
Czyli:
\(\displaystyle{ x|ay, y|ax}\)
wnioskuję, że:
\(\displaystyle{ x=sk , y=ask}\)
Po podstawieniu do (*) otrzymamy:
\(\displaystyle{ sk(1+a)|as^2k^2}\)
żeby ta podzielność była spełniona powinno być:
\(\displaystyle{ a=s-1}\)
mamy więc rozwiązanie:
\(\displaystyle{ x=sk, y=(s-1)sk, s \ge 3 , k \ge 1}\)
Teraz musimy na k i s porobić ograniczenia, żeby mieściło się to w naszym zbiorze
\(\displaystyle{ 1 \le x<y \le 2^n}\)
wypiszmy pary liczb spełniające nasze równanie dla: \(\displaystyle{ n=3,4}\)
\(\displaystyle{ 2^3=8}\)
\(\displaystyle{ N=\left\{ 1,2,3,4,5,6,7,8\right\} }\)
Szału nie ma naszą jedyną parą jest:
\(\displaystyle{ (3,6)}\)
Czyli jeżeli wyrzucimy jedną liczbę z tej naszej pary otrzymamy zbiór niepodzielnych o liczności: \(\displaystyle{ 2^2+3=7}\)
Zgodnie z zadaniem
Teraz popatrzmy dla:
\(\displaystyle{ n=4}\)
\(\displaystyle{ N=\left\{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\right\} }\)
Pary, które spełniają nasze równanie to:
\(\displaystyle{ (3,6);(6,12);(4,12)}\)
Jeżeli z każdej pary odrzucimy pewną liczbę czyli trzy to znowu otrzymamy zbiór liczb, które nie spełniają naszego równania
\(\displaystyle{ 2^3+4=12}\)
\(\displaystyle{ 16-3=13 }\)
Oznaczmy ilość par spełniających nasze równanie w zbiorze N przez \(\displaystyle{ A_{n}}\)
Trzeba nam udowodnić, że:
(**) \(\displaystyle{ A_{n} \le 2^n-2^{n-1}-n=2^{n-1}-n}\)
Pasuje teraz wyliczyć: \(\displaystyle{ A_{n}}\)
wiadomo, że:
\(\displaystyle{ y=(s^2-s)k \le 2^n}\)
\(\displaystyle{ k \le \frac{2^n}{s^2-s} }\)
Więc rozwiązań, przy ustalonym n powinno być:
\(\displaystyle{ A_{n}= \sum_{s=3}^{ \infty }\left[ \frac{2^n}{s^2-s} \right] }\)
łatwo udowodnić indukcyjnie nierówność (**), korzystając z:
\(\displaystyle{ \left[ 2x\right] \le 2\left[ x\right] +1 , x>0}\)
(*) \(\displaystyle{ x+y|xy}\)
Potem starałem się rozwiązać to równanie diofantyczne:
\(\displaystyle{ xy=ax+ay}\)
Założyłem, że: \(\displaystyle{ x<y}\)
Czyli:
\(\displaystyle{ x|ay, y|ax}\)
wnioskuję, że:
\(\displaystyle{ x=sk , y=ask}\)
Po podstawieniu do (*) otrzymamy:
\(\displaystyle{ sk(1+a)|as^2k^2}\)
żeby ta podzielność była spełniona powinno być:
\(\displaystyle{ a=s-1}\)
mamy więc rozwiązanie:
\(\displaystyle{ x=sk, y=(s-1)sk, s \ge 3 , k \ge 1}\)
Teraz musimy na k i s porobić ograniczenia, żeby mieściło się to w naszym zbiorze
\(\displaystyle{ 1 \le x<y \le 2^n}\)
wypiszmy pary liczb spełniające nasze równanie dla: \(\displaystyle{ n=3,4}\)
\(\displaystyle{ 2^3=8}\)
\(\displaystyle{ N=\left\{ 1,2,3,4,5,6,7,8\right\} }\)
Szału nie ma naszą jedyną parą jest:
\(\displaystyle{ (3,6)}\)
Czyli jeżeli wyrzucimy jedną liczbę z tej naszej pary otrzymamy zbiór niepodzielnych o liczności: \(\displaystyle{ 2^2+3=7}\)
Zgodnie z zadaniem
Teraz popatrzmy dla:
\(\displaystyle{ n=4}\)
\(\displaystyle{ N=\left\{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\right\} }\)
Pary, które spełniają nasze równanie to:
\(\displaystyle{ (3,6);(6,12);(4,12)}\)
Jeżeli z każdej pary odrzucimy pewną liczbę czyli trzy to znowu otrzymamy zbiór liczb, które nie spełniają naszego równania
\(\displaystyle{ 2^3+4=12}\)
\(\displaystyle{ 16-3=13 }\)
Oznaczmy ilość par spełniających nasze równanie w zbiorze N przez \(\displaystyle{ A_{n}}\)
Trzeba nam udowodnić, że:
(**) \(\displaystyle{ A_{n} \le 2^n-2^{n-1}-n=2^{n-1}-n}\)
Pasuje teraz wyliczyć: \(\displaystyle{ A_{n}}\)
wiadomo, że:
\(\displaystyle{ y=(s^2-s)k \le 2^n}\)
\(\displaystyle{ k \le \frac{2^n}{s^2-s} }\)
Więc rozwiązań, przy ustalonym n powinno być:
\(\displaystyle{ A_{n}= \sum_{s=3}^{ \infty }\left[ \frac{2^n}{s^2-s} \right] }\)
łatwo udowodnić indukcyjnie nierówność (**), korzystając z:
\(\displaystyle{ \left[ 2x\right] \le 2\left[ x\right] +1 , x>0}\)