next_inactive up previous


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

  1. 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'$ n$-esimo numero di Fibonacci, ovvero che $ \vert S_{n}\vert=f(n)=f(n-1)+f(n-2)$, per ogni $ n\geq 2$, con $ f(0)=1$ e $ f(1)=2$
    b) Dimostrare per induzione su $ n$ 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 $ f(0)=1$ e $ f(1)=2$ per il punto a).

  2. Dimostrare per induzione su $ n$ che $ \sum_{j=1}^{n}j^{2}=\frac{n(n+1)(2n+1)}{6}$ per ogni $ n\geq 1$.

  3. 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$.
  4. Dimostrare che $ \left({n \atop m}\right)=\left({n \atop n-m}\right)$, per ogni $ n,m \in \mathbb{N}$ con $ m\leq n$.
  5. 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}$
  6. 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 $ n$ elementi]

  7. 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 $ n$ che $ f(n)$ è dispari per ogni $ n$.
    Dimostrare per induzione su $ n$ che $ f(n)=\frac{1}{5}\left[7(-1)^{n+1}+\frac{1}{2}4^{n+1}\right]$

  8. 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 $ (f(n+2),f(n+1))=1$.

  9. Quale parola di 13 lettere dà luogo al maggior numero di anagrammi? Quale al minor numero?

  10. Calcolare, utilizzando l'algoritmo di Euclide, i seguenti:

  11. Quanti sono i divisori di 345? Elencarli tutti.
    Calcolare $ \Phi(345)$.
  12. Ha più divisori 345 o 225?

  13. Trovare $ \Phi(m)$ per ogni $ m$ da 90 a 100.

  14. 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$

  15. 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$

  16. 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}

  17. 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.

  18. Calcolare, se esiste l'inverso di:

  19. Elencare gli elementi invertibili di $ \mathbb{Z}_{15}$.
    Calcolare se esiste l'inverso di $ 7 \mod 15$.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -local_icons -image_type gif -split +0 eserc2

The translation was initiated by Luminati Domenico on 2002-05-30


next_inactive up previous
Luminati Domenico 2002-05-30