Liczenie po chińsku, czyli ilu jest policjantów?

13.08.2009 - Agata Murawska
TrudnośćTrudność

Liczby 2, 5 i 9 są parami względnie pierwsze, to znaczy żadne dwie z nich nie mają wspólnych dzielników. Dlaczego jest to takie ważne? To dzięki tej własności możemy udowodnić, że zagadka ma dokładnie jedną poprawną odpowiedź (której wcale nie musimy znać).
Niech $ M = 9*5*2 = 90 $. Chcemy pokazać, że wśród liczb z przedziału [0, M) układ równań modulo opisany w zadaniu ma jedno rozwiązanie.
Załóżmy zatem, że ma on dwa rozwiązania, czyli istnieją $ N_1 $ i $ N_2 $ spełniające układ równań.  Niech $ N_1 \geq N_2 $. Co wiemy o różnicy $ N_1-N_2 $? To bardzo ciekawa liczba. Zachodzi:

  • skoro $ N_1 \equiv_9 5 $ i $ N_2 \equiv_9 5 $,to $ N_1-N_2 $ jest podzielne bez reszty przez 9
  • skoro $ N_1 \equiv_5 1 $ i $ N_2 \equiv_5 1 $,to $ N_1-N_2 $ jest podzielne bez reszty przez 5
  • skoro $ N_1 \equiv_2 1 $ i $ N_2 \equiv_2 1 $,to $ N_1-N_2 $ jest podzielne bez reszty przez 2

Ale zaraz zaraz. Jaka liczba mniejsza od $ 9*5*2 $ jest podzielna przez 9, 5 oraz 2? Całkiem dobrze znamy najmniejszą taką liczbę - 0 i najmniejszą dodatnią - to najmniejsza wspólna wielokrotność ($ \mathrm{NWW} $) tych trzech liczb. Być może wiesz już, że skoro 5 i 9 nie mają wspólnych dzielników, to $ \mathrm{NWW} (9,5) = 9*5 = 45 $. Ale 45 nie dzieli się przez 2, więc nie jest to szukana wartość $ N_1-N_2 $. Poprawmy: $ \mathrm{NWW}(\mathrm{NWW}(9, 5), 2 ) = \mathrm{NWW}(45,2) = 90 $. Coś tu się nie zgadza, prawda? Chcieliśmy dostać liczbę mniejszą od 90, a dostaliśmy dokładnie 90. Co to znaczy? Wśród liczb z rozważanego przedziału: [0, 90) jedyną możliwą wartością różnicy $ N_1-N_2 $ jest 0, a zatem $ N_1=N_2 $. Rozwiązanie jest dokładnie jedno!
Wśród liczb większych od $ M $, układ równań modulo ma więcej rozwiązań. Czy potrafisz podać kilka z nich? A może uda Ci się wymyślić jakiś wzór na kolejne rozwiązania?

Przedstawione powyżej rozumowanie to przykład wykorzystania własności liczb o której mówi chińskie twierdzenie o resztach. Wrócimy jeszcze do tego tematu, żeby nauczyć się mądrzej szukać najmniejszego rozwiązania. Będzie to trochę trudniejsze, niż rozważania o policjantach, ale niezwykle przydatne - niektóre obliczenia łatwiej wykonuje się na liczbach pierwszych (lub ich potęgach). Rozłożenie liczby na czynniki pierwsze i zastosowanie chińskiego twierdzenia o resztach upraszcza tego typu zadania pod warunkiem, że potrafimy odzyskać ostateczny wynik. CToR (matematycy i informatycy lubią takie skróty) jest też przydatnym narzędziem w kryptografii - między innymi przy jego pomocy dowodzi się poprawności algorytmu RSA. Ale to już zupełnie inna historia..

4
Twoja ocena: Brak Ocena: 4 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com