Bankiet dla wybrańców
W wejściówce na bankiet z poprzedniego wpisu nie krył się żaden podstęp. Wbrew przypuszczeniom Andrzeja zadanie było po prostu proste. Może podstępnie będzie teraz, czyli przed kolejnym matbankietem potęgowym. Przedtem jednak powróćmy na chwilę do minionego.
Aby określić minimalną liczbę kroków warunkujących dotarcie „na piechotę” od x do x^n, stosuje się zwykle prosty schemat: k-krotne podnoszenie do kwadratu kolejnych kwadratów x (x^2^k), czyli mnożenie ich przez siebie, aż do znalezienia się w okolicach x^n. Następnie, jeśli to konieczne, wykonywane jest mnożenie lub dzielenie przez potęgę obliczoną wcześniej lub dodatkowo. Oczywistym jest, że do celu nie dotrze się szybciej, niż w [log2n] krokach (nawias kwadratowy oznacza część całkowitą wartości logarytmu). Dla n=1000 [log2n] = 9, jednak działań potrzeba dwunastu – dziesięciu mnożeń do x^1024, następnie dodatkowego mnożenia tworzącego x^24 i wreszcie dzielenia „cofającego”. Wędrówka byłaby nieco bardziej skomplikowana i trwałaby dłużej (ile co najmniej kroków?), gdyby działania ograniczyć tylko do mnożeń. Jednak to i tak pestka w porównaniu z analogicznym jak poprzednio warunkiem, który należało spełnić, chcąc dostać się na trzeci bankiet u szalonego matematyka.
Tym razem matematyk zażyczył sobie wpisania na zaproszeniu minimalnej liczby działań (mnożeń i dzieleń), które należy wykonać, aby obliczyć wartość x^170. Konieczne było także podanie przykładu z tym minimum.
Proszę spróbować znaleźć tę liczbę, wspierając ją oczywiście przykładowym ciągiem działań – nawet jeśli na bankiet nie mają Państwo ochoty.
Komentarze
Rozumiem, ze „x” jest dane i ustalone? Choc niekonieczne podane…
Jesli nie to ja mam szybkie rozwiazanie:
0 dzialan 🙂
Wezmy x=1 … 🙂
A z innej beczki – minimalna ilosc dzialan to [log_2 n] +1, chyba ze log_2 n jest liczba calkowita…
Dzialan tylko z mnozeniem w poprzednim zadaniu wystarczy 15.
Znalazłam 10. Szukałam, czy można 9 wykonac 9 działań, ale nie udało mi się znaleźc.
Oto przykład:
x*x
x^2*x^2
x^4*x^4
x^8*x^8
x^16*x^16
x^32*x^32
x^64*x^64
x^128*x^32
x^160*x^8
x^168*x^2
Potrafie wykonac 9 dzialan:
x^2, x^4, x^8, x^16
x^17, x^34, x^68, x^136
x^170=x^136*x^34.
Niech x=2.
4=2*2
16=4*4
256=16*16
65536=256*256
131072=65536*2
17179869184=131072*131072 (tu zarzucilem liczenie na kartce)
295147905179352825856=17179869184^2
87112285931760246646623899502532662132736=(poprzedni wynik)^2
1496577676626844588240573268701473812127674924007424= (poprzedni wynik)*17179869184.
Uffff.
Okropienstwo.
Ciekawe, czy ktos sie skusi na uzycie x inego niz 2?
Tym razem nie będę uwalniał przedwcześnie także błędnych rozwiązań, bo byłyby podpowiedziami.
mp
Udało mi się znaleźc 9 działań:
x*x
x^2*x^2
x^4*x^4
x^8*x^2
x^10*x^10
x^20*x^20
x^40*x^40
x^80*x^80
x^160*x^10
wydaje się, ze w 9, ale jak będe miał czas to jeszcze pomyślę:)
1-2-3-5-10-20-40-80-160-170
pozdr
Uzupełnienie do poprzedniego wpisu.
Gdyby działania ograniczyć tylko do mnożenia, to wędrówka trwałaby o dwa kroki dłużej, czyli czternaście kroków wystarczy do wejścia na bankiet
x*x=x^2
x^2*x^2=x^4
x^4*x^4=x^8
x^8*x^8=x^16
x^16*x^16=x^32
x^32*x^32=x^64
x^64*x^64=x^128
x^128*x^128=x^256
x^256*x^256=x^512
x^512*x^256=x^768
x^768*x^128=x^896
x^896*x^64=x^960
x^960*x^32=x^992
x^992*x^8=x^1000,
ale nie na ten bankiet, bo reguły wejścia na imprezę ustala matematyk, więc …, gdyby działania ograniczyć tylko do mnożeń, to wędrówka trwałaby o zero kroków dłużej, czyli wystarczy dwanaście kroków
x*x=x^2
x^2*x^2=x^4
x^4*x^4=x^8
x^8*x^8=x^16
x^16*x^16=x^32
x^32*x^32=x^64
x^64*x^64=x^128
x^128*x^128=x^256
x^256*x^256=x^512
x^512*x^512=x^1024
x^1024*x^8=x^1032
x^1032*x^-32 (mnożymy odwrotność potęgi)
………………………………………………………………………….
Trzecia próba wejścia na bankiet.
Liczba działań: 9?
Przykład:
x*x=x^2
x^2*x^2=x^4
x*x^4=x^5
x^5*x^5=x^10
x^10*x^10=x^20
x^20*x^20=x^40
x^40*x^40=x^80
x^80*x^80=x^160
x^10*x^160=x^170
Pozdrawiam
Moim zdaniem wystarczy 9 działań. Znalazłem 6 takich rozwiązań, oto jedno z nich:
x*x = x^2
x^2 * x^2 = x^4
x^4 * x^4 = x^8
x^8 * x^8 = x^16
x^16 * x = x^17
x^17 * x^17 = x^34
x^34 * x^34 = x^68
x^68 * x^68 = x^136
x^136 * x^34 = 170.
Poszukując rozwiązania w naturalny sposób znajduje się rozwiązanie z 10 mnożeniami i dzieleniami. Istota lepszego rozwiązania leży w zapisie dwójkowym liczby 170 = 10101010. Można ją zapisać jako sumę dwóch „podobnych” liczb:
10100000 + 1010 lub 10001000 + 100010.
Nie umiem sobie wyobrazić, jak w tym zadaniu błędne rozwiązania mogą być podpowiedziami? Albo się wie albo nie wie jak je rozwiązać. Chyba, że chodzi tu o błędy edytorskie. A może istnieje jeszcze lepsze rozwiązanie?.
Z pozdrowieniami,
Jazz_off
Ujawnienie błędnego rozwiazania w n krokach podpowiada, że należy szukać rozwiązania w n-1 krokach.
mp
Sama policzyłabym tak:
x^2
(x^2)^2 = x^4
(x^4)*x = x^5
(x^5)^2 = x^10
(x^10)^2 = x^20
(x^20)^2 = x^40
(x^40)^2 = x^80
(x^80)^2 = x^160
(x^160)*(x^10) = x^170
Wystarczy 9 operacji mnożenia.
a=x*x=x^2
b=a*a=x^4
c=b*b=x^8
d=c*c=x^16
e=d^x=x^17
f=e*e=x^34
g=f*f=x^68
h=g*g=x^136
i=h*f=x^170