[Maths] Marathon de problèmes

a marqué ce sujet comme résolu.
Banni

@entwanne : il faut gérer le cas limite où les valeurs sont réparties entre $n$ et $n+1$ (edit : qui n’est d’ailleurs pas si limite que ça car on arrive dessus dès que le maximum et le minimum n’ont pas même parité).

Voici ma proposition de solution pour le problème 5 (c’est majoritairement des détails, il faut trouver comme organiser l’argument…).

On note $\DeclareMathOperator{\diam}{diam}\diam(X)$ le diamètre d’une famille d’entiers, c’est-à-dire la distance maximale entre deux termes. On a $\diam(X) = \max(X) - \min(X)$ et $\min(X) ≤ S ≤ \max(X)$ avec $S$ la moyenne des éléments de $X$.

Soit $X$ la famille des entiers de la table. On sépare $X$ en trois sous-familles : les éléments supérieurs ou égaux à $S+1$, ceux inférieurs ou égaux à $S-1$ et ceux qui sont égaux à $S$. Les éléments de la première sous-famille sont envoyés dans $[S,\max(X)-1]$, ceux de la deuxième dans $[\min(X)+1,S]$ et ceux de la troisième sont fixés à $S$. Le nouveau maximum est $\max(\max(X)-1, S) ≤ \max(X)$. Le nouveau minimum est $\min(\min(X)+1,S) ≥ \min(X)$. Le diamètre diminue donc toujours (pas forcément strictement).

Supposons qu’une opération soit effectuée. C’est donc que l’une des deux sous-familles sur laquelle on effectue les opérations est non vide, donc que $\max(X) ≥ S+1$ ou $\min(X) ≤ S-1$ (en fait les deux sont vérifiés mais on n’a pas besoin de ça). Si on est dans le premier cas, on a $\max(X)-1 ≥ S$ et donc $\max(\max(X)-1,S) = \max(X)-1 < \max(X)$. Symétriquement pour le minimum. On en déduit que dans ce cas, le diamètre diminue strictement.

Comme il n’existe pas de suite strictement décroissante d’entiers naturels, le diamètre doit être fixe au bout d’un moment, moment à partir duquel on n’effectue donc plus d’opération.

Et voici le problème suivant.

Problème 6.   Montrer que, parmi 5 points distincts aux coordonnées entières, il y en a toujours deux tels que le segment les joignant passe par un point aux coordonnées entières autre que ses extrémités.

+1 -0

Comme le suggère l’énoncé, montrons qu’il y a toujours deux points tels que leur milieu soit à coordonnée entières. On dira que deux points $A(x_a, y_a)$ et $B(x_b, y_b)$ qu’ils sont aimables si $ x_a \equiv x_b \pmod 2$ et $y_a \equiv y_b \pmod 2$. Afin de prouver l’énoncé il suffit donc de montrer que parmis $5$ points $A, B, C, D, E, F$, il existe une paire qui est aimable. Or pour un point la coordonnée en $x$ peut-être soit paire, soit impaire, de même pour la coordonnée en $y$ ce qui nous donne $2^2 = 4$ possibilités. Ainsi avec $5$ points on en a au moins qui à les mêmes parités en $x$ et en $y$ qu’un autre point et donc il existe une paire de points qui est aimable. Ce qui conclut.

Problème 7 :

Existe-t-il un ensemble infini $E$ d’ensembles d’entiers positifs $A_1$, $A_2$, $A_3$,… tel que $\forall$ $ i\neq j\neq k\neq l$, on a:

$\cdot$ $A_i \cap A_j\cap A_k$ est un singleton.

$\cdot$ $A_i \cap A_j\cap A_k\cap A_l$ est vide?

+0 -0
Banni

Ouais, et en dimension $n$ ça donne $2^n+1$ points. Le truc célèbre utilisé s’appelle le « principe des tiroirs » : si on a $n+1$ chaussettes distribuées parmi $n$ tiroirs, il y aura obligatoirement un tiroir contenant deux chaussettes. On peut le montrer/généraliser en disant que le nombre maximal de chaussettes dans un tiroir est supérieur ou égal au nombre moyen de chaussettes.

Après vous avez aussi le principe des chaussettes : le nombre de chaussettes que vous mettez dans un lave-linge n’est jamais congru au nombre de chaussettes qui en sort modulo 2.

Pour ton problème 7 : just-do-it !
Liens : https://gowers.wordpress.com/2008/08/16/just-do-it-proofs/ ; https://www.dpmms.cam.ac.uk/%7ewtg10/justdoit.html

+2 -0

Oui le problème était sympa :p En fait je connais le principe des tiroirs, mais le problème c’est que comme c’est quelque chose d’évident ça me fit toujours bizarre de dire "par le principe des tiroirs on a " :)

Vraiment sympa le lien, je connaissais pas du tout ce type de preuve, néanmoins j’attends que quelqu’un utilise cette technique pour résoudre le problème au dessus (la solution tient en 3-4 lignes )

+0 -0
Banni

Bon bah, personne… :(

j’attends que quelqu’un utilise cette technique pour résoudre le problème au dessus (la solution tient en 3-4 lignes )

Tu voulais dire que tu n’attends pas une utilisation de cette technique ? Voici ma solution.

On construit les $A_i$ les uns après les autres, le plus simplement possible. On commence avec $A_0$, on ne met rien dedans. Puis on ajoute $A_1$, on ne met toujours rien dedans. Puis on ajoute $A_2$, et là on veut que $A_0 ∩ A_1 ∩ A_2$ soit un singleton. Bon, eh bien on ajoute juste un point contenu dans $A_0$, $A_1$ et $A_2$. Ensuite on ajoute $A_3$. Là on veut que $A_i ∩ A_j ∩ A_3$ soit un singleton pour tout $0≤i<j<3$. On ajoute donc un point dans $A_0 ∩ A_1 ∩ A_3$, un dans $A_0 ∩ A_2 ∩ A_3$ et un dans $A_1 ∩ A_2 ∩ A_3$. Et ainsi de suite. Jamais un point ne sera contenu dans $4$ ensemble à la fois, puisque tous seront contenus dans exactement $3$ ensembles. Et on aura bien un nombre dénombrable de points comme demandé.

Explicitement, $A_i$ va contenir tous les triplets d’entiers naturels contenant $i$. On peut choisir une numérotation par $ℕ$ de ces triplets pour voir les $A_i$ comme des parties de $ℕ$.

Quelle est ta solution ?

+1 -0

Bon bah, personne… :(

blo yhg

:'(

Tu voulais dire que tu n’attends pas une utilisation de cette

blo yhg

Non pas du tout :) Je voulais justement voir cette technique pour ce problème ;)

Voilà une autre solution :

On note la suite strictement croissante et infinie des nombres premiers $p_1,p_2,p_3...$

On définit $A_i=\{p_ip_rp_s\}$ avec $1\leq r\leq s$

Dans ce cas $A_i\cap A_j\cap A_k=\{p_ip_jp_k\}$ qui est un singleton et $A_i \cap A_j\cap A_k\cap A_l=\{p_ip_jp_k\}\cap A_l=\emptyset$

$E$ existe donc.

Je pense que tu peux proposer un nouveau problème :D

+0 -0
Banni

Un autre qui peut se résoudre en mode "just do it".

Montrer qu’il existe une chaîne indénombrable dans l’ensemble des parties de $ℕ$. (C’est-à-dire qu’il existe un ensemble $X$ de parties de $ℕ$ indénombrable et totalement ordonné : pour tout $a,b ∈ X$, on a $a ⊆ b$ ou $b ⊆ a$.)

Edit : je ne sais pas trop quel type de problème serait le mieux, je suis peut-être à côté de la plaque, désolé…

+0 -0

Et on aura bien un nombre dénombrable de points comme demandé. Explicitement, $A_i$ va contenir tous les triplets d’entiers naturels contenant $i$. On peut choisir une numérotation par $ℕ$ de ces triplets pour voir les $A_i$ comme des parties de $ℕ$.

Je ne comprend pas.

+0 -0
Banni

Soit $X$ l’ensemble des parties de $ℕ$ de cardinal $3$. Pour chaque triplet d’ensembles $A_i, A_j, A_k$, on va avoir un point spécial dédié à eux $\{i,j,k\}$ qui va être dans leur intersection. Alors $A_i$ va contenir tous les triplets $\{a,c,b\}$ contenant $i$. Explicitement, $A_i = \{ a∈X\,|\,i ∈ a \}$.

Ensuite, on choisit une injection $f$ de $X$ dans $ℕ$ et à travers cette injection $A_i⊆X$ devient un sous-ensemble de $ℕ$. Explicitement, c’est $\{n∈ℕ\,|\,i∈f(n)\}$. La solution de Universite correspond à prendre comme injection $\{a,b,c\} ∈ X \mapsto p_a p_b p_c ∈ ℕ$ où $p_k$ est le $k$ième nombre premier.

+0 -0

On peut construire une bijection entre $\mathbb{Q}$ et $\mathbb{N}$, (voir |ici pour l’explication). De |même on peut construire une injection entre $\mathbb{R}$ et $P(\mathbb{Q})$ (par exemple : $f: \mathbb{R} \rightarrow P(\mathbb{Q}) : \mapsto x \rightarrow \{q \in \mathbb{Q}, q \leq x\}$. Or on sait que $\mathbb{R}$ n’est pas dénombrable, et les $\{q \in \mathbb{Q}, q \leq x\}$ sont clairement ordonnés, ce qui conclut.$\square$

Trouver les fonctions continues $f : \mathbb{R} \rightarrow \mathbb{R}$ tels que :

$$\displaystyle \forall x \in \mathbb{R}, f(x) + \int_{0}^{x} (x-t) \cdot f(t) \mathrm{d}t = 1$$
+0 -0
Banni

Bravo pour ta solution ! Mais tu as écrit à la fin (par inadvertance) « clairement » au lieu de « totalement ». :P
La solution que j’avais en tête est la suivante (et c’est en fait la même que la tienne comme expliqué à la fin).

On va construire la chaîne pas à pas, en intercalant à chaque étape des éléments dans ce qu’on a déjà construit. Lorsqu’on veut compléter une certaine chaîne de cette manière, les problèmes d’ajouter un maximum de choses entre chaque couple d’éléments consécutifs sont indépendants. (Il se peut qu’il n’y ait pas d’éléments consécutifs mais laissons ce détail.) Les éléments qu’il est possible d’ajouter entre $A⊆ℕ$ et $B⊆ℕ$ avec $A⊆B$ sont les $C$ tels que $A⊆C⊆B$. On a un isomorphisme d’ordres de $\{C\,|\,A⊆C⊆B\}$ vers $P(B\setminus A)$ donné par $C ↦ C\setminus A$ (son inverse est $X ↦ X∪A$). Ainsi, le problème d’intercaler un maximum de choses entre deux parties $A$ et $B$ de $ℕ$ ne dépend que du cardinal de $B \setminus A$.

On commence avec la chaîne $\{\varnothing,ℕ\}$, sans perte de généralité (on peut toujours placer $\varnothing$ et $ℕ$ dans notre chaîne). Ensuite, on va choisir un élément à ajouter, de manière à laisser le plus de liberté possible pour la suite. Comme vu plus haut, on a tout avantage à choisir un élément qui soit infini et dont le complémentaire soit aussi infini. Prenons par exemple $2ℕ$. On se retrouve donc avec deux problèmes indépendants : celui de compléter $\{\varnothing,2ℕ\}$ et celui de compléter $\{2ℕ,ℕ\}$. Mais ces deux problèmes sont équivalents au problème initial. On recommence donc la procédure, encore et encore.

La chaîne ainsi construite est isomorphe à l’ensemble ordonné $\mathbb{D}$ des rationnels dyadiques entre $0$ et $1$. C’est dénombrable. Mais la complétion de Dedekind de $\mathbb{D}$ est $[0,1]$ et on obtient donc par la propriété universelle de cette complétion un plongement de $[0,1]$ dans $\mathcal{P}(ℕ)$ : on a trouvé une chaîne non dénombrable.

Explicitons ce qu’il se passe. On écrit chaque entier naturel en base $2$. Cela donne une suite de bits que l’on considère comme le développement en base $2$ d’un rationnel dyadique entre $0$ et $1$. Ça donne une injection dense et croissante $i$ de $ℕ$ dans $[0,1]$. Puis on réplique la même astuce que la solution de Universite : chaque réel $x ∈ [0,1]$ est envoyé sur $\{n∈ℕ\,|\,i(n)<x\}$.

+0 -0

Trouver les fonctions continues $f : \mathbb{R} \rightarrow \mathbb{R}$ tels que :

$$\displaystyle \forall x \in \mathbb{R}, f(x) + \int_{0}^{x} (x-t) \cdot f(t) \mathrm{d}t = 1$$
Universite

Bon, j’ai un trou dans ma démonstration qui fait que je ne peux pas conclure sur toutes les fonctions, mais ça me permet d’en identifier deux.

On a $f$ définie et continue sur $\mathbb{R}$ et on sait que $\forall x \in \mathbb{R}, f(x) + \int_{0}^{x} (x-t) \cdot f(t) \mathrm{d}t = 1$.

Je note $F$ la primitive de $f$ s’annulant en 0, et $G$ la primitive de $F$ s’annulant en 0.

$$ f(x) + \int_{0}^{x} (x-t) \cdot f(t) \mathrm{d}t = 1 \\ \Leftrightarrow f(x) + \int_0^x x f(t) dt - \int_0^x t f(t) dt = 1 \\ \Leftrightarrow f(x) + x \int_0^x f(t) dt - \int_0^x t f(t) dt = 1 \\ \Leftrightarrow f(x) + x [F(t)]_0^x - \int_{0}^{x} t f(t) dt = 1 \\ \Leftrightarrow f(x) + x F(x) - \int_{0}^{x} t f(t) dt = 1 \\ \Leftrightarrow f(x) + x F(x) - \int_{0}^{x} (t f(t) + F(t) - F(t)) dt = 1 \\ \Leftrightarrow f(x) + x F(x) - \int_{0}^{x} (t f(t) + F(t)) dt + \int_{0}^{x} F(t) dt) = 1 \\ $$

On reconnaît dans la première intégrale la dérivée d’un produit des fonctions $u: x \rightarrow x$ et $F$.

$$ \Leftrightarrow f(x) + x F(x) - [tF(t)]_0^x + [G(t)]_0^x = 1 \\ \Leftrightarrow f(x) + x F(x) - x F(x) + G(x) = 1 \\ \Leftrightarrow f(x) + G(x) = 1 \\ \Leftrightarrow G(x) = 1 - f(x) \\ \Rightarrow F(x) = -f'(x) $$

Et de là les fonctions $\cos$ et $-\cos$ apparaissent évidentes. Mais je me demande si la dernière implication est vraiment légitime et si en dérivant je ne perds pas des informations.

En tout cas je ne vois pas comment conclure à partir de ces deux seules solutions évidentes.

+1 -0

@entwanne

Dans l’énoncé je ne dis pas que $f$ est dérivable, je pense donc qu’il faut que tu justifie ta dernière ligne ;) Sinon $\x \mapsto \cos x$ est bien l’unique solution, et suit le conseil de Lucas-84 en te ramenant à une équa diff. (Tu peux aussi récupérer des informations sur $f(0)...$).

@blo-yhg Le mérite ne me revient pas entièrement puisque j’ai eu un cours dessus et donc disons que je savais par quel chemin je devais chercher. Sinon, merci ta solution est très clair, et je connaissais pas cette histoire de la complétion de Dedekind :)

+0 -0

@Ozmox Un cours classique de dénombrabilité.

@entwanne [[secret]] | Je viens de remarquer qu’il y a une erreur à la fin. Effectivement : tu écris : $[G(t)]_0^x = G(x)$ mais rien ne te dit que : $G(0) = 0$. Donc en fait à la fin tu te ramène à une équation différentielle linéaire d’ordre $2$ : $g = g(0)+1-g''$, cette équation à pour solution : $ g(x) = k_1 \cdot \sin x + k_2 \cdot \cos x +g(0)+1$, donc $f(x) = g''(x) = k_1 \cdot \cos x - k_2 \cdot \sin x$, et maintenant en utilisant le fait que : $f(0) = 1$ on a : $f(0) = k_1 = 1$ soit $k_1 = 1$ donc $f(x) = \cos x - k_2 \cdot \sin x$. En remplaçant ça dans l’équation de départ on doit avoir : | $\cos x -k_2 \cdot \sin x + x \cdot [\sin t + k_2 \cos t]_0^x -[t \cdot \sin t + \cos t +k_2 \cdot \sin t -t \cdot k_2 \cdot \cos t]_0^x =$$ \cos x - k_2 \cdot \sin x +x\cdot \sin x + k_2\cdot \cos x -k_2-x \cdot \sin x -\cos x -k_2 \cdot \sin x + x \cdot k_2 \cdot \cos x +1 =$$ k_2 \cdot \cos x -2 \cdot k_2 \sin x -x \cdot k_2 \cdot \cos x - k_2 = 0$ Pour $x = 1$ on a : $-3 \cdot k_2 = 0$, on en déduit que $k _2 = 0$ et donc l’unique solution est $x \mapsto \cos x$. Bon comme tu as du lre remarquer tu as fais tout le boulot, après c’était plus chiant, il fallait surtout tout développer. A part si tu as des choses à ajouter tu peux proposer un nouveau problème :D

+0 -0

Merci à vous, j’avais bien identifié l’équation différentielle $y=-y'' + k$, mais je ne sais pas vraiment comment m’en démêler.

@InaDeepThink, en fait j’ai défini $G$ comme étant la primitive s’annulant en 0, mais c’était probablement déjà une première erreur puisqu’il faudrait tenir compte des autres primitives possibles.

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte