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
Réponses
-
Avec $n$ points droites, on a généralement $n(n-1)/2$ points. C'est le cas s'il n'y a aucun point multiple, et pas de droites parallèles.
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Salut:
Mais pourquoi tout ce charabia, alors que la réponse à la question initiale saute aux yeux ? -
Je propose ma figure pour le problème de départ.Le problème général est plus compliqué. Je me suis servi, pour ma figure, du fait qu'on pouvait changer le nombre d'intersections grâce à autre chose que la simple direction : la position exacte de la droite change le nombre d'intersections. Si ma droite bleue intersectait la 4ème parallèle noire un peu plus haut que le point $B$, elle intersecterait aussi la droite rouge strictement entre $B$ et $E$, et on aurait une intersection de trop.Je pense que tenir compte de toutes configurations d'intersections possibles est quelque chose d'assez compliqué...
-
Merci @lourrran pour les points perdus.Merci @{Homo Topi} pour la figure.J'en suis donc à $i(2)=i(3)=\emptyset$, $i(4)=\lbrace2\rbrace$, $i(5)=\lbrace2,3\rbrace$.Aujourd'hui : $i(6)\subset\lbrace2,3,4,13\rbrace$.Le $13$ me paraît bien bizarre, mais bon, pour l'instant je sèche.Peut-être une petite règle pour la partition $m+1+1$ de $n$ : elle permet d'obtenir $2m-1$ ou $2m$ intersections.EDIT. Comme le dit lourrran : $2m+1$, pas $2m$. Fin EDIT.Amicalement,Swingmustard.
-
$i(2)$ n’est pas vide puisqu’il contient 2.
Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
OK, je définis mieux ma fonction $i$.Il s'agit d'examiner les nombres entre $0$ et $\begin{pmatrix}n\\2\end{pmatrix}$, raison pour laquelle je considère que $2$ est hors-jeu pour $i(2)$.Amicalement,Swingmustard
-
Pour 6 droites, si on n'a aucun atypisme, on a 1+2+3+4+5=15 points d'intersection.
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Le nombre de cas possibles donne une suite d’OEIS ?
Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
Merci @lourrran pour tes $\begin{pmatrix}6\\2\end{pmatrix}-1-1=13$ intersections issues de la partition $2+2+1+1$.Comme tu l'as signalé, un point de concours fait perdre deux points.On peut donc aussi proposer $\begin{pmatrix}6\\2\end{pmatrix}-2=13$ de la partition $1+1+1+1+1+1$.Merci aussi pour ta correction : c'est bien $2m+1$ et pas $2m$.Amicalement,Swingmustard
-
On peut voir le problème de façon un peu différente.
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)$Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Bonjour
Je restreins le problème à la partition $1+1+1+1+1+1+1$ de $6$, autrement dit "aucune paire de parallèles".Peut-on s'attendre à tous les nombres d'intersections possibles entre :$1$ de "toutes concourantes" et$\begin{pmatrix}6\\2\end{pmatrix}=15$ de "toutes sécantes" ?Non, et je crois que ce petit tableau "Écriture en base $\begin{pmatrix}6\\2\end{pmatrix}=15$, $\begin{pmatrix}5\\2\end{pmatrix}=10$, $\begin{pmatrix}4\\2\end{pmatrix}=6$, $\begin{pmatrix}3\\2\end{pmatrix}=3$, $\begin{pmatrix}2\\2\end{pmatrix}=1$" va m'aider à faire un peu de tri.\begin{array}{|c|c|c|c|c|c|c|}
\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[Le compilateur $\LaTeX$ ne compile que ce qui est entouré de $\$^\dagger$. L'environnement tabular ne l'est pas, il n'est pas compilé.
AD]
[${}^\dagger$ Les environnements array, align, et sans doutes quelques autres passent automatiquement en mode mathématique.]P.S. Comment ça marche ? Par exemple la ligne $2+0+3=5$ signifie qu'il existe peut-être un dessin avec $2$ points, chacun étant point de concours de $4$ droites; et $3$ points, chacun étant intersection de $2$ droites.Comme $2\begin{pmatrix}4\\2\end{pmatrix}+3\begin{pmatrix}2\\2\end{pmatrix}=2\times6+3\times1=15=\begin{pmatrix}6\\2\end{pmatrix}$, si tant est que ce dessin existe, il aura $2+3=5$ points "d'intersection" en tout.D'une part, l'absence de $2, 12, 14$ dans la colonne de droite dit qu'il est inutile d'essayer d'obtenir $2, 12, 14$ points d'intersection avec nos six droites "sécantes ou concourantes". D'autre part, chaque ligne indique un moyen potentiel d'obtenir une somme donnée.Pour rester avec l'exemple "$5$ points d'intersection", je le chercherai soit comme dit à l'instant, soit d'après la ligne $5+0=5$, donc avec $5$ fois trois droites concourantes. (Ces lignes sont des candidatures, mais beaucoup ne peuvent être retenues, comme quand trop de droites sont déjà concourantes.)Bon, hélas je ne crois pas que l'idée puisse trop servir quand on a des parallèles.
-
Je crois qu'aucun des deux cas décrits ci-dessus en exemple (donnant $5$ points d'intersection) n'est réalisable. (Trop de concours exigés.)En revanche, il y a dans le tableau quelqu'un d'assez connu (que je n'ai pas vu venir), c'est "$4+3=7$ points d'intersection"...N'importe quel triangle cévien, avec ses $4$ points de concours de 3 droites, et les $3$ pieds des céviennes.Amicalement,SwingmustardP.S. Je réalise, un peu tard, que @lourrran avait exactement annoncé cette formule, avec ses $N_i$ ! Je ne peux pas dire à quel degré il m'a inspiré, car quand j'ai compté les points de cette manière sur un de mes dessins, j'ai eu l'impression de faire une trouvaille. Tu parles, Charles !..Bref, merci à toi.Par ailleurs, je me demande s'il y a d'autres domaines où ce type de décomposition "en base de combinaisons" a des applications.
-
Pour info
- 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.[1] P. Erdös, On a problem of Grünbaum, Can. Math. Bull. 15, 23-25 (1972).
C'est d'ailleurs Grünbaum qui avait remarqué les deux exceptions ci-dessus.
Pierre. -
Pour le problème initial de $10$ droites et $20$ intersections, il suffit de choisir $7$ droites parallèles, disons horizontales, puis une droite $D_1$ verticale. Elles déterminent $7$ points d'intersections. On choisit une droite $D_2$ ni verticale ni horizontale, qui rencontre $D_1$ ailleurs qu'en une des $7$ droites horizontales, ce qui fournit $8$ nouvelles intersections. Enfin, on prend une droite $D_3$, ni verticale ni horizontale, qui rencontre $D_1$ et $D_2$ en deux des points d'intersections avec des droites horizontales, ce qui ajoute $5$ nouveaux points.
Pierre. -
Merci PierreB,1) Pour le problème initial, je me promets de chercher si la solution qu'Homo Topi et toi proposez est unique.2) J'aimerais accéder au problème de Quadrature que tu mentionnes, qui confirme que le "trou" $i(5)=\lbrace{2,3}\rbrace$, $i(6)=\lbrace{2,3,4}\rbrace$ (je m'enhardis à conjecturer pour $n=6$) va grandir régulièrement et nous promet quelques ajouts rigolos pour $k>n$.Hélas je tombe sur un site ancien de Quadrature (la revue a-t-elle cessé de paraître en 2011 ?) qui me renvoie à un site inaccessible.Plus de recherche m'apprend seulement que Quadrature est ou était éditée par EDP Sciences (pour Édition Diffusion Presse), maison fondée en 1920 par d'illustres scientifiques. Et rachetée en 2019 par CSPM (Chinese Science Publishing and Media), elle-même contrôlée à 74% par l'Académie des sciences chinoise.Quadrature paraît-elle encore ?
Amicalement,
Swingmustard -
Bonjour,
En tant qu'abonné, j'ai reçu le numéro 126 il y a quelques jours.
Cordialement,
Rescassol
-
Merci Rescassol,Je tente de m'abonner !Amicalement,Swingmustard
-
Pour avoir une autre solution, on peut chercher une solution 'duale' de la solution proposée.7 droites parallèles horizontales $\rightarrow$ ça devient 7 droites concourantes, presque horizontales. 1 point d'intersection.
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Pour le problème de Quadrature, voir fichier ci-joint.
Pierre. -
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 16
+12 Invités