Enigme Echecs et maths @ Prise2Tete

L00ping007 · #1

Je pourrais placer ce problème dans la partie mathématique, mais le mode opératoire de résolution est plutôt logique, donc ...

On place les entiers de 1 à 64 sur les cases d'un échiquier.
On les place l'un après l'autre sur l'échiquier, mais pas forcément dans l'ordre croissant. Chaque entier est évidemment à placer sur les cases encore vides au moment de le placer.

Pour chaque nombre n que l'on place sur une case, on calcule la somme S(n) des termes déjà placés avant lui dans la rangée et dans la colonne correspondantes.

Une fois que les 64 entiers sont placés, on additionne les 64 sommes S(n), ce qui donne la somme S.

La question est :
Quel ordre de placement des entiers doit-on adopter de manière à rendre la somme S minimale ? Et que vaut S dans ce cas ?

La case réponse valide la somme S minimale.

Indice 1 : Spoiler : [Afficher le message]

luludu28 · #2

Logique.
Ne surtout pas chercher au hasard !

Vasimolo · #3

Merci de ne pas donner d'indice , je cherche ce soir

Vasimolo

L00ping007 · #4

Ton intérêt me confirme qu'il faudrait bien déplacer ce sujet côté maths

halloduda · #5

Je place les entiers successivement, dans l'ordre croissant 1, 2, 3, ..., 64.

Pour chacun, j'essaie de placer plutôt les plus petits d'abord, car les 8 premiers seront comptés 14 fois, les 8 suivants 12 fois, etc... les 8 derniers pas du tout.

Je remplis donc d'abord une diagonale x-y=0, avec les nombres 1 à 8.
Chaque ligne/colonne a un élément non vide.
Puis une deuxième, x-y=1 modulo 8, (diagonale "étendue") avec 9 à 16.
Chaque ligne/colonne a 2 éléments non vides.
Puis une troisième x-y=2 modulo 8, avec 17 à 24

Et ainsi de suite...

Je trouve bien 9184 maintenant.
c'est 56x57+48x49+40x41+32x33+24x25+16x17+8x9.
(la somme de l'ensemble des nombres 1 à 8 comptés 14 fois + les nombres 9 à 16 comptés 12 fois + les nombres 17 à 24 comptés 10 fois + etc...)

Vasimolo · #6

J'ai obtenu 9377 qui n'est pas validé par la case réponse

Vasimolo

L00ping007 · #7

On peut effectivement faire mieux, mais tu n'es pas trop trop loin ;-)

Vasimolo · #8

J'ai trouvé 9184 !!!

Vasimolo

L00ping007 · #9

Félicitations ! Vasimolo trouve le score optimal :-)

Vasimolo · #10

On commence par les plus petites valeurs dans les lignes et les colonnes ayant le plus "d'ouvertures" .

Il est clair qu'on ne peut pas faire mieux !

Amusant

Vasimolo

rivas · #11

Bonjour,

Intéressante et pas facile à mon goût.
J'en suis pour le moment à 9409 mais apparemment on peut faire mieux.
Je continue de chercher...

L00ping007 · #12

Tu peux effectivement améliorer

Pour les autres, vous pouvez essayer de vous entraîner sur une grille de 16 cases, 4x4, pour obtenir un score optimal de 248...

rivas · #13

Ca y est, j'ai trouvé: 9184
Au début j'ai essayé de ne pas avoir trop de nombres apparaissant souvent surtout au début, mais c'est une erreur.
Ca ressemble beaucoup a une optimisation de surface pour laquelle la meilleure solution est la plus régulière.
En répartissant les nombres de façon à ce que 8 d'entre eux apparaissent 14 fois dans la somme (sur une diagonale), puis 8 d'entre eux apparaissent 12 fois dans la somme (l'autre diagonale), puis 8 d'entre eux appaissent 10 fois dans la somme, puis 8, 8 fois, ... on trouve cette solution optimale.
Il n'est pas étonnant non plus que la solution soit symétrique.
Ni que chaque ligne et chaque colonne comprenne un nombre de chaque.

La grille ressemble à ca (grille d'occurences, il suffit ensuite de remplir en commençant par les chiffres les plus petits pour les occurences les plus grandes):

Code:

12 10  8  6  4  0  8 14
10 12  6  2  0  4 14  8
 2  6 12 10  8 14  4  0
 6  2 10 12 14  8  0  4
 4  0  8 14 12 10  2  6
 0  4 14  8 10 12  6  2
 8 14  4  0  2  6 12 10
14  8  0  4  6  8 10 12

En tout cas merci. Cette énigme était fort intéressante.

L00ping007 · #14

Bravo rivas qui trouve aussi l'optimum !

Avec une méthode de remplissage encore différente de la mienne ou de celle de Vasimolo, apparemment

L00ping007 · #15

Je ne sais pas si certains cherchent encore, mais si c'est le cas, un petit indice pour aider dans le raisonnement.

Indice 1 : Spoiler : [Afficher le message]

Palin01 · #16

Pour te conforter dans ton idée que certains cherchent encore : j'en fais parti.
J'ai bien trouvé le minimum pour le 4*4 avec mon idée de départ mais pour le 8*8 j'ai trouvé S = 9290 ce qui ne valide pas.

L00ping007 · #17

Une petite centaine de points en moins encore, et tu auras le minimum !
N'hésitez pas a me poser des questions, MP, car c'est vrai que ce problème n'est pas facile.

scarta · #18

L'idée est de faire en sorte que les plus grands nombres soient les derniers de leur ligne et de leur colonne pour n'être jamais comptés, les suivants un minimum de fois, etc...

On place tous les nombres dans l'ordre sur l'échiquier, de la manière suivante :
- de 1 à 8 sur la diagonale
- chaque nombre n restant sur la case à droite de celle de (n-8), ou la première case libre de la même ligne en partant de la droite s'il n'y a pas de case à gauche.

Le total vaut alors :
14 * (8*9/2) => chaque nombre de 1 à 8 est compté 14 fois (autant de fois que les nombres de cases vide sur leurs lignes/colonnes)
+ 12 * (16*17/2 - 8*9/2) => Pareil pour les nombres de 9 à 16
+ 10 * (24*25/2 - 16*17/2)
+ 8 * (32*33/2 - 24*25/2)
+ 6 * (40*41/2 - 32*33/2)
+ 4 * (48*49/2 - 40*41/2)
+ 2 * (56*57/2 - 48*49/2)
Total : 56*57 + 48*49 + 40*41 + 32*33 + 24*25 + 16*17 + 8*9 = 9184

L00ping007 · #19

Bien joué scarta

L00ping007 · #20

Bravo à vous 3 pour avoir trouvé le minimum ! Je vais juste préciser le mode opératoire, même si les démos proposées sont équivalentes.

Quand on place un nombre n sur une case de la ligne i et la colonne j, le nombre de fois où il sera compté en tout dans le score total correspond au nombre de cases vides des ligne i et colonne j. En effet, on viendra placer un nombre dans chacune de ces cases vides, et on comptera à chaque fois le nombre n.

On va donc essayer de remplir en priorité les cases avec le maximum de cases encore vides dans les ligne et colonne correspondantes.
Il est également évident qu'il vaut mieux placer les nombres dans l'ordre croissant, car les premiers nombres seront comptés plus de fois (il y aura de moins en moins de cases vides)

Une manière de procéder ainsi est représentée dans la grille suivante :

Les nombres de 1 à 8 seront comptés 7+7=14 fois
Les nombres de 9 à 16 seront comptés 6+6=12 fois
Les nombres de 17 à 24 seront comptés 5+5=10 fois
Les nombres de 25 à 32 seront comptés 4+4=8 fois
Les nombres de 33 à 40 seront comptés 3+3=6 fois
Les nombres de 41 à 48 seront comptés 2+2=4 fois
Les nombres de 49 à 56 seront comptés 1+1=2 fois
Les nombres de 57 à 64 ne seront pas comptés

Ce qui fait un total de 9184 comme l'a bien détaillé scarta.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 06-05-2011 19:17:09

Echecs ett maths

#0 Pub

#2 - 07-05-2011 16:13:15

Echcs et maths

#3 - 07-05-2011 18:42:57

echecs et matjs

#4 - 07-05-2011 19:07:25

echecs et mzths

#5 - 07-05-2011 21:57:29

evhecs et maths

#6 - 08-05-2011 08:44:10

checs et maths

#7 - 08-05-2011 10:10:15

Echecs e tmaths

#8 - 08-05-2011 11:01:07

Echecs ett maths

#9 - 08-05-2011 11:20:51

Echces et maths

#10 - 08-05-2011 11:45:10

echevs et maths

#11 - 09-05-2011 13:35:47

rchecs et maths

#12 - 09-05-2011 14:01:18

exhecs et maths

#13 - 09-05-2011 16:31:30

Echecs et mathhs

Code:

#14 - 09-05-2011 16:39:07

Ecehcs et maths

#15 - 12-05-2011 01:23:25

echecd et maths

#16 - 12-05-2011 09:08:56

checs et maths

#17 - 12-05-2011 09:29:56

Echecs et mahs

#18 - 12-05-2011 11:25:09

Echesc et maths

#19 - 12-05-2011 11:54:36

echecs et mathq

#20 - 17-05-2011 01:27:38

Echecs et mmaths

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums