[Maths] Marathon de problèmes

Pour le 1, on regarde la dimension de « l’espace des ellipses ». Une ellipse peut être paramétrisée par deux points (ses foyers) et un rayon, ce qui fait 5 réels. La dimension est 5 : étant donné une ellipse, on a 5 « directions » dans lesquelles bouger. Quand on fixe un point sur une courbe, ça ne compte pas comme deux paramètres (le nombre de coordonnées) mais que comme un seul car il y a une direction dans laquelle on peut bouger sans changer la courbe. Formellement, on forme le produit de l’espace des ellipses avec le plan, on considère le sous-espace de codimension 1 « le point est sur l’ellipse », intersecté avec le sous-espace de codimension 2 « le point est égal à $p$ » (pour un certain point $p$). Il faut donc spécifier 5 points au minimum. (Avec le cercle, ça donne bien 3 paramètres réels (un centre et un rayon par exemple) et donc 3 points.)

Pour le 2, il n’est peut-être pas très difficile de montrer que lorsqu’on prend $n$ cercles de même rayon, avec leurs centres alignés et assez proches, ça donne $\binom{n}{2}$ points d’intersection. Mais même si on doute du fait que chaque point d’intersection est distinct, on peut perturber un peu la situation. Pour chaque couple de points d’intersection, le sous-espace constitué de l’ensemble des configurations dans lesquelles ces deux points d’intersection sont confondus est d’intérieur vide (de dimension strictement inférieur à la dimension de l’espace des configurations). L’union de tous ces sous-espaces ne peut donc pas être l’espace des configurations en entier (au voisinage de la configuration considérée). Il y a donc une configuration au moins dans laquelle tous les points d’intersection sont distincts.

Pour le 3, chaque zone coloriée est l’« intérieur » d’une parabole (wikipédia). On ajoute un point « à l’infini » à $ℝ^2$ pour chaque direction (orientée). Alors chaque zone coloriée ne va colorier qu’un point à l’infini, donc au bout d’un nombre fini d’étapes il y aura un point à l’infini (une direction) non couverte, et en allant très loin dans cette direction on trouvera forcément des points non coloriés. [On pourrait se dire qu’apparemment, ça fonctionnerait aussi pour un nombre dénombrable d’étapes, mais en fait on utilise que l’union finie de fermés est fermée, pour pouvoir dire que pour un point à l’infini non colorié, il existe un voisinage non colorié (contenant donc des points finis non coloriés).]

Soit $P = a_1 X + a_2 X^2 + ⋯ + a_m X^m ∈ ℝ[X]$ vérifiant les hypothèses.

On commence par se ramener à l’hypothèse que l’image de $(P(n))_n$ dans $ℝ∕ℤ$ (modulo $1$) a un nombre fini de valeurs d’adhérences. Soit $(b_n)_n$ l’image de $(P(n))_{n∈ℕ}$ dans $ℝ∕2ℤ$. La suite $(\cos(𝜋 P(n)))_n$ se retrouve comme image de $(b_n)_n$ par $x ∈ ℝ∕2ℤ ↦ \cos(𝜋x)$. Comme chaque point de $[0,1]$ a au plus deux antécédents par $x ∈ ℝ∕2ℤ ↦ \cos(𝜋x)$, la suite $(b_n)_n$ a un nombre fini de valeurs d’adhérence (si elle en avait un nombre infini, son image aussi). Cela équivaut à ce que l’image de $(2 P(n))_n$ dans $ℝ∕ℤ$ ait un nombre fini de valeurs d’adhérences. En multipliant les coefficients de $P$ par $2$, on se ramène à l’hypothèse voulue.

Commençons par supposer que $a_2,…,a_m$ sont rationnels et montrons que $a_1$ l’est aussi.

Lemme. Soit $(u_n)_n$ et $(v_n)_n$ deux suites dans $ℝ∕ℤ$. Si $(u_n)_n$ a un nombre fini de points d’accumulation et que $(v_n)_n$ en a un nombre infini, alors $(u_n + v_n)_n$ a un nombre infini de points d’accumulation.

Preuve. Comme $(u_n)_n$ a un nombre fini de points d’accumulation, on peut partitionner la suite en un nombre fini de suites convergentes. Ça donne une partition de $ℕ$ en un nombre fini de parties $A_1,A_2,…,A_k$. L’ensemble des points d’accumulation de $\{v_n\}_{n∈A}$ est l’union des points d’accumulations de chaque $\{v_n\}_{n∈A_i}$ et donc il existe un $i$ tel que $\{v_n\}_{n∈A_i}$ ait un nombre infini de points d’accumulation. On s’est réduit au cas où $(u_n)_n$ converge vers un certain point $a$. Il existe une infinité de points $x$ avec une sous-suites de $(v_n)_n$ convergeant vers $x$, et la sous-suite correspondante de $(u_n + v_n)_n$ converge vers $a+x$. Donc $(u_n+v_n)_n$ a un nombre infini de points d’accumulation.

Remarque. Il se peut que $(u_n)_n$ ait un nombre fini de points d’accumulation et que $(v_n)_n$ soit d’image dense dense, mais que $(u_n+v_n)_n$ soit d’image non dense. Si les deux suites ont un nombre infini de points d’accumulation, il se peut que la somme en ait un nombre fini, par exemple avec $u_n = -v_n$.

Comme $a_2,…,a_m$ sont supposés rationnels, on peut écrire $(a_2,…,a_m) = (p_1,…p_m) ∕ q$ avec $p_i, q ∈ ℤ$. Alors la suite $(\frac{a_2 n^2 + ⋯ + a_m n^m}{q})_n$ a un nombre fini de points d’accumulation car son image est dans $(\frac{1}{q} ℤ) ∕ ℤ ⊆ ℝ∕ℤ$ qui est fini. Si $a_1$ était irrationnel, alors $(a_1 n)_n$ aurait un nombre infini de points d’accumulation, et donc il en irait de même pour $(P(n))_n$ d’après le lemme, contradiction.

Pour traiter les cas restants, on remarque que si $(a_n)_n$ a un nombre fini de valeurs d’adhérence, alors $(a_{n+1} - a_n)_n$ aussi. Soit $𝛥P(X) ≔ P(X+1) - P(X)$. Supposons que $P$ ne soit pas à coefficients rationnels et soit $k$ maximal tel que $a_k$ soit irrationnel. Si $k=1$, on a une contradiction d’après ce qui précède. Sinon, alors dans $𝛥P$ :

• Le coefficient de $X^{k-1}$ est $∑_{i=k}^n \binom{k-1}{i} a_i$, somme dans laquelle tous les termes sont rationnels sauf $k a_k$.
• Chaque coefficient d’une puissance supérieure de $X$ est rationnel.

Par récurrence sur $k$, on obtient une contradiction et donc $P$ doit être à coefficients rationnels.

On définit $m$ comme étant le plus petit entier vérifiant :

On en déduit donc que dans le pire des cas, cet algorithme est de complexité $O(\sqrt{n})$.

On définit $m$ comme le plus petit entier vérifiant :

Ici, monter d’un étage en fait économiser beaucoup (en $O\left(n^{K-1}\right)$ comme on a $K+1$ étudiants), donc le pire des cas est là où on économise le moins, à savoir le cas où le premier étudiant meure dès le premier "lancer". Il reste donc $m^k$ étages à tester avec $K$ étudiants, le problème se résout donc en $O\left(M\right)$ soit en $O\left(\sqrt[k]{n}\right)$.