Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

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

lol37
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 68

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

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.

  • |
  • Répondre

#0 Pub

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

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

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

Bonne question !


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

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

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

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

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 ?


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

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

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

[géométrie / combinatoire] trop de droites tueny les droites.

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 smile

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

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

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.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete