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

# Lista 3

## 1

$f(n) = \displaystyle\sum_{k=1}^{n}\lceil log_2k \rceil = \displaystyle\sum_{k=1}^{\lceil\frac{n}{2}\rceil}\lceil log_2(2k-1)\rceil + \displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\lceil log_2(2k)\rceil = \displaystyle\sum_{k=1}^{\lceil\frac{n}{2}\rceil} 1 + \lceil log_2(k-\frac{1}{2})\rceil + \displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} 1 + \lceil log_2(k)\rceil =$$= \lceil \frac{n}{2} \rceil + \lfloor \frac{n}{2} \rfloor + \displaystyle\sum_{k=1}^{\lceil\frac{n}{2}\rceil} \lceil log_2(k-\frac{1}{2})\rceil + \displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \lceil log_2(k)\rceil = n + \displaystyle\sum_{k=1}^{\lceil\frac{n}{2}\rceil} \lceil log_2(k-\frac{1}{2})\rceil + \displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \lceil log_2(k)\rceil=$
$=n + log_2\frac{1}{2} + \displaystyle\sum_{k=2}^{\lceil\frac{n}{2}\rceil} \lceil log_2(k)\rceil + f(\lfloor \frac{n}{2} \rfloor) = n - 1 + \displaystyle\sum_{k=1}^{\lceil\frac{n}{2}\rceil} \lceil log_2(k )\rceil + f(\lfloor \frac{n}{2} \rfloor) = n - 1 + f(\lceil \frac{n}{2} \rceil) + f(\lfloor \frac{n}{2} \rfloor)$
$\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\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$

Jeżeli f(1) = 0 to funkcja jest jednoznaczna, bo
f(2) = 1 + f(1) + f(1)
f(3) = 2 + f(2) + f(1)
f(4) = 3 + f(2) + f(2)
...
Jak widzimy, żeby poznać inne wartości musimy znać jedną wartość początkową. Dla innej wartości f(0), funkcja byłaby już inna, więc oznacza to, że dla f(1) = 0 funkcja ta jest jednoznaczna.

## 3

Udowodnię to najpierw pokazując, że każdą liczbę można zapisać w tej postaci, a następnie, że nie istnieją dwa różne zapisy tej samej liczby w takiej postaci.

**1$^\circ$** Każdą liczbę można zapisać w tej postaci.

Dowód tej części przeprowadzę przez indukcje.

**1$^{\circ\circ}$**
Weźmy kilka pierwszych wyrazów początkowych.
$1 = 1\times F_2 + 0\times F_3 + 0\times F_4 + ... + 0\times F_k$
$2 = 0\times F_2 + 1\times F_3 + 0\times F_4 + ... + 0\times F_k$
$3 = 0\times F_2 + 0\times F_3 + 1\times F_4 + ... + 0\times F_k$
$4 = 1\times F_2 + 0\times F_3 + 1\times F_4 + ... + 0\times F_k$
**2$^{\circ\circ}$**
Załóżmy, że dla $\forall _{m<=n, m\in\mathbb{N}}$ m ma przedstawienie w tej postaci
Wtedy rozpatrzmy 2 przypadki. Gdy m = $F_x$ i gdy m $\neq$ $F_x$ dla jakiegoś naturalnego x
**1$^{\circ\circ\circ}$** m = $F_k$
Wtedy m = $0\times F_2 + 0\times F_3 + ... + 0\times F_{x-1} + 1\times F_x + 0\times F_{x+1} + ... + 0\times F_{k}$ (jedna jedynka stoi przy $F_x$)
**2$^{\circ\circ\circ}$** m $\neq$ $F_k$
Wtedy $\exists_{p\in\mathbb{N}}$ $F_{p-1} < m < F_p$
Weźmy takie y, że $F_{p-1} + y= m$ Wtedy $y < F_{p-2}$ (Jakby było równe lub większe to m byłoby większe od $F_p$ z własności liczb fibonacciego)
Czyli z założenia indukcyjnego y można zapisać w postaci podanej w zadaniu, i możemy zauważyć, że z tego, że $y < F_{p-2}$ , a $F_{p-1}$ to w tej postaci to $1\times F_{p-1}$ to $m = y + F_{p-1}$ co po dodaniu będzie wyglądało w postaci podanej w zadaniu podobnie jak y, z różnicą, że będzie dodatkowo $0\times F_{p-2} + 1\times F_{p-1}$.(Czyli inaczej mówiąc m = y + $0\times F_{p-2} + 1\times F_{p-1}$ (mając na myśli y rozpisany według założenia indukcyjnego)) Czyli w tym przypadku również można zapisać tę liczbę w podanej w zadaniu postaci.

Na podstawie indukcji matematycznej udowodniłem, że każdą liczbę naturalną większą od 0 można zapisać w tej postaci.

**2$^\circ$** Nie istnieją dwa różne zapisy tej samej liczby w takiej postaci.

Dowód przeprowadzę nie wprost
weźmy liczbę n i załóżmy, że tę liczbę można przedstawić w dwóch różnych postaciach w układzie liczb Fibonacciego.
Rozpatrzmy teraz największą pozycję, na której te liczby się różnią (znajdziemy taką, ponieważ obie liczby sumują się do tej samej wartości, ale mają inny zapis w układzie liczb Fibonacciego). Wtedy ta druga liczba musi "nadrobić" tę liczbę sumując do niej kilka mniejszych liczb Fibonacciego. Jest to niemożliwe, ponieważ żeby otrzymać tę liczbę musimy wykonać sumę $F_{z-1} + F_{z-2}$ jeżeli ta liczba była na indeksie z. Jednak nie możemy tego zrobić, ponieważ według zadania zapis tej liczby nie może zawierać sumy dwóch kolejnych liczb Fibonacciego. Idąc tym tropem musimy rozpisać na sumę liczbę $F_{z-2}$ co również sprowadzi się do tego, że będziemy musieli zapisać liczbę $F_{z-4}$ itd, co dowodzi, że nie da się zapisać drugiej liczby w przypadku jak jest ona różna od tej pierwszej. Co dowodzi, że istnieje maksymalnie jeden taki układ liczb Fibonacciego dla każdej liczby naturalnej.

$\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$

## 4

int xdokmoduln(x,k,n)
{
    if (k==1) return x%n;
    x0 = xdokmoduln(x,k/2,n)
    if (k%2==0) return (x0 * x0) % n;
    return (x0 * x0 * x) % n;
}

$T(k) = T(\lfloor \frac{k}{2}\rfloor) + x$, gdzie x = 1 dla k parzystego, x = 2 dla k nieparzystego
Czyli $T(k)=\lceil log_2k\rceil$
## 11
a)
gcd(448,721):
721 - 448 = 273
448 - 273 = 175
273 - 175 = 98
175 - 98 = 77
98 - 77 = 21
$77 - 3\times21 = 14$
21 - 14 = 7
$14 - 2\times7 = 0$
gcd(448,721) = 7

$7 = 21 - 14 = 21 - (77 - 3\times21) = 4\times21 - 77 = 4\times(98-77) - 77 =4\times98 - 5\times77 =$$= 4\times98 - 5\times(175-98) = 4\times98 - 5\times175 + 5\times98 = 9\times98 - 5\times175 = 9\times(273-175) - 5\times(175) =$$= 9\times273 -14\times175= 9\times273 -14\times(448 - 273) =23\times273-14\times448$$=23\times(721 - 448)-14\times448 = 23\times721 -37\times448$
x = 23, y = -37

b)
gcd(1234,333):
$1234-3\times333=235$
333-235 = 98
$235-98\times2 = 39$
$98-2\times39=20$
39-20=19
20-19=1
1-1=0

$1=20-19=20-(39-20) =2\times20-39=2\times(98-2\times39)-39=2\times98 - 5\times39=$$=2\times98 - 5\times(235-2\times98) =12\times98 - 5\times235 = 12\times(333-235)-5\times235 = 12\times333 - 17\times235=$$=12\times333 - 17\times(1234-3\times333) = 63\times333 - 17\times1234$
x = 63, y=-17

$333\times x$ mod $1234=1$ wiedząc, że $63\times333-17\times1234=1$
to $333^{-1}\equiv 63$ mod 1234

c) $-69^{-1}$ mod $1313$
gcd(1313, 1244):
1343 - 1244 = 69
$1244-18\times69 = 2$
$69-24\times2=1$
$1-1=0$

$(1313- 69)x + 1313y = 1$
$1 =69 - 34 \times 2 = 69 - 34 \times (1244 - 18 \times 69) = 613 \times 69 - 34 \times 1244 =$$= 613(1313 - 1244) - 34 \times 1244 = 613 \times 1313 - 647 \times 1244$

$x = -647 \equiv 666 (mod 1313)$
$-69^{-1} \equiv 666(mod 1313)$

## 12
$gcd(F_{n-1},F_n) = 1$ Dowód przeprowadzę przez indukcję.

**1$^\circ$** Sprawdźmy dla n=2 i n=3
$gcd(F_1,F_2) = gcd(1,1) = 1$
$gcd(F_2,F_3) = gcd(1,2) = 1$

**2$^\circ$** Załóżmy, że dla każdego x naturalnego mniejszego od n zachodzi $gcd(F_{x-1},F_x)=1$
Wtedy $gcd(F_{n-1},F_n) = gcd(F_{n-1},F_{n-1} + F_{n-2}) = gcd(F_{n-1}, F_{n-2}) = gcd(F_{n-3}, F_{n-2})$ co z założenia indukcyjnego = 1

Na podstawie indukcji matematycznej udowodniłem, że $gcd(F_{n-1},F_n) = 1$

$gcd(F_m, F_n) =F_{gcd(m,n)}$ Dowód przeprowadzę przez indukcję po n, zakładając bez straty ogólności, że m $\leq$ n

**1$^\circ$** Sprawdźmy dla n=1
$gcd(F_m,F_n) = gcd(1,1) = 1 = F_1 = F_{gcd(1,1)}$

**2$^\circ$** Załóżmy, że dla każdego n-1 i m$\leq$n-1 $gcd(F_m, F_{n-1}) =F_{gcd(m,n-1)}$ zachodzi. Wtedy dla n

Wiemy, że $F_{m+n} = F_mF_{n+1} + F_{m-1}F_n$

Więc $F_n = F_{m+(n-m)} = F_mF_{n-m+1} + F_{m-1}F_{n-m}$

$gcd(F_m, F_n) = gcd(F_m, F_mF_{n-m+1} + F_{m-1}F_{n-m}) =gcd(F_m, F_{m-1}F_{n-m}) = gcd(F_m, F_{n-m})$ (bo gcd($F_m$ i $F_{m-1}$) = 1)
$=$ z założenia indukcyjnego $= F_{gcd(m,n-m)} = F_{gcd(m,n)}$

Na podstawie indukcji matematycznej udowodniłem, że $gcd(F_m, F_n) =F_{gcd(m,n)}$.

## 14.

Udowodnię 2 rzeczy. Pierwsza- każda liczba naturalna n ma taką potęgę.
Druga- nie istnieją dwie różne potęgi spełniające warunek zadania.

**1$^\circ$** Każda liczba naturalna n ma taką potęgę

Dowód przeprowadzę przez indukcję

**1$^{\circ\circ}$** dla n=1
$2^0 = 1$

**2$^{\circ\circ}$** załóżmy, że istnieje taka potęga 2, zaczynająca się cyfrą 1 oraz mająca n cyfr. Wtedy dla n>1
Z założenia indukcyjnego weźmy tę liczbę i nazwijmy ją p.
Rozpatrzmy $p\times2^x$. Wtedy istnieje takie x, aby ta liczba miała n+1 cyfr i zaczynała się od cyfry 1, gdyż każda cyfra najbardziej znacząca pomnożona przez 2 daje maksymalny wynik 18 (19 jeżeli bierzemy pod uwagę cyfry mniej znaczące), więc za każdym razem jak pomnożymy tę liczbę przez 2 to albo dostaniemy naszą liczbę szukaną, albo dostaniemy liczbę za małą i będziemy musieli znowu domnożyć przez 2 (liczba tych "domnożeń" to jest x).

**2$^\circ$** Nie istnieją dwie różne potęgi spełniające warunek zadania.
Załóżmy nie wprost, że istnieje potęga a i b taka, że $a\neq b$ oraz $2^a$ zarówno jak $2^b$ mają tyle samo liczb w zapisie dziesiętnym (n) oraz zaczynają się cyfrą 1.
Wtedy jedna z liczb jest co najmniej 2x większa. Z założenia $2^a = 1.....$ więc każda liczba co najmniej 2x mniejsza będzie miałą mniej liczb w zapisie dziesiętnym. Z kolei liczba co najmniej 2x większa nie ma możliwości aby miała cyfrę 1 na początku (i miała n cyfr).

Na podstawie indukcji matematycznej oraz dowodu nie wprost zastosowanego w drugiej części dowodu udowodniłem, że istnieje dokładnie jedna potęga 2, która w układzie dziesiętnym ma n cyfr z najbardziej znaczącą cyfrą 1.

## 15

$ax_o + by_0 = c = ax + by$
$ax_o + by_0 = ax + by$
$ax_o - ax = by - by_0$
$a(x_o - x) = b(y - y_0)$
Załóżmy, że $gcd(a,b) = d$
$a = d\times r$ ($r = \frac{a}{d}$)
$b = d\times s$ ($s = \frac{b}{d}$)

**gcd(s,r)=1**

$d\times r(x_o - x) = d\times s(y - y_0)$
$r(x_o - x) = s(y - y_0)$
skoro $gcd(s,r)=1$ oraz $r | s(y - y_0)$ to $r | y-y_0$
więc $y-y_0 = r\times t$
$y = y_0 + r\times t$

$r(x_o - x) = s(y - y_0)$ podstawiam
$r(x_o - x) = s\times r\times t$
$x_o - x = s\times t$
$x = x_0-s\times t$

Czyli
$y = y_0 + r\times t = y_0 + \frac{a}{d} \times t$
$x = x_0 - s\times t = x_0 - \frac{b}{d} \times t$
gdzie $t\in\mathbb{Z}$, a $d=gcd(a,b)$