Przedwczoraj zapodałem zagadkę o stu pstryczkach-elektryczkach. Dziś pokażę jak ją rozwiązać.
Najpierw wersja dla leniwych posiadaczy Excela:
1. Uruchamiamy Excela, tworzymy nowy, pusty dokument.
2. W komórki od A2 do A101 wpisujemy liczby od 1 do 100, po kolei.
3. W komórki od B1 do CX1 wpisujemy liczby od 0 do 100, po kolei.
W ten sposób mamy utworzoną macierz 100 x 101 komórek, w której każdy wiersz reprezentuje jeden pstryczek (przełącznik), a każda kolumna - jeden krok algorytmu (kolumna numer 0 reprezentuje stan przed rozpoczęciem algorytmu, czyli "krok zero")
Na przykład komórka L5 (na przecięciu kolumny 10 i wiersza 4) reprezentuje stan czwartego przełącznika w dziesiątym kroku.
4. W kolumnę B wpisujemy same zera (stan początkowy przełączników - wszystkie wyłączone)
5. W kolumnę C wpisujemy same jedynki (po pierwszym kroku wszystkie przełączniki są włączone)
6. W komórkę D2 wpisujemy formułę: =IF(MOD($A2, D$1)=0, 1-C2, C2)
Wyjaśnienie formuły: jeżeli numer numer przełącznika podzielony przez numer kroku daje resztę zero (czyli dzieli się bez reszty), przełącznik należy przełączyć na przeciwny (1-C2 - od jedynki odejmujemy stan poprzedni, czyli jeżeli poprzednio była jedynka, teraz będzie zero i na odwrót). Jeżeli się nie dzieli bez reszty, to w tym kroku ten przełącznik pozostaje bez zmian, kopiujemy więc jego stan z poprzedniego kroku.
7. Kopiujemy powyższą formułę do wszystkich kolumn i wierszy (a więc aż do komórki CX101)
8. Zliczamy ilość jedynek w ostatniej kolumnie (CX) - jest ich dziesięć, i to jest poprawna odpowiedź.
Teraz wersja bardziej ambitna, nie wymagająca Excela:
Spróbujmy najpierw zmienić sposób myślenia o zagadce. Zamiast próbować wykombinować co dzieje się z poszczególnymi przełącznikami w danym kroku, spróbujmy pomyśleć co dzieje się z danym przełącznikiem w poszczególnych krokach. Weźmy na przykład przełącznik numer 6: ile razy będzie on przełączony? Na pewno stanie się to w krokach numer 1, 2, 3 i 6. Czy jakieś inne kroki wpłyną na przełącznik 6? Na pewno nie. Krok numer 4 przełączy przełączniki 4,8,12,16 itd (ominie szóstkę), krok numer 5 przełączy przełączniki 5, 10, 15 itd... a kroki powyżej szóstego zaczynają się poza szóstym przełącznikiem, więc nie warto sobie nimi zawracać głowy.
Czyli widać, że przełącznik numer 6 będzie przełączony czterokrotnie: off->on->off->on->off. W efekcie widać, że po stu krokach będzie on na pewno wyłączony.
Weźmy inny - na przykład numer 4. Będzie on przełączony w krokach 1, 2 i 4, czyli trzy razy: off->on->off->on - oznacza to, że po stu krokach pozostanie on włączony.
Wniosek stąd płynie taki, że przełączniki na pozycjach będących liczbami z nieparzystą ilością podzielników będą po stu krokach włączone, a pozostałe - wyłączone.
Właśnie zredukowaliśmy zadanie do postaci:
Znajdź wszystkie liczby naturalne nie większe niż sto, które mają nieparzystą ilość podzielników.
Zastanówmy się teraz jak to właściwie jest z tymi podzielnikami. Jeżeli liczba N dzieli się przez liczbę A (mówiąc "dzieli się" mam na myśli "dzieli się bez reszty"), dając w wyniku liczbę B, to oczywistym jest, że liczba N dzieli się również przez liczbę B, dając w wyniku A. Ponadto, A * B = N.
Na przykład:
34 dzieli się przez 17: 34/17=2. A więc 34 dzieli się też przez 2: 34/2=17
2 * 17=34.
Proste?
No to jedziemy dalej. Spróbujemy teraz udowodnić, że dwie liczby naturalne, dające po przemnożeniu N, muszą:
1. Albo leżeć po przeciwległych stronach pierwiastka z N
2. albo też być jedną i tą samą liczbą, równą pierwiastkowi z N
Przykład 1: niech N=12. Wówczas pierwiastek z N jest równy (w przybliżeniu) 3,46410162. Twierdzę, że dowolne dwie liczby naturalne dające po przemnożeniu 12, muszą leżeć po przeciwnych stronach 3,46410162. Są dokładnie trzy takie pary: (1 i 12), (2 i 6), (3 i 4). Widać, że w każdej parze jedna z liczb jest mniejsza od 3.46410162 a druga większa. Żeby udowodnić tę "naprzemienność" podzielników względem pierwiastka z N wystarczy spróbować rozwiązać układ dwóch nierówności i jednego równania: 1. A>sqrt(N), 2. B>sqrt(N), 3. A * B = N - proszę spróbować, dostajemy w efekcie sprzeczność sqrt(N) * sqrt(N) < N. Podobnie będzie jeżeli zamienimy znaki nierówności na przeciwne.
Przykład 2: Niech N=4. Istnieją dwie pary liczb naturalnych, których iloczyn daje 4: (1 i 4) oraz (2 i 2). Widać, że druga para jest "zbudowana" z dwóch dwójek. Dwójka jest pierwiastkiem z czwórki.
Jak to się ma do parzystości?
Otóż ma się tak, że skoro podzielniki zawsze "chodzą parami", będzie ich zawsze parzysta ilość. Jednak jeżeli w jakiejś parze ten sam podzielnik występuje dwukrotnie, liczymy go tylko raz, bo w naszej zagadce każdy krok pstrykania przełącznikami wykonujemy tylko raz. A więc tę dwójkę w parze (2 i 2) liczymy jako jedną liczbę. Jeden podzielnik. Czwórka ma więc trzy podzielniki: 1, 2, 4. Podobnie będzie z liczbą 36: pary liczb naturalnych dające w wyniku 36 to: (1,36), (2, 18), (3, 12), (4, 9), (6, 6). Ostatnią parę liczymy jako jedną liczbę, bo krok numer sześć będzie wykonany tylko raz. A więc 36 ma nieparzystą liczbę podzielników, stąd też pstryczek numer 36 pozostanie włączony.
W ogólnym przypadku, każda liczba naturalna N będąca kwadratem innej liczby naturalnej, ma nieparzystą ilość podzielników naturalnych, ponieważ zawsze istnieje taka para (a,b) w której a=b=sqrt(N). A więc przełącznik na pozycji odpowiadającej tej liczbie pozostanie włączony, ponieważ będzie pstryknięty nieparzystą ilość razy.
Reasumując: po stu krokach, wyłączone będą wszystkie przełączniki z wyjątkiem przełączników na pozycjach 1, 4, 9, 16, 25, 36, 49, 64, 81 i 100.
Uff.
kurde z tymi pierwiastkami to bym nie wpadł. Fajne.
I podoba mi się ta macierz. Ten chaos nad przekątną próbowałem sobie jakoś wizualnie usystematyzować ale się nie dał memy słabemu rozumkowi pokonać.