wredne potęgi Basia: Eta, Bogdan, As, Jakub, b. i wszyscy inni chętni Zetknęłam się z takim zadaniem i nie mam pojęcia jak go ugryźć. Oto ono: Proszę określić wszystkie liczby, które można przedstawić na dokładnie 2010 sposobów jako sumę potęg o podstawie 2 i nieujemnych całkowitych liczbach jako wykładniki. W każdej z tych sum potęga o tym samym wykładniku może wystąpić co najwyżej trzy razy. Należy uważać także na to, ze dwa sposoby należy uznać jako jeden jeśli sposoby te różnią się tylko kolejnością zapisania potęg, nie jednak samymi potęgami. Oprócz tego suma może składać się w tym zadaniu także tylko z jednej potęgi. Udowodnij poprawność twojego wyniku. Metodą zwykłego rozpisywania wyszło mi, że dla liczb 2n i 2n+1 jest tych sposobów n+1 ale nie umiem tego udowodnić.

Basia: Godzi, As może Wam coś do głowy przychodzi ?

Basia: O Timuś jest ! Może Ty masz jakiś genialny pomysł

AS: Z aparatem fotograficznym witam wiosnę.

tim: Jestem od 10 i mnie nie zauważyłaś?

Basia: Nie spiesz się tak Asie, bo zima nam na złość może jeszcze zrobić. Chyba nie patrzyłam na spis obecnych, Timuś

justyś: pomożesz

b.: Trochę się zastanawiałem, ale wiele nie zrobiłem. Przedstawiamy liczbę, powiedzmy N, w systemie dwójkowym, czyli jako sumę: N = 2^k₁+2^k₂+...+2^k_n, gdzie k₁ < k₂ <...<k_n No to już jeden rozkład na sumę podanych składników mamy, pytanie, ile można dostać innych rozkładów. Zastanówmy się najpierw jak jest dla liczb N postaci 2^p. Oznaczmy liczbę ich rozkładów jak w zadaniu przez F_p. Dla 2⁰=1 mamy 1 rozkład, Dla 2¹=2 mamy 2 rozkłady (2, 1+1), Dla 2²=4 mamy 3 rozkłady (4, 2+2, 2+1+1). Zatem F₀=1, F₁=2, F₂=3. Dla 2^p, gdzie p>2, mamy: jeden rozkład 2^p (na jeden składnik), plus F_p−1 rozkładów postaci 2^p−1 + (rozkład 2^p−1), plus (F_p−2)−1 rozkładów postaci 2^p−2 + 2^p−2 + 2^p−2 + (rozkład 2^p−2 na więcej niż 1 składnik), dostajemy więc wzór rekurencyjny F_p = F_p−1+F_p−2, więc F_p jest ciągiem Fibonacciego. Niestety, 2010 nie jest liczbą Fibonacciego Sytuacja trochę się komplikuje, jak jedynek w zapisie dwójkowym jest więcej. Pozdrowienia

Basia: Dziękuję b. Jeśli coś jeszcze wymyślisz napisz. Zależy mi.

b.: hmm pomyliłem się, będzie więcej rozkładów niż napisałem są jeszcze możliwe rozkłady 2^p−2 + 2^p−2 + (rozkłady 2^p−1 na składniki mniejsze niż 2^p−2) takich rozkładów 2^p−1 na składniki mniejsze niż 2^p−2 jest: wszystkich (na dowolne składniki) F_p−1 w tym 1 na 1 składnik 2^p−1, F_p−2 rozkładów 2^p−2 + (rozkład 2^p−2) pozostałe mają składniki < 2^p−2 czyli razem F_p−1 − (F_p−2+1) rozkłady, w których byłby tylko jeden składnik 2^p−2 i żadnych większych są już niemożliwe (bo 2^p−2 + 3*(2^p−3+...+2⁰) < 2^p) czyli jednak właściwy (chyba ) wzór rekurencyjny to F_p = F_p−1 + F_p−2 + (F_p−1 − (F_p−2+1)) = 2F_p−1 − 1 dla p>2 e nie jestem przekonany...

Godzio: zdesperowany człowiek któremu nie pomogłem ?

Godzio: ...

Basia: Nie akceptujemy tutaj takiego słownictwa. Prawda Godzio ?

Godzio: Oczywiście

Godzio: Prawda, to nie mój poziom.

Godzio: nie da się jakoś zablokować tych ip ?

Godzio: Wiem, że mam neo

Basia: Da się zblokować. Blokada działa do 4 w nocy. Teraz już chyba nie warto.

tim: Trochę pokasowane, ale już ktoś się zmył.

Synek: yyy nie ?

terra: nie macie co robic w nocy?

Basia: Hm.... Chyba niezupełnie się zgadza np. 2=2¹=2⁰+2⁰ F₂=2 3=2¹+2⁰=2⁰+2⁰+2⁰ F₃=2 natomiast wg tego drugiego wzoru F₃ = 2F₂−1=2*2−1=3 ale ja już zupełnie przy tym zadaniu zgłupiałam

b.: a nie nie, ja to tylko dla liczb postaci 2ⁿ pisałem, więc F₃ dotyczy rozkładów liczby 2³=8: 8 = 4+4 = 4+2+2 = 4+2+1+1 = 2+2+2+1+1, więc F₃=5 oczywiście od potęg dwójki do dowolnych liczb jeszcze chyba daleko, ale od czegoś zacząć trzeba

Basia: a racja, tak chyba się zgadza, chociaż już teraz niczego nie jestem pewna muszę na dziś odpuścić, może jak to prześpię, zacznę na nowo myśleć

b.: Ok, chyba mam oznaczmy przez A_n liczbę takich rozkładów liczby n mamy A₁ = 1, A₂=A₃=2, A₄=A₅=3, ... znajdziemy wzór rekurencyjny: 1. jeśli n=2k, to rozkład n na składniki możemy dostać na następujące sposoby: n = 2*(rozkład k na składniki) (tzn. każdy składnik z rozkładu k mnożymy przez 2) albo n = 1+1+2*(rozkład k−1 na składniki) w ten sposób dostaniemy każdy możliwy rozkład dokładnie raz, więc A_2k = A_k + A_k−1 1. jeśli n=2k+1, to rozkład n na składniki możemy dostać na następujące sposoby: n = 1 + 2*(rozkład k na składniki) albo n = 1+1+1+2*(rozkład k−1 na składniki) w ten sposób dostaniemy każdy możliwy rozkład dokładnie raz, więc A_2k+1 = A_k + A_k−1 Ten wzór rekurencyjny pozwala udowodnić indukcyjnie Twoją hipotezę. Wobec tego A_2*2009 = A_2*2009+1 = 2010 i to są jedyne rozwiązania.

Basia: b. jesteś WIELKI Dziękuję

AS: A ja się nie zgadzam z Basią! b. jesteś bardzo WIELKI

tim: b. jest NAJWIĘKSZY!

miki: Stanowczo za mało b jest WIELKI²⁰¹⁰

b.: no troszkę rzeczywiście ostatnio przytyłem, ale − bez przesady − nie jestem jeszcze wcale taki wielki! pozdrowienia

AS: Ale zaimponowałeś!