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)
[Ciągi][Funkcje] Wstrętne i złowieszcze liczby
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
- adamm
- Użytkownik
- Posty: 253
- Rejestracja: 1 paź 2009, o 22:04
- Płeć: Mężczyzna
- Lokalizacja: Sopot/Warszawa
- Podziękował: 5 razy
- Pomógł: 15 razy
[Ciągi][Funkcje] Wstrętne i złowieszcze liczby
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}\).
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}\).
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
[Ciągi][Funkcje] Wstrętne i złowieszcze liczby
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.
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.
- Swistak
- Użytkownik
- Posty: 1874
- Rejestracja: 30 wrz 2007, o 22:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 99 razy
- Pomógł: 87 razy
[Ciągi][Funkcje] Wstrętne i złowieszcze liczby
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 .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}\).
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 ; ).