Suma z Newtonem

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Suma z Newtonem

Post autor: mol_ksiazkowy »

:arrow: 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}\)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Suma z Newtonem

Post autor: arek1357 »

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...
ODPOWIEDZ