Inscription / Connexion Nouveau Sujet
pions sur un plateau
Bonjour à tous
Il y a quelques jours je me suis posé un problème dont je cherche la solution optimale
Je le formule comme une énigme, donc je le mets dans la catégorie Enigmes
On part d'un plateau de 11x11 cases dont on enlève le centre (le centre n'existe pas, ce n'est pas une case)
On met en évidence le carré de 9x9 centré à l'intérieur du plateau
Règle du jeu
On doit placer des pions sur les cases du carré 9x9. On a donc en tout 80 cases où on peut placer des pions
Une fois que c'est fait, chaque pion va (dans un ordre aléatoire) choisir une de ses 4 cases adjacentes qui sera sa "voisine", telles que :
a) la case n'est pas occupée par un autre pion
b) la case n'est pas déjà la voisine d'un autre pion
note : les pions sont situés sur le carré 9x9 mais ils ont le droit de choisir une case voisine qui sorte du carré 9x9
Le but est que chaque pion ait trouvé une case voisine
Le problème est donc de trouver des répartitions de pions au départ qui garantissent que chaque pion pourra choisir sa case voisine, et si possible trouver le plus grand nombre possible de pions au départ !
La clause b est un peu ambigue :
la case n'est pas déjà la voisine d'un autre pion.
Si il faut comprendre : la case n'est pas également voisine d'un autre pion, alors la solution de Zormuche semble optimale.
Si il faut comprendre : la case n'est pas déjà la case de destination sélectionnée pour un autre pion, alors la solution de LittleFox est certainement la bonne.
C'est la première version qu'il faut comprendre
On peut le voir comme ça, aussi ;
Chaque pion doit donner naissance à un bébé pion qui devra se placer sur une case vide parmi les 4 cases adjacentes
Le problème c'est qu'on ne sait pas quel pion donne naissance à un bébé en premier (l'ordre est aléatoire) et on ne sait pas non plus où est-ce que le bébé pion va se placer parmi les cases possibles (c'est aléatoire aussi)
La solution de Littlefox ne me convient pas car les pions au milieu ont de grandes chances de se retrouver avec aucune case disponible pour placer leur progéniture
Et je me suis rendu compte qu'on pouvait ajouter deux pions à ma solution : en e2 et e10 si on voit le plateau 11x11 comme un grand échiquier
Je sais que ce problème est bizarre et ne présente peut-être pas un grand intérêt mathématique, mais pour moi il représente quelque chose de très particulier dans un célèbre jeu
La solution de Littlefox ne me convient pas car les pions au milieu ont de grandes chances de se retrouver avec aucune case disponible pour placer leur progéniture
Non, il n'y a pas de problème. 56 est bien le maximum si on n'impose que les conditions a et b. Une autre disposition plus bordélique, mais où j'ai indiqué les dominos :
Cliquez pour afficher
GBZM dans la première solution proposée par LittleFox, il y avait bel et bien un problème. Peut-être alors que je me suis mal exprimé dans les conditions, tu ne peux pas choisir à l'avance quelle case adjacente chaque pion élira comme étant sa voisine, c'est aléatoire, et le but est que chaque pion puisse trouver une voisine, et ce quelles que soient les voisines qu'ont choisi les pions avant lui, en supposant tous les scénarios possibles
LittleFox ta deuxième solution me convient parfaitement, elle est meilleure que la mienne, je vais m'en inspirer désormais 
Tant qu'à faire, je m'en vais vous révéler ce qui m'a fait imaginer ce problème
Cliquez pour afficher
Bien formuler le problème est essentiel.
Je ne connais pas Minecraft, mais voici comment je comprends le problème.
C'est ce que j'imagine. Peut-être que le vrai problème est différent.
- On a une grille 11x11. La case centrale de cette grille est interdite.
- On doit disposer un nombre N de pions (les parents) dans le carré central 9x9. Le joueur choisit le nombre N de pions qu'il va placer, ainsi que là où il va placer ses pions.
- Quand les pions parents sont placés, un processus aléatoire va se dérouler.
Pour chaque pion-parent, le processus va choisir aléatoirement une des cases voisines, pas déjà occupée par un pion parent. Cette case sera notée case-enfant.
A la fin du processus aléatoire, on compte le nombre de case-enfant. Sans double-compte : si pour 2 pions-parents, le processus a choisi la même case enfant, cette case est comptée une seule fois.
On note N1 le nombre de cases-enfants.
Pour une certaine disposition initiale des N pions-parents, en général, on ne connaît donc pas avec certitude le nombre N1 qu'on va obtenir, mais on peut calculer l'espérance de N1. On va noter E1 cette espérance.
L'objectif du challenge, ce serait donc de maximiser cette espérance E1.
On voit très vite qu'avec la 1ère proposition de Zormuche, N1 sera toujours égal à 44 , et donc l'espérance E1 vaut aussi 44.
A l'opposé, avec la dernière proposition de GBZM, N1 peut varier entre ??? et 56. La probabilité d'obtenir 56 est très faible, mais non nulle !
Ce que je comprends finalement du problème :
Le Gentil pose des pions rouges sur le carré central de 9x9 cases auquel il manque la case du milieu.
Le Méchant pose des pions verts. Il a le droit de poser des pions verts dans une case voisine d'un pion rouge non coché, si elle est libre ; il coche alors le pion rouge choisi. Le Méchant gagne si, à un moment, il y a un pion rouge non coché dont toutes les cases voisines sont occupées.
Question : combien de pions rouges au maximum peut poser le Gentil en étant sûr que le Méchant ne pourra pas gagner ?
GBZM en effet, c'est une façon originale de le voir mais le problème est le même
ty59847 je pensais justement à une variante de ce problème où on n'impose plus que tous les pions donnent naissance à un enfant, mais que le maximum d'entre eux donnent naissance
à partir de la dernière solution proposée par Littleguy, où on était sûr que tous les pions parents donnaient naissance à un enfant, j'ai trouvé ces solutions qui me semblent meilleures si on veut simplement maximiser le nombre d'enfant
Cliquez pour afficher
dans mon contexte, ces deux solutions seraient donc meilleures, et je laisse en exercice au lecteur le calcul de l'espérance de N1
Les 2 grilles que tu proposes sont des 'variantes' de celles déjà proposées. 56 'dominos'.
Et c'est évident qu'il n'y a pas mieux que 56 dominos, dans cette variante du jeu.
Il y a 121 cases , moins la case centrale = 120.
Parmi les 3 cases (A1,A2,B1), il y a forcément au maximum une case utile, et donc 2 cases perdues, parce que ces 3 cases ne peuvent être 'ensemencées' que via la case B2.
Donc on peut considérer qu'on a 2 cases condamnées.
Idem aux 3 autres coins.
On a donc seulement 120 - 4*2=112 cases exploitables.
Toute disposition avec 56 dominos est donc optimale, vu que 56*2=112.
J'ai tout de même le sentiment que les premières grilles à "56 dominos" proposées (par GBZM et LittleFox) sont moins efficaces, on court beaucoup plus le risque que des pions parents au centre ne puissent pas donner naissance à un enfant
Tu parlais même d'espérance E1 du nombre de pions parents donnant naissance à un enfant, toutes les dispositions à 56 dominos ne se valent pas en terme d'espérance
Je pense que mes dernières propositions sont optimales sur ce point là, mais toute tentative de me prouver le contraire est fortement appréciée, surtout si elle porte ses fruits !
Donc tu valides l'énoncé que je donnais hier. L'objectif est de trouver une disposition qui maximise E1 ... avec les notations d'hier 13h52.
Annuler
connectez vous