Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Tym razem bez wprowadzenia teoretycznego – zapraszam na porcję zadań o różnej tematyce, związanych z potęgami dwójki.
Zadania
1. Rozstrzygnąć, czy istnieje taka liczba naturalna \(k,\) że w zapisie dziesiętnym liczby \(2^k\) każda z cyfr: \(0,1,2,\ldots,9\) występuje taką samą liczbę razy. (LXX OM)
Sprawdzić podzielność przez \(3.\)
2.Liczby rzeczywiste \(x,\) \(y,\) \(z\) spełniają równość \(x+y+z=0.\) Udowodnić, że \(x\cdot2^x+y\cdot2^y+z\cdot2^z\ge0.\) (XI Wielkopolska Liga Matematyczna)
Liczby \(t\) i \(2^t-1\) są tego samego znaku, więc \(t(2^t-1)\ge 0.\)
3. Rozstrzygnąć, czy istnieje wielokąt, którego boki mają długości wyrażające się różnymi potęgami dwójki o wykładnikach całkowitych nieujemnych.
Najdłuższy bok miałby długość większą od sumy długości pozostałych boków, gdyż \(\sum_{k=0}^{n-1}2^k<2^n.\)
4. Niech \(a_n\) oznacza najmniejszą liczbą całkowitą dodatnią, która ma dokładnie \(n\) dzielników. Udowodnić, że w tym ciągu występuje nieskończenie wiele potęg dwójki.
Jeśli \(p\) jest liczbą pierwszą, to \(a_p=2^{p-1}.\)
5. Ustalmy liczbę nieparzystą \(n.\) Dla \(k=1,2,\ldots,n\) określamy taką liczbę naturalną \(a_k,\) że \(2^{a_k-1}\le\frac nk<2^{a_k}.\) Udowodnić, że \(a_1+a_3+a_5+\ldots+a_n=n.\) (IX WLM)
W zbiorze \(\{1,2,\ldots,n\}\) jest dokładnie \(a_k\) liczb, które można (jednoznacznie!) zapisać w postaci iloczynu liczby nieparzystej \(k\) i potęgi dwójki.
6. Wykazać, że dla całkowitych dodatnich \(n\) liczba \(n!\) nie dzieli się przez \(2^n.\)
Na mocy wzoru Legendre’a \(\nu_2(n!)=\sum_{k\ge 1}\lfloor n/2^k\rfloor < n.\)
7. Niech \(k\ge2\) będzie liczbą naturalną. Dowieść, że jeśli iloczyn \(k\) kolejnych liczb naturalnych dzieli się przez \(4^k,\) to dokładnie jeden z czynników dzieli się przez \(2^{k+1}.\) (XI WLM)
Niech \(P=(m-a)\dots(m+b)\) będzie rozważanym iloczynem, przy czym \(m=t\cdot 2^n\) dla nieparzystego \(t\) z maksymalnym \(n.\) Wtedy, po skorzystaniu z tezy zadania 6, dostajemy: \(2k \le \nu_2(P) = n+\nu_2(a!)+\nu_2(b!)\le n+a+b = n+k-1.\)
8. Dane są liczby całkowite dodatnie \(k,\) \(m\) i \(n,\) dla których \(\texttt{NWD}(km,n)=1.\) Udowodnić, że istnieją takie liczby całkowite dodatnie \(a,\) \(b,\) \(c,\) że \(a^k+b^m=c^n.\)
Istnieją takie liczby całkowite dodatnie \(x\) i \(y,\) że \(x(km)+1=yn\) (por. Kącik 29 w \(\Delta^5_{21}\)).
9. W pewnym kraju jest \(n+1\) miast, ponumerowanych liczbami od \(0\) do \(n.\) Miasta o numerach \(a\) i \(b\) mają połączenie drogowe wtedy i tylko wtedy, gdy \(a+b\) jest potęgą dwójki. Udowodnić, że z każdego miasta można dojechać do każdego innego. (XIII WLM)
Z każdego miasta o niezerowym numerze można dojechać do jakiegoś miasta o numerze mniejszym.
10. Dla każdej liczby całkowitej dodatniej \(n\) porównać liczby \(2^{n!}\) i \((2^n)!.\)
Wykorzystać oszacowanie \(m!<m^m\) dla \(m=2^n.\) To rozwiązuje problem dla \(n\ge 6.\)
11. W ciągu niemalejącym \((a_1,a_2,a_3,\ldots)\) występują wyłącznie liczby całkowite dodatnie. Każda liczba występuje w nim dokładnie tyle razy, ile wynosi największy wykładnik potęgi dwójki dzielącej tę liczbę. Początkowe wyrazy wyglądają następująco: \[2,4,4,6,8,8,8,10,12,12,14,16,16,16,16,18,20,20,\ldots\] Udowodnić, że \(a_n>n\) dla wszystkich całkowitych dodatnich \(n.\) (XIII WLM)
Liczba \(k\) występuje w ciągu \(\nu_2(k)\) razy dla \(k=1,2,\ldots,n,\) więc \(n\le \nu_2(1)+\nu_2(2)+\ldots+\nu_2(a_n) = \nu_2(a_n!) < a_n.\)
12. Wyznaczyć wszystkie liczby całkowite dodatnie, które można przedstawić w postaci \(\frac{a}{b}+\frac{a+1}{b+1}\) dla pewnych całkowitych dodatnich \(a\) i \(b.\) (Matematyczny Kalendarz Adwentowy 2021)
Jeśli \(n=\frac{a}{b}+\frac{a+1}{b+1},\) to \(n-2=\frac{(2b+1)(a-b)}{b(b+1)},\) więc \(2b+1\mid n-2\) (dlaczego?), czyli \(n-2\) nie może być potęgą dwójki.
W drugą stronę, jeśli \(n-2\) nie jest potęgą dwójki, to ma dzielnik nieparzysty \(d\) i można wziąć \(b=\frac 12(d-1)\) i \(a=\frac{(d-1)(dn+n-2)}{4d}.\)
13. Rozważmy wszystkie liczby nieparzyste, które w zapisie dwójkowym mają dokładnie \(120\) jedynek. Udowodnić, że wśród nich jest nieskończenie wiele kwadratów liczb naturalnych. (MKA 2023)
\((2^{a_1}+\ldots+2^{a_{15}})^2 = \sum_{i}2^{2a_i}+\sum_{i<j}2^{a_i+a_j+1}\) – jest to suma \(120\) potęg dwójki. Należy jeszcze zadbać o to, by były to różne potęgi – wystarczy założyć \(a_{i+1}>2a_i.\)
14. Dana jest liczba naturalna \(n\ge2.\) Niech \(r_k\) oznacza resztę z dzielenia przez \(n\) liczby \(1+2+\ldots+k.\) Wyznaczyć wszystkie liczby \(n,\) dla których \((r_1,r_2,\ldots,r_{n-1})\) jest permutacją ciągu \((1,2,\ldots,n-1).\) (LX OM)
Niech \(n=2^m.\) Jeśli \(r_i=r_j,\) to \(2^{m+1}\mid(i-j)(i+j+1),\) co prowadzi do \(i=j.\)
Niech \(n=mp,\) \(p>2\) pierwsze. Wtedy liczby \(r_{kp}\) i \(r_{(k+1)p-1}\) są podzielne przez \(p\) dla \(k=0,1,\ldots,m-1.\)
15. Wyznaczyć liczbę sposobów zapisu liczby całkowitej dodatniej \(n\) w postaci sumy potęg dwójki o wykładnikach całkowitych nieujemnych, jeśli każdy z wykładników może powtórzyć się co najwyżej trzy razy. (LXVI OM)
Niech \(n=\sum_k a_k2^k\) dla \(a_k\in\{0,1,2,3\}.\) Określmy \(x=\sum_{k\colon a_k\geq 2}2^k\) oraz \(y=\sum_{k\colon a_k\in\{1,3\}}2^k.\) Zadajemy w ten sposób bijekcję między szukanymi sposobami zapisu a rozwiązaniami równania \(2x+y=n.\)
16. Rozważmy bardzo długi rząd wiaderek. W środkowym znajduje się \(n\) krówek, pozostałe są puste. Możemy wykonywać operacje dwóch typów: albo z wiaderka liczącego co najmniej \(3\) krówki przenosimy jedną krówkę do wiaderka bezpośrednio po prawej stronie i dwie krówki do wiaderka bezpośrednio po lewej, albo z wiaderka z co najmniej \(2\) krówkami przenosimy jedną krówkę do wiaderka bezpośrednio po prawej stronie i jedną zjadamy. Załóżmy, że po jakimś czasie nie da się już wykonać żadnego ruchu. Wykazać, że liczba pozostałych krówek równa jest liczbie jedynek w zapisie dwójkowym liczby \(n.\) (USA MTS 2019, zmodyfikowane)
Ponumerujmy wiaderka liczbami całkowitymi tak, żeby \(n\) krówek było w wiaderku o numerze \(0.\) Kierunki lewo i prawo rozważamy tak jak na osi liczbowej. Niech \(a_k\) będzie liczbą krówek w wiaderku o numerze \(k.\) Wówczas wartość wyrażenia \(\sum_ka_k\cdot 2^k\) się nie zmienia.