 |
#1 - 08-11-2018 10:00:04
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Ecarts tous différents entre entiers rrelatifs.
Bonjour @ tous.
Une fois n'est pas coutume, ce message s'adresse aux programmeurs, vu que, à la main, c'est un peu laborieux...
Trouver dans l'intervalle des entiers relatifs [C-, C+] le maximum m de nombres tels que les écarts absolus entre 2 quelconques d'entre eux sont tous distincts.
Comme on cherche par ailleurs à obtenir le max de l'expression C*m - s(m), s(m) étant la somme des valeurs absolues des nombres trouvés, Il y a tout intérêt à trouver les nombres le plus près possible de 0, dont évidemment 0 et 1.
On limitera C à 2000.
Merci d'avance à ceux qui veulent bien s'y intéresser.
Le problème sous jacent est celui-ci : Placer sur une grille C*C m pièces (imaginer un échiquier) telles que 4 d'entre eles ne forment jamais un rectangle de cotés parallèles à la grille.
#2 - 10-11-2018 14:00:56
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
ecarts tous difgérents entre entiers relatifs.
Bonjour nodgim,
1) Je n'arrive pas à voir le lien entre ta question et le problème sous jacent… 
2) On peut trouver une expression aussi grande que l'on veut (2*C-1) en prenant les valeurs 0 et 1, et en faisant croître C.
3) Pour C=2000, j'arrive à placer m=46 nombres, correspondant à 1035 écarts différents. L'expression à maximiser vaut alors 31078.
Je vais essayer d'améliorer…
#3 - 10-11-2018 16:39:15
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
ecarts tius différents entre entiers relatifs.
Bonjour Enigmatus,
Et merci de t'intéresser à ce problème pas simple du tout.
En relisant le texte du problème sous jacent, j'ai malencontreusement écrit " nombres " pour " pièces " ( sous entendu pièces d'un échiquier par exemple), la phrase ne voulait donc plus rien dire. Le placement de ces pièces, pour être conforme à la contrainte, en lignes en diagonale toutes espacées d'un écart différent, semble être ce qu'on peut faire de mieux.
Je suis très surpris par ta réponse : aucun nombre, en valeur absolue, en dessous de 31, alors qu'à la main, j'avais comme 1er éléments :
0,1, -2, 5 , -8, 15, -20.....
Cela dit, ça te permet sans doute d'en placer beaucoup plus, et peut être finalement d'y gagner. On dirait que ton algo démarre à 2000, au lieu de 0.
Tu as dû y trouver un avantage.
#4 - 10-11-2018 18:30:27
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
eczrts tous différents entre entiers relatifs.
Je n'ai toujours pas compris ton explication avec l'échiquier.
Avec C=2000, j'obtiens curieusement une valeur maximum de 54196 pour l'expression avec seulement m=38.
Édité :
Pour C=2000, on a au plus 4000 écarts différents. Il en résulte que m ne peut pas être supérieur à 89, correspondant à 3916 écarts différents.
#5 - 11-11-2018 15:03:09
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,996E+3
ecarts tous difdérents entre entiers relatifs.
Ce serait la règle optimale. Mais il a déjà fallu des années à des ordinateurs pour venir à bout de ce problème avec 27 termes < 600.
On peut normalement faire avec des formules simples une règle à n termes dans une fourchette de n^2 nombres, ce qui ferait 63 termes pour 4000.
Ce problème est NP-complet, en passant... voir règles de Golomb.
#6 - 11-11-2018 17:02:10
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
ecarts touq différents entre entiers relatifs.
Merci Enigmatus pour tes efforts, tu as bien amélioré ton premier score !
Merci à Gwen pour cette info, je ne connaissais pas.
Je reviens sur la question de l'échiquier, ou du damier avec des pions.
Contrainte: placer des pions de sorte que 4 quelconques d'entre eux ne forment jamais un rectangle ( cotés parallèles à ceux du damier).
L'une des solutions qui marche bien: on place les pions sur des lignes en escalier, toutes parallèles et à 45°. On se rend compte que s'il existe le même écart entre 2 couples de lignes, on transgresse la contrainte, et non dans le cas contraire. Les nombres négatifs et positifs reflétent leur position par rapport à la diagonale.
#7 - 12-11-2018 07:27:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
ecarts tous différents entre entierq relatifs.
@ Enigmatus :
Ton algo démarre t 'il au 0, le milieu, ou à une extrémité ( + ou - 2000 ) ?
Je reste étonné que la zone centrale reste aussi vide.
#8 - 12-11-2018 08:04:07
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
carts tous différents entre entiers relatifs.
nodgim a écrit:Ton algo démarre t 'il au 0, le milieu, ou à une extrémité ( + ou - 2000 ) ?
1) Les nombres sont pris dans l'intervalle [0,2*C]
2) On part de (0,1)
On aurait pu choisir l'intervalle [-C,+C], et démarrer avec (-C,-C+1)
3) On calcule la liste des écarts
4) On prend le 1er nombre qui n'est pas déjà un écart
5) On ajoute cet écart au dernier nombre choisi, et on vérifie que les écarts sont tous différents
- si oui, retour en 3)
- sinon, on élimine le dernier nombre et retour en 4)
Arrêt quand plus aucun nombre ne convient, ou que l'on dépasse 2*C
6) On décale tous les nombres pour qu'ils soient dans l'intervalle [-C,C], en minimisant l'expression 2*C-som(m)
Correction : suite à la remarque de nodgim en #9
#9 - 12-11-2018 10:48:21
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Ecarts tous différents entre etniers relatifs.
Dans ton algo, tu dois revenir en 3) si nombre OK.
Je me doutais bien un peu que tu travaillais en positif, et tu décales à la fin.
A la main, je faisais ainsi, à partir de 0,1 : je cherche le relatif le plus proche de 0 compatible avec l'écart permis, donc ici -2. Ensuite écart 4 disponible, le plus proche est coté +, donc +5.
C'est pour ça que la densité proche du 0 est plus forte que quand on s'en éloigne.
Cela dit, c'est peut être un peu compliqué à programmer ?
#10 - 12-11-2018 17:46:22
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Ecarts tous différents entre entieers relatifs.
Dans ton algo, tu dois revenir en 3) si nombre OK.
Merci ! C'est corrigé.
Édité :
En appliquant la méthode que tu indiques en #9, j'obtiens 40 valeurs, et l'expression vaut 58493
|
 |
Accueil
