Reprise du message précédent :
Manque pas un truc ?  

Non. J montre l'une des cases, par exemple B6. Le but du jeu est que M1 fasse deviner cette case à M2. Pour ce faire, il a le droit de retourner au plus une pièce de l'échiquier.

Quand M2 rentre, tout ce qu'il voit, c'est l'échiquier dans la disposition finale. Et il doit deviner la case (pas la case dont la pièce a été retournée, celle qui a été montrée par J).

Aaaah okay il me manquait donc la compréhension du but du jeu
 
Bon ben là comme ça ça m'a l'air impossible, mais pas le temps de m'y mettre à fond.

Oui pardon, je l'explique mal à chaque fois

Est-ce que M1 écrit un nombre sur 6 cases de l'échiquier ? Mais comme il ne peut changer qu'un bit, il faut qu'il trouve 6 cases qui l'arrangent bien, et que M2 devine quelles sont ces cases grâce à la stratégie pré-établie...

Il faut effectivement coder 6 bits (je t'apprends pas grand chose)

Mais toutes les cases sont utiles

On peut avoir un exemple s'il te plaît ?

C'est-à-dire ? Je te montre une disposition de l'échiquier et la case que ça désigne ?

Un échiquier au hasard, la case désignée et la pièce a modifier si on en modifie une

Ok je posterai ça plus tard ce soir, mais je doute que voir une valeur t'aide beaucoup à trouver la fonction

D'ac merci
Ah ^^

Ok alors
 
Pile = 0
Face = 1
 
Position de départ :
 

 
Case désignée par le joueur : B4.
 
Pièce à retourner : D5.
 
Voilà, honnêtement c'est difficile d'extrapoler à partir de ça Surtout qu'il y a plusieurs implémentations possibles de la solution, ne serait-ce que par symétrie du plateau.
 
(Et d'ailleurs, même hors équivalence à symétrie près, la solution n'est certainement pas unique. Il suffit de voir que le problème se reformule ainsi : trouver une fonction f qui à une disposition associe un entier dans [0,63] et telle que pour toute disposition D et tout entier n, il existe une disposition D' différant de D par au plus une case et tq f(D')=n. Formulé encore autrement il faut partitionner l'espace des 2^64 dispositions en 64 classes d'équivalence telles que l'on puisse toujours passer d'une classe à n'importe quelle autre par un seul retournement. Vu le nombre astronomique de tels partitionnements, il doit y en avoir un petit paquet qui vérifie la propriété demandée En revanche, il n'est pas évident qu'il y en ait plusieurs qui aient une formulation simple à comprendre pour un humain !).
 
Quelques indications :
 

• le fait que ce soit un échiquier n'apporte rien au problème. La solution fonctionne sur une liste de 64 cases numérotées (c'est implicite en fait dans la définition du problème mais ça peut éviter de faire fausse route )

• Hint

  Spoiler : Décomposition en base 2 Ca peut paraître évident comme hint (mais perso j'étais parti sur une autre piste la première fois )

Ca me rappelle les groupes et l'ensemble des parties d'un ensemble à 64 éléments... Alors toi à 3 heures du matin t'es encore fort en maths    
 
Ne donne pas la solution tout de suite stp, je n'ai pas le temps tout de suite mais j'y réfléchirais sûrement ce soir c'est une question d'avatar !

Ta solution marche pour 2*2 mais pas au-delà
 
Sur le 8*8, le reste de ta division par 128 est simplement donné par les 7 premières cases, les 57 autres sont inutiles (les retourner ne change pas le reste).
 
Ainsi, à partir d'une disposition donnée, tu pourras en atteindre au plus 7 autres, et pas 63 autres comme il faudrait

Salut, je viens quémander votre aide.    
 
J'ai Jn=intégrale de 0 à 1 de (x^n/(1+x^n)) et je dois montrer que ça vaut :  
 
(ln2/n -1/n*(intégrale de 0 à 1 de ln(1+x^n))
 
Je sèche un peu. Je vois pas se formule directe et mon intégration par parties ne me donne pas ça.

u=x et v'=x^(n-1)/(1+x^n), u'=1 et v=ln(1+x^n)/n ????

 
Ah ouais merci, je m'étais planté dans ma primitive de v'.  

 
Ca doit pouvoir se faire de tête (pour M1 et M2) ?

Ca se fait pas trop de tête, mais presque (l'algo est facile, mais avec 64 cases, ça fait un peu beaucoup de trucs à retenir pour le faire de tête dans se tromper ) Disons que ça se fait en une ou deux minutes avec un papier et un crayon.

Bonjour    
 
http://fileserver.bankexam.fr/telecharger/annale/1820
 
http://mathsece.free.fr/sujetsenti [...] 05_E-c.pdf
 
Pourquoi les coordonnées dans la base à la question 3b sont (1,0,0,0) et non (1,0,0,-1) ? J'avais compris l'autre jour mais d'une oreille distraite visiblement car je suis plus vraiment convaincu par ce qu'il me semble avoir entendu.  
 
Merci
 
ÉDIT : Ah c'est bon je m'en suis souvenu, il fallait multiplier par U1 non (et ainsi de suite ce qui explique le 0,0,0,3 pour f(I)) ?

Si j'ai bien compris tu as trouvé (1,0,0,-1) en calculant la différence f(J1-J4) = f(J1)-f(J4) sur les vecteurs colonnes ?
Le problème c'est que le vecteur que tu trouves est bien celui de f(J1-J4) mais il est exprimé dans la base A.
Il faut l'exprimer dans la base B. Donc ici mieux vaut calculer en f(J1-J4) en fonction des Ji puis ensuite les exprimer dans la bonne base.
C'est d'ailleurs ce qui est fait dans le corrigé.

Groumpf, du coup je passe
 

J'ai peut être mal compris alors. Comment est codé ton nombre initial (avant de prendre le reste) ? Ce n'est pas simplement la somme des 2^i pour les i tq la case i est sur face ?

 
Ah Bon si on pense à la même chose, je pense pas qu'il y ait beaucoup plus simple de toute façon (au sens plus facile à faire de tête), car il est nécessaire que les 64 cases (ou 63 si on autorise à n'en bouger aucune) soient utiles dans l'algo...

Grosso modo, voila rapidement l´idée qui me vient.
 
Pour chaque case d´indice i sur laquelle on a "face", on ajoute à x la valeur i.
Par exemple si on a face uniquement case 4, 8 et 54, x vaudra 66.
Puis on calcule y = x module 64.
Ensuite, si la position rechercher est z, on retourne la pièce à la position z-y (modulo 64).
La nouvelle somme sera donc y + z - y (modulo 64), soit z (modulo 64), c´est à dire la position recherchée.
 
La solution doit être dans cette direction
 

C'est une bonne idée, j'étais parti là-dessus au début Malheureusement ça marche pas dans tous les cas. dans ton exemple, ça ne marche que si la case z-y n'est pas déjà sur face. Sinon tu vas ajouter y-z au lieu de z-y. En fait tu as toujours le choix entre 2 cases (par exemple pour faire +10 tu peux faire +10 ou -54) -sauf pour les cases 0 et 32-, mais même comme ça, tu peux te retrouver dans un cas (1 chance sur 4) ou les deux pièces que tu peux retourner sont dans la mauvaise position.

Y a ptet moyen de s'en sortir, mais j'ai pas trouvé sur cette piste

En fait on peut voir avec cet exemple qu'à partir du moment où on a un algorithme tel que le retournement de deux cases différentes mène au même résultat, on est à peu près foutus

Bon je donne la solution - du moins une solution

je sais pas si je l'ai déjà posté mais je la met :
un tyran a enfermé 100 mathématiciens dans son château
il leur propose une énigme :  
il y a une salle avec 100 coffres numérotés, dans chaque coffre il y a un papier avec un nom de mathématicien, chaque mathématicien est nommé dans un coffre
 
tous les jours, chaque mathématicien va devoir aller dans la salle des coffres et il aura le droit d'ouvrir 50 coffres
si tous les mathématiciens trouvent leur nom ils sont tous libérés, sinon ils restent enfermés jusqu'au lendemain
 
les papiers ne changent pas de coffres entre les passages ni de jour en jour
ils ont le droit d'établir une stratégie qu'ils exécuteront à la lettre aussi complexe soit-elle, par contre une fois que le premier mathématicien entre le premier jour ils n'ont plus le droit de communiquer
 
trouver une stratégie permettant de sortir en un temps raisonnable

 
Oui c'est con Une bonne énigme, c'est une énigme que tu cherches longtemps et dont la solution est relativement simple

Je ne comprends pas? Le deuxième jour, ils seront libres, non?

 
Yep excellente devinette, merci, je la note  

Ben c'est clair au vu de l'énoncé:

A+,

Yes l'énigme est mal posée il faut soit que le méchant change les coffres tous les jours, soit que les mecs meurent tous au premier jour s'ils ont pas tous trouvé

C'est pas plutot un mathématicien par jour va ouvrir 50 coffres ?

L'énigme est posée bizarrement. Je connaissais la variante avec les 100 prisonniers et l'interrupteur:
- 100 prisonniers.
- 1 salle avec 1 interrupteur qui commande une ampoule (état initial: éteinte)
Toutes les x minutes, le gardien de la prison va chercher individuellement un prisonnier tiré aléatoirement parmis les 100 (donc un prisonnier peut se faire appeler une infinité de fois). Le prisonnier a la possibilité d'actionner l'interrupteur, puis retourne dans sa cellule.
À n'importe quel moment, un prisonnier peut déclarer: "Nous avons tous été appelés". S'il a raison ils sont tous libérés, sinon ils se font tous exécuter.
 
Les 100 prisonnier ont 24h pour se mettre d'accord sur une stratégie. Ils sont ensuite placés dans des cellules individuelles complétement coupées de l'exterieur.

oui les noms changent chaque jour sinon c'est pas drôle

Là c'est carrément une autre énigme elle est pas mal non plus

D'ailleurs on n'est pas obligé de connaître l'état initial de l'ampoule (mais ça met plus longtemps).

Je l'ai trouvé, elle n'est pas trop difficile. La clef est que

 Le plus dur est de calculer le temps moyen de libération... qui doit être monstrueux...

Sauf que non, cette énigme n'a pas nécessairement de solution, vu comment elle est posée:

De ce fait, il est tout à fait possible, même si c'est avec une probabilité s'amenuisant à chaque tirage, que l'un des 100 prisonnier ne soit jamais tiré au sort dans aucun des tirages successifs, et donc que les prisonniers ne puissent jamais dire "Nous avons tous été appelés".
 
A+,

Oui, on peut par exemple dire qu'il tire au sort de façon iid avec une loi qui a pour support l'ensemble des mecs, ça suffit

Sinon, pour le temps d'atteinte, à supposer qu'il tire en loi uniforme :

- au début, tu as 99 chances/100 de prendre un mec qui n'est pas le compteur, temps moyen d'atteinte 100/99.
- ensuite il faut tirer le compteur, 1 chance /100, temps moyen d'atteinte 100.
- ensuite 98 chances sur 100 de prendre ni le compteur ni le premier mec -> temps d'atteinte 100/98.
- puis de nouveau le compteur, temps moyen d'atteinte 100.

etc.

Au total le temps moyen d'atteinte est 100 * (100 + sum (i=1..99) 1/i) qui vaut à peu près 100*(100+ln(100)). Bon je l'ai pas démontré proprement, mais la propriété de Markov permet d'additionner les espérances des temps d'atteinte sans trop de souci