Funkcja Iza: Funkcja f :{1,2,3,...,2008}→N przyporządkowuje liczbie n taką liczbę naturalną k, że 2^k jest dzielnikiem liczby ( 2n ) n i 2^k+1 nie jest dzielnikiem liczby ( 2n ) n . Dla ilu argumentów funkcja f przyjmuje wartość 7? Zapis: ( 2n ) n to symbol Niutona.

Basia: Wiem o co tu chodzi, ale kompletnie gubię się w zapisach. Może macie jakiś pomysł ?

Iza: A mogłabyś mi wytłumaczyć o co w tym chodzi? Może sobie sama dam radę dalej.

b.: Jest taki ogólny fakt, że liczba pierwsza p dzieli n! dokładnie w wykładniku równym [n/p] + [n/p²] + [n/p³] + ... ( [x] oznacza tu część całkowitą x) Myślę, że w ten sposób dałoby radę. Ale mam jakieś dziwne wrażenie, że to jakieś proste jest

b.: Jest taki ogólny fakt, że liczba pierwsza p dzieli n! dokładnie w wykładniku równym [n/p] + [n/p²] + [n/p³] + ... ( [x] oznacza tu część całkowitą x) Myślę, że w ten sposób dałoby radę. Ale mam jakieś dziwne wrażenie, że to jakieś proste jest

b.: Podam może przykładowe wartości: żeby policzyć f(3), liczymy (6 po 3) = 20, patrzymy jaka maksymalna potęga dwójki dzieli 20: 2²=4 dzieli 20, ale 2³ już nie zatem f(3)=2 (maksymalny wykładnik) a np. dla f(10): (20 po 10) = 11*12*...*20 / (10!) = = 11*2*13*2*15*2*17*2*19*2 / (1*3*5*7*9) czyli tutaj f(10)=5 (bo tyle dwójek mamy w rozkładzie) o chyba się mi samo rozwiązało

b.: A nie, pomyłka! powinno być (20 po 10) = 11*12*...*20 / (10!) = = 11*2*13*2*15*2*17*2*19*2 / (1*2*3*4*5) czyli jednak f(10)=2 (pięć dwójek w liczniku minus trzy w mianowniku) czyli jednak się mi nie rozwiązało

Basia: Ja mam przede wszystkim problem z jakimś sensownym zapisem (2n nad n). Wiem, że wszystkie parzyste z mianownika skrócą się z parzystymi z licznika, ale liczby tych, które zostaną w liczniku nie udaje mi sie zapisać.

b.: Ok druga próba - skorzystajmy z tego faktu powyżej: 2 dzieli (2n)! dokładnie w wykładniku [2n/2] + [2n/4] + [2n/8] + ... = n + [n/2] + [n/4] + ... a n! dokładnie w wykładniku [n/2] + [n/4] + ... więc 2 dzieli (n!)² w wykładniku 2*([n/2] + [n/4] + ...) Zatem f(n) = (n + [n/2] + [n/4] + ... ) - 2*([n/2] + [n/4] + ...) pytanie jest więc o znalezienie tych n ze zbioru {1,2,...2008}, dla których 7 = (n + [n/2] + [n/4] + ... ) - 2*([n/2] + [n/4] + ...) czyli 7 = n - ([n/2] + [n/4] + ...) To już się chyba da policzyć... A co na to Iza?

Basia: Po rozpisaniu wychodzi mi, że jeśli skracać tylko parzyste to dla n parzystego (2n nad n) = (n+1)*(n+3)*.......................*(2n-1)*2^n/2 ------------------------------------------------------ 1*2*3*....*(n/2) (n+3)*(n+5)*................*(2n-1)*2^(n-1)/2 (2n+2 nad n+1) =-------------------------------------------------------- 1*2*3*.........*[(n+1)/2]*2^(n-1)/2 i za diabła nie potrafię wyliczyć ile tam jeszcze w mianownikach "dwójek" ZOSTAŁO niby to powinno być: 2+4+6+....+(n/2) = 2*1 + 2*2 + 2*3+.....+2*(n/4)

Eta: Proponuję "korki 24h"

b.: Rozwiązuję dalej: 7 = n - ([n/2] + [n/4] + ...) = (n/2 + n/4 + n/8 + ...) - ([n/2] + [n/4] + ...) = = (n/2 - [n/2]) + (n/4 - [n/4]) + (n/8 - [n/8]) + ... a to chyba = liczba jedynek w zapisie n w systemie dwójkowym ale nie jestem pewien

Basia: A jak policzyć sumę [n/2] + [n/4] + [n/8]+............................... ?

Basia: chyba coś tu nie gra ! np. dla n = 10 byłoby (5 - 5) + (2,5 - 2) + (10/8 - 1) + (1-1) = 1/2 + 2/8 = 1/2 + 1/4 = 3/4 czy coś źle liczę ?

Basia: ale żadnego błędu w Twoim rozumowaniu też nie widzę !

b.: no źle, bo skąd (1-1)? zamiast tego jest (10/16 - 0) + (10/32 - 0) + ... = 10/8 = 5/4, co razem z Twoimi 3/4 daje 2 -- jak trzeba i 10 = 1010₂ czyli się zgadza (ta suma jest nieskończona... wprawdzie [n/2^k] równa się zero od pewnego miejsca, ale już n/2^k (bez części całkowitej) nie)

b.: Nie jestem pewien co do tej liczby jedynek w rozwinięciu dwójkowym, ale reszta powinna być ok (modulo durne pomyłki )

Basia: no jasne; podzieliłam przez 10 (chyba pójdę spać)

Basia: Reszta jest o.k. Z całą pewnościa!

b.: No to się Basiu pobawiliśmy przy fajnym zadanku, a Izy już chyba dawno nie ma

Basia: Zapewne, poza tym obawiam się, że trzeba by jej to znacznie dokładniej wytłumaczyć. A swoją droga ciekawa jestem skąd to zadanie ? Może Iza odpowie. I teraz to już stanowczo dobranoc !

b.: Poza tym, wcale go jeszcze do końca nie rozwiązaliśmy... Dobranoc!

Basia: Fakt, ale reszta to "betka". 2008 w zapisie dwójkowym to 11111011000 (11 miejsc) więcej nie będzie ma być 7 "jedynek" i 4 "zera" czyli tych rozwiązań będzie tyle ile jest sposobów ustawienia 4 zer i 7 jedynek na 11 miejscach czyli (11 nad 4) = (11 nad 7) czyli 11! / (4!*7!) = 8*9*10*11 / 1*2*3*4 = 3*10*11 = 330

Basia: I to już jest rozwiązanie, bo w zadaniu zadano pytanie "dla ilu argumentów f. przyjmuje wartość 7"

Iza: Dzięki wielkie za rozwiązanie Jesteście kochani Nawet to zrozumiałam Jeszcze raz dziękuje

b.: ,,czyli tych rozwiązań będzie tyle ile jest sposobów ustawienia 4 zer i 7 jedynek na 11 miejscach czyli (11 nad 4) = (11 nad 7)'' tak by było, gdyby pytanie było o zbiór {1,2,...,2047} (2047=11 111 111 111₂) trzeba więc od 330 odjąć te liczby ze zbioru {2009, ..., 2047}, które mają 7 cyfr 1 w zapisie dwójkowym Ale... czy to już jest takie jasne, że (n/2 - [n/2]) + (n/4 - [n/4]) + (n/8 - [n/8]) + ... = liczba jedynek w zapisie n w systemie dwójkowym Na razie nie zostało to uzasadnione...

Basia: W kwestii (n/2 - [n/2]) + (n/4 - [n/4]) + (n/8 - [n/8]) + ... = liczba jedynek w zapisie n w systemie dwójkowym uwierzyłam Ci na słowo. 2008 = 11 111 011 000₂ 2048 = 11 111 111 111₂ to o ile dobrze rozumuję może być tylko jedna liczba n taka,że: 2008 < n ≤ 2048 i mająca w zapisie 7 "jedynek" mianowicie: 11 111 110 000₂ czyli to byłoby 329. W kwestii zapisu spróbuję pogrzebać w literaturze. Jestem prawie pewna, że sobie tego nie wymyśliłeś. A swoją drogą nie przyznała się co studiuje (bo, że nie ze szkoły średniej to zadanie, jestem pewna). Podejrzewam informatykę.

Mickej: 2048₁₀=100000000000₂ same jedynki to zawsze liczba nieparzysta bo ostatni bit tzn 1 ma wartość 1 lub 0

Mickej: a podziw za rozwiązanie zadania bo ja sie w samym zapisie pogubiłem

Basia: oczywiście Mickey masz rację chodziło o 2047 wszędzie tam ma być 2047 zamiast 2048