Dać rzeczy słowo

Kto po tytule niniejszego wpisu spodziewał się poezyj podchmurnych tudzież próz ambitnych, zawiedzie się srodze. Jam bowiem jest bazyl hartowany, nierdzewny, na cztery kwerendy kuty, a nie jakiś wierszoklet. Miast więc w cichości rymy pisać, zabawię się dziś słowem od strony statystyczno-obliczeniowej. W tym celu potrzebować będę składników następujących: Czytaj dalej Dać rzeczy słowo

Carpe diem, carpe noctem

Sen jest dobrem ekskluzywnym współczesnej cywilizacji Zachodu. Stres związany z szybkim tempem życia odbija się na ilości i jakości naszego snu bardziej niż wizyta tygrysa szablastozębnego w szałasie śpiącego Homo Australopitecus (być może właśnie pomieszałem epoki, jeżeli więc któryś z Czytelników pasjonuje się prehistorią, proszę o korektę). Chodzimy spać późno, wstajemy wcześnie, żeby zdążyć wyekwipować dzieciaki do szkół a samych siebie do hut, fabryk i na zmywaki. Czytaj dalej Carpe diem, carpe noctem

Ad infinitum – węzeł gordyjski

Pisałem kilka dni temu o problemie z poprawkami z Windows Update, które mi się zapętliły i nijak nie chciały zniknąć z listy aktualizacji, mimo ich wielokrotnego instalowania i traktowania rozmaitymi środkami owadobójczymi. Czytaj dalej Ad infinitum – węzeł gordyjski

Na plażę!

W dni robocze, po pracy, robię rundkę po okolicznych hutach, fabrykach i zmywakach, zbieram (za przeproszeniem) członków rodziny do swego wehikułu i uderzamy do domu. Czasem zdarzy nam się potem jakiś spacer po okolicznych spacerniakach, ale na ogół spędzamy resztę dnia w domowych pieleszach. Czytaj dalej Na plażę!

Rozwiązanie zagadki o stu przełącznikach

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.

Jak z bicza strzelił

Stary dowcip mówi, że najlepszą metodą na zapamiętanie urodzin żony jest zapomnieć o nich. Na szczęście o urodzinach swojej żony pamiętam, natomiast przegapiłem wczoraj urodziny bloga. Otóż dokładnie 21 maja 2011. roku umieściłem tutaj swój pierwszy wpis, a także drugi i trzeci. Czytaj dalej Jak z bicza strzelił

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). Czytaj dalej Myślaki, do boju!

Michael Connelly – krótka recenzja zbiorcza

Jakiś czas temu jeden z dawnych znajomych (nawiasem mówiąc większy mól książkowy ode mnie, co zawsze wydawało mi się niemożliwe) zainteresował mnie twórczością Michaela Connelly-ego. Jednak dopiero niedawno znalazłem dość czasu, żeby się za to zabrać – jak już zacząłem, nie mogłem się oderwać i przez ostatnie trzy tygodnie przeczytałem cztery jego powieści (i czytam piątą). Czytaj dalej Michael Connelly – krótka recenzja zbiorcza

CDN ciąg dalszy

O moich próbach z CDN pisałem jakiś czas temu – wówczas był to Amazoński CloudFront, a ostatnio zainteresowałem się usługą CloudFlare, która – w odróżnieniu od poprzedniczki – jest w podstawowej wersji darmowa. Czytaj dalej CDN ciąg dalszy