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 - 08-11-2018 10:00:04

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

Ecarts tous différents entre entiers reltaifs.

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.

  • |
  • Répondre

#0 Pub

 #2 - 10-11-2018 14:00:56

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

ecarts tius différents entre entiers relatifs.

Bonjour nodgim,

1) Je n'arrive pas à voir le lien entre ta question et le problème sous jacent… sad

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.

Code:

-2000 -1799 -1593 -1356 -1157  -927  -782  -512
 -381  -256   -31   102   177   426   475   603
  686   839   982  1028  1082  1176  1223  1336
 1405  1433  1523  1597  1637  1708  1746  1794
 1816  1850  1875  1901  1917  1932  1953  1967
 1977  1985  1990  1994  1996  1997

Je vais essayer d'améliorer…

 #3 - 10-11-2018 16:39:15

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

Ecarts tous difféernts 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

Ecarts tous différents entre entiers relatifs

Je n'ai toujours pas compris ton explication avec l'échiquier. sad

Avec C=2000, j'obtiens curieusement une valeur maximum de 54196 pour l'expression avec seulement m=38.

Code:

 -400  -399  -397  -393  -388  -380  -370  -356
 -335  -320  -304  -278  -253  -219  -197  -149
 -111   -40     0    74   164   192   261   374
  421   515   569   615   758   911   994  1122
 1171  1420  1495  1628  1853  1978

É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,973E+3

Ecarts tous différents entre entiers reatifs.

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 tous différents entre entiers relatis.

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

ecartq tous différents entre entiers 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

Ecarts tous différents entre entiers realtifs.

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 entiers relatifd.

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 entiers rekatifs.

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

Code:

-1820 -1553 -1426 -1309 -1066  -846  -771  -588
 -489  -427  -329  -247  -192  -126   -89   -78
  -40   -18    -6     0     2     3     7    17
   33    61   107   148   184   272   324   440
  558   692   824   892  1107  1296  1452  1668
 

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 : Riri, Fifi et ?

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