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.