Esercizi su calcolo combinatorio, divisibilità e congruenze

a cura di Michela Pagliacci

I seguenti esercizi sono riferiti agli argomenti svolti nelle lezioni di esercitazione del 16.05.2002 e del 23.05.2002

Per ogni $n \in \mathbb{Z}^{+}$ si definisca $[n]=\{1,2,\dots, n\}$ e

$\displaystyle S_{n}=\{T \subseteq [n]$ tale che $T$ non contiene due interi consecutivi $\displaystyle \}.$
a) Dimostrare che $\vert S_{n}\vert$ è l'-esimo numero di Fibonacci, ovvero che $\vert S_{n}\vert=f(n)=f(n-1)+f(n-2)$ , per ogni $n\geq 2$ , con e
b) Dimostrare per induzione su che $f(n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right]$ , dove e per il punto a).
Dimostrare per induzione su che $\sum_{j=1}^{n}j^{2}=\frac{n(n+1)(2n+1)}{6}$ per ogni $n\geq 1$ .
Dimostrare che $\left({n \atop m}\right)=\left({n-1 \atop m-1}\right)+\left({n-1 \atop m}\right)$ , per ogni $n,m \in \mathbb{N}$ con $m\leq n$ .
Dimostrare che $\left({n \atop m}\right)=\left({n \atop n-m}\right)$ , per ogni $n,m \in \mathbb{N}$ con $m\leq n$ .
Dimostrare usando la definizione di coefficiente binomiale che:
$n^2= \left({n \atop 2}\right)+ \left({n+1 \atop 2}\right)$ , per ogni $n\in \mathbb{N}$
Dare un'interpretazione combinatoria, ovvero trovare una biiezione fra insiemi di cardinalità opportuna, della seguente uguaglianza:

$\displaystyle n^2=\frac{n!}{(n-2)!}+n$
[Sugg. Pensare a come possono essere le funzioni da un insieme di 2 elementi ad uno di elementi]
Si consideri la successione definita per ricorsione da:
$\begin{displaymath}\begin{cases} f(n+2)=3f(n+1)+4f(n)\\ f(0)=-1\\ f(1)=3 \end{cases}\end{displaymath}$
Dimostrare che per induzione su che è dispari per ogni .
Dimostrare per induzione su che $f(n)=\frac{1}{5}\left[7(-1)^{n+1}+\frac{1}{2}4^{n+1}\right]$
Si consideri la successione definita per ricorsione da:
$\begin{displaymath}\begin{cases} f(n+2)=3f(n+1)+f(n)\\ f(0)=1\\ f(1)=3 \end{cases}\end{displaymath}$
Dimostrare che .
Quale parola di 13 lettere dà luogo al maggior numero di anagrammi? Quale al minor numero?
Calcolare, utilizzando l'algoritmo di Euclide, i seguenti:
- [risp. 1];
- [risp. 17];
- [risp. 1];
- [risp. 13];
- [risp.7];
- [risp.4].
Quanti sono i divisori di 345? Elencarli tutti.
Calcolare $\Phi(345)$ .
Ha più divisori 345 o 225?
Trovare $\Phi(m)$ per ogni da 90 a 100.
Trovare, se esiste, una soluzione delle seguenti congruenze lineari:

a)

$31x\equiv 15 mod 81$

b)

$103x\equiv 612 mod 676$

c)

$27x\equiv 25 mod 256$

d)

$27x \equiv 72 mod 384$

e)

$51x \equiv 99 mod 102$

f)

$9x \equiv 12 mod 21$
Trovare una soluzione delle seguenti congruenze:

a)

$x^3\equiv 2 mod 11$

b)

$x^9\equiv 5 mod 23$

c)

$x^5\equiv 16 mod 27$
Trovare, se possibile, la minima soluzione positiva dei seguenti sistemi di congruenze:

a)

$\begin{displaymath}\begin{cases} x\equiv 3 mod 5 \\ x\equiv 5 mod16 \end{cases}\end{displaymath}$

b)

$\begin{displaymath}\begin{cases} x\equiv 12 mod 31 \\ x\equiv 87 mod127\\ x\equiv 91 mod 255 \end{cases}\end{displaymath}$

c)

$\begin{displaymath}\begin{cases} x\equiv 103 mod 900 \\ x\equiv 511 mod841\\ \end{cases}\end{displaymath}$

d)

$\begin{displaymath}\begin{cases} x\equiv 17 mod 27 \\ x\equiv 41 mod42\\ \end{cases}\end{displaymath}$
Trovare il più piccolo intero positivo che dà resto 1 quando diviso per 11, resto 2 quando diviso per 12 e resto 3 quando diviso per 13.
Calcolare, se esiste l'inverso di:
- $12 \mod 27$
- $12 \mod 36$
- $9 \mod 11$
Elencare gli elementi invertibili di $\mathbb{Z}_{15}$ .
Calcolare se esiste l'inverso di $7 \mod 15$ .