Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 05-01-2018 16:08:13

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

OIM 2017 - Exo 1

Bonjour,
Un ancien camarade de prépa, pour plaisanter, m'a envoyé deux exos des Olympiades Internationale de Mathémétique
ça a piqué ma curiosité et je me suis penché dessus.
Je pense avoir une solution pour le 2 et une piste pour le 1, mais je ne suis pas sûr, je n'ai pas encore rédigé au propre et le diable se cache parfois dans les détails.

Je soumet le premier à ceux qui veulent un peu de remue méninges (c'est censé être de niveau terminale)

Pour tout entier $a_0 > 1$, on définit la suite $a_0, a_1, a_2, ...$ par :
$\displaystyle \forall n \ge 0,\ a_{n+1} =
  \begin{cases}
    \sqrt{a_n}       & \quad \text{si } \sqrt{a_n} \text{ est un entier}\\
    a_n + 3  & \quad \text{sinon}
  \end{cases}$
Déterminer toutes les valeurs de $a_0$ pour lesquelles il existe un nombre $A$ tel que $a_n = A$ pour une infinité de valeurs de $n$.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#2 06-01-2018 15:43:47

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : OIM 2017 - Exo 1

Salut,

Je pense avoir la solution de celui-là (et pour des terminales spé math, l'idée doit venir assez vite), par contre l'autre... je crois avoir la réponse, mais je n'arrive pas à la démontrer...

Texte caché

Notons $\mathcal{P}$ la propriété "il existe un nombre $A$ tel que $a_n=A$ pour une infinité de valeurs de $n$".



Tout d'abord, on peut remarquer que si $a_0\notin\mathbb{N}$, alors $\forall n\in\mathbb{N}, a_n\notin\mathbb{N}$, et donc $\sqrt{a_n}\notin\mathbb{N}$.
Donc $(a_n)_n$ est une suite arithmétique de raison 3 strictement croissante, et ne respectera jamais $\mathcal{P}$.
On peut donc restreindre notre étude aux suites entières.



On remarque aussi que si $(u_n)_n$ est une suite respectant $\mathcal{P}$, alors tous les termes de $(u_n)_n$ aurait pu être choisi pour premier terme.
Par contraposée, pour une suite $(u_n)_n$ donnée, s'il existe un terme de $(u_n)_n$ qui ne peut pas être choisi comme premier terme d'une suite respectant $\mathcal{P}$, alors $(u_n)_n$ ne respecte pas $\mathcal{P}$.



Étudions le comportement de $(a_n)_n$ selon la valeur de $a_0$ modulo 3.


* Si $a_0\equiv 0\ [3]$,
Comme $\forall k\in\mathbb{N}, (k\equiv 0\ [3]\ \Leftrightarrow\ k^2\equiv 0\ [3])$, tous les termes de la suite seront congru à 0 modulo 3.
Soit $(a_{\phi(n)})_n$ la sous-suite des carrés de $(a_n)_n$.
On montre facilement que $(a_{\phi(n)})_n$ est une suite d'entiers naturels décroissante.
Donc $(a_{\phi(n)})_n$ est constante à partir d'un certain rang.
Donc $\exists A, a_n=A$ pour une infinité de valeurs de $n$.



* Si $a_0\equiv 2\ [3]$,
Aucun carré n'est congru à 2 modulo 3,
Donc $(a_n)_n$ ne croisera jamais de carré et sera donc une suite arithmétique de raison 3 strictement croissante.



* Si $a_0\equiv 1\ [3]$,
On va montrer que ça ne fonctionne pas non plus par récurrence forte.
On note $(u_n)_{n\ge 0}$ la suite des carrés congru à 1 modulo 3 strictement supérieur à 1. (On a $u_0=4$, $u_1=16$,...)

Initialisation
Pour $a_0=7$, on obtient la suite 7, 10, 13, 16, 4, 2,...
2 étant congru à 2 modulo 3, à partir de là on croisera plus de carré.
Donc tous les entiers congru à 1 modulo 3 inférieurs à 16 ne conviennent pas.

Hérédité
Soit $n\in\mathbb{N}$.
Supposons que tous les entiers congru à 1 modulo 3 inférieurs à $u_n$ ne conviennent pas.
Montrons que les entiers congru à 1 modulo 3 inférieurs à $u_{n+1}$ ne conviennent pas.
Si $a_0\in]]u_n;u_{n+1}]]$,
alors le premier carré rencontré par $(a_n)_n$ sera $u_{n+1}$.
Or $\forall n\sqrt{u_{n+1}}<u_n$.
Donc le terme suivant le premier carré rencontré par $(a_n)_n$ est un entier qui ne convient pas par hypothèse de récurrence.



Pour résumer, les valeurs de $a_0$ pour $(a_n)_n$ respecte $\mathcal{P}$ sont les entiers strictement positifs congrus à 0 modulo 3.

Dernière modification par tibo (06-01-2018 16:15:15)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#3 07-01-2018 17:07:08

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : OIM 2017 - Exo 1

Bonsoir

@tibo

Ce n'est pas exactement le cheminement que j'avais en tête mais ça se recoupe pas mal.
Pour ma part, j'avais conclu à l'équivalence entre la propriété $\mathcal{P}$ et le fait qu'il existe deux indices $i < j$ tels que $a_i=a_j$. Dans ce cas, le suite devient périodique à partir d'un certain rang et je devais traiter le cas de $a_0=1 \mod 3$.
J'ai deux remarques concernant ta démonstration :
1- La décroissance de la suite extraite $a_{\phi(n)}$ : il me semble que ça mérite d'être détaillé
2- Dans ta récurrence, tu dis $\forall n \sqrt{u_{n+1}}<u_n$, cette affirmation n'est pas toujours vraie (pour $n=0$ en particulier il y a égalité : $4^2=u_0^2=u_1=16$)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#4 07-01-2018 17:24:53

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : OIM 2017 - Exo 1

Bonjour,

@Yassine

2- Il faut en effet écrire $\forall n>1, \sqrt{u_{n+1}}<u_n$.
C'est pour ça que je commence ma récurrence à 16 et non à 4.

1- Pour la décroissance de $(a_{\phi(n)})_n$, il suffit de remarquer que $a_{\phi(n)+1}<a_{\phi(n)}$.
Donc le carré suivant dans la suite $(a_n)_n$ est soit $a_{\phi(n)}$, soit un carré strictement plus petit.
En l’occurrence, je pense que $(a_{\phi(n)})_n$ est strictement décroissante jusqu'à atteindre 9.
Mais je n'en avais pas besoin pour la démonstration.

Dernière modification par tibo (07-01-2018 17:25:47)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#5 08-01-2018 11:01:28

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : OIM 2017 - Exo 1

@tibo

Bonjour tibo
Je précise d'abord que je suis d'accord avec la conclusion. Je discute uniquement le chemin !
Quand tu dis : Donc le carré suivant dans la suite $(a_n)_n$ est soit $a_{\phi(n)}$, soit un carré strictement plus petit, je ne suis pas sûr de bien voir pourquoi.
Est-ce que le terme "carré suivant dans la suite" se réfère à $a_{\phi(n+1)}$ ?
Si oui, pourquoi aurait-on $a_{\phi(n+1)} \le a_{\phi(n)}$ ?
Pour moi ce qu'on sait à ce stade de la démonstration, c'est que $\exists k, a_{\phi(n+1)} = \sqrt{a_{\phi(n)}} + 3k$ et que $a_{\phi(n)+1} = \sqrt{a_{\phi(n)}} < a_{\phi(n)}$


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#6 08-01-2018 13:12:21

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : OIM 2017 - Exo 1

Re,

@Yassine

Ok, je vois ce qui te chagrine.

On est dans le cas où tous les termes de $(a_n)$ sont congrus à 0 modulo 3.

Pour un $n$ donné, on a
$a_{\phi(n)}\equiv 0\ [3]$ et $a_{\phi(n)+1} < a_{\phi(n)}$
Et les termes suivants vont parcourir tous les entiers congrus à 0 modulo 3 plus grand ou égal à $a_{\phi(n)+1}$ jusqu'à $a_{\phi(n+1)}$.

Soit il existe un carré congru à 0 modulo 3 dans $[[a_{\phi(n)+1};a_{\phi(n)}[[$.
Auquel cas , $a_{\phi(n+1)}<a_{\phi(n)}$.

Soit ce carré n'existe pas.
Alors la suite $(a_N)_{N>\phi(n)}$ va recroiser sur sa route $a_{\phi(n)}$, vu qu'elle parcourt tous les entiers congrus à 0 modulo 3 et que $a_{\phi(n)}$ en est un.


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#7 08-01-2018 14:07:21

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : OIM 2017 - Exo 1

@tibo

Yep !
D'ailleurs, je peux adapter ta démonstration pour le cas $1 \mod 3$. En effet, tu n'utilises pas le fait que ce soit vraiment $0 \mod 3$ mais le fait que tous les termes sont de la même classe. Dans mon approche, j'avais montré que si $a_0 = 1 \mod 3$, alors tous les termes devaient être $=1 \mod 3$ pour espérer la périodicité (si on rencontre $2 \mod 3$, on n'aura plus aucun carré, et la suite sera strictement croissante).


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

Pied de page des forums