Myślaki, do boju!

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…

Dodaj komentarz

5 komentarzy do "Myślaki, do boju!"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
pendragon
Gość

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.

butter
Gość

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

lacki
Gość

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ć?

admin
Gość

Bardzo słuszna uwaga, w zasadzie nic dodać, nic ująć. Lada chwila wrzucę szczegółowe rozwiązanie w osobnym wpisie.

wpDiscuz