|
#1 - 06-05-2011 19:17:09
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Echecs ett maths
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] Plutôt que de minimiser directement le score de chacun des nombres n à placer, essayez de voir comment on peut compter le nombre de fois où chaque nombre n est compté dans le score total. Ce nombre de fois est fonction des cases vides restantes dans les ligne et colonne de la case où on place n...
#2 - 07-05-2011 16:13:15
- luludu28
- Amateur de Prise2Tete
- Enigmes résolues : 45
- Messages : 6
Echecs et amths
Logique. Ne surtout pas chercher au hasard !
#3 - 07-05-2011 18:42:57
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
echecq et maths
Merci de ne pas donner d'indice , je cherche ce soir
Vasimolo
#4 - 07-05-2011 19:07:25
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Echesc et maths
Ton intérêt me confirme qu'il faudrait bien déplacer ce sujet côté maths
#5 - 07-05-2011 21:57:29
- halloduda
- Professionnel de Prise2Tete
- Enigmes résolues : 24
- Messages : 495
- Lieu: Ardèche
Echecs et math
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...)
#6 - 08-05-2011 08:44:10
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
rchecs et maths
J'ai obtenu 9377 qui n'est pas validé par la case réponse
Vasimolo
#7 - 08-05-2011 10:10:15
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
echecs et mathq
On peut effectivement faire mieux, mais tu n'es pas trop trop loin ;-)
#8 - 08-05-2011 11:01:07
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
zchecs et maths
J'ai trouvé 9184 !!!
Vasimolo
#9 - 08-05-2011 11:20:51
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Echecs et mths
Félicitations ! Vasimolo trouve le score optimal :-)
#10 - 08-05-2011 11:45:10
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Ececs et maths
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
#11 - 09-05-2011 13:35:47
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
Echecss et maths
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...
#12 - 09-05-2011 14:01:18
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Echces et maths
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...
#13 - 09-05-2011 16:31:30
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
exhecs et maths
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):
En tout cas merci. Cette énigme était fort intéressante.
#14 - 09-05-2011 16:39:07
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
cEhecs et maths
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
#15 - 12-05-2011 01:23:25
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
echecs er maths
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] Plutôt que de minimiser directement le score de chacun des nombres n à placer, essayez de voir comment on peut compter le nombre de fois où chaque nombre n est compté dans le score total. Ce nombre de fois est fonction des cases vides restantes dans les ligne et colonne de la case où on place n...
#16 - 12-05-2011 09:08:56
- Palin01
- Passionné de Prise2Tete
- Enigmes résolues : 39
- Messages : 70
- Lieu: Lille
echecs et mayhs
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.
#17 - 12-05-2011 09:29:56
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Ecchecs et maths
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.
#18 - 12-05-2011 11:25:09
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Echecs et matsh
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
#19 - 12-05-2011 11:54:36
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Echecs et mathhs
Bien joué scarta
#20 - 17-05-2011 01:27:38
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
echrcs et maths
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.
Mots clés des moteurs de recherche
|
|