Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2

11.06.2017
niedziela

6174 do 1

11 czerwca 2017, niedziela,

Dawno temu pisałem o tzw. stałej Kaprekara, czyli o liczbie 6174, która kończy każdy specyficzny ciąg działań na liczbach czterocyfrowych – szczegóły tu albo w Wikipedii. Przed miesiącem powróciłem do tego tematu w Świecie Nauki w nieco szerszym kontekście, dotyczącym procesu iteracji. Przy okazji zamieściłem zadanie tylko formalnie związane z tą stałą, które wywołało kontrowersje, więc gwoli ich rozstrzygnięcia postanowiłem przytoczyć to zadanie w Łamiblogu.

Zbiór 6174 liczb – od 1 do 6174 – poddano następującej iteracji (powtarzanie tej samej instrukcji): w każdym kroku dwie dowolne liczby zastępowano ich nieujemną różnicą. Iteracja zakończyła się jedną liczbą. Jaką, jeśli liczba ta jest dzielnikiem 6174 i nie zawiera żadnej z cyfr tworzących liczbę 6174?

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 13

Dodaj komentarz »
  1. Eksperyment komputerowy pokazuje, że zbiór zmierza w stronę zerojedynkową.
    W pewnym momencie wydaje się, że mamy jakiś tam constans:
    proporcje zer i jedynek mniej więcej jeden do jednego, czyli po około 50% zbioru.
    Ale (i to „ale” jest według mnie najciekawsze):
    Inuicja podpowiada, że zera wygrają.
    Wystarczy tylko odpowiednio długo poczekać.

    Szkopuł w tym, że można mieć problem z uznaniem zera za dzielnik liczby 6174.

  2. W nawiązaniu do komentarza apartado:
    Powiedzmy, że w pierwszym ruchu wylosowane zostały liczby 2 i 3, których nieujemna różnica wynosi 1. Czy teraz w zbiorze liczb, z których usunięte zostały liczby 2 i 3, są dwie liczby 1? Jeżeli tak, to najprawdopodobniej iteracja zakończy się zerem. Jeżeli jednak jedynka zostanie tylko jedna, czyli w zbiorze wszystkie liczby będą różne, to zero nigdy sie nie pojawi.

  3. Jeśli wybierzemy dwie liczby o tej samej parzystości, dostajemy parzystą różnicę. W przeciwnym wypadku nieparzystą. To powoduje, że w naszym zbiorze liczba nieparzystych liczb przez cały proces zachowuje swoją parzystość 😉 Tzn. jeśli na początku mieliśmy 1111 nieparzystych, to na końcu zostanie jedna nieparzysta. Jeśli było ich 1112, to wynik będzie parzysty. W początkowym zbiorze {1,…,N} będzie parzysta liczba nieparzystych, gdy N%4 = 0 lub 3.
    6174%4 = 2, więc wynik będzie nieparzysty.

    Wynikiem iteracji może być każda nieujemna liczba i nie większa od największej liczby ze zbioru, która dodatkowo spełnia powyższy warunek na parzystość*.
    Wśród nieparzystych dzielników 6174 są dwa niezawierające jej cyfr: 3 i 9. I to są rozwiązania zadania.

    *Dowód (dla masochistów). Skonstruujmy funkcję zwracającą zbiór zdefiniowaną tak:
    F(1) = {1}
    F(2) = {1}
    F(N) = N-F(N-1) U |(N-(N-1))-F(N-2)| = N-F(N-1) U |1-F(N-2)|, N > 2
    U oznacza sumę zbiorów. Odejmowanie liczby i zbioru daje w wyniku zbiór różnic między liczbą a elementami zbioru. |X| oznacza zbiór wartości bezwzględnych z elementów zbioru X.

    Funkcja opisuje dwie możliwe strategie podczas naszej iteracji: a) najpierw odejmujemy liczby z podzbioru {1,…,N-1} (aż zostanie jedna), a w ostatnim kroku wynik odejmujemy od N, b) najpierw odejmujemy liczby z podzbioru {1,…,N-2} (aż zostanie jedna), następnie N – (N-1), a w ostatnim kroku odejmujemy ich wyniki. Nie są to wszystkie możliwe strategie, ale jeśli udowodnimy, że za ich pomocą można uzyskać wszystkie możliwe wyniki, to nam wystarczy.

    1. Jeśli N jest nieparzyste, a F(N-2) oraz F(N-1) dają ten sam zbiór liczb {1,3,…,N-2}, to F(N) = {0,2,…,N} (można sprawdzić wg wzoru, nie będę rozpisywał). F(N+1) => pkt 2.
    2. Jeśli N jest parzyste, F(N-2) daje {1,3,…,N-2}, a F(N-1) daje {0,2,…,N-2}, to F(N) = {0,2,…,N}. F(N+1) => pkt. 3.
    3. Jeśli N jest nieparzyste, a F(N-2) oraz F(N-1) dają ten sam zbiór liczb {0,2,…,N-1}, to F(N) = {1,3,…,N}. F(N+1) => pkt 4.
    4. Jeśli N jest parzyste, F(N-2) daje {0,2,…,N-2}, a F(N-1) daje {1,3,…,N-1}, to F(N) = {1,3,…,N-1}. F(N+1) => pkt 1.

    Poza opisanymi wyżej są jeszcze inne kombinacje parzystości N i parzystości F(N-1) oraz F(N-2), ale one nigdy nie będą spełnione dla żadnego N > 2 (ze względu na cykl, o którym niżej).

    F(3) spełnia warunek z pkt 1. W każdym punkcie wynikiem jest zbiór liczb parzystych lub nieparzystych z przedziału 0-N. W każdym punkcie jest odnośnik do przepisu na F(N+1), więc następują one po sobie cyklicznie, a parzystość wyniku zależy od N%4.
    Zgodnie z pierwszym akapitem, nie pojawi się wśród wyników iteracji żadna liczba o innej parzystości, żadna ujemna, czy większa od N (bo odejmujemy dwie nieujemne liczby, zawsze mniejszą od większej). Czyli F(N) daje nam wszystkie możliwe wyniki iteracji na zbiorze {1,…,N}.

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Eksperyment Komputerowy Numer 2:
    Uzyskane liczby to 3 albo 9 (wielokrotne powtarzanie opisanej instrukcji daje na końcu jedną z tych liczb).
    Obie są dzielnikami liczby 6174 i nie zawierają tworzących ją cyfr.
    Czyli nieznane mi kontrowersje chyba nie wyjaśniają się…

    Jest OK. Kontrowersje dotyczyły innych liczb.
    mp

  6. Ani 1, ani 0 nie spełnia warunków zadania.

  7. W wyniku iteracji można otrzymać dowolną liczbę nieparzystą z przedziału od 1 do 6173. A oto przepis, jak to uzyskać:

    1. Niech n będzie liczbą nieparzystą, którą chcemy uzyskać.
    2. Liczby grupujemy w pary:
    —- a. (1, n+1)
    —- b. (2, 3), (4, 5), (6, 7), …, (n-1, n)
    —- c. (n+2, n+3), (n+4, n+5), …, (6173, 6174)
    3. W kolejnych iteracjach usuwamy kolejne pary z grup b i c – każda z nich dokłada do zbioru liczbę 1 – w sumie mamy 3086 takie pary, więc do zbioru dołożyliśmy 3086 jedynek.
    4. Te jedynki łączymy w pary i usuwamy w kolejnych iteracjach – każda taka para do zbioru dodaje zero.
    5. W tej chwili w zbiorze mamy liczby: n+1, 1 i pewną liczbę zer. Parę (n+1, 1) zastępujemy liczbą n, a potem pary (n, 0) zastępujemy liczbą n dopóki w zbiorze występują jeszcze jakiekolwiek zera.
    6. Iteracje zakończyliśmy z liczbą n w zbiorze.

    Odpowiedź: Spośród nieparzystych dzielników liczby 6174 tylko 3 i 9 nie zawierają cyfry występującej w 6174 i tylko one mogły pozostać na końcu iteracji.

    PS. Warto dodać, że liczba uzyskana na końcu nie może być parzysta.

    Dowód: początkowo suma liczb w zbiorze jest nieparzysta (6174 * 6175 / 2). Każdy krok iteracji nie zmienia parzystości sumy liczb w zbiorze, bowiem wyjmując ze zbioru liczby a i b dokładamy liczbę a-b lub b-a, czyli suma liczb w zbiorze zmienia się o 2a lub 2b – nie zmieniając parzystości. Zatem gdy zostanie jedna liczba, to musi ona być nieparzysta.

    PPS. @Michał S
    Nawet gdybyśmy traktowali dany zbiór liczb jako faktyczny matematyczny zbiór (czyli bez powtórzeń), to dalej można na końcu uzyskać dowolną liczbę nieparzystą od 1 do 6173. Wtedy wykonując 3 krok podanego przeze mnie algorytmu dokładane do zbioru jedynki od razu zostają wchłaniane przez występującą już w zbiorze jedynkę i po 3 kroku od razu zostaje nam zbiór {1, n+1}, który zamienia się w {n}
    Przy takim podejściu łatwo można również uzyskać dowolną liczbę parzystą od 2 do 6172 – nie opisuję sposobu, bo sam wymyśliłem go bez problemu.

  8. @Michał S
    @timon

    Mój pierwszy komentarz oparty był na błędnym odczytaniu warunków zadania: sądziłem, że nieujemną różnicę dwóch liczb należy umieścić dwukrotnie w modyfikowanym zbiorze (ilość elementów zbioru pozostawała stała).

    Właściwa metoda oznacza zastąpienie dwóch liczb JEDNĄ różnicą (tym samym ilość elementów w zbiorze maleje).

    (mój nieuwolniony komentarz numer 191983 jest wynikiem tej, już właściwej procedury)

  9. Z pomocą komputera wychodzi mi, że może być wiele rozwiązań.
    Na razie znalazłem: 2, 3, 9, 98, 882, 2058

    To są właśnie wspomniane kontrowersje.
    mp

  10. W międzyczasie zauważmy, że tekst z wpisu różni się od tekstu ze ŚN o: „…nie jest liczbą pierwszą…”.
    A więc powyższa iteracja w Łamiblogu może się kończyć dodatkowo 2 lub 3, czego nie może w Świecie Nauki.
    Poza liczbami podanymi przez Witmana nie może być więcej rozwiązań.

  11. @apartado
    Jest jednak jeszcze jedna możliwość i tę miał na myśli Michał S.: wybieramy w pierwszym kroku powiedzmy 2 i 3, i mamy 1. Ponieważ jednak w zbiorze jest już jeden raz 1, więc to się nie dubluje, i od tej pory mamy 1, 4, 5… Według wariantu z nieuwolnionego komentarza 191983, byłoby to 1, 1, 4, 5…, a według wariantu „apartado I”, wręcz 1, 1, 1, 4, 5… Przyznam, że na ten trzeci nie wpadłem, i właściwie nadal się waham między dwoma pierwszymi. Za pierwszym jest ten argument, że gdy mówimy o zbiorze liczb, na przykład zbiorze liczb naturalnych, to mamy 1, 2, 3, 4, 5…, i nie zastanawiamy się, ile razy występuje jedynka, ile dwójka, etc. To nie jak zbiór tabliczek z cyferkami. Dodatkowo, w tym wariancie, jeśli w następnym kroku wybierzemy powiedzmy 4 i 6, to 2 wróci, stąd zależy od kroków poprzednich, czy w danym kroku liczba liczb zmniejszy się o 2, czy tylko o 1. Zapowiada się przypadek na niezwykle skomplikowany, dlatego skupię się na wariancie II, zwłaszcza że komentarz 191983 jest nieuwolniony.

  12. Sprawdziłem programem, że wszystkie liczby: 2, 3, 9, 98, 882, 2058 są osiągane. Zatem zadanie ma 6 (lub 4 bez 2 i 3) rozwiązań. Nie widzę tu żadnych kontrowersji 🙂

  13. Rozwiązując tę łamigłówkę Miś Puchatek powiedziałby, że im bardziej szuka błędu w swoim programie, tym bardziej go tam nie znajduje.

    Wygląda na to, że o rozstrzygnięciu kontrowersji trzeba będzie zadecydować przy pomocy głosowania.
    Tylko jaką metodą wybierzemy metodę głosowania?

    Zapytany o to komputer wyświetlił „42”
    Krótko mówiąc: „niezła odyseja”.

  14. O, już uwolnione… a właśnie miałem napisać, że doszedłem do tego, że w wariancie niedublowania liczb obecnych w zbiorze właściwie każda liczba n mniejsza od górnej granicy, w tym wypadku 6174, może być, bo da się tak zrobić, by na końcu zostały n+1 i 1, i w następnym ruchu mamy n. To dlatego niektórym rozwiązującym wychodziły wszystkie dzielniki, spełniające warunek dotyczący cyfr. W wariancie dopuszczalnego dublowania uznałem (niestety nie udowodniłem), że dzielnik musi być nieparzysty, co łatwo pokazać na przykładzie 3087 (nieważne, że nie spełnia warunku): odejmujemy 6174-3087, 6173-3086, itd, dostajemy 3087 razy liczbę 3087 i potem na przykład 3086/2 zer i 3087, co prowadzi do 3087.

css.php