11 out
Urokliwe zadanie z rumuńskiego turnieju matematycznego dla licealistów:
Znajdź najdłuższy ciąg kolejnych liczb całkowitych dodatnich takich, aby suma cyfr żadnej liczby nie była podzielna przez 11.
Warto by dodać, że liczba zaczynająca ciąg powinna być najmniejszą możliwą. Korci też, by zadanie uogólnić, czyli zastąpić 11 dowolnym n>1. Dla nieco mniejszych n=9 i 10 sprawa jest prosta, bo rozwiązania zaczynają się na starcie – pierwsze sięga od 1 do 8, drugie od 1 do 18. Dla n=11 wbrew pozorom rozwiązanie nie jest analogiczne, czyli nie obejmuje 28-liczbowego fragmentu od 1 do 28. Aby uporać się z najdłuższym ciągiem bez sumy cyfr 11, należy „odkryć” kluczowy odcinek ciągu liczb naturalnych skrywający rozwiązanie. Nie wydaje się to zbyt trudne, a zatem jaką (najmniejszą) liczbą będzie zaczynał się rumuński ciąg i z ilu liczb będzie się składał?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Przy przejściu od n do n+1 suma cyfr zwykle zwiększa się o 1.
Jeżeli n kończy się na k dziewiątek, suma cyfr zmniejsza się o 9k−1. Długi ciąg jest możliwy wyłącznie w miejscu, gdzie suma cyfr nagle silnie maleje, zamiast rosnąć o 1. Dzieje się to tylko przy liczbach kończących się na wiele dziewiątek. Przy pięciu lub mniej dziewiątkach spadek sumy cyfr jest zbyt mały, by ominąć kilka kolejnych wielokrotności 11. Dopiero przy sześciu dziewiątkach (999999) spadek jest wystarczająco duży.
Dla 999999 suma cyfr wynosi 54, leżąc między 44 a 55, czyli między kolejnymi wielokrotnościami 11. Po przejściu do następnej liczby suma cyfr spada do 1, również niepodzielnej przez 11. To pozwala połączyć dwa bezpieczne fragmenty w jeden długi ciąg 38 liczbowy (28+10).
Lewą granicę wyznacza 999980 (suma cyfr 44), a prawą 1000019 (suma cyfr 11). Dlatego jedynym możliwym maksymalnym przedziałem jest 999981–1000018. (przy warunku „jaką najmniejszą liczbą będzie zaczynał się rumuński ciąg”). Siedem i więcej dziewiątek nic nie zmienia.
Taki ciąg składa się z 38 liczb i najwcześniej wystąpi przy przejściu przez granicę 1000000(=10^6)
Najmniejszą liczbą jest 10^6-19=999981, zaś największą 10^6+18=1000018.
Następne wystąpienia takiego ciągu możemy znaleźć dopisując przed pierwszą liczbą (najmniejszą) jakąś liczbę o sumie cyfr podzielnej przez 11. Po stronie liczby największej zastępujemy cyfrę 1 tą (dopisywaną) liczbą powiększoną o 1;
(Suma cyfr tej drugiej musi być sumie pierwszej +1, a więc np. 29 nie pasuje)
Przykładowe ciągi: od 38999981 do 39000018 (dopisaliśmy na początku 38).
od 137999981 do 138000018 (dopisaliśmy na początku 137)
zaczyna się 999981 i ma długość 38
Myślałem o tym zadaniu w drodze samochodem i jedyne, na co wpadłem, to że musi to być ciąg od 99… do 10…018, bo 1+0+1+9 daje już 11.
W głowie nie udało mi się dojść do rozwiązania, ale już z pomocą komputera okazało się, że chodzi o 999981 do 1000018 – 38 liczb. Przypadkiem lub nie, jest po 19 liczb z każdej strony 10^6.
Później po konsultacji z koleżanką okazało się, że liczbę dziewiątek da się ustalić analitycznie.
Niestety ta reguła nie zawsze działa dla dowolnego n>1, ale o tym może napiszę później.
Zadanie jest świetne!
38 liczb od 999981
Ciąg 38-wyrazowy, od 999981 do 1000018