Inscription / Connexion Nouveau Sujet
3 points non alignés
Bonjour à tous,
L'exercice proposé par derny sur les alignements m'a inspiré celui-ci:
Comment disposer 11 points ayant un repère orthonormal entier de façon à ne pas
avoir 3 points alignés ?
Et quel sera l'aire la plus petite les encadrant?
Exemple pour 6 points un carré de 4
>derny
Je note que ton minimum actuel pour 11 est un rectangle de 5x8 soit 40
J'avais 42 et maintenant 30 ,à suivre.
Comme tu as commencé à le faire pour 10 ,on peut chercher de 7 à 9 puis tenter 12.
Cliquez pour afficher
Je me sui inspirée de la figure de derny en séparant son point C en deux, et en écartant un peu d'autres points.
3 , 
bonjour à tous
merci dpi pour ce petit jeu sympa
(je vais le proposer à ma petite famille !)
Cliquez pour afficher
Bonjour à tous 
Ce problème n'est pas loin de rappeler celui des 8 dames sur un échiquier , d'ailleurs je me demande s'il n'aurait pas été plus judicieux de poser les pions dans les cases plutôt qu'aux nœuds du quadrillage . La grille 5X5 de Sylvieg fait plutôt penser à une grille 6X6 .
D'ailleurs le minimum est-il forcément réalisé avec la même configuration dans les deux cas ?
Imod
Une autre remarque : les meilleures grilles semblent toujours carrés . Une autre façon d'aborder de problème est d'essayer de placer un maximum de points dans un carré .
Imod
Je reprends les exemples de Dpi
1X1 -> 1
2X2 -> 4
3X3 -> 6
4X4 -> 8
5X5 ->10
Il est clairement impossible d'améliorer car chaque ligne ou colonne ne peut pas contenir plus de deux pions .
6X6 -> 11 ... on peut espérer un pion de plus mais je n'y crois pas .
Imod
J'aurais du y croire 
Dans une grille 6X6 on place 12 pions de la façon suivante : (1,4),(1,5),(2,2),(2,3),(3,1),(3,5),(4,3),(4,6),(5,1),(5,4),(6,2),(6,6) .
Imod
J'ai pas mal cherché aussi à passer de 11 à 12 points.
Sans succès, mais j'ai appris à repérer les alignements
>Imod
Je préfère les noeuds car le lignes verticales et horizontales sont déjà tracées...
Il ne reste que les angles de 45° et de tangente 1/2 et 1/3* à tracer pour éliminer les points impossibles.
>Sylvieg
Bravo
Je valide ton 12 avec 25
L'étape suivante devra au mieux se contenter de 30 ou de 36...
Perso...cela me rappelle le morpion :comment ne pas laisser l'adversaire aligner
3 pions 
*du moins pour les carrés inférieurs à 8
Je reviens sur la question initiale :
Comment disposer 11 points ayant un repère orthonormal entier de façon à ne pas
avoir 3 points alignés ?
Et quel sera l'aire la plus petite les encadrant?
comment démontrer que c'est le min ?
Si on ne dispose que de 5 lignes horizontales, chaque ligne ne peut pas contenir plus de 2 points ; on ne peut donc pas dépasser 10 points.
Idem avec verticales.
Autrement dit :
Il faut au moins 6 lignes horizontales et 6 lignes verticales pour ne pas avoir 3 des 11 points sur l'une d'elles.
Une généralisation :
Pour disposer 2n ou 2n-1 points à coordonnées entières de façon à ne pas avoir 3 points alignés, il faut au moins n lignes verticales et n lignes horizontales.
Donc pas d'aire inférieure à (n-1)2.
Ou 2n pions sur une grille nXn . Je n'insiste pas mais c'est clairement un jeu de plateau
Une façon amusante de chercher une solution maximale de 2n pions ( si elle existe ) : On place 2 pions sur chaque ligne et colonne de la grille ( il y a plein de façon de le faire ) . On considère deux pions qui ne sont pas sur la même ligne ni sur la même colonne , ils constituent les extrémités d'une diagonale d'un rectangle . Si les extrémités de la deuxième diagonales sont vides , on peut déplacer les pions sur cette diagonale sans perdre la propriété initiale et éliminer au passages quelques alignements obliques .
Ca pourrait presque être un jeu , supprimer tout alignement à partir d'une position donnée en désignant simplement les diagonales à échanger .
Imod
Nous avons gardé un carré de 5x5 pour placer 12 points (Sylvieg )
On remarque qu'il est "saturé" donc pour 13 points ,il faudra passer à 6x6
Je pense avoir 14 pions sur une grille 7X7 :
a4 , a7 , b1 , b3 , c6 , c7 , d3 , d5 , e1 , e2 , f2 , f6 , g4 , g5 .
Imod
Mais j'ai l'impression qu'il y en a 13 en supprimant c6.
C'est déjà pas mal ; je n'y étais pas arrivée
Oui , j'avais trouvé le même alignement en voulant illustrer . On peut en effet en trouver 13 en supprimant n'importe lequel des trois points incriminés .
Je n'ai pas renoncé au 14 mais ce n'est pas facile 
Imod
Un petit coup de pouce de l'ordinateur?
Voici mes solutions pour 2xn avec n de 2 à 8, généré par ce petit programme : 
Cliquez pour afficherIl ne cherche pas toutes les solutions, juste une. Pour n=9 ça devient lent
.
En changeant l'ordre de recherche, j'obtiens les solutions beaucoup plus rapidement.
Je mets deux pions dans la première colonne puis deux dans la suivante, etc au lieu d'en mettre un dans chaque colonne puis un deuxième dans chaque.
Certaines solutions sont différentes :
Cliquez pour afficher
Evidemment quand on commence à compter les solutions on fini par arriver sur l'oeis où quelqu'un a déjà été beaucoup plus loin :
Celà mène ici :
Par exemple voici toutes les solutions pour n=15: 
Je vais donner mon récapitulatif (14 ) "à la main".
Pour 13/14 j'ai transformé les pions de Imod en points pour rester sur les noeuds.
Au vu du travail de Littlefox et de l'OEIS ,je crois bien que c'est fini.
Bravo à tous.
Bonjour
Bravo à tous et surtout à LittleFox pour son programme. Je ne me suis pas trop investi mais, ne programmant qu'en Basic, je ne pense pas que j'aurais su programmer ce genre de problème. Ne comprenant pas ton programme, examine-t-il tous les alignements possibles ? Je pense que oui alors ton programme, mutatis mutandis, pourrait convenir pour résoudre la première question de la nouvelle énigme que je vais bientôt poser.
Il n'est pas très intelligent, il place les points comme je le ferais à la main: en mettant les pions un à un et en revenant en arrière s'il n'est plus possible de placer le pion courant.
La partie "intelligente" a été de créer un identifiant unique pour chaque ligne barrée (c'est l'équation d'une droite mais unique, avec des coefficients entiers et sans problèmes d'infini).
Logiquement, j'évite le maximum d'alignements en fait Donc, non, je ne les parcours pas tous.
Annuler
connectez vous