Natrafiłem ostatnio na interesującą zagadkę, nad którą spędziłem całkiem sporo czasu. Najpierw udało mi się ją rozwiązać metodą "brute force" (niech żyje Excel!), potem trochę poguglałem, znalazłem parę dziwnych rozwiązań, których nie zrozumiałem, a na koniec wymyśliłem jak ją rozwiązać klasycznie (czyli bez próbowania wszystkich możliwych kombinacji).
Zagadka jest następująca:
Mamy sto pstryczków. Zwykłych, dwupozycyjnych przełączników, z których każdy może być albo włączony ("on") albo wyłączony ("off").
Na początku wszystkie pstryczki są wyłączone ("off").
W pierwszym kroku przełączamy wszystkie pstryczki (a więc, każdy z "off" na "on")
W drugim kroku przełączamy co drugi pstryczek (a więc drugi, czwarty, szósty i tak dalej - skoro wszystkie były "on", połowa z nich przejdzie na "off")
W trzecim kroku przełączamy co trzeci pstryczek (a więc trzeci, który był "on", zrobi się "off", szósty, który był "off", zrobi się "on", dziewiąty... i tak dalej).
W czwartym kroku przełączamy co czwarty pstryczek.
W piątym - co piąty.
Powtarzamy kroki, za każdym razem w N-tym kroku przełączamy co N-ty pstryczek.
W ostatnim, setnym kroku, przełączamy setny pstryczek.
Pytanie: ile pstryczków będzie włączonych ("on") po wykonaniu stu kroków?
Jeszcze raz powtórzę: można to zasymulować w arkuszu kalkulacyjnym i dostać wynik w 3 minuty. Proszę jednak najpierw spróbować bez Excela...
Nie umiem rozwiązywać takich zagadek więc podejrzewam że jest w tym jakaś sztuczka typu 100 przełączników, 100 kolejek z przełączaniem, na koniec wszystkie są on albo off. W każdym razie ja jestem off.
wszystkie na pewno nie. Pierwszy pozostanie włączony
imho algorytm wygląda następująco:
a. robimy macierz: 100×100 – pozycje razy iteracje
b. dla każdej pozycji macierzy dzielimy numer pozycji modulo krok iteracji
c. sumujemy dla każdej pozycji ilość zer
d. dzielimy modulo 2
suma d., gdzie wynik = 0 to nasz wynik
Zgadza się, ale to jest rozwiązanie poprzez symulację. A da się to zrobić ściśle arytmetycznie, bez macierzy.
mi wychodzi (z gapienia się w tę macierz 100z100) że jedynki (znaczy "on") będą tam gdzie nr pozycji przełącznika ma nieparzystą liczbę podzielników (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) ale jak na to wzór wyprowadzić?
Bardzo słuszna uwaga, w zasadzie nic dodać, nic ująć. Lada chwila wrzucę szczegółowe rozwiązanie w osobnym wpisie.