Sujet
On a placé dans l'ordre les nombres \(1,2, \ldots, N\) aux sommets d'un polygone régulier.
La notion de distance est prise dans le sens suivant :
Soient A et B deux sommets du polygone. La distance entre A et B est la longueur du plus petit arc de cercle qui joint A et B , l'unité étant la longueur de l'arc séparant deux sommets consécutifs.
Par exemple, pour \(N=12\), si A et B correspondent aux points marqués 3 et 5, la distance entre A et B est 2 . Si C et D correspondent aux points marqués 9 et 1 , la distance entre \(C\) et \(D\) est 4.
- Dans cette question, on suppose que le polygone a 12 sommets.
a) Montrer qu'il est possible de colorier quatre de ces points en vert de sorte que les distances entre chaque paire de points verts soient toutes différentes.
b) Expliquer pourquoi ce n'est pas possible avec cinq points. On pourra comparer le nombre de paires avec le nombre de distances possibles.
On désigne désormais par \(N\) le nombre de sommets du polygone régulier, \(N>12\).
2. Quelle est la valeur minimale de \(N\) pour laquelle les points marqués \(1,2,4,8,16\) peuvent être coloriés en vert de sorte que les distances entre chaque paire de points verts soient toutes différentes?
3. On suppose que 5 points sont coloriés en vert de sorte que les distances entre chaque paire de points verts soient toutes différentes.
a) Justifier que \(N \geqslant 20\).
b) Démontrer que si \(N\) est pair, la distance entre deux points marqués \(a\) et \(b\) est un entier de même parité que \(a-b\). En déduire que \(N\) est différent de 20 .
c) Quelle est la valeur minimale de \(N\) qui permet de colorier cinq points en vert de sorte que les distances entre chaque paire de points verts soient toutes différentes?
4. Montrer que pour \(N=2016\), on peut colorier au moins 11 points ayant la propriété habituelle.
- a) En coloriant en vert les points correspondant à \(1,2,4\) et 8 , toutes les distances sont différentes.
b) \(N=12\) donc il ne peut y avoir que 6 distances possibles entre des points distincts : les entiers de 1 à 6 . Lorsqu'on a 5 points, cela donne 10 paires possibles donc 10 distances. Nécessairement deux au moins d'entre elles sont égales. Il est donc impossible de colorier 5 points en vert de sorte que les distances entre chaque paire de points soient différentes. - Il est nécessaire que \(N \geqslant 16\). Les distances entre les paires de points sont alors \(1,2,4,8,3,6,12\) si \(N \geqslant 24\) ou \(N-12\) sinon, 7,14 si \(N \geqslant 28\) ou \(N-14\) sinon, 15 si \(N \geqslant 30\) ou \(N-15\) sinon.
Pour \(N=24\), toutes les distances sont différentes donc \(N \leqslant 24\).
Si \(N<24\), les distances sont \(1,2,3,4,6,7,8, N-12, N-14\) et \(N-15\). On doit donc avoir \(N-15 \geqslant 5\) donc \(N \geqslant 20\).
Pour \(N=20, N-12=8\) et il y a donc deux distances égales à 8 .
Pour \(N=21, N-14=7\) et il y a donc deux distances égales à 7 .
Pour \(N=22, N-15=7\) et il y a donc deux distances égales à 7 .
Pour \(N=23, N-15=8\) et il y a donc deux distances égales à 8 .
Finalement la plus petite valeur possible de \(N\) est donc 24 .
3. a) 5 points donnent 10 paires de points. Pour que les 10 distances soient différentes, il est donc nécessaire que \(N \geqslant 2 \times 10\) soit \(N \geqslant 20\).
b) La distance entre \(a\) et \(b\) est égale à \(|a-b|\) ou \(N-|a-b|\). Si \(N\) est pair, ces deux entiers ont la même parité que \(a-b\).
Avec 5 points coloriés, on a trois possibilités :
- Les 5 nombres ont la même parité. Les 10 distances sont alors paires.
- Parmi les 5 nombres, il y en a 4 d'une certaine parité et 1 de l'autre. Dans ce cas, parmi les 10 distances, 4 exactement sont impaires.
- Parmi les 5 nombres, il y en a 3 d'une certaine parité et 2 de l'autre. Dans ce cas, parmi les 10 distances, 6 exactement sont impaires.
Pour \(N=20\), les 10 distances différentes ne pourraient être que \(1,2,3,4,5,6,7,8,9,10\) et il y aurait donc exactement 5 distances impaires. C'est donc en contradiction avec les résultats précédents. Ainsi \(N \neq 20\).
c) La valeur minimale de \(N\) est 21 . En coloriant les points \(1,4,5,10\) et 12 , les distances sont \(3,1,5,2,4\), 6, 7, 9, 8 et 10. Elles sont toutes différentes.
- Pour \(N=2016\), en coloriant les points correspondant aux puissances de \(2(1,2,4,8,16,32,64,128,256\), \(512,1024)\) on obtient 11 points ayant la propriété souhaitée.