Udowodnić, że jeśli \(\displaystyle{ n+m-k+1}\) jest potęgą dwójki (o wykładniku naturalnym), to \(\displaystyle{ {n \choose k}+ {m \choose k}}\) jest parzyste.
zakł: \(\displaystyle{ n \geq m \geq k \geq 0}\)
Suma z Newtonem
- mol_ksiazkowy
- Użytkownik
- Posty: 11413
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Suma z Newtonem
Wykorzystałem tu słynne ( za dużo powiedziane) twierdzenie, które nam mówi, że:
\(\displaystyle{ {n \choose k} = \prod_{i=0}^{s} {n_{i} \choose k_{i}} \left( \mod p\right) }\)
gdzie:
\(\displaystyle{ n=n_{0}+n_{1}p+n_{2}p^2+...+n_{s}p^s}\)
\(\displaystyle{ k=k_{0}+k_{1}p+k_{2}p^2+...+k_{s}p^s}\)
Przyjmujemy, że:
\(\displaystyle{ {n \choose k} =0 ,n<k}\)
Takie systemy petkowe...
w przypadku naszego zadania:
\(\displaystyle{ p=2}\)
warunek zadania to:
(**) \(\displaystyle{ n+m-k+1=2^s}\)
Reprezentacjami naszych liczb będą:
\(\displaystyle{ n=\left( a_{1},...,a_{s-1}\right) }\)
\(\displaystyle{ m=\left( b_{1},...,b_{s-1}\right) }\)
\(\displaystyle{ k=\left( c_{1},...,c_{s-1}\right) }\)
\(\displaystyle{ a_{i}, b_{i}, c_{i}=0 \vee 1 , 1 \le i \le s-1}\)
Tylko tu inaczej niż we wzorze zapisałem na odwrót znaczy np:
\(\displaystyle{ 8=(1,0,0,0)}\)
czyli zapiszmy:
\(\displaystyle{ {n \choose k} = \prod_{i=0}^{s-1} {a_{i} \choose c_{i}} \left( \mod 2\right)}\)
\(\displaystyle{ {m \choose k} = \prod_{i=0}^{s-1} {b_{i} \choose c_{i}} \left( \mod 2\right)}\)
Zauważmy też, że:
\(\displaystyle{ {a_{i} \choose c_{i}} \vee {b_{i} \choose c_{i}} = {1 \choose 1} \vee {1 \choose 0} \vee {0 \choose 1} \vee {0 \choose 0} =0 \vee 1}\)
Z warunku zadania (**) oraz z zapisu zerojedynkowego łatwo zauważyć, że:
\(\displaystyle{ a_{i}+b_{i}-c_{i}+1=0 \mod 2, 0 \le i \le s-1}\) - co jest dość fajne
Jeżeli by teraz nie został spełniony warunek zadania , to znaczy dla pewnego \(\displaystyle{ i}\) musiało by być:
np:
\(\displaystyle{ {a_{i} \choose c_{i}} =0 \wedge {b_{i} \choose c_{i}}=1}\)
lub na odwrót...
Znaczyłoby to, że:
\(\displaystyle{ a_{i}=0, c_{i}=1, b_{i}=1}\)
ale z warunku (**) musi być:
\(\displaystyle{ a_{i}+b_{i}-c_{i}+1=0 \mod 2}\)
po podstawieniu mamy:
\(\displaystyle{ 0+1-1+1=1 \mod 2}\)
czyli sprzeczność a więc suma:
\(\displaystyle{ {n \choose k} + {m \choose k} }\) - parzysta...
cnd...
\(\displaystyle{ {n \choose k} = \prod_{i=0}^{s} {n_{i} \choose k_{i}} \left( \mod p\right) }\)
gdzie:
\(\displaystyle{ n=n_{0}+n_{1}p+n_{2}p^2+...+n_{s}p^s}\)
\(\displaystyle{ k=k_{0}+k_{1}p+k_{2}p^2+...+k_{s}p^s}\)
Przyjmujemy, że:
\(\displaystyle{ {n \choose k} =0 ,n<k}\)
Takie systemy petkowe...
w przypadku naszego zadania:
\(\displaystyle{ p=2}\)
warunek zadania to:
(**) \(\displaystyle{ n+m-k+1=2^s}\)
Reprezentacjami naszych liczb będą:
\(\displaystyle{ n=\left( a_{1},...,a_{s-1}\right) }\)
\(\displaystyle{ m=\left( b_{1},...,b_{s-1}\right) }\)
\(\displaystyle{ k=\left( c_{1},...,c_{s-1}\right) }\)
\(\displaystyle{ a_{i}, b_{i}, c_{i}=0 \vee 1 , 1 \le i \le s-1}\)
Tylko tu inaczej niż we wzorze zapisałem na odwrót znaczy np:
\(\displaystyle{ 8=(1,0,0,0)}\)
czyli zapiszmy:
\(\displaystyle{ {n \choose k} = \prod_{i=0}^{s-1} {a_{i} \choose c_{i}} \left( \mod 2\right)}\)
\(\displaystyle{ {m \choose k} = \prod_{i=0}^{s-1} {b_{i} \choose c_{i}} \left( \mod 2\right)}\)
Zauważmy też, że:
\(\displaystyle{ {a_{i} \choose c_{i}} \vee {b_{i} \choose c_{i}} = {1 \choose 1} \vee {1 \choose 0} \vee {0 \choose 1} \vee {0 \choose 0} =0 \vee 1}\)
Z warunku zadania (**) oraz z zapisu zerojedynkowego łatwo zauważyć, że:
\(\displaystyle{ a_{i}+b_{i}-c_{i}+1=0 \mod 2, 0 \le i \le s-1}\) - co jest dość fajne
Jeżeli by teraz nie został spełniony warunek zadania , to znaczy dla pewnego \(\displaystyle{ i}\) musiało by być:
np:
\(\displaystyle{ {a_{i} \choose c_{i}} =0 \wedge {b_{i} \choose c_{i}}=1}\)
lub na odwrót...
Znaczyłoby to, że:
\(\displaystyle{ a_{i}=0, c_{i}=1, b_{i}=1}\)
ale z warunku (**) musi być:
\(\displaystyle{ a_{i}+b_{i}-c_{i}+1=0 \mod 2}\)
po podstawieniu mamy:
\(\displaystyle{ 0+1-1+1=1 \mod 2}\)
czyli sprzeczność a więc suma:
\(\displaystyle{ {n \choose k} + {m \choose k} }\) - parzysta...
cnd...