Les défis Mathématiques du monde,épisode 3
Bonjour
Et voilà
http://www.dailymotion.com/video/xyy7h2_les-defis-mathematiques-du-monde-episode-3-la-grille-de-sommes_news#.UWgEBaIoKpQ
Prière ne pas griller l'exercice
Et voilà
http://www.dailymotion.com/video/xyy7h2_les-defis-mathematiques-du-monde-episode-3-la-grille-de-sommes_news#.UWgEBaIoKpQ
Prière ne pas griller l'exercice
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Domi
S
@samok : J'ai du regarder deux fois et demi pour comprendre l'énoncé.
La vidéo n'est pas géniale pour comprendre: je trouve que ce n'est pas une super idée de faire semblant de se tromper une première fois dans les calculs, ça embrouille plutôt qu'autre chose.
Domi
Je n'ai pas compris : cette façon de remplir le carré,de gauche à droite et de haut en bas ?
Façon de remplir le carré?
Domi
$x_{\sigma(1)}=x_{\sigma(2)}=1$, puis pour $i$ entre $3$ et $9$:
$x_{\sigma(i)}=\sum_{j<i, \|\sigma(i)-\sigma(j)\|_{\infty}=1} x_{\sigma(j)}$.
Il faut maximiser $x_{\sigma(9)}$.
Aldo
61
Vérifié plusieurs fois! j'ai mis du temps.
Modulo le groupe du carré, il y a 8 positions initiales possibles.
Reste à tirer le meilleur total de chacune d'elles
Sans doute la meiileure position initiale n'est pas l'une des deux que l'animateur présente en exemples...;)
Ça paraît plus rigolo en prenant $a>0$ et $b>0$ comme premiers chiffres.
Amicalement.
[Edit: Mon raisonnement est FAUX!:-(]
Domi
Maintenant il faut que j'optimise mon programme car tester tous les cas c'est pas joli.
Joseph comment trouves tu 61 ?
En MP ?
calcm(L):={ local j,k,l,m,M; M:=[[0,0,0],[0,0,0],[0,0,0]]; M[iquo(L[0]-1,3),irem(L[0]-1,3)]:=1; M[iquo(L[1]-1,3),irem(L[1]-1,3)]:=1; m:=0; for(j:=2;j<=8;j++) { for(k:=max(0,iquo(L[j]-1,3)-1);k<=min(2,iquo(L[j]-1,3)+1);k++){ for(l:=max(0,irem(L[j]-1,3)-1);l<=min(2,irem(L[j]-1,3)+1);l++){ m:=m+M[k,l]; } } M[iquo(L[j]-1,3),irem(L[j]-1,3)]:=m; m:=0; } return M,M[iquo(L[8]-1,3),irem(L[8]-1,3)]; }Ce premier programme prend une liste des numéros des cases numérotées de gauche à droite et de haut en bas. Exemple calcm([1,2,3,4,5,6,7,8,9]) renvoie en sortie le premier exemple de la vidéo.Ensuite, le second programme se charge d'effectuer tous les cas selon ce qui exposé par Cedric Nicolas ci-dessus, c'est-à-dire qu'on a 8 initialisations différentes possibles (les autres étant symétriques), ensuite dans chaque cas sont effectués tous les cas possibles.
calcm2():={ local cas,k,M,mmax,Mmax,permumax,permu,bonpermu,init; mmax:=0; init:=[[1,2],[1,3],[1,9],[1,8],[1,5],[2,5],[4,6],[2,4]]; for(cas:=0;cas<=7;cas++){ k:=1; permu:=[0,1,2,3,4,5,6]; while (k<=7!) { bonpermu:=permu+[1,1,1,1,1,1,1]; if (is_element(init[cas][0],bonpermu)!=0) then bonpermu[is_element(init[cas][0],bonpermu)-1]:=8; end_if; if (is_element(init[cas][1],bonpermu)!=0) then bonpermu[is_element(init[cas][1],bonpermu)-1]:=9; end_if; M:=calcm(concat(init[cas],bonpermu)); if (M[1]>=mmax) then mmax:=M[1]; Mmax:=M[0]; permumax:=concat(init[cas],bonpermu); end_if; permu:=nextperm(permu); k++; } } return Mmax,permumax; }Après une minute de calcul (selon les performances de votre PC), le résultat s'affiche.Je pense à la résolution du problème des quatre couleurs.Les calculatrices ne sont pas autorisées.Sérieusement est ce une démonstration?
@Baggins : pourrais-tu nous dire de combien de façons différentes on obtient 57 ?
C'est qu'une proposition de ma part, j'ai peux-être faux.
from itertools import * def somme(p,a,b): l=[0]*10 l[p[0]],l[p[1]]=a,b for j in range(2,9): if p[j]==1: l[1]=l[2]+l[4]+l[5] elif p[j]==2: l[2]=l[1]+l[3]+l[4]+l[5]+l[6] elif p[j]==3: l[3]=l[2]+l[5]+l[6] elif p[j]==4: l[4]=l[1]+l[2]+l[5]+l[7]+l[8] elif p[j]==5: l[5]=l[1]+l[2]+l[3]+l[4]+l[6]+l[7]+l[8]+l[9] elif p[j]==6: l[6]=l[2]+l[3]+l[5]+l[8]+l[9] elif p[j]==7: l[7]=l[4]+l[5]+l[8] elif p[j]==8: l[8]=l[4]+l[5]+l[6]+l[7]+l[9] elif p[j]==9: l[9]=l[5]+l[6]+l[8] return(l[1:10]) def test(a,b): lp=permutations(range(1,10)) M=0 for p in lp: l=somme(p,a,b) if max(l)>M: M=max(l) pmax=p lmax=l print(M,pmax,lmax)La première fonction prend comme arguments une permutation de (1,2,3,4,5,6,7,8,9) qui correspond à l'ordre dans lequel on remplit le carré (les cases étant numérotées en commençant par celle en haut à gauche) et les valeurs a et b qu'on met dans les premières cases. Elle renvoie la liste des nombres obtenus.
La deuxième fonction teste toutes les permutations possibles et renvoie le plus grand nombre obtenu, la permutation correspondante et la liste des nombres obtenus dans le carré :
Je trouve également 16 permutations maximales.
En revoyant la vidéo on a l'impression que c'est le dernier résultat qui compte, mais au final cela ne change rien (bien qu'il y ait des grilles pour lesquelles le plus grand nombre n'est pas le dernier nombre calculé).
S
Cela dit je serais curieux de voir une preuve non informatique simple du problème.
Voilà qui est bien dit,une preuve non informatique ça n'a pas de sens,une preuve tout court oui.;)
Cordialement
S
Perso, j'avais pas fait mieux que 55, blocage psychologique ?
AitJoseph est-il prêt à envoyer sa grille de 61 à quelqu'un par MP pour vérification ?
La recherche systématique à l'aide d'un ordinateur est un bon exercice, mais ça ne correspond pas à l'esprit des défis du Monde, à moins que Gilles Cohen n'ait l'intention d'évoquer l'avènement des ordis en tant qu'outil d'investigation (fin du XXe siècle)
Sinon, comment prouver qu'on a obtenu à la main, le score optimal ? Sans votre participation, je serais resté convaincu que c'est 55...
Amicales salutations à tous. jacquot
Résultat de Test(1,x), x de 0 à 9 du programme de Juge Ti modifié avec la formalisation d'aléa :
S
Domi
vu que l'ordre de remplissage est important, comment pourriez-vous me convaincre que l'on peut égaler le score maximum en dernier ?
S
Domi
je suis convaincu. C'est une histoire de dés non transitifs qui m'a fait douter.
[size=x-small]pourtant une parcelle de moi même pense que c'est faux, quelle est-elle ?[/size]
S
Pour moi l'outil informatique est un assistant, de la même façon qu'une feuille et un crayon l'est. Cependant, dans ce problème, si on fait faire à l'ordinateur le calcul de toutes les combinaisons, c'est certe plus rapide que de tout faire à la main, mais c'est complétement inintéressant du point de vue mathématiques. C'est là qu'intervient selon moi les mathématiques : l'optimisation. Dans un premier temps on dégage 8 cas d'initialisations différents à symétrie près ce qui réduit déjà considérablement le temps de calcul (divisé par 9 dans mon cas par rapport au calcul bourrin qui consiste à tester toutes les grilles).
Après il est certainement possible de chercher une autre optimisation (par exemple écarter des configurations par paquets, on devrait finir par arriver à un nombre raisonnable de configurations restantes dont on pourrait tirer la solution au problème).
Mais pour ça il y a certainement des personnes bien plus compétentes que moi à qui je laisse le soin de résoudre le problème joliment.
Ce qui montre bien qu'avec un peu de méthode dans le remplissage on arrivait assez vite à ce résultat.
De là à en tirer une démonstration rigoureuse, c'est une autre histoire, mais on peut néanmoins bien déblayer le terrain avec les remarques suivantes :
- il faut essayer de finir sur une case qui en touche beaucoup, or si on termine par la case centrale, le chemin obtenu pour y parvenir est très pauvre car toute nouvelle case remplie touche au plus 2 cases déjà remplies, donc il faut plutôt essayer de finir sur une case d'arête
- en testant différentes positions pour les deux premiers 1, on peut assez vite éliminer les configurations qui séparent le carré en deux zones, car chaque zone va travailler séparément, ce qui n'est pas rentable. Au final les seuls candidats sérieux sont
1 1 x,
x x x,
x x x
et
1 x 1,
x x x,
x x x
avec une préférence pour le deuxième car dans la première, si on commence à remplir en haut à droite, on ne peut mettre qu'un 1, et si on ne commence pas par cette case alors la case sera isolée dans le remplissage donc inutile
- il faut remplir par un chemin connexe pour des raisons évidentes
à partir de là on teste différentes approches et on tombe assez vite sur le chemin à 57.
voilà, comme un peu, j'ai trouvé 57, et j'ai une "pseudo-démo" qui me permet d'éliminer un bon nombre de cas, avant de faire les cas restants.
Tout d'abord, pour rebondir sur ce qu'à dit lalalo : - il faut essayer de finir sur une case qui en touche beaucoup, or si on termine par la case centrale, le chemin obtenu pour y parvenir est très pauvre car toute nouvelle case remplie touche au plus 2 cases déjà remplies, donc il faut plutôt essayer de finir sur une case d'arête
Je suis pour ma part en désacord complet avec cela, je l'expliquerai par la suite.
Alors, pour placer les 1, on sait qu'il y a 8 possibilités (j'élimine les symétries), dont 4 ou les 1 se touchent :
et 4 ou les 1 se touchent pas.
J'ai alors mis en place l'idée de cases voisines, que j'explique par cette façon :
en rouge, la case que j'ajoute, et en bleu, les cases voisines.
et bizarrement, (je n'ai aucune façon de l'expliquer, et toute la démonstration doit résider dans le fait qu'il faudrait arriver à l'expliquer; je l'ai fait sur beaucoup d'essai, ça marche, si c'est faux, merci de m'en donner un contre exemple), si les 1 se touchent ( comme dans l'exemple), on a 19 cases voisines en tout, et si les 1 ne se touchent pas, on a 20 cases voisines (je vous laisse essayer)
Il parait donc logique que plus on a de voisin, plus on est gros, donc il faudrait que les 1 ne se touchent pas, mais on va le montrer autrement.
on différencie alors 3 sortes de cases :
la case du centre : 8 voisins
les milieux d'arrête : 5 voisins
les coins : 3 voisins
soit les 9 chiffres qui se trouvent dans le carré : 1 ; 1 ; a ; b ; c ; d ; e ; f ; g (dans l'ordre que je les ajoute, le g étant alors le max.
mon désacord avec lalalo étant que comme le g n'intervient pas dans les voisins, il me parait logique que le chiffre final se trouve dans un coin. En effet, comme il n'intervient plus, autant qu'il intervienne sur le moins de case possible. Bien sur, il arrive dans certains cas ( et le ou on arrive au max) où l'inversion du f et g ne change rien.
maintenant, pour choisir l'emplacement des 1, il me parrait logique que les 1 doivent intervenir le moins possible dans les 19 ou 20 voisins ! donc mettre les 1 dans les coins permet de les faire intervenir très peu.
Il nous reste donc 2 départ possible
si on met les 1 dans les diagonales, on a deux possibilités,
soit a vaut 1 et donc on stagne
soit a vaut 2, mais il faut le mettre au centre. si on le met au centre, on se rend alors qu'on ne décolle pas, puisque comme la case centrale a 8 voisins (6 sans les 1), il faut la maximiser.
C'est pourquoi j'en arrive a la conclusion que les 1 doivent se trouver dans deux sommets consécutifs.
parmi les 20 voisins, on a alors les 1 qui possèdent 6 voisins, il reste donc alors 14 voisins parmi les a,b,c,d,e,f,g.
Toujours dans la même idée, si on veut maximiser, il faut éviter que a vale 1, donc pour que a vale 2, il y a 2 possibilités :
soit au centre, il aura 6 voisins
soit entre les 1. il aura 3 voisins
donc comme le 2 reste un petit chiffre, il vaut mieux qu'il se trouve entre les 1.
jen suis donc arrivé à cette première conclusion, le max sera dans ce carré :
plaçons le chiffre b : 3 possibilités :
- le centre (P2), mais il aura bcp de voisins alors qu'il sera petit. donc pas possible
- P1
-P3.
il est logique qu'il faille le mettre en P1 car en P3, il interviendrait alors dans le chiffre final, alors que c'est un petit chiffre
Je ne continue pas, étant donné que je pense que tout le monde a compris, et que je ne vais pas mettre la grille finale.
Bien sur, ça ne présente pas une démonstration mathématique mais un moyen d'avancer et de pouvoir se dire que l'on possède probablement le max.
Si je n'ai pas été assez clair à un instant, merci de me le dire, j'essaierai de réexpliquer
Enfin, ceci reste mon humble avis.
Domi
- On numérote les cases de la grille de gauche à droite en allant vers le bas:
1 2 3
4 5 6
7 8 9
et notons (Ui),i=1,.....,9, les termes de la grille maximale en suivant la règle de remplissage,et soit s la permutation de {1,2,....,9},qui décrit l'ordre de remplissage,à l'étape i:la grille s(i) est remplie par Us(i)
.
Posons Vi=Us(i)
On peut poser V1=V2=1
V3= aV1+bV2; a et b valent 0 ou 1
V4=cV1+dV2+eV3 ; c,d et f=0 ou 1 ; suivant que l'élément figure dans la somme ou non
Et ainsi de suite ....
On peut se demander s'il est possible de faire mieux dans certains cas, par exemple si a est beaucoup plus grand que b, il suffirait d'obtenir 34 a, quitte à sacrifier ce qui vient de b.
On peut donc raisonner avec un seul nombre au départ. Il faudra bien sûr ne remplir que 8 des 9 cases (en effet, il faut bien laisser 1 case libre pour b).
Une analyse exhaustive devient assez facile. On s’aperçoit rapidement qu’il est impossible de dépasser 33a.
Mais si l’on cherche une démo excluant ce type d’analyse, même ce simple résultat n’est pas du tout évident à démontrer : avec un seul 1 au départ, et en n’utilisant que 8 des 9 cases, montrer qu’on ne peut pas dépasser 33.
A noter que le jeu à un seul 1 de départ et n’utilisant que 8 des 9 cases est identique au jeu initialement prévu sur 9 cases dans le cas où les deux 1 de départ se touchent. Par contre les positions de départ dans lesquelles les deux 1 ne se touchent pas n’appartiennent pas à cette catégorie.
Alors, existe-t-il un raisonnement qui permette d’éviter l’étude de tous les cas possibles ?
On peut aussi se demander s’il n’y a pas moyen de raccourcir la recherche systématique. Dans le problème initial, on peut énormément simplifier en distinguant le moment auquel on remplit la case centrale. En effet, une fois la case centrale remplie, il n’y a plus vraiment de suspense.
Bon, rien de plus pour l’instant…
Aldo