Bonjour
je crois que j'ai la bonne réponse.
Le nombre maximum des setons renversés est 56 jetons.

CHOUKRANE!

Lotfi

Bonjour, je ne suis pas sûr mais je dirait 53 (cf le schéma).

Merci pour l'énigme ^^

Je ne suis pas arrivé à conserver moins de 24 jetons blancs, donc à retourner plus de 57 jetons.
Il est facile de montrer qu'il faut au moins 20 jetons blancs : au moins deux par ligne et 3 sur les lignes correspondant aux jetons blancs sur les colonnes extrèmes. Mais est-ce bien 24 le minimum?...

Bonjour,

Aller, je me jette à l'eau en espérant ne pas croiser de poisson.

Je propose : il est possible de retourner jusqu'à 55 pions.

Merci pour cette énigme.

Ma solution est 56 jetons.
Je serai intéressé par savoir comment les autres ont trouvé la solution ... Ca m'a semblé pas du tout évident : ca méritait en tout cas plus que 3 étoile je pense (4)

Le nombre maximal de jetons à retourner pour qu'il n'y ait aucun alignement de 4 jetons noirs sur des cases consécutives, en ligne, en colonne ou en diagonale est égal à 56.
On remarque une symétrie par rapport au point central.

Oups !
je viens de me rendre compte que j'avais oublié de poster une des solutions pour 56 jetons retournés. En voilà une (N signifie que le jeton a été retourné, B signifie que ne l'a pas été) :

B N N N B N N N B
N N B N N N B N N
N B N B N N N B N
N N N B N B B N N
B N N N B N N N B
N N B B N B N N N
N B N N N B N B N
N N B N N N B N N
B N N N B N N N B

Bonjour,

juste avant de passer à table...
pas moins que 26 blancs pour moi soit un maximum de jetons à retourner.

Merci pour l'énigme.

allez en vitesse une petite figure...

Bonjour,

Je n'ai pas trouvé mieux que 53 jetons.

A+ et bon week-end,
gloubi

bonjour,

je ne sais pas si ma solution est "optimale", mais elle l'est par rapport a tout ce que j'ai pu trouvé!

Je réponds donc que le nombre maximal de jetons que l'on peut retourner de telle façon qu'il n'y ait aucun alignement de 4 jetons noirs sur des cases consécutives, en ligne, en colonne ou en diagonale est 52.

Voir schéma ci dessous:

Bonjour
Je sais que seul la première réponse est compté mais bon ma réponse est 49 jetons.

Choukrane

Bonjour
Je suppose qu'il s'agit de toutes les diagonales et pas seulement de la grande diagonale principale + de la grande diagonale secondaire
Dans ce cas je n'ai pas trouvé mieux que 30 Blanches  donc   Noires
c'est un peu désordonné mais soit
A+

Salut à tous,

je n'ai pas réussi à trouver plus de 51 jetons noirs.



@+

Bonsoir !

On peut retourner au maximum 56 jetons (=81-25)

Au final la grille de "reversi" ressemblera à cette figure:



A++

Bonsoir Minkus

J'ai trouvé 53 jetons :

N N N B N N N B N
N N B N N N B N N
N N N B N N N B N
B B N B B B N B  B
N N N B N N N B N
N N B N N N B N N
N N N B N N N B N
B B N B B B N B  B
N N N B N N N B N

En espérant que ce soit le maximum...

Merci pour le défi
Moomin

Je pense que l'on peut retourner au maximum 55 jetons
disposition possible :
NNN N NNN
NNN N NNN
NN NNN NN
  NN NN
N N N N N
  NN NN
NN NNN NN
NNN N NNN
NNN N NNN

N= piont retouné face noire apparante

Aprés plusieurs tentatives, le meilleur score que j ai pu obtenir est 55 pions. Cependant, je ne suis pas sur que le résultat soit optimum (mais je ne pense pas etre trop loin de la reponse correcte).

J'obtiens ce score pour la configuration suivante, par exemple:
NBNNNBNNN
BNNNBNNNB
NBBNNBBNN
NNNBNBNBN
NBNNNBNNN
BNBBBNNNB
NNBNNBBNN
NNNBNNNBN
NBNNNBNNN

merci pour cette énigme.

Bonjour,

La reponse que j'avais était 56, donnée par plusieurs d'entre vous, image à l'appui.

Piepalm, tu nous proposes 57 et il n'est pas impossible que ce soit la bonne réponse car il est très difficile de prouver qu'une valeur est la meilleure possible.

Etant donné que tu n'as pas fourni d'image, pour l'instant j'ai considéré que 56 était la bonne réponse meme si elle n'a été donnée que par un petit nombre (seulement 3 si je ne compte pas Lotfi qui a modifié sa réponse après coup, ce qui doit faire figure de précédent ou ?).

Cependant Piepalm, dès que tu auras joint une image (meme sous la forme NBNBN ...) et que 57 sera confirmé par tout le monde alors je changerai les notations et tu seras le seul avec un ce qui n'est peut-etre jamais arrivé...

En attente de tes nouvelles.

minkus

Bonjour
Si j'avais encore la possibilité j'allais mettre une autre réponse.mais la réponse 56 étais mon idée initiale, mais (en lavant la vaisselle) je ne sais pas comment j'ai eu l'idée de ma seconde réponse.
En tout cas merci.

Choukrane!

Ah elles font mal, les questions ouvertes

borneo
^{D'un cyber café colmarien climatisé}

bonsoir bornéo, on aurait pu se rencontrer,je suis un peu sur les hauteurs dans la vallée de munster,j'ai justement pensé à toi en passant à ribeauvillé à cause de la jff sur le match avec les profs du lycée,ce message n'est pas trop à sa place ici mais irais-tu le lire dans l'expresso?

Pour cette énigme, tout d'abord bravo à ceux qui ont trouvé la solution "à la main" .. Quant à moi, j'ai pris la solution plus sûre, mais plus difficile de la programmation.

Première idée : exploration brutale de toutes les configuration spossibles, soit , soit environ . Autant dire qu'à moins d'avoir un ordi de la NASA, il faut trouver une autre solution ...

Les professeurs d'informatique répétent toujours qu'il faut "diviser pour régner" : il vaut mieux résoudre 2 petits problèmes puis rassembler les solutions, plutôt que d'essayer de résoudre un gros problème.
Un exemple : imaginons que vous vouliez calculer ( peut être une matrice par exemple). Plutôt que de faire fois le produit de , il vaut écrire la puissance cherchée sous la forme si est pair ou si est pair. On calcule (on divise le problème), on élève cette valeur au carré et c'est gagné. De cette manière, on a un algorithme dont la durée est proportionnelle à , et non plus à si on avait fait une méthode "brutale" : c'est particulièrement appréciable lorsque est très grand.

Dans le cas du Reversi,
1. j'ai d'abord calculé quelques étaient les différentes combinaisons possibles de jetons sur une colonne (diviser le problème) pour respecter la consigne : il y en a environ 700 ( de mémoire), je les enregistre toutes. La meilleure ligne comporte 7 jetons noirs.
2. Je calcule ensuite quels sont les blocs de 4 colonnes qui respectent la consigne. Mais un bloc où rien ne serait retourné ne me servirait à rien ... Imaginons que je cherche une solution où l'ensemble du plateau contient au moins 52 jetons noirs (une solution à 52 jetons à été trouvée à la main par exemple) : dans une telle solution, tous les blocs de 4 colonnes contiennent au moins 52-5*7=17 jetons noirs. En effet, dans le meilleur des cas, les 5 autres colonnes contiennent 5*7 jetons noirs.
Je m'apercois (au bout d'un certain temps de calcul) que le meilleur bloc de 4 colonnes contient 26 jetons noirs : les blocs de moins de 52-26-7=19 jetons noirs ne me serviront plus.
J'obtients alors un grand nombre de bloc de 4 colonnes possibles : 300000 de mémoire.
3. J'essaie ensuite de les agencer pour former un plateau complet : bloc de 4 col + bloc de 4 col + 1 col.  Dès que je trouve mieux que 52 (sans attendre la fin du calcul qui durerait encore longtemps), je modifie la liste des blocs de 4 colonnes "acceptables" (étape 2) pour en diminuer le nombre et je relance l'étape 3

Au bout d'un moment, le programme ne trouve pas mieux que 56 jetons noirs.

Merci aux 3 autres qui ont trouvé la solution (ou à Minkus) de me faire partager leur raisonnement pour trouver 56

Ne vous inquiétez pas! Je me suis aperçu après coup qu'il subsistait un alignement de 4 noirs sur une diagonale; ma "solution" à 57 n'en est donc pas une.
Je n'ai pas beaucoup de temps à consacrer à ces énigmes, et je réponds souvent trop vite!
Par contre, il me semble qu'il est déjà arrivé qu'un seul concurrent obtienne un smiley : je crois que c'était Nofutur2 sur l'énigme du solitaire; j'avais encore répondu trop vite, et n'ai trouvé la solution qu'à ma seconde réponse...

Piepalm, ok j'en prends note. Le classement reste donc inchangé pour l'instant.

Nobody, personnellement ma solution était fournie avec l'énoncé et j'avoue ne pas avoir trop cherché parce que ce genre de problèmes n'est vraiment pas mon point fort.

Ok Minkus, mais la solution n'était donnée sans aucune explication ?

Salut Nobody,

J'ai cherché à la main. J'ai commencé par quelques motifs simples répétés de façon périodique (ou par symétrie). Par exemple je suis arrivé aux deux motifs suivants qui comportent 52 cases noires :



^{(Du moins ce sont les deux grilles que j'ai gardées dans ma feuille Excel !)}

J'en ai cherché d'autres mais sans réussir mieux que 52 cases. Puis j'ai cherché si je pouvais améliorer l'un des motifs. En l'occurence j'ai remarqué que oui, en ce qui concerne le second : on peut rajouter 4 cases noires près du centre (on perd alors les symétries horizontales et verticales) et on tombe sur la solution proposée par nofutur2, lofti, toi et moi. Voilà comment j'y suis arrivé, j'admets avoir eu un peu de chance !

Donc non je n'avais pas la certitude d'avoir trouvé l'optimal, mais plutôt une intime conviction, car cette grille me semblait suffisamment simple et belle pour ne pouvoir être que la bonne solution !! J'ai donc posté sans me poser plus de questions !

Puisque tu as adopté une approche systématique, je pense qu'on a maintenant une bonne assurance qu'il s'agit de l'optimal "absolu" pour ce problème (par opposition à l'optimal "relatif" parmi toutes les solutions proposées par les mathiliens).

A++  

A moins d'une erreur de programmation de ma part,
dès ma réponse, j'avais l'assurance qu'il s'agissait de la meilleure solution. Merci en tout cas Torpedo pour ta réponse !

J'ai un peu travaillé comme toi, nobody, en partant les 700 et quelques lignes possibles.
Dans mon programme, j'ai enregistré toutes les combinaisons de 2 lignes possibles.
Puis j'ai combiné ces groupes de deux lignes et j'ai enregistré les groupes de 4 lignes qui convenaient.
Puis j'ai combiné les groupes de 4 lignes qui convenaient, et j'ai conservé les groupes de 8 lignes qui convenaient.
Enfin, j'ai ajouté une ligne aux groupes de 8 qui convenaient pour trouver la seule et unique solution (aux syméties près).

Petit oubli..!!!
Comme j'avais trouvé à la main une solution à 53, je me suis arrangé pour éliminer les groupes de 2, 4, 8 et 9 lignes qui ne permettaient pas d'atteindre ce score...

Merci NF2 !
Donc (à part lotfi, qui n'a pas donné de réponse), la recherche de la solution se faisait :
* soit à la main (cf Torpedo)
* soit informatiquement, avec une méthode pas évidente (NF2 et moi)

En ce qui me concerne, la correction que je possède dit : "Il est très difficile dans ce genre de problème de savoir si on a trouvé la valeur optimale aussi n'avons nous rien d'autre à vous proposer qu'une résolution informatique."