Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2

3.01.2008
czwartek

Kaprekar 2008

3 stycznia 2008, czwartek,

Okazuje się, że liczba 2008 ma własność absolutnie niezwykłą, choć nieco zakręconą. Aby wyjaśnić, w czym rzecz, przyda się algorytmiczny wstęp.

(1) Napisz dowolną liczbę czterocyfrową, byle nie złożoną z czterech jednakowych cyfr (np. 5555) lub trzech jednakowych i czwartej mniejszej lub większej o 1 (np. 1011 albo 6676);
(2) cyfry, z których się składa, ustaw najpierw w porządku rosnącym, a potem malejącym, tworząc w ten sposób dwie nowe liczby;
(3) odejmij mniejszą liczbę od większej;
(4) powtórz etapy (2) i (3) z otrzymaną różnicą i powtarzaj z każdą następną dotąd, aż różnica się „ustabilizuje”.

Od jakiejkolwiek liczby byśmy nie zaczęli, zawsze najdalej po siódmej operacji pojawi się różnica równa 6174, która w kolejnych odejmowaniach już nie będzie się zmieniać, ponieważ 7641 – 1467 = 6174.

Przykład dla liczby 1949 (siedem powtórek):
9941 – 1499 = 8442
8442 – 2448 = 5994
9954 – 4995 = 5355
5553 – 3555 = 1998
9981 – 1899 = 8082
8820 – 288   = 8532
8532 – 2538 = 6174

Ta osobliwa cecha liczb 4-cyfrowych sprawia, że 6174 jest białym krukiem, zwanym stałą Kaprekara – od nazwiska hinduskiego matematyka, który odkrył ją w roku zaczynającym powyższy przykład.
Z czasem stałą Kaprekara zaczęto nazywać każdą liczbę n-cyfrową, jeśli stanowi ona jedyny możliwy finał opisanego procesu, zwanego algorytmem Kaprekara, dla wszystkich liczb n-cyfrowych – oprócz wyjątków analogicznych do wymienionych w (1). W systemie dziesiętnym jest jeszcze jedna taka stała, „obsługująca” liczby trzycyfrowe – 495. Łatwo sprawdzić, że spełnia ona warunek dostateczny, czyli przechodzi sama w siebie po jednorazowej obróbce algorytmem (kroki 1-3): 954 – 459 = 495. Dla n innych niż 3 i 4 stałych Kaprekara nie ma, bo zakończenie stosowania algorytmu może być różne – najczęściej powstaje pętla, czyli różnice zaczynają się cyklicznie powtarzać. Czasem cykl oscyluje między dwiema wartościami, np. dla n = 5 są to 53955 i 59994 (95553 – 35559 = 59994; 99954 – 45999 = 53955).

Pora na unikalność liczby 2008. Otóż jest ona także stałą Kaprekara, czyli białym krukiem – dla n = 7 w trójkowym systemie liczbowym. Aby pokazać, że w tym wypadku warunek dostateczny jest spełniony, należałoby najpierw 2008 „utrójkowić”. Większość redaktorów Polityki miałaby z tym problem, ale dla czytelników Łamibloga to oczywiście pestka, więc nie będę wyjaśniał, dlaczego dziesiętne 2008 równe jest trójkowemu 2202101. Odejmowanie w systemie trójkowym (2221100 – 11222) chyba też nie sprawiłoby Państwu kłopotu. Różnica wynosi 2202101, co potwierdza, że zapewne mamy do czynienia ze stałą Kaprekara. Aby mieć pewność, wypadałoby sprawdzić algorytmicznie prawie wszystkie liczby siedmiocyfrowe (liczbomaniacy już to zrobili).

Znam jeszcze dwie stałe Kaprekara w systemie trójkowym: mniejszą – 5-cyfrową i większą – 8-cyfrową. Obie, zapisane w systemie dziesiętnym, występują w poniższej łamigłówce – stanowią czynniki mnożenia, które należy rozszyfrować.
Cyfry w zapisie działania zastąpiono kwadracikami. Oznaczone na zielono stanowią klucz do rozwiązania, są bowiem „tegoroczne”, czyli każdy zasłania cyfrę 0, 2 lub 8.

Kapre_1.JPG

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 8

Dodaj komentarz »
  1. Działania arytmetyczne w innym systemie liczbowym niż system dziesiętny, to tak jak kazać osobie praworęcznej pisać lewą ręką, a to nie jest takie proste. Być może byłoby łatwiej, gdyby można było zresetować mózg i na nowo wyćwiczyć pewne nawyki.
    A zadanie jest „sehr gut”.

    Pozdrawiam

  2. Na szczęście odejmowanie w każdym systemie liczbowym rządzi się tymi samymi regułami i jest stosunkowo proste . Dlatego nie ma potrzeby przeliczania liczb na system dziesiętny. Po kilku odejmowaniach w systemie trójkowym kolejne są coraz łatwiejsze, i to bez operacji na mózgu 🙂
    Panie Marku , a czy wyznaczał ktoś mediany dla poszczególnych przypadków dla liczby kroków na dojście do stałej Kaprekara, ponieważ jestem ciekawy jak długiej drogi mogę się spodziewać?
    Chyba że odwrócę zagadkę i mnożenie potraktuję nie jako sprawdzenie, ale jako prostsze i szybsze dojście do stałych.

    Pozdrawiam
    AC

  3. Panie Alku, czyżby zamierzał Pan szukać stałych Kaprekara dla liczb różnej długości w różnych systemach liczbowych?
    Niestety, nie wgłębiałem się tak mocno w temat, abym mógł odpowiedzieć na pytanie dotyczące median; z tego, co pamiętam, liczba iteracji dla liczb kilkucyfrowych nie przekracza kilkunastu, ale nie wiem czy i jak szybko rośnie wraz ze wzrostem liczby cyfr.
    Z tabelki na Mathworldzie (a właściwie z jej zaczątku) wnioskuję, że sprawa została gruntownie przeanalizowana.
    Pozdrawiam
    mp

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Rozwiązanie jest nast:
    5332
    x 184
    ———–
    21328
    42656
    5332
    ————
    981088

  6. Dziękuję Panie Marku za informację , że liczba kroków (iteracji) do znalezienia stałej Kaprekara nie przekracza kilkunastu dla liczb kilkucyfrowych .
    Miałem w takim razie trochę szczęścia , ponieważ pięciocyfrową znalazłem w drugim kroku (20211 czyli 184) a ośmiocyfrową w czwartym kroku (21022111 czyli 5332) .
    A moje pytanie wynikało tylko z lenistwa , czy aby nie zmęczę się szukając stałych w kilkudziesięciu odejmowaniach . Los okazał sie łaskawy a odejmowanie w systemie trójkowym rzeczywiście jest proste .

    Wspaniałego roku 2008 dla Gospodarza i wszystkich Gości !

    AC

  7. 5332*184 = 981088

    5332 -> 2102211
    184 -> 20211

  8. Rozumiem, ze trzeba zalozyc ze cyfry 0,2,8 występują tylko na zielonych miejscach. (W kazdym badz razie wtedy potrafie rozwiazac)

    Pytanie:
    1) czy to jest niezbedne zalozenie?
    2) Jesli jest, to moze wystarczy tylko dodac informacje, ze sa liczbami Kaprekara (5-cio i 8-mio cyfrowymi)

    Ad.2 Oczywiscie nie wyznaczajac „komputerowo” tych liczb; ale np. daje to „od ręki” pewne ograniczenia na wielkosci czynnikow.

  9. Esteonie, bardzo trafna uwaga, tzn. wypadałoby dodać, że „zazielenione” są wszystkie cyfry 0, 2, 8.
    Moim zdaniem z informacji, że czynniki sa stałymi Kaprekara (nie liczbami, bo liczby Kaprekara to coś zupełnie innego – jeszcze większe „nikomu-nie-potrzebne” dziwadła) – 5- i 8-cyfrową – praktycznie przydaje sie przy rozwiązywaniu tylko ta druga, bo z niej można wywnioskować, że mnożna zaczyna się co najmniej trójką, a w związku z tym pierwszą cyfrą mnożnika jest co najwyżej trójka.
    mp

    PS nadsyłane rozwiązania uwolnię tuż przed następnym wpisem.

css.php