[Ciągi][Funkcje] Wstrętne i złowieszcze liczby

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
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.
Awatar użytkownika
Swistak
Użytkownik
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

Post autor: Swistak » 8 lip 2011, o 17:02

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: http://www.artofproblemsolving.com/Foru ... 7&t=417049 (które dla tych, którzy czytają moje posty, może się z czymś kojarzyć xD)

Awatar użytkownika
adamm
Użytkownik
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

Post autor: adamm » 13 lip 2011, o 11:02

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}\).

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

[Ciągi][Funkcje] Wstrętne i złowieszcze liczby

Post autor: » 13 lip 2011, o 12:15

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.

Awatar użytkownika
Swistak
Użytkownik
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

Post autor: Swistak » 13 lip 2011, o 22:07

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 ; ).

ODPOWIEDZ