6174 do 1
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?
Komentarze
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.
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.
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}.
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
Ani 1, ani 0 nie spełnia warunków zadania.
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.
@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)
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
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ń.
@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.
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
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”.
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.