Bonjour à vous tous !
J'ai un problème de mathématiques dont je n'arrive pas à entrevoir la solution.
Son énoncé est tout simple :

Citation

On a <math>\(2n\)</math> points répartis régulièrement sur un cercle (ex : {<math>\({z | z^{2n} = 1}\)</math>}). Existe-t'il une famille de <math>\(n\)</math> segments reliant chaque point à un seul et unique autre telle que chacun de ces segments ait une longueur différente?

On peut aussi poser la question différemment, est-il possible de trouver une telle famille <math>\(E\)</math> de segment tel que <math>\(card(E)=n\)</math>

J'ai déjà essayé avec 2,4,6,8 et 10 points ; ça ne fonctionne qu'à partir de 8points.Un petit exemple graphique avec 6 points :

On constate qu'on n'arrive pas à relier les points 3 et 6 avec un segment de taille différente des deux autres. (on peut essayer d'autre configuration, on n'y arrivera jamais).
La question est donc ouvert pour un n quelconque !

Quel est votre avis ?

Ton schéma est faux, puisque tes deux segments font la même taille là, ou j'ai pas compris. Dans ton exemple, Relis le 1 à un 6, le 2 à l'autre 6, et les 3 ensembles. Les segments ne font pas la même taille.

EDIT : ah non ok j'ai compris.

Hum... intéressant comme problème.

Déjà, quitte à effectuer une rotation tu peux effectivement considérer les racines 2n-iemes de l'unité.
Après, je ne sais pas si c'est si utile, mais on peut constater que si on arrive résoudre le problème pour n=k*p, on l'a résolu pour n=p (il suffit de retirer des points et remarquer que par un point, il ne passe exactement qu'un seul segment). Ainsi, il te suffit de montrer que le problème n'est pas soluble pour p premier.

Je ne sais pas si ça simplifie le problème, mais en général c'est cool les nombres premiers.

@schadocalex : oui tu as raison, mon schéma est faux, il fallait relier 1 à 2 et 3 à 3

Par rapport à ta remarque, sebsheep, je ne vois pas comment tu arrives à la conclusion que si c'est bon pour n=k*p, ça l'est pour n=p.

Oups... rien dit... j'enlevais les points qui étaient symétriquement opposés... La prochaine fois, j'attendrai d'être réveillé pour poster des âneries.

Intéressant en effet ! Il faut chercher n segments de « longueur » 1 à n, où par « longueur » j'entends nombre de points d'écart. (Selon cette définition, deux points contigus ont une longueur de 1 et deux points diamétralement opposés ont une longueur de n.)

Je ne sais pas exactement comment trouver la réponse pour un n quelconque, mais on peut remarquer qu'il faut un et un seul diamètre partageant le cercle en deux. De plus, je dirais qu'il faut éviter de mettre les autres segments de façon trop symétrique par rapport à ce diamètre, sinon on va se retrouver avec des segments de même taille…

J'y avait déjà réflechi et je suis tout à fait d'accord avec Me Capello ; de manière générale, il est vrai que quand on a trop de symétrie, le problème ne se résoud pas bien !

Là je suis en train d'essayer de l'implémenter informatiquement, pour l'essayer avec un nombre raisonnable de point et voir l'évolution en fonction de n

J'ai bien l'impression qu'il n'y a une solution que pour <math>\(2n \in \{2;8m;8m+2;m\in \mathbb{N^*}\}\)</math> (ce qui expliquerait que ça marche pour 8, 10, 16, 18 mais pas pour 6 ni 12). J'aurais même une stratégie pour ces configurations. Ça va dans votre sens ?

Ah tout à fait ! Je serais curieux de voir votre démarche !

C'est juste une piste, je n'ai pas réfléchi beaucoup sur le problème et je n'ai pas bien démontré proprement, mais voici des exemples de dispositions qui fonctionnent :

Pour 18 points :


Pour 50 points :


Ça vient en gros du fait que <math>\(n-1 \equiv \lfloor{\frac{n-1}{2}}\rfloor \mod 2 \Leftrightarrow n \equiv 0\mod 4 \text{ ou } n \equiv 1\mod 4\)</math>

Bon, je ne suis qu'en TS, c'est peut-être tout simplement faux

@Frapy : Merci de ta réponse, mais je crois que tu n'as pas compris mon problème ! En fait, je ne cherche pas à disposer les points de la bonne manière (ils sont en cercle, à distance régulière), mais juste à les relier par des segments de longueurs différentes !

Citation : Me Capello

Il faut chercher n segments de « longueur » 1 à n, où par « longueur » j'entends nombre de points d'écart. (Selon cette définition, deux points contigus ont une longueur de 1 et deux points diamétralement opposés ont une longueur de n.)

Donc on définit la « longueur » entre deux points comme étant le nombre de points situés entre ces deux points ajouté de 1 (deux points contigus sont donc séparés par une longueur de <math>\(0+1=1\)</math>, deux points opposés sont séparés par une distance de <math>\(\frac{2n-2}{2}+1=n\)</math>). Ainsi, peu importe que les points soient sur un cercle ou non : nous avons affaire à un graphe.
Peut-être aurais-je dû préciser que les nombres sur mes schémas doivent être lus comme ceci : deux points sont reliés par un segment si, et seulement si, ils possèdent le même nombre et sont distants d'une longueur égale à ce nombre.

Enfin, peut-être n'ai-je pas compris le problème ... Peux-tu alors me l'expliquer ?

Je n'avais pas vu que tes images étaient des gif ! À bien y regarder, je me rends compte qu'en effet tes deux solutions fonctionnent très bien ! Au temps pour moi (j'ai parlé trop vite, tu avais compris :p).

Citation : Frapy

Ça vient en gros du fait que <math>\(n-1 \equiv \lfloor{\frac{n-1}{2}}\rfloor \mod 2 \Leftrightarrow n \equiv 0\mod 4 \text{ ou } n \equiv 1\mod 4\)</math>

Par contre, je ne comprends pas en quoi ça peut servir dans notre problème

NB : ça m'interesserait de savoir comment tu as trouvé les répartitions

Ben, ça nous intéresse dans le sens ou, pour qu'il existe la famille de n segments, il faut que n = 4k ou que n = 4k + 1.

Citation : schadocalex

Ben, ça nous intéresse dans le sens ou, pour qu'il existe la famille de n segments, il faut que n = 4k ou que n = 4k + 1.

J'avais saisi ce point, mais comment montrer l'équivalence entre "Le problème a une solution" et "n=4k ou n=4k+1" ?

Il faut démontrer que toutes les solutions sont telles que n = 4k ou 4k+1. On a une conjecture qui semble juste, ça peut aider à la démonstration.

Pour trouver des solutions qui fonctionnent, c'est l'intuition ... J'ai testé quelques cas, et ça a eu l'air de marcher. Bon, de là je me suis intéressé à mes configurations : il y a deux "phases" pour former une configuration qui fonctionne : d'abord la phase notée en bleu sur mes schémas, puis la phase notée en rouge. À la fin de la première phase, il semble (conjecture) toujours rester un nombre pair de points dans la ligne du bas. Cela se traduit mathématiquement par :
<math>\(\lceil{\frac{n-1}{2}}\rceil \equiv 0 \mod 2 \Leftrightarrow n-1 \equiv \lfloor{\frac{n-1}{2}}\rfloor \mod 2 \Leftrightarrow n \equiv 0\mod 4 \text{ ou } n \equiv 1\mod 4\)</math>
D'où les solutions de la forme <math>\(8m\)</math> et <math>\(8m+2\)</math>.

Maintenant il reste à démontrer tout cela, c'est-à-dire qu'il faut montrer que :

• s'il reste un nombre pair de points dans la ligne du bas après la première phase (pas très clair, je sais), alors ma disposition des segments fonctionne.
• s'il reste un nombre impair de tels points après la première phase, alors on ne peut pas trouver de disposition de segments qui corresponde à l'énoncé.

Le premier point doit être relativement simple, le deuxième plus difficile.
Enfin, il y a surement une méthode plus propre et plus directe pour trouver le résultat. Ma méthode, c'est simplement du bidouillage

Intéressant comme approche, je vais voir si j'arrive à le montrer dans le premier cas.
En tout cas bonne analyse du problème, merci

J'ai peut-être une démonstration pour montrer que si un tel ensemble de segments existe, alors n doit être congru à 0 ou 1 modulo 4.
Vous êtes preneurs ?

Bien sûr.

Re-bonsoir tout le monde.
D'abord quelques notations:
- on numérote les points sur le cercle de 1 à 2n
- un segment est représenté par un couple (p,q), on lie le point d'affixe exp(i.pi.p/n) au point d'affixe exp(i.pi.q/n)
- p et q sont compris entre 1 et 2n

Avoir toutes les longueurs de segment c'est avoir tous les |p-q| qui décrivent tous les nombres de 1 à n.
Ensuite (p,q) et (q,p) représente le même segment, donc on peut supposer q>p.
Ainsi pour résumer le problème on cherche des couples (pk,qk) pour k allant de 1 à n vérifiant qk-pk=k (équation [*]).
Maintenant j'en viens à nos histoires de modulo 4 qui provient de la chose suivante :
En sommant toutes les équations [*] et en prenant le tout modulo 2, comme le corps à deux éléments à la super bonne propriété que +x c'est la même chose que -x, on a sum(qk-pk)=sum(qk+pk) mod 2.
Ainsi on a sum(qk-pk)=sum(k), avec bien évidemment k allant de 1 à n. En regardant droit dans les yeux cette égalité, on utilise un superbe résultat (démontré par Gauss en CE2 selon la légende) que sum(x, x=1->M)=M.(M+1)/2 et donc notre égalité modulo 2 devient :
sum(x, x=1->2N)=sum(k, k=1->N) mod 2

Au final on a n.(2n+1)=n.(n+1)/2 mod 2
Puis comme 2=0 mod 2 on obtient n=n.(n+1)/2 mod 2
Soit n.(n-1)=0 mod 4
Et donc coup de baguette magique n=0 ou n=1 mod 4

Voilà, il ne reste plus qu'à démontrer la réciproque, en exhibant par exemple une construction des segments.