Witam,
Tytuł może nieco mylący, ale nie mogłem 'wpaść' na lepszy pomysł.
Oto zadanie:
Niech \(\displaystyle{ A}\) będzie zbiorem \(\displaystyle{ n}\) dodatnich liczb całkowitych. Pokaż, że każdy ciąg \(\displaystyle{ 2^{n}}\) liczb z \(\displaystyle{ A}\) zawiera kolejne liczby, których iloczyn jest kwadratem liczby naturalnej. Na przykład: ciąg \(\displaystyle{ {2,5,3,2,5,2,3,5}}\) zawiera \(\displaystyle{ 5,3,2,5,2,3}\)
Ma ktoś jakiś pomysł, jak to rozwiązać? Mam nadzieję, że w miarę jasno przedstawiłem treść zadania.
Liczę na wsparcie i pozdrawiam,
Ciamolek
Udowodnij, że iloczyn liczb zawiera kwadrat.
-
SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
Udowodnij, że iloczyn liczb zawiera kwadrat.
Na szybko skonstruowany kontrprzykład, może być w nim błąd: \(\displaystyle{ 2, 3, 2, 5, 2, 3, 2, 7, 2, 3, 5, 3, 7, 3, 2, 3}\)
Oczywiście \(\displaystyle{ n=4}\) oraz \(\displaystyle{ A=\{2, 3, 5, 7\}}\).
EDIT (9:33):
Oczywiście późna pora zrobiła swoje, nie wziąłem pod uwagę całego ciągu. Poprawię to albo wezmę się poważnie za zadanie
EDIT2 (9:51):
Zadanie okazało się proste. Niech \(\displaystyle{ A=\{a_1,a_2,\cdots,a_n\}}\). Pomyślmy o ciągu z treści zadania jak o słowie. Rozważmy wszystkie jego \(\displaystyle{ 2^n+1}\) prefiksów (łącznie ze słowem pustym i całym słowem). Dla i-tego (dla \(\displaystyle{ i=0,1,\cdots,2^n}\)) prefiksu rozważmy krotkę \(\displaystyle{ x_i=(x_{i1}, x_{i2},\cdots,x_{in})}\), gdzie \(\displaystyle{ x_{ik}}\) jest liczbą wystąpień \(\displaystyle{ a_k}\) w i-tym prefiksie, po czym weźmy ją modulo 2. Wszystkich możliwych ciągów zero-jedynkowych długości n jest \(\displaystyle{ 2^n}\), zatem z zasady szufladkowej Dirichleta pewne dwie krotki \(\displaystyle{ x_i \mod 2=(x_{i1} \mod 2, x_{i2}\mod 2,\cdots,x_{in}\mod 2)}\) oraz \(\displaystyle{ x_j \mod 2=(x_{j1} \mod 2, x_{j2}\mod 2,\cdots,x_{jn}\mod 2)}\) dla \(\displaystyle{ 2^n\geq i>j\geq 0}\) się powtórzą. To oznacza, że \(\displaystyle{ x_i-x_j=(x_{i1}-x_{j1}, x_{i2}-x_{j2},\cdots,x_{in}-x_{jn})}\) składa się z samych liczb parzystych. Dalej już prosto zauważyć, że \(\displaystyle{ x_{ik}-x_{jk}}\) jest liczbą wystąpień liczby \(\displaystyle{ a_k}\) na pozycjach od \(\displaystyle{ j+1}\) do \(\displaystyle{ i}\). To z kolei implikuje, że wśród tych pozycji każda z liczba \(\displaystyle{ a_k}\) występuje parzyście wiele razy, czyli w iloczynie \(\displaystyle{ \prod_{m=j+1}^i a_m}\) każda liczba \(\displaystyle{ a_k}\) występuje w wykładniku parzystym, czyli cała liczba jest kwadratem liczby naturalnej.
Oczywiście \(\displaystyle{ n=4}\) oraz \(\displaystyle{ A=\{2, 3, 5, 7\}}\).
EDIT (9:33):
Oczywiście późna pora zrobiła swoje, nie wziąłem pod uwagę całego ciągu. Poprawię to albo wezmę się poważnie za zadanie
EDIT2 (9:51):
Zadanie okazało się proste. Niech \(\displaystyle{ A=\{a_1,a_2,\cdots,a_n\}}\). Pomyślmy o ciągu z treści zadania jak o słowie. Rozważmy wszystkie jego \(\displaystyle{ 2^n+1}\) prefiksów (łącznie ze słowem pustym i całym słowem). Dla i-tego (dla \(\displaystyle{ i=0,1,\cdots,2^n}\)) prefiksu rozważmy krotkę \(\displaystyle{ x_i=(x_{i1}, x_{i2},\cdots,x_{in})}\), gdzie \(\displaystyle{ x_{ik}}\) jest liczbą wystąpień \(\displaystyle{ a_k}\) w i-tym prefiksie, po czym weźmy ją modulo 2. Wszystkich możliwych ciągów zero-jedynkowych długości n jest \(\displaystyle{ 2^n}\), zatem z zasady szufladkowej Dirichleta pewne dwie krotki \(\displaystyle{ x_i \mod 2=(x_{i1} \mod 2, x_{i2}\mod 2,\cdots,x_{in}\mod 2)}\) oraz \(\displaystyle{ x_j \mod 2=(x_{j1} \mod 2, x_{j2}\mod 2,\cdots,x_{jn}\mod 2)}\) dla \(\displaystyle{ 2^n\geq i>j\geq 0}\) się powtórzą. To oznacza, że \(\displaystyle{ x_i-x_j=(x_{i1}-x_{j1}, x_{i2}-x_{j2},\cdots,x_{in}-x_{jn})}\) składa się z samych liczb parzystych. Dalej już prosto zauważyć, że \(\displaystyle{ x_{ik}-x_{jk}}\) jest liczbą wystąpień liczby \(\displaystyle{ a_k}\) na pozycjach od \(\displaystyle{ j+1}\) do \(\displaystyle{ i}\). To z kolei implikuje, że wśród tych pozycji każda z liczba \(\displaystyle{ a_k}\) występuje parzyście wiele razy, czyli w iloczynie \(\displaystyle{ \prod_{m=j+1}^i a_m}\) każda liczba \(\displaystyle{ a_k}\) występuje w wykładniku parzystym, czyli cała liczba jest kwadratem liczby naturalnej.
Ostatnio zmieniony 6 lis 2010, o 23:39 przez SaxoN, łącznie zmieniany 1 raz.
-
Ciamolek
- Użytkownik
- Posty: 440
- Rejestracja: 4 mar 2008, o 17:32
- Płeć: Mężczyzna
- Lokalizacja: Zielona Góra
- Podziękował: 45 razy
- Pomógł: 42 razy
Udowodnij, że iloczyn liczb zawiera kwadrat.
WOW! Wielkie dzięki. Ja myślałem o Dirichlecei, ale niestety nie w kontekście mod 2.
Niestety, nie rozumiem jednej (acz kluczowej) części Twojego rozwiązania:
Skąd masz \(\displaystyle{ 2^{n}+1}\) prefiksów? I czym tak właściwie jest prefiks w tym przypadku? Ja myślałem raczej o podzbiorach A, których w moim rozumieniu jest \(\displaystyle{ 2^{n}}\)
Pozdrawiam,
Ciamolek
Niestety, nie rozumiem jednej (acz kluczowej) części Twojego rozwiązania:
Skąd masz \(\displaystyle{ 2^{n}+1}\) prefiksów? I czym tak właściwie jest prefiks w tym przypadku? Ja myślałem raczej o podzbiorach A, których w moim rozumieniu jest \(\displaystyle{ 2^{n}}\)
Pozdrawiam,
Ciamolek
-
SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
Udowodnij, że iloczyn liczb zawiera kwadrat.
W tym momencie nie rozważam zbioru \(\displaystyle{ A}\), tylko dowolny \(\displaystyle{ 2^n}\)-elementowy ciąg \(\displaystyle{ b_n}\) o wyrazach z tego zbioru. Prefiks to pewien początkowy spójny podciąg naszego ciągu- dla wygody zakładam, że istnieje coś takiego jak ciąg zeroelementowy. Kolejne prefiksy będą wyglądały mniej więcej tak: \(\displaystyle{ (), (b_1), (b_1, b_2),\ldots,(b_1,\ldots,b_{2^n})}\) - jest ich \(\displaystyle{ 2^n+1}\). Multizbiór wyrazów każdego spójnego podciągu zawsze jest różnicą dwóch prefiksów. Jakbyś miał jakieś pytania to pisz na gg, wtedy łatwiej mi będzie tłumaczyć