[Maths] Marathon de problèmes

1. Trouver une formule donnant le nombre de régions délimitées par $n$ hyperplans dans $ℝ^k$ (en position générale). Lui ajouter le nombre de sous-espaces qui s’obtiennent comme intersection de certains de ces hyperplans.
2. Trouver une formule donnant pour $k$ élèves et $n$ lancers permis, le nombre maximal d’étages qu’il est possible de tester.
3. Trouver une interprétation de pourquoi ça donne la même formule.

$k = P(1)$ (on obtient donc la somme des coefficients de $P$). On note $s$ le nombre de chiffres de $k$. Ensuite on demande gentiment : $P(10^{s+1})$. On obtient alors : $\displaystyle \sum_{k = 0}^{n} a_k \cdot 10^{sk+k}$, donc puisque le coefficent devant $a_{k+1}$ est : $10^{(sk+k)+s+1}$ et que chacun des $a_k$ est positif et à un nombre de chiffres strictement inférieur à $s$, on peut bien identifier dans $P(10^{s+1})$ les coefficients.

Hahaha t’as eu peur hein !

Généralement quand on résout le problème on a l’idée de demander P(1), puis (P(P(1) + 1), et alors les coefficients sont affichés en base P(1) + 1. Sauf que donner des coefficients en base P(P(1) + 1) c’est pas intuitif, on préfère les coefficients en base 10. Pour ça, évaluer P à la puissance de 10 directement supérieure à P(1) te donne les coefficients en base 10 (et donc tu n’as pas besoin de faire des changements de base calculatoires).

Rappelons rapidement les conditions, pour partir sur une même compréhension du problème qui est posé. On peut jeter un étudiant d’une fenêtre et celui-ci peut soit mourir soit survivre, si il meurt on a un étudiant en moins, si il survit on peut le réutiliser.

On essaie de déterminer l’immeuble le plus grand possible (en nombre d’étages) tels qu’il est possible avec $n$ lancés de déterminer, l’étage fatal de cet immeuble, tels que :

• dans tous les cas le dernier étage de l’immeuble est fatal, donc si un immeuble à $m$ étages et qu’un étudiant suivit au à tous les étages $ \leq m-1$ alors on peut directement en déduire que le $m$-ième étage est fatal.
• si l’étudiant survit à tous les étages de l’immeuble alors le premier étage est fatal, puisqu’on considère que dans un immeuble dans tous les cas au moins un étage est fatal.

Ceci étant dit, commençons par trouver une formule donnant le nombre maximal d’étage que peut avoir un immeuble si on nous donne $k$ étudiants et $n$ lancés.

On note $f : \mathbb{Z}^2 \rightarrow \mathbb{N}$ la fonction, qui à tout couples de la forme : $($nombre d’étudiants, nombre de lancés$)$ associe le nombre d’étages maximal qu’on peut obtenir. Par exemple : $\forall k \in \mathbb{N}^*, f(k,1) = 2$, avec la convention : $f(a, b) = 0$ si $a \leq 0$ ou bien si $b \leq 0$.

Si on a $n+1$ lancés, remarquons qu’on a alors : $f(k, n+1) = f(k-1, n)+f(k, n)$. Effectivement, lorsqu’on lance notre premier étudiant d’un étage , soit il meurt et dans ce cas là il nous reste $n$ lancés et $k-1$ étudiants, donc on se retrouve à calculer $f(k-1, n)$, ou bien il survit et dans ce cas on se retrouve donc à calculer $f(k, n)$. On a donc $f(k, n+1) = f(k-1, n) + f(k, n)$ (on notera que c’est bien une somme disjointe car si l’étudiant survit alors on doit déterminer le nombre d’étages que l’on peut obtenir "au dessus", et si il meurt on doit déterminer le nombre d’étages "en-dessous").

En utilisant la condition initiale, $ \forall k \in \mathbb{N}^*, f(k, 1) = 2$ on trouve (c’est pas trop compliqué, je mettrai dans la semaine les détails des calculs) :

Essayons de prouver que c’est la même formule qui donne le nombre de régions délimités par $n$-hyperplan, en comprenant le lien avec les étudiants et l’immeuble.

2.

Introduisons la relation d’équivalence : $\sim$, on dira que deux mots $a$, $b$ sur l’alphabet $\{0, 1\}$ sont tels que $ a \sim b$ si et seulement si  :

• si $a = b$
• ou bien si $a = m \overbrace{0 \ldots 0}^{k \text{ fois }} c$ et $b = m \overbrace{0 \ldots 0}^{k \text{ fois }} d$ ou $m \in \sum^*$ et $c, d \in \sum^{+}$.

On a alors : $f(k, n) = \sup\{ \mid E \mid : E \subset \sum^+, \forall m \in E, \mid m \mid = n, \not\exists a, b \in E, a \sim b \} = \mid E/\sim \mid $.

En fait, ce résultat se voit si on représente $0$ comme un étudiant qui meurt et $1$ comme un étudiant qui survit. Si on se trouve dans un immeuble à $m$ étages et que l’on arrive à déterminer quel étage est fatal, ça veut dire qu’on arrive à trouver un mot binaire nous permettant de trouver cet étage, soit une succession de $n$ lancés étudiants qui soit valide.

Par exemple prenons le cas ou $(n, k) = (2,2)$ , dans ce cas là on peut avoir au maximum $4$ étages. Supposons que l’étage fatal soit l’étage numéro $2$. Bon on commence par jeter un étudiant au deuxième étage, il meurt on a donc pour l’instant le mot $0$. Ensuite on jette le dernier étudiant qu’il reste au premier étage, cet étudiant survit et on en déduit que le deuxième étage est fatal grâce au mot $01$. Maintenant, il faut comprendre que la relation d’équivalence introduite est très importante. En effet elle s’assure de supprimer les suites non valides. Si on a $k$ fois le caractère $0$ dans une de nos suites, ça veut dire que $k$ étudiants meurent, mais dans ce cas il est impossible de jeter plus d’étudiants puisqu’ils sont tous morts, donc les caractères qu’il y a derrière ces $k$ $0$, ne servent à rien, ainsi c’est pourquoi on "identifie" ces mots à un seul puisqu’un de ces mots détermine un seul étage.

On comprend mieux pourquoi, $f(n, k)$ est égal à l’ensemble des classes d’équivalences de $E$ par $ \sim$, effectivement, qu’importe ou se trouve l’étage fatal on doit avoir une suite de $0$ et de $1$ (donc une suite d’étudiants qui meurent ou survivent) de taille $n$ (on a que $n$ lancés) tels qu’il est possible d’identifier cet étage, on a donc bien : $f(n, k) = \mid E / \sim \mid$, ou $E = \{m \in \sum^+ \mid \mid m \mid = n\}$ .

A partir de cette nouvel "visualisation" du problème (comme le cardinal de l’ensemble des classes équivalences d’un ensemble par une relation bien choisit), on va mieux comprendre le lien avec $2.$. Effectivement on va montrer que le nombre de régions délimitées par ces $n$ hyperplans, détermine exactement ce cardinal.

On commence par noté $g:\mathbb{Z}^2 \rightarrow \mathbb{Z}$ la fonction qui à un couple donne le nombre de régions que l’on peut délimité dans $\mathbb{R}^k$ avec $n$ hyperplans.

Maintenant on peut identifier un lancé à un hyperplan, et une intersection à une suite. A chaque fois qu’un hyperplan sépare l’espace en deux parties on peut associer ces deux parties à : l’une représente le cas ou un étudiant meurt et l’autre à celle ou il survit. Pour $(n, k) = (2, 2)$ on peut donc avoir la figure suivante :

On remarque que pour des petites valeurs de $k$, on a un lien entre le cardinal de $E/\sim$ et $g(k, n)$, on va essayer de comprendre pourquoi c’est vrai pour des valeurs plus grandes.

Maintenant l’idée c’est que lorsqu’on rajoute un hyperplan, pour maximiser le nombre de régions il faut clairement que cet hyperplan intersecte tous les hyperplans déjà en place, on rajoute alors un $1$ à chacun de ceux-ci (on a alors des mots de $n+1$ caractères). Pour les autres nouvelles régions délimitées, on y rajoute à $0$, mais il faut savoir lesquelles peuvent obtenir un $0$ (càd faire mourir un étudiant), or ce nombre est tout simplement de $f(k-1, n)$, puisque c’est le nombre d’anciennes régions se terminant n’ayant pas encore de sous mots avec $k$ $0$.

Ainsi en gros, un hyperplan représente le lancé d’un étudiant, on peut lire l’intersection des hyperplans comme une suite de $0$ et de $1$, tels que le $0$ représente la mort d’un étudiant et le $1$ la survit de celui-ci. Lors de l’ajout d’un hyperplan, si l’on veut maximiser le nombre de région il faut que ce nouvel hyperplan intersecte tous les autres hyperplans déjà en place, en bref ce $n+1$ième hyperplan coupe l’espace en deux, d’un côté on a l’espace d’origine (même nombre de région), cela correspond au cas ou on rajoute un $1$, car le lancé du $n+1$ième étudiant survit, et dans le cas ou il meurt on a exactement le nombre de régions délimités par $n$ hyperplans dans $\mathbb{R}^{k-1}$ (ça se voit assez bien sur un dessin, même si pour $k \geq 3$ c’est un peu plus chaud :D), ainsi on rajoute un $0$ à l’ensemble des mots n’ayant pas $k$ $0$ comme sous mot et qui ne sont pas égaux par $\sim$.

Donc on a clairement : $g(n,k) = \mid E/\sim \mid$

Tout d’abord, si on choisit trois points au hasard sur un sphère, alors l’intersection du plan passant par ces trois points et de la sphère forme un cercle. On peut donc se restreindre au cercle. Je fais alors appel à la figure suivante : L’idée est la suivante : si je choisis deux points aléatoirement sur le cercle, quelle est la probabilité qu’en choisissant le troisième point, le traingle formé est acutangle ? J’ai donc les points $B$ et $C$. Si on trimbale un point $D$ sur le cercle, on voit bien que le seul arc sur lequel il répond au problème est l’arc rouge. On observe un angle obtus sinon. Par construction $BCEG$ forme un rectangle, donc $\widehat{EOG} = \widehat{BOC}$. Ensuite il n’y a plus qu’à se demander quel est l’angle moyen $\widehat{BOC}$ : on place au hasard le premier point, et le deuxième point forme avec lui un angle entre $0$ et $180°$, donc en moyenne $90°$. Cela veut dire que, ayant placé les deux premiers points, il y a en moyenne une chance sur quatre que les trois points forment un triangle acutangle. Donc la probabilité est de $\frac{1}{4}$. NB : pour la dernière étape, on peut le justifier comme suivant : si $X$ est la variable aléatoire qui vaut $1$ lorsque le triangle est acutangle et $0$ sinon, et $Y$ la mesure de l’arc entre les deux premiers points, alors on sait que :

Soit $A,B,C$ les trois points et soit $O$ l’origine. On conditionne par $A$ et on effectue une rotation ramenant $A$ à l’origine, les deux autres points sont indépendants et uniformément répartis. On conditionne par $B$. La densité de probabilité d’obtenir un angle $\angle AOB$ (non orienté) de $𝜃$ est proportionnelle à la longueur du cercle correspondant, soit proportionnelle à $\sin(𝜃)$. L’intégrale de $\sin(𝜃)$ de $0$ à $𝜋$ est $2$, donc la densité est $\sin(𝜃)/2$.

Ensuite on regarde sur un dessin, pour $A$ et $B$ fixés, la zone de la sphère dans laquelle peut se situer $C$ pour que $ABC$ soit acutangle. Soit $𝜃$ l’angle non orienté $\angle AOB$. La zone recherchée est la sphère à laquelle on a retiré trois secteurs sphériques, l’un d’angle $𝜃$ et les deux autres d’angles $𝜋-𝜃$. La probabilité de tomber dans l’un de ces secteurs sphériques est

On trouve que la probabilité que $ABC$ soit acutangle sachant $\angle AOB = 𝜃$ est

La probabilité que $ABC$ soit acutangle est donc

Et wolframalpha dit que ça vaut $1/2$… je le crois (pour moi c’est beaucoup de calculs ). De toute manière c’est ce que j’ai vérifié expérimentalement.