\input exos
\fiche{Propriétés de $ℕ$}

%-----------------------------------------------------------------
\ex Dénombrement de $ℕ²$
Soit $\application f {ℕ²} ℕ {(p,q)} {½(p+q)(p+q+1) + p}$

\qq  Montrer pour $q > 0$ : $f(p+1,q-1) = f(p,q)+1$ et $f(0,p+1) = f(p,0)+1$.
\qq  Montrer que : $f(0,p+q) ⩽ f(p,q) < f(0,p+q+1)$.
\qq  Montrer que $g$ : $n↦f(0,n)$ est strictement croissante.
\qq  Montrer que $f$ est injective (on supposera $f(p,q) = f(p',q')$
     et on montrera dans un premier temps que $p+q = p'+q'$).
\qq  Montrer que $f$ est surjective.

%-----------------------------------------------------------------
\ex Parties dénombrables
Soit $(n_k)$ une suite d'entiers naturels. On dit que la suite est
presque nulle s'il existe $p∈ℕ$ tel que $∀k⩾p$, $n_k=0$,
et qu'elle est stationnaire s'il existe $p∈ℕ$ tel que $∀k⩾p$, $n_k=n_p$.

Montrer que les ensembles des suites presque nulles et des suites
stationnaires sont dénombrables.

%-----------------------------------------------------------------
\ex Propriétés du pgcd et du ppcm
Soient $a,b∈ℕ$. On pose $m = a∨b$ et $d = a∧b$.

\qq  Soit $x$ un multiple commun à $a$ et $b$. En écrivant la division
     euclidienne de $x$ par $m$, montrer que~$m│x$.
\qq  Soit $x$ un diviseur commun à $a$ et $b$.
     Montrer que $x∨d$ est aussi un diviseur commun à $a$ et $b$.
     En déduire $x│d$.
\qq  Comment qualifier $m$ et $d$ pour la relation d'ordre de divisibilité ?

%-----------------------------------------------------------------
\ex Bases de numération
Soit $b ∈ ℕ∖⦃0,1⦄$ et $p∈ℕ$.
Montrer que pour tout entier $n∈ ⟦0,b^p-1⟧$, il existe
un unique $p$-uplet $(n₀,…,n_{p-1})$ d'entiers naturels tel que :
$∀k<p$, $n_k ∈ ⟦0,b-1⟧$, et $n = ⅀_{k=0}^{p-1} n_kb^k$.

%-----------------------------------------------------------------
\ex Bases de numération
Soit $n∈ℕ^*$. Montrer qu'il existe $p∈ℕ$ et $n₀,n₁,…,n_p ∈ ⦃1,2⦄$
uniques tels que $n = ⅀_{k=0}^p n_k2^k$.

%-----------------------------------------------------------------
\ex Bases de numération
Soient $n,p∈ℕ^*$ avec $n < p!$. Montrer qu'il existe
un unique $p$-uplet $(n₁,…,n_p)$ d'entiers naturels tel que
$∀k ⩽ p$, $n_k ⩽ k$, et $n = ⅀_{k=1}^p n_kk!$.

%-----------------------------------------------------------------
\ex Récurrence d'ordre 2
On note $a_n = 25ⁿ + 2^{3n+4}$.

\qq  Trouver $a,b∈ℤ$ tels que : $∀n∈ℕ$, $a_{n+2} = a.a_{n+1} + b.a_n$.
     \reponse{$a=33$, $b=-200$.}
\qq  En déduire : $∀n ∈ ℕ$, $a_n$ est divisible par $17$.

%-----------------------------------------------------------------
\ex Ordre sur $ℕ^ℕ$
Soit $E = ℕ^ℕ$. Pour $f,g∈E$ avec $f≠g$,
on note $n_{f,g} = \min⦃k$ tq $f(k) ≠ g(k)⦄$.

On ordonne $E$ par :
$$∀f,g∈ E,\
  f ≼ g ⇔ (f = g) \text{ ou } (f(n_{f,g}) < g(n_{f,g})).$$

\qq  Montrer que c'est une relation d'ordre total.
\qq  Montrer que toute partie de $E$ non vide admet une borne inférieure
     et toute partie de $E$ non vide et majorée admet une borne supérieure.

%-----------------------------------------------------------------
\ex $f∘f(n) = n+k$
On veut montrer qu'il n'existe pas d'application $f:ℕ→ℕ$
vérifiant : $∀n ∈ ℕ$, $f(f(n)) = n + 1987$
({\it Olympiades 1987}).

Soit $f$ une telle application. On pose :
$E = ⟦0,1986⟧$, $F = ℕ∖E$, $G = f(ℕ)∩E$, $H = E∖G$.

Démontrer successivement :

{\qq  $f$ est injective,
\qq  $f(F) ⊂ F$,
\qq  $f^{-1}(F) = F∪G$,
\qq  $f^{-1}(G) = H$,\par}

puis obtenir une contradiction.

%-----------------------------------------------------------------
\ex $f(f(n)) < f(n+1)$

Soit $f:ℕ→ℕ$ telle que : $∀n∈ℕ$, $f(f(n)) < f(n+1)$.
On veut montrer que $f = \id_ℕ$
{\it (Olympiades 1977)}.

\qq Montrer : $∀n∈ ℕ$, $∀x⩾n$, $f(x)⩾n$.
    \reponse{récurrence sur $n$.}
\qq Soit $n∈ℕ$ et $a⩾n$ tel que $f(a) = \min⦃f(x)$ tq $x⩾n⦄$.
    Montrer que $a=n$.
    \reponse{Si $a > n$, alors $a = b+1$ avec $b ⩾ n$, donc $f(b) ⩾ n$,
    donc $f(f(b)) ⩾ f(a)$~; contradiction.}
\qq En déduire que $f$ est croissante, puis conclure.

\bye
