Enigme [Géométrie / Combinatoire] trop de droites tuent les droites. @ Prise2Tete

lol37 · #1

Salut,
Soit p(n) le nombre MINIMAL de points du plan tel que pour TOUT entier k entre 1 et n il EXISTE une droite passant par EXACTEMENT k de ces points,
peut t'on déterminer une expression explicte de p(n) ?
il n'y a aucune erreur d'énoncé le problème est bien posé j'ai mis en gras et souligné les termes fondamentaux du problème car c'est de la qu'il s'y articule.

shadock · #2

Bonne question !

MthS-MlndN · #3

p(1)=1
p(2)=2
p(3)=4 (trois points alignés, un quatrième hors de la droite)
p(4)=6 (quatre points A, B, C, D alignés, un point E hors de cette droite, un point F sur la droite (AE))
p(5)=9 (on se base sur un alignement de cinq points et un alignement de quatre points, on les fait partager un point par souci d'économie, et il ne reste plus que le cas k=3 à traiter en ajoutant un point sur une droite quelconque)

Un début de construction, peut-être ? Bof : difficile à arrêter.

Je peux peut-être construire par récurrence, par contre. Si j'ai une telle disposition pour n points, je peux rajouter un point sur le plus grand alignement pour le faire passer à n+1 points, un point sur le deuxième plus grand alignement pour le faire passer à n points, etc. jusqu'à ajouter un point sur un alignement de 2 points pour le faire passer à 3 points. Je trouverai de toute façon une droite passant par 2 points et 2 seulement, à un ajustement près au pire, et idem pour une droite à un point. La suite p(n) est alors majorée par q(n) définie par

q(1)=1
q(2)=2
q(3)=4
q(n+1)=q(n)+n-2 pour n>=3

Ca doit nous faire du q(n)=n(n-1)/2-n+4 ? Je ne garantis rien, fatigue oblige...

As-tu une solution, ou est-ce un problème ouvert ?

kossi_tg · #4

Proposition
Par intuition rapide, je procéderais comme ci-dessous pour construire les points:
1-) n points alignés pour la droite k=n (direction d1),
2-) n-2 autres points alignés avec un point dans d1 pour la droite k=n-1 (direction d2),
3-) n-4 autres points alignés avec un point dans d1 et un point dans d2 pour la droite k=n-2 (direction d3),
...
...
m-) n-2*m points alignés avec un point des (m-1) précédentes directions où m=n/2 si n est pair ou m=(n+1)/2 si n est impair.

p(n) est la somme des points ainsi obtenus. Bref p(n) est la somme des m premiers entiers impairs si n est impair ou la somme des m premiers entiers pairs non nuls si n est pair.
[TeX]\[p(n) = \left\{
\begin{array}{l l}
\frac{(n+1)^2}{4} & \quad \text{si $n$ est impair} \\
\\
\frac{n(n+2)}{4} & \quad \text{si $n$ est pair}\\ \end{array} \right. \][/TeX]
Voilà, je ne garantis rien; j'attends les contre-exemples pour faire évoluer ma réflexion en conséquence

nodgim · #5

D'accord avec kossi-tg et voici une construction qui peut tenir lieu de preuve.
Pour n=7 par exemple, tracer 7 droites sécantes 2 à 2 (intersections de 2 droites exclusivement) numérorées de 1 à 7, le numéro correspondant au nombre de points.
Pour la droite 1, mettre le point à l'intersection de la d. 7
Pour la droite 2, mettre les 2 pts en inter 6 et 7
Pour la droite 3, mettre les 3 pts en 5,6,7.
Pour la droite 4, mettre 3 pts en 5,6,7, et un pt isolé.
Pour la droite 5, mettre 2 pts en 6,7. 2 autres pts existent déja, ajouter un pt isolé.
Pour la droite 6, mettre 1 pt en 7, 4 autres pts existent déja, ajouter un isolé.
Pour la droite 7, 6 pts existent déja, ajouter 1 isolé.

Généralisable à un nombre quelconque de droites.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 03-09-2013 14:30:23

[Géométie / Combinatoire] trop de droites tuent les droites.

#0 Pub

#2 - 24-09-2013 23:33:49

[Géométrie / Combinatoire] trop de droites tuen les droites.

#3 - 25-09-2013 00:48:19

[géométrie / comvinatoire] trop de droites tuent les droites.

#4 - 25-09-2013 01:22:27

[Géométrie / Combinatorie] trop de droites tuent les droites.

#5 - 25-09-2013 19:18:20

[Géométrie / Combinaoire] trop de droites tuent les droites.

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums