Nombres impossibles d'intersections de n droites du plan
Bonjour
Le point de départ est une "Narration de recherche" proposée par le livre de 6ème de Sésamath.
Le point de départ est une "Narration de recherche" proposée par le livre de 6ème de Sésamath.
Elle demande de dessiner $n=10$ droites ayant $20$ intersections.
N'y arrivant pas pour l'instant, je commence avec des nombres plus petits.
Pour m'y retrouver, je partitionne $n$ en $p$ termes : les nombres de droites ayant la même direction.
Pour $4$ parallèles, $0$ intersection.
Pour $4$ parallèles, $0$ intersection.
À la partition $3+1$, j'associe la situation présentant $3$ droites
parallèles et $1$ sécante. Ces $4$ droites forment $3\times1=3$
intersections.
À la partition $2+2$, j'associe la situation présentant $2$ droites
parallèles et $2$ autres. Ces $4$ droites forment $2\times2=4$
intersections.
Pour la partition $2+1+1$, ($2$ parallèles, $1$
première sécante, et $1$ sécante avec les trois précédentes), on aura
$3$ points d'intersection s'il y a un point de concours, et $5$ en
l'absence de concours.La partition $1+1+1+1$ me semble donner comme nombres d'intersections possibles $1$, $4$ et $6$.
Tous les nombres d'intersections compris entre $0$ et $\begin{pmatrix}4\\2\end{pmatrix}=6$ ont-ils été rencontrés ?
Il me semble que non, et que le premier "nombre impossible"
d'intersections de droites, c'est de former $2$ intersections avec $n=4$
droites.
J'ai aussi exploré $n=5$, sans être sûr d'oublier du monde ou pas.
J'ai aussi exploré $n=5$, sans être sûr d'oublier du monde ou pas.
$5\rightarrow 0$
$4+1\rightarrow4$
$3+2\rightarrow6$
$3+1+1\rightarrow5$ ou $7$
$2+2+1\rightarrow4$ ou $6$ ou $8$
$2+1+1+1\rightarrow4$ ou $7$ ou $9$
$1+1+1+1+1\rightarrow1$ ou $5$ ou $8$ ou $10$
Ce qui précède me laisse penser que $2$ et $3$ sont impossibles pour $n=5$.
Mais vous sentez où je bloque. Soit $p$ le nombre de termes de la partition $n_1+n_2+...+n_p$.
Au delà de
$p=1\rightarrow0$
et $p=2\rightarrow n_1\times n_2$,
je n'ai encore aucune règle fiable pour toutes les réponses en "ou".
1) Avez-vous un éclairage sur $i(n)$, l'ensemble des nombres impossibles pour $n$ droites, comme $i(5)=\lbrace2,3\rbrace$ ?
2) Voyez-vous des règles pour les partitions $1+1+\dots+1$, voire $2+1+1+\dots+1$ ?
Amicalement,
Swingmustard
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
la $k$-ième droite apporte $k-1$ nouveaux points, on a la somme des $n-1$ premiers entiers.
Si $2$ droites sont parallèles, on perd $1$ point.
Si $3$ droites sont parallèles, on devait avoir 3 points, et on n'en a aucun, on perd $3$ points
Si $k$ droites sont parallèles, on perd $k(k-1)/2$ points.
Si $3$ droites sont concourantes, on perd $2$ points
Si $4$ droites sont concourantes, on devait avoir $6$ points, et on n'en a qu'$1$, on perd $5$ points
Si $k$ droites sont concourantes, on perd $k(k-1)/2-1$ points.
Avec ces 2 règles, on bascule (totalement ?) dans le domaine de la combinatoire.
On part du cas général (aucun point multiple, aucun couple de droites parallèles), et on décrémente pour tous les cas particuliers.
Mais pourquoi tout ce charabia, alors que la réponse à la question initiale saute aux yeux ?
-- Schnoebelen, Philippe
Comme vu précédemment, si on a 2 couples de droites parallèles, et aucun autre atypisme, on devrait avoir 13 points d'intersection.
2 droites horizontales, 2 droites verticales : on obtient un rectangle, 4 points.
On ajoute une droite inclinée, qui ne passe par aucun des 4 sommets, elle donne 4 nouveaux points.
Et on ajoute une autre droite inclinée, qui ne passe par aucun des sommets, et qui n'est pas parallèle à la droite précédente, elle apporte 5 nouveaux points. Donc 13 points à l'arrivée, avec ces 6 droites.
Pour la partition $m+1+1$ de $n$, si on n'a aucun point triple, on obtient $(m+2)(m+1)/2 -m(m-1)/2$ points , donc $2m+1$ points
Et si on a en plus un point triple, on perd $2$ points, donc on arrive à $2m-1$ points.
$m$ droites verticales, $1$ oblique qui entraine donc $m$ points.
Une autre oblique, qui entraine $m$ nouveaux aux intersections avec les verticales, et un point de plus avec l'autre oblique. $2m+1$ points.
Sauf si on a un point triple. Et dans ce cas $2m-1$ point. Chaque point triple décrémente de $2$ le total.
-- Schnoebelen, Philippe
On a les points triples, quadruples, les points multiples de manière générale.
Et on a les droites parallèles. 2 droites parallèles, c'est en fait un point d'intersection rejeté à l'infini.
$n$ droites parallèles (avec $n>2$), c'est en fait un point multiple, rejeté à l'infini.
On a donc comme caractérisation :
- L'ordre de chaque point (point normal, intersection de 2 droites, point triple, intersection de 3 droites etc)
- Et pour chaque point, est-il visible, ou rejeté à l'infini.
Donc notons $N_2$ le nombre de points doubles, $N_3$ le nombres de points triples etc et $K$ le nombre de points rejetés à l'infini , on a :
Nombre total théorique de points $= \frac{n(n-1)}{2}$
Nombre de points visibles $= \Sigma N_i - K $
et on a cette relation : $\Sigma \frac{i(i-1)}{2} N_i = \frac{n(n-1)}{2}$
Qu'on peut simplifier : $\Sigma i(i-1) N_i = n(n-1)$
Je restreins le problème à la partition $1+1+1+1+1+1+1$ de $6$, autrement dit "aucune paire de parallèles".
\hline
15&10&6&3&1&&\Sigma\\
\hline
\hline
&&&&15&&15\\
\hline
&&&1&12&&13\\
\hline
&&&2&9&&11\\
\hline
&&&3&6&&9\\
\hline
&&&4&3&&7\\
\hline
&&&5&0&&5\\
\hline
&&1&0&9&&10\\
\hline
&&1&1&6&&8\\
\hline
&&1&2&3&&6\\
\hline
&&1&3&0&&4\\
\hline
&&2&0&3&&5\\
\hline
&&2&1&0&&3\\
\hline
&1&0&0&5&&6\\
\hline
&1&0&1&2&&4\\
\hline
1&0&0&0&0&&1\\
\hline
\end{array}
Ah zut, je ne sais pas faire un tableau ici. EDIT Heureusement, AD est là ! Merci ! Fin EDIT
Amicalement,
Swingmustard
[${}^\dagger$ Les environnements array, align, et sans doutes quelques autres passent automatiquement en mode mathématique.]
- Dans Quadrature, pb. E-367, pour $n \geq 3$, les entiers $k \in \{0,1, \cdots, n\}$ pour lesquels il existe $n$ droites du plan qui déterminent exactement $k$ points d'intersections sont $k=0$, $1$, $n-1$ et $n$.
- Pour les valeurs de $k >n$, c'est plus compliqué et le problème est en général posé dans l'autre sens : Existe-t-il un ensemble de $n$ points qui déterminent exactement $m$ droites (en tant que points d'intersections de ces droites)? Erdös a prouvé [1] qu'il existe une constante $c$ telle que si $c n^{3/2} < m \leq n(n-1)/2$ alors un tel ensemble de $n$ points existe bien, sauf si $m = \dfrac{n(n-1)}{2} -3$ ou $m = \dfrac{n(n-1)}{2} -1$ pour lesquels il n'existe pas d'ensemble adéquat.
C'est d'ailleurs Grünbaum qui avait remarqué les deux exceptions ci-dessus.
Pierre.
Pierre.
Amicalement,
Swingmustard
En tant qu'abonné, j'ai reçu le numéro 126 il y a quelques jours.
Cordialement,
Rescassol
Une droite $D_1$ verticale $\rightarrow$ inchangé, une droite $D_1$ verticale. 7 nouveaux points.
Une droite $D_2$ ni verticale ni horizontale $\rightarrow$ devient une droite $D2$ verticale. 7 nouveaux points.
Et la fin est inchangée, on prend 2 des points d'intersection déjà tracés, 1 sur $D_1$ et l'autre sur $D_2$, et on trace la droite passant par ces 2 points, 5 nouveaux points.
Le point rejeté à l'infini n'est plus rattaché au groupe de 7 droites horizontales ou presque, il est rattaché à un groupe de 2 verticales.
Pierre.
Erdös et Grünbaum : dès que j'aurai le temps, j'essaierai de trouver les plus petits $m$ et $n$.
Amicalement,
Swingmustard