Parzystość
-
mol_ksiazkowy
- Użytkownik
- Posty: 11581
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 749 razy
Parzystość
Udowodnić, że \(\displaystyle{ {2^n - k \choose k-1}}\) jest liczbą parzystą, o ile \(\displaystyle{ 2 \leq k \leq 2^{n-1}}\).
-
arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 132 razy
- Pomógł: 526 razy
Re: Parzystość
Zapiszmy odpowiednio:\(\displaystyle{ 2^n}\)
\(\displaystyle{ 2^n=(2^{n-1}+2^{n-2}+...+2^1)+2}\)
Jest \(\displaystyle{ n}\) składników a w nawiasie \(\displaystyle{ n-1}\) składników...
Niech teraz \(\displaystyle{ k}\) ma rozwinięcie dwójkowe następujące:
\(\displaystyle{ k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+r , r=0 \vee 1}\)
1) niech: \(\displaystyle{ r=1}\)
\(\displaystyle{ k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+1}\)
Reprezentacja dwójkowa:
\(\displaystyle{ 2^n-k=\left( 1-s_{n-1}\right) 2^{n-1}+\left( 1-s_{n-2}\right) 2^{n-2}+...+\left( 1-s_{1}\right) 2^1+1}\)
teraz jak mamy reprezentację dwójkową: \(\displaystyle{ k-1}\)
\(\displaystyle{ k-1=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+0 \cdot 1}\)
Łatwo wywnioskować, że:
\(\displaystyle{ \bigvee\limits_{s_{i}} s_{i}=1}\)
więc reprezentacja dwójkowa będzie obu tych liczb wyglądać następująco:
\(\displaystyle{ 2^n-k=\left( 1,1,...,0,...,1 \right) , k-1=\left( s_{1},s_{2},...,1,...,s_{0} \right)}\)
Znaczy to, że na tym samym miejscu w rozwinięciu dwójkowym liczby: \(\displaystyle{ 2^k-k}\) występuje \(\displaystyle{ 0}\), a w tym samym miejscu rozwinięcia dwójkowego liczby: \(\displaystyle{ k-1}\) występuje \(\displaystyle{ 1}\)
2) Załóżmy teraz, że \(\displaystyle{ k}\) jest parzyste, czyli: \(\displaystyle{ r=0}\)
wtedy:
\(\displaystyle{ 2^n-k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+0}\)
\(\displaystyle{ k-1=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+1}\)
Jak widać wtedy ostatni współczynnik w rozwinięciu dwójkowym \(\displaystyle{ 2^n-k}\) wynosi zero, a ostatni współczynnik: \(\displaystyle{ k-1}\) w rozwinięciu dwójkowym wynosi jeden a więc jest większy...
Teraz twierdzenie Lucasa:
\(\displaystyle{ {m \choose n} =\Pi_{i=0}^k {m_{i} \choose n_{i}} \mod p}\)
Przyjmujemy, że:
(**) \(\displaystyle{ {m_{i} \choose n_{i}}=0}\) jeżeli: \(\displaystyle{ m_{i}<n_{i}}\)
gdzie:
\(\displaystyle{ m=m_{k}p^k+m_{k-1}p^{k-1}+...+m_{1}p^1+m_{0}}\)
\(\displaystyle{ n=n_{k}p^k+n_{k-1}p^{k-1}+...+n_{1}p^1+n_{0}}\)
\(\displaystyle{ 0 \le m_{i} , n_{i}<p}\)
U nas przyjmiemy:
\(\displaystyle{ m:=2^n-k , n:=k-1 , p=2}\)
więc obliczamy:
\(\displaystyle{ {2^n-k \choose k-1} =\Pi_{i=0}^{n-1} {s_{i} \choose s_{i}'} \mod 2}\)
U nas współczynniki:
\(\displaystyle{ {s_{i} \choose s_{i}'} }\)
Mogą wynosić:
\(\displaystyle{ {1 \choose 0} ={1 \choose 1} ={0 \choose 0} =1 \vee {0 \choose 1}=0 }\)
Ale wykazaliśmy, że w obu przypadkach gdy \(\displaystyle{ k}\) jest parzyste i nieparzyste zawsze wystąpi symbol:
\(\displaystyle{ {0 \choose 1}=0 }\)
a więc:
\(\displaystyle{ {2^n-k \choose k-1} =\Pi_{i=0}^{n-1} {s_{i} \choose s_{i}'} \mod 2= {0 \choose 1}=0 \mod 2 }\)
cnd...
\(\displaystyle{ 2^n=(2^{n-1}+2^{n-2}+...+2^1)+2}\)
Jest \(\displaystyle{ n}\) składników a w nawiasie \(\displaystyle{ n-1}\) składników...
Niech teraz \(\displaystyle{ k}\) ma rozwinięcie dwójkowe następujące:
\(\displaystyle{ k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+r , r=0 \vee 1}\)
1) niech: \(\displaystyle{ r=1}\)
\(\displaystyle{ k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+1}\)
Reprezentacja dwójkowa:
\(\displaystyle{ 2^n-k=\left( 1-s_{n-1}\right) 2^{n-1}+\left( 1-s_{n-2}\right) 2^{n-2}+...+\left( 1-s_{1}\right) 2^1+1}\)
teraz jak mamy reprezentację dwójkową: \(\displaystyle{ k-1}\)
\(\displaystyle{ k-1=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+0 \cdot 1}\)
Łatwo wywnioskować, że:
\(\displaystyle{ \bigvee\limits_{s_{i}} s_{i}=1}\)
więc reprezentacja dwójkowa będzie obu tych liczb wyglądać następująco:
\(\displaystyle{ 2^n-k=\left( 1,1,...,0,...,1 \right) , k-1=\left( s_{1},s_{2},...,1,...,s_{0} \right)}\)
Znaczy to, że na tym samym miejscu w rozwinięciu dwójkowym liczby: \(\displaystyle{ 2^k-k}\) występuje \(\displaystyle{ 0}\), a w tym samym miejscu rozwinięcia dwójkowego liczby: \(\displaystyle{ k-1}\) występuje \(\displaystyle{ 1}\)
2) Załóżmy teraz, że \(\displaystyle{ k}\) jest parzyste, czyli: \(\displaystyle{ r=0}\)
wtedy:
\(\displaystyle{ 2^n-k=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+0}\)
\(\displaystyle{ k-1=s_{n-1}2^{n-1}+s_{n-2}2^{n-2}+...+s_{1}2+1}\)
Jak widać wtedy ostatni współczynnik w rozwinięciu dwójkowym \(\displaystyle{ 2^n-k}\) wynosi zero, a ostatni współczynnik: \(\displaystyle{ k-1}\) w rozwinięciu dwójkowym wynosi jeden a więc jest większy...
Teraz twierdzenie Lucasa:
\(\displaystyle{ {m \choose n} =\Pi_{i=0}^k {m_{i} \choose n_{i}} \mod p}\)
Przyjmujemy, że:
(**) \(\displaystyle{ {m_{i} \choose n_{i}}=0}\) jeżeli: \(\displaystyle{ m_{i}<n_{i}}\)
gdzie:
\(\displaystyle{ m=m_{k}p^k+m_{k-1}p^{k-1}+...+m_{1}p^1+m_{0}}\)
\(\displaystyle{ n=n_{k}p^k+n_{k-1}p^{k-1}+...+n_{1}p^1+n_{0}}\)
\(\displaystyle{ 0 \le m_{i} , n_{i}<p}\)
U nas przyjmiemy:
\(\displaystyle{ m:=2^n-k , n:=k-1 , p=2}\)
więc obliczamy:
\(\displaystyle{ {2^n-k \choose k-1} =\Pi_{i=0}^{n-1} {s_{i} \choose s_{i}'} \mod 2}\)
U nas współczynniki:
\(\displaystyle{ {s_{i} \choose s_{i}'} }\)
Mogą wynosić:
\(\displaystyle{ {1 \choose 0} ={1 \choose 1} ={0 \choose 0} =1 \vee {0 \choose 1}=0 }\)
Ale wykazaliśmy, że w obu przypadkach gdy \(\displaystyle{ k}\) jest parzyste i nieparzyste zawsze wystąpi symbol:
\(\displaystyle{ {0 \choose 1}=0 }\)
a więc:
\(\displaystyle{ {2^n-k \choose k-1} =\Pi_{i=0}^{n-1} {s_{i} \choose s_{i}'} \mod 2= {0 \choose 1}=0 \mod 2 }\)
cnd...