Działanie modulo, reszta z dzielenia, parzystość, kombinatoryka.
- Działanie "modulo [tex]k[/tex]" jest (dla zbioru liczb naturalnych) "funkcją" przyporządkowującą liczbie będącej argumentem wartość "dowolnej możliwej reszty" z dzielenia przez [tex]k[/tex]. Przykładowo:
[tex]4 \equiv 1 (mod \; 3) \equiv -2 (mod \; 3) \\7 \equiv -2 (mod \; 9) \equiv 7 (mod \; 9)\\67 \equiv 1 (mod \; 6) \equiv 7 (mod \; 6) \equiv 43 (mod \; 6) \equiv -6 (mod \; 6)[/tex]
- W powyższym zadaniu należy zbadać numery, które mają [tex]p+3[/tex] cyfr.
- Jest narzucony warunek na wartość p: [tex]p \equiv c+d (mod \; 3)[/tex]
gdzie [tex]c,d[/tex] to pewne cyfry. Innymi słowy interesuje nas reszta z dzielenia [tex]c+d[/tex] przez 3. - Dla [tex]c=0, d=5[/tex] mamy (przy takowym oznaczeniu):
[tex]p \equiv 0+5 (mod \; 3) \equiv 2 (mod \; 3)[/tex]
czyli zapewne: [tex]p+3 = 2+3 = 5[/tex]
- Dalej badamy te (p+3)-cyfrowe liczby, które mają [tex]n[/tex] cyfr parzystych.
- Warunek na n jest postaci: [tex]n \equiv c+e+1 (mod \; p+3)[/tex]
- Czyli dla [tex]c=0,e=2[/tex] mamy:
[tex]n \equiv 0+2 (mod \; 5) \equiv 2 (mod \; 5)[/tex]
- Pozostaje znaleźć więc (dla wspomnianych przykładowych wartości zmiennych c, d, e):
"Ile jest 5-cyfrowych liczb o 2 cyfrach parzystych?" - Mamy 5 miejsc, do rozdysponowania 2 cyfry parzyste i pozostałych (5-2=3) cyfr nieparzystych.
- Możliwych parzystych cyfr {0,2,4,6,8} jest 5, nieparzystych {1,3,5,7,9} również 5.
- Stąd:
[tex]x = {5 \choose 2} * 5^2 * 5^3 = {5 \choose 2} *5^5 = \frac{5!}{2!(5-2)!}*5^5 = 5*2 *5^5 = 31250[/tex]
innymi słowy wybieramy dwa miejsca (z pięciu) na których wpisujemy liczby parzyste (możemy wpisać każdą liczbę parzystą na 5 sposobów) - ten wybór determinuje już nam pozostałe trzy miejsca na liczby nieparzyste (które to także możemy uzupełnić na 5 sposobów).
