###### tags: `Matematyka Dyskretna M`

# Lista 5

## 3
Teza: Pokaż, że iloczyn dowolnych $k$ kolejnych liczb naturalnych dzieli się przez $k!$.

Dowód:
Wiemy, że $k! = 1\times2\times3\times...\times k$
Weźmy dowolne $k$ i $k$ kolejnych liczb naturalnych.
Wtedy, $\frac{n\times (n-1)\times (n-2)\times ...\times (n - k + 1)}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!\times(n-k)!} = \binom{n}{k}$
a wiemy, że $\binom{n}{k}\in\mathbb{N}$, czyli iloczyn dowolnych $k$ kolejnych liczb naturalnych dzieli się przez $k!$.
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$

## 6

Minimalna suma takiego podzbioru $0$
Maksymalna suma takiego podzbioru wynosi
$99+98+97+96+95+94+93+92+91+90 = 945$
Czyli różnych sum podzbioru takiego zbioru jest maksymalnie $946$

Podzbiór można wybrać na $2^{10} = 1024$ sposobów, bo każdą liczbę można albo wziąć do przedziału, albo nie.

Z zasady szufladkowej Dirichleta wiemy, że zawsze istnieje co najmniej jedna taka suma, którą można uzyskać sumując elementy w dwóch różnych podzbiorach zbioru 10-elemetowego o elementach < 100.
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$
## 8
Weźmy szachownicę $m\times n$ i weźmy $m(k−1) + 1$ wież.
Podzielmy szacownicę według schematu na rysunku, gdzie każda cyfra oznacza numer "szufladki". Wtedy żadne dwa pola znajdujące się w tej samej "szufladce" nie mają ani wspólnej kolumny, ani wspólnego wiersza (Tylko wtedy kiedy $m\geq n$ a tak jest z założenia zadania). Zauważmy, że mamy m "szufladek". Mamy $m(k−1) + 1$ wież, więc z zasady szufladkowej Dirichleta wiemy, że istnieje taka szufladka, w której będzie co najmniej k wież. A wiedząć również, że żadne dwa pola z jednej "szufladki" nie mają wspólnych ani kolumn, ani wierszy więc postawione tam wieże się nie biją.
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$


## 9
### a)
**Dokładnie jedna cyfra występuje więcej niż jeden raz.**
**1$^\circ$** Dokładnie jedna cyfra występuje 2 razy.
Wtedy tę cyfrę wybieramy na 10 sposobów, a 2 miejsca dla niej na $\binom{5}{2}$ sposobów. Pozostałe cyfry wybieramy na $9\times8\times7$ sposobów. Czyli takich numerów jest $10\times\binom{5}{2}\times9\times8\times7 =50400$
**2$^\circ$** Dokładnie jedna cyfra występuje 3 razy.
Wtedy tę cyfrę wybieramy na 10 sposobów, a 3 miejsca dla niej na $\binom{5}{3}$ sposobów. Pozostałe cyfry wybieramy na $9\times8$ sposobów. Czyli takich numerów jest $10\times\binom{5}{3}\times9\times8 =7200$
**3$^\circ$** Dokładnie jedna cyfra występuje 4 razy.
Wtedy tę cyfrę wybieramy na 10 sposobów, a 4 miejsca dla niej na $\binom{5}{4}$ sposobów. Pozostałą cyfrę wybieramy na $9$ sposobów. Czyli takich numerów jest $10\times\binom{5}{4}\times9 =450$
**4$^\circ$** Dokładnie jedna cyfra występuje 5 razy.
Wtedy tę cyfrę wybieramy na 10 sposobów. Czyli takich numerów jest $10$

Czyli wszystkich numerów, gdzie dokładnie jedna cyfra występuje więcejniż jeden raz jest $50400+7200+450+10=58060$
### b)
**Przynajmniej jedna cyfra występuje więcej niż jeden raz**
Wszystkich numerów jest $10^5$, a numerów, w których każda cyfra występuje dokładnie raz wynosi $10\times9\times8\times7\times6 = 30240$. Czyli numerów takich, że przynajmniej jedna cyfra występuje więcej niż jeden raz jest $10^5-30240 = 69760$

## 10
### a)
**Ile jest różnych rozłożeń wszystkich białych i czarnych figur i pionków szachowych na szachownicy?**
Szachownica ma 64 pola.
Figury białe:
Pionki możemy ustawić na $\binom{64}{8}$
Wieże możemy ustawić na $\binom{56}{2}$ (8 miejsc już jest zajętych przez pionki białe)
Skoczki możemy ustawić na $\binom{54}{2}$
Gońce możemy ustawić na $\binom{52}{2}$
Hetmana możemy ustawić na $\binom{50}{1}$
Króla możemy ustawić na $\binom{49}{1}$

Figury czarne:
Pionki możemy ustawić na $\binom{48}{8}$ (16 miejsc jest już zajętych przez bierki czarne)
Wieże możemy ustawić na $\binom{40}{2}$
Skoczki możemy ustawić na $\binom{38}{2}$
Gońce możemy ustawić na $\binom{36}{2}$
Hetmana możemy ustawić na $\binom{34}{1}$
Króla możemy ustawić na $\binom{33}{1}$
Czyli różnych rozłożeń wszystkich białych i czarnych figur i pionków szachowych na szachownicy jest $\binom{64}{8}\times\binom{56}{2}\times\binom{54}{2}\times\binom{52}{2}\times\binom{50}{1}\times\binom{49}{1}\times\binom{48}{8}\times\binom{40}{2}\times\binom{38}{2}\times\binom{36}{2}\times\binom{34}{1}\times\binom{33}{1}$

### b)
**Ile jest rozłożeń w których para gońców każdego z kolorów zajmuje pola różnych kolorów?**

Białe gońce:
Goniec na biały polu: $\binom{32}{1}$
Goniec na czarnym polu: $\binom{32}{1}$
Czarne gońce:
Goniec na biały polu: $\binom{31}{1}$
Goniec na czarnym polu: $\binom{31}{1}$

Pozostałe figury białe:
Pionki możemy ustawić na $\binom{60}{8}$
Wieże możemy ustawić na $\binom{52}{2}$
Skoczki możemy ustawić na $\binom{50}{2}$
Hetmana możemy ustawić na $\binom{48}{1}$
Króla możemy ustawić na $\binom{47}{1}$

Pozostałe figury czarne:
Pionki możemy ustawić na $\binom{46}{8}$
Wieże możemy ustawić na $\binom{38}{2}$
Skoczki możemy ustawić na $\binom{36}{2}$
Hetmana możemy ustawić na $\binom{34}{1}$
Króla możemy ustawić na $\binom{33}{1}$
Czyli rozłożeń w których para gońców każdego z kolorów zajmuje pola różnych kolorów jest $\binom{32}{1}\times\binom{32}{1}\times\binom{31}{1}\times\binom{31}{1}\times\binom{60}{8}\times\binom{52}{2}\times\binom{50}{2}\times\binom{48}{1}\times\binom{47}{1}\times\binom{46}{8}\times\binom{38}{2}\times\binom{36}{2}\times\binom{34}{1}\times\binom{33}{1}$

## 11

**Pokaż, że liczba przedstawień $n$ w postaci sumy $k$ liczb naturalnych (różnych od zera) wynosi$\binom{n-1}{k-1}$, jeśli przedstawienia na różniące się kolejnością składników uważamy za różne**

Rozbijmy liczbę $n$ na sumę n liczb równych 1 (Tak jak na rysunku). Wtedy musimy tak zsumować te liczby, żeby z sumy n liczb, została nam suma k liczb. Żeby mieć $k$ liczb, muszę wybrać $k-1$ symboli $"+"$, które muszę "zostawić", a resztę obliczyć. Więc, symboli $"+"$ mam $n-1$ i wśród wśród nich muszę wybrać ich $k-1$ co mogę zrobić na $\binom{n-1}{k-1}$ sposobów.

**Ile jest przedstawień $n$ w postaci sumy dowolnej ilości liczb naturalnych?**
Wtedy przy każdym symbolu $"+"$ możemy wybrać, albo go obliczymy albo nie. Mając tych symboli $n-1$ możemy to zrobić na $2^{n-1}$ sposobów.


## 15
Teza: $a^p\equiv a$ mod $p$ dla liczby pierwszej p i naturalnej a
Dowód przeprowadzę przez indukcję po a.
1$^\circ$ dla a = 0 i a = 1
$0^p = 0$, a $0 \equiv 0$ mod $p$
$1^p = 1$, a $1 \equiv 1$ mod $p$

2$^\circ$ załóżmy, że $a^p\equiv a$ mod $p$ dla liczby pierwszej p i naturalnej a. Wtedy dla $a+1:$

$(a+1)^p = \displaystyle\sum_{k=0}^p\binom{p}{k}a^{p-k}\times1^{k} = \displaystyle\sum_{k=0}^p\binom{p}{k}a^{p-k} = a^0 + a^p + \displaystyle\sum_{k=1}^{p-1}\binom{p}{k}a^{p-k} =$
$= 1 + a^p + \displaystyle\sum_{k=1}^{p-1}\binom{p}{k}a^{p-k}$

Teraz udowodnię, że dla liczby pierwszej p i naturalnej a: $p\space|\space\displaystyle\sum_{k=1}^{p-1}\binom{p}{k}a^{p-k}$

$\binom{p}{k}a^{p-k} = \frac{p!\times a^{p-k}}{k!(p-k!)}$

Zauważmy, że żeby $p\space|\space \frac{p!\times a^{p-k}}{k!(p-k!)}$ to mianownik i $p$ muszą być względnie pierwsze czyli $k< p$, $k\neq 0$ (Bo wtedy $p!$ z licznika podzieli się przez $p$) oraz $p$ musi być pierwsze (Bo dla $k=1$ mianownik zawiera iloczyn liczb naturalnych z przedziału $<1,p-1>$).
W tezie mamy oba przpadki (p jest pierwsze oraz rozpatrujemy k z przedziału $<1,p-1>$). Z tego wynika, że $p$ dzieli każdy składnik tej sumy, więc $p$ również dzieli całą sumę.

Wracając do dowodu głównego:
$(1 + a^p + \displaystyle\sum_{k=1}^{p-1}\binom{p}{k}a^{p-k})$ mod $p = (1 + a^p)$ mod $p$ (Bo $p\space|\space \displaystyle\sum_{k=1}^{p-1}\frac{p!\times a^{p-k}}{k!(p-k!)}$)
$(1 + a^p)$ mod $p$
Kontutuując z założenia inducyjnego
Czyli $1 + a^p\equiv a + 1$ mod $p$
Czyli $(a+1)^p \equiv a + 1$ mod $p$

Na podstawie indukcji matematycznej pokazałem dowód małego twierdzenia Fermata.