Matematyka.pl

Wstrętne liczby to liczby, które mają nieparzystą liczbę jedynek w rozwinięciu dwójkowym, a złowieszcze liczby, to liczby, które mają parzystą liczbę jedynek w rozwinięciu dwójkowym (0 też się do nich zalicza).
Dla każdej liczby całkowitej n określamy \(\displaystyle{ f(n)}\), jako różnicę liczności zbioru liczb wstrętnych i złowieszczych mniejszych od n (może być ujemna, jeśli złowieszczych jest więcej). Udowodnij, że \(\displaystyle{ |f(n)| \le 1}\).
P.S. Za nazewnictwo nie wińcie mnie, tylko OEIS

EDIT: Kurde, uświadomiłem sobie, że to jest strasznie proste . No ale, czekam na rozwiązanie . Dla tych, co to zrobią, to "troszkę" trudniejsze zadanie o tychże liczbach: ... 7&t=417049 (które dla tych, którzy czytają moje posty, może się z czymś kojarzyć xD)

Zauważmy, że w parze liczb postaci \(\displaystyle{ \left(2k, 2k+1\right)}\), gdzie \(\displaystyle{ k\in \mathbb{N}}\) występuje tak liczba złowieszcza jak i wstrętna. Koniec xd.
Formalizując trochę, to wynika to z tego, że jeżeli \(\displaystyle{ (2k)_{10}=(1\ldots0)_{2}}\) to dodając obustronnie jedynkę ( korzystając przy tym z tego, że \(\displaystyle{ (1)_{10}=(1)_{2}}\)) dostajemy \(\displaystyle{ (2k)_{10}+(1)_{10}=(2k+1)_{10}=(1\ldots0)_{2}+(1)_{2}=(1\ldots1)_{2}}\), a więc istotnie w parze \(\displaystyle{ \left(2k, 2k+1\right)}\) znajdą się obie rzeczone liczby. Można zatem zauważyć, że dla \(\displaystyle{ n}\) parzystego \(\displaystyle{ f(n)=0}\), a dla nieparzystego \(\displaystyle{ f(n)=\pm1}\).

Inny pomysł (szkic):
Nietrudno zauważyć, że \(\displaystyle{ f(2^k)=0}\) (bo w zbiorze zero-jedynkowych ciągów długości \(\displaystyle{ k}\) jest tyle samo ciągów z nieparzystą liczbą jedynek co z parzystą). I teraz indukcja - załóżmy, że dla \(\displaystyle{ n\le 2^k}\) teza zachodzi i pokażmy, że zachodzi też dla \(\displaystyle{ n\le 2^{k+1}}\). W tym celu wystarczy zauważyć, że jeśli \(\displaystyle{ n\in [0,2^k]}\) jest wstrętna/złowieszcza, to \(\displaystyle{ n+2^k\in [2^k,2^{k+1}]}\) jest złowieszcza/wstrętna (to znaczy odwrotnie), bo różni się tylko o jedynkę. Skoro więc w przedziale \(\displaystyle{ [0,2^k]}\) teza zachodzi (z założenia indukcyjnego), to w przedziale \(\displaystyle{ [2^k,2^{k+1}]}\) też będzie zachodzić (bo wartości \(\displaystyle{ f}\) różnią się tylko znakiem).

Q.

adamm pisze:Zauważmy, że w parze liczb postaci \(\displaystyle{ \left(2k, 2k+1\right)}\), gdzie \(\displaystyle{ k\in \mathbb{N}}\) występuje tak liczba złowieszcza jak i wstrętna. Koniec xd.
Formalizując trochę, to wynika to z tego, że jeżeli \(\displaystyle{ (2k)_{10}=(1\ldots0)_{2}}\) to dodając obustronnie jedynkę ( korzystając przy tym z tego, że \(\displaystyle{ (1)_{10}=(1)_{2}}\)) dostajemy \(\displaystyle{ (2k)_{10}+(1)_{10}=(2k+1)_{10}=(1\ldots0)_{2}+(1)_{2}=(1\ldots1)_{2}}\), a więc istotnie w parze \(\displaystyle{ \left(2k, 2k+1\right)}\) znajdą się obie rzeczone liczby. Można zatem zauważyć, że dla \(\displaystyle{ n}\) parzystego \(\displaystyle{ f(n)=0}\), a dla nieparzystego \(\displaystyle{ f(n)=\pm1}\).

Oczywiście rozwiązanie jest dobre, ja na początku myślałem mniej więcej o takim rozwiązaniu, jak rozwiązanie Qńa i założyłem ten temat, a potem wymyśliłem to rozwiązanie i wtedy dopisałem, że to zadanie jednak jest strasznie proste .
Jednak pierwsza linijka Twojego rozwiązania brzmi dużo mądrzej niż to, co potem napisałeś. Po co w ogóle odnosisz się do takiego głupiego tworu jak system dziesiętny ? Zapis \(\displaystyle{ (2k)_{10}}\) jest bez sensu, gdyż \(\displaystyle{ 2k}\) nie jest to liczba zapisana w żadnym systemie pozycyjnym, jest po prostu jakąś sobie liczbą.
Nie zmienia to jednak faktu, że rozwiązanie ideowo jest poprawne ; ).