Emmaenne me fait remarquer que le placement d'un point peut créer plusieurs alignements et qu'on peut donc se trouver dans une situation où l'on pourrait tracer un segment sans utiliser le point que l'on vient de placer . On peut considérer que c'est une variante du problème initial .

Avis aux amateurs

Vasimolo

autre question:

si on en mettant une croix on peut faire 2 lignes est on obligé de faire les 2 lignes ou alors mettre une croix au bout des 5 pour faire 6 et ne prendre que 5 croix alignées

XXXXOXXXX puis XXXXOXXXXX

le O est le premier coup le X le second

ou XXXXOXXXX

suis je clair?

En 5T le record est de 170, en 5D de 80.

kosmogol donne bien le maximum ( plutôt impressionnant !!! ) mais ma question était plus simple : comment montrer ( sans grosse artillerie ) qu'il existe bien un maximum .

La pratique nous laisse penser qu'il existe mais comment s'en assurer ?

Vasimolo

Vasimolo a écrit:

La pratique nous laisse penser qu'il existe mais comment s'en assurer ?

En programmant un algorithme heuristique en C++

pour trouver une "chaine" infini, il nous faudrait la possibilité de crée a la suite, des lignes
le plus petits, et donc le plus réalisable des schéma est un rectangle de propagation.

il faut donc que l'on crée assez de nouveau point pour progresser, or on remarque que l'on crée par zone:
5 demi segments utilisable au extrémité de la zone, et 8 a l'intérieur, soit
10+8n (en prenant n, la taille de l'intérieur de la zone)
or on a besoin de créer N+2 points, ce qui nous donne
(10+8n)/(n+2)  or il nous faudrait que ce chiffre soit supérieur a 8 (la quantité de demi segment par ligne) ce qui est impossible quelque soit la taille du rectangle.

on va donc finir par manquer de demi-segment pour tracer de nouvelle ligne.

CQFD.



on remarquera que pour des lignes de 4 points, on a pas ce soucis:
(10+8n)/(n+2)>=6 pour tout n, il existe donc certainement une progression infini


P.S. j'ai trop de mal a rédiger un truc convenable, j'espère juste que vous avez compris mon idée.

tu ne prends pas en compte le nombre de point sur le segment, ni la topologie, ce qui sous entends que ton raisonnement marche dans tout cas,

or pour 4points (3+1), il y a des solutions infini,
j'ai raté un truc?

Depuis 1976, le record était de 170 coups, et semblait imbattable.
Mais depuis le mois dernier (août 2010), le nouveau record mondial est passé à 172 coups.
Qui fera mieux ?

Voir www.morpionsolitaire.com !

Ce type de record m'étonnera toujours. Pourquoi un informaticien/mathematicien n'a pas fait un programme pour donner le maximum ?

Celui qui pourra décortiquer ce jeu et trouver soit la manière d'aller à l'infini, soit de donner la limite max, celui là deviendra cèlèbre.

@godisdead:

Ce type de record m'étonnera toujours. Pourquoi un informaticien/mathematicien n'a pas fait un programme pour donner le maximum ?

(je n'ai pas lu beaucoup de chose sur le site) mais tu veux dire que le record actuel n'a pas été obtenu par un informaticien mathématicien? Ça m'étonnerait beaucoup! Mais bon quoiqu'il en soit ça implique que peu de choix: soit les records successifs sont bien des records de programmeur chacun ajoutant une branche à l'heuristique utilisé pour atteindre une profondeur compétitive (et je penche pour cela çà ne me semble pas très dur), soit on a pas de bonne heuristique pour atteindre de telles profondeurs en temps correcte.

Et puis en fait en cliquant sur le lien PDF sur la frontpage on voit clairement que c'est bien un informaticien mathématicien :p et que le problème est réservé à cette communauté, le problème catégorisé NP-Hard est donc de mieux en mieux connu par amélioration des heuristiques et par augmentation de la puissance de calcul disponible.
Donc le gros titre "tentez votre chance pour battre le record mondial" est un magnifique mensonge, car il est très probable que si toute l'humanité y réfléchissait à la main pendant des milliers d'année on n'arrive que très loin des records actuels...