Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 11-11-2012 19:09:36

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

checs 20

Un petit problème que je traîne dans mes tiroirs depuis longtemps ( j'espère ne pas l'avoir déjà proposé ) .

On pose trois pions comme indiqué sur la figure dans les trois cases rouges de l'angle d'un échiquier .

http://img145.imageshack.us/img145/1281/echiquier.jpg

On considère ensuite un pion tel que les deux cases immédiatement au dessus et immédiatement à droite soient vides . On enlève alors le pion choisi et on place un nouveau pion dans chacune des deux cases libres désignées précédemment . L'ensemble de ces manipulations s'appelle un coup . 

http://img19.imageshack.us/img19/1385/constructionu.jpg

Questions : Peut-on libérer les trois cases rouges par une succession de coups ? Si oui quel est le nombre minimal de manœuvres nécessaires ?

Amusez-vous bien smile

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 11-11-2012 19:44:56

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

echexs 20

Bon, si c'est possible, je n'y parvient pas sad

Je pense donc que c'est impossible, maintenant pour le justifier...

Je continue de chercher.

 #3 - 11-11-2012 22:42:51

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

cEhecs 20

On peut montrer que c'est impossible, même sur un échiquier aussi grand que l'on veut.

On attribue une valeur à chaque case de l'échiquier, en fonction de la diagonale NW/SE qu'elle occupe :
[TeX]1[/latex] pour la case en bas à gauche.

[latex]\frac12[/latex] pour chacune des 2 cases de la diagonale juste au-dessus.

[latex]\frac1{2^{k-1}}[/latex] pour chacune des k cases de la diagonale NW/SE.

Puis on attribue une valeur à une configuration de pions sur le plateau, qui est la somme des valeurs des cases occupées par des pions.

Pour la configuration de départ, la valeur est égale à : [latex]1+ \frac12 + \frac12 = 2[/TeX]
Lors d'un coup, on enlève un pion d'une diagonale k pour en rajouter 2 sur la diagonale k+1, ce qui fait que la valeur de la configuration après le coup est la même que la valeur de la configuration avant le coup. Donc la valeur d'une configuration issue de la position de départ (après un certain nombre de coups) est toujours égale à 2.

Maintenant, pour une configuration où les 3 cases de départ sont libres, la valeur est inférieure strictement à [latex]\sum_{k\geq3}{k\times\frac1{2^{k-1}}[/latex]

Evaluons cette somme :

On définit une fonction f sur l'intervalle ]-1;1[ par [latex]f(x)=\sum_{k\geq0}{x^k}=\frac1{1-x}[/latex].
Alors [latex]f'(x)=\sum_{k\geq1}{k\times x^{k-1}}=\frac1{(1-x)^2}[/latex]

Donc [latex]f'\left(\frac12\right)=\sum_{k\geq1}{k\times \frac1{2^{k-1}}}=\frac1{\left(1-\frac12\right)^2}=4[/latex]

On en déduit que [latex]\sum_{k\geq3}{k\times\frac1{2^{k-1}}=4-2=2[/latex]

Par conséquent, toute configuration où les 3 cases de départ sont libres a une valeur strictement inférieure à 2, et donc elle ne peut être obtenue à partir de la position de départ.

Joli problème !

 #4 - 11-11-2012 23:28:44

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Ehcecs 20

C'est ça Titou , on peut faire un peu plus simple avec la même idée smile

Vasimolo

 #5 - 12-11-2012 13:02:48

catous
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 2

Ehcecs 20

ils seront libérés en 4 coups

 #6 - 12-11-2012 21:42:08

Razzer
Visiteur

Echecs 200

Je suppose que c'est :... Aucune possibilité! Enfin je n'y arrive pas ^^ apres il y a surement un enchainement speciale tout comme le rubicks cube pour le resoudre, sinon le minimale ne serait pas souligner tres insistement ^^

 #7 - 12-11-2012 23:26:24

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Echec 20

Ce problème est difficile , il faut trouver ce que les matheux appellent un invariant puis il faut voir en quoi cet invariant est incompatible avec la suppression des trois cases rouges .

Bon courage à ceux qui cherchent smile

Vasimolo

 #8 - 13-11-2012 09:56:45

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Echecs 2

Le mot "invariant" m'a fait tilter en une demi-seconde.



Je numérote les cases de 1 à n dans chaque direction, en partant du coin en bas à gauche, puis j'attribue à chaque case de coordonnées [latex](i,j)[/latex] la valeur [latex]\frac{1}{2^{i+j-2}}[/latex]. Ainsi, le coin inférieur droit vaut 1, les deux autres cases rouges valent 1/2, les trois cases de la diagonale suivante valent 1/4, etc.

Dans la position de départ, la somme des cases occupées par des pions vaut 2. Un coup laissera cette somme intacte, puisqu'elle enlèvera un pion d'une case de valeur k pour mettre deux pions, chacun dans une case de valeur k/2 (on vide la case [latex](i,j)[/latex] pour remplir les cases [latex](i+1,j)[/latex] et [latex](i,j+1)[/latex]).

Voilà notre invariant : la somme des valeurs des cases occupées par des pions vaut toujours 2.

Maintenant, on constate qu'il y a une case de valeur 1 dans la grille, deux cases de valeur 1/2, trois cases de valeur 1/4, quatre cases de valeur 1/8, etc. On généralise pour calculer la somme des valeurs des cases d'une grille infinie :
[TeX]\sum_{i=1}^{\infty} \frac{n}{2^{n-1}} = 4[/TeX]
La grille considérée est finie, donc la somme des valeurs des cases est strictement inférieure à 4, donc il est impossible de disposer des pions sur des cases dont les valeurs s'ajoutent à 2 sans garder au moins un pion dans une des trois cases rouges.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #9 - 13-11-2012 16:59:45

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

Ecehcs 20

J'ai une proposition à faire.

Je considère que les pions peuvent s'empiler avant d'être dispatchés.

Comme il faut exclure les 3 pions de départ, on doit passer obligatoirement par les étapes de la première ligne :

http://img15.hostingpics.net/pics/140363techno.jpg

On se retrouve avec 2-4-2 dans la diagonale. On ne peut laisser qu'un pion sur chaque case, donc sur les 2 des cases du haut et du bas, 1 doit virer, ainsi que 3 sur les 4 de la case du milieu.

Je débarrasse ainsi les cases une à une, en ne laissant qu'un pion sur chaque case derrière moi.

La progression est "exponentielle" et je vois bien que je fini par bloquer.

J'espère que cette explication te satisfera Vasimolo...

 #10 - 13-11-2012 18:08:16

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Echces 20

Bravo Mathias !

@Golgot : intuitivement c'est ça mais ça peut se justifier proprement .

Un petit indice en image pour ceux qui cherchent encore :

http://img820.imageshack.us/img820/8721/indiceu.jpg

Vasimolo

 #11 - 14-11-2012 18:29:13

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Echecs 02

C'est drôle je me souviens avoir planché sur cette énigme il y a quelque temps mais je n'ai aucun souvenir de la solution...
Je vois bien l'invariant de valeur 2, mais je sais pas trop quoi en faire.

 #12 - 14-11-2012 19:24:25

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

zchecs 20

Félicitation à ceux qui ont trouvé smile

Si on ne voit pas l'invariant on peut chercher longtemps sad

Après on peut justifier très facilement que les trois cases dans l'angle ne peuvent être toute libérées . Je reprends la numérotation donnée dans l'indice .

La 1ère ligne 1+1/2+1/4+... est clairement inférieure à 2 .
La 2ème est la moitié de la 1ère donc inférieure à 1 .
...
La somme de toutes les lignes est inférieure à 2+1+1/2+...=2(1+1/2+1/4+...)=4 .

Après tout a déjà été dit .

Merci pour la participation smile

Vasimolo

 #13 - 14-11-2012 19:40:05

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Eches 20

Bon pour moi, c'est l'explication de MthS qui m'a ouvert les yeux.
C'est en effet expéditif !

 #14 - 15-11-2012 06:54:32

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

Echcs 20

yikes

Je pouvais toujours chercher !

Ce coup de l'invariant a déjà servi dans un autre problème ? Parce qu'à moi, l'indice n'a rien évoqué du tout !!!

 #15 - 15-11-2012 17:59:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

EEchecs 20

Je pense qu'il y a des dizaines de problèmes avec invariants sur le site , j'en ai personnellement proposé un bon paquet . Tu peux faire une recherche sur le site avec le mot clé "invariant" .

Vasimolo

 #16 - 15-11-2012 22:06:32

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

Echec 20

Merci du conseil smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques
P2T
Gâteau 20 par Vasimolo
03-08-2010 Enigmes Mathématiques
P2T
Echecs 16 par titoufred
05-10-2012 Enigmes Mathématiques
P2T
Echecs 9 par Vasimolo
15-03-2011 Enigmes Mathématiques
P2T
Echecs 10 par Vasimolo
25-11-2011 Enigmes Mathématiques
21-02-2014 Enigmes Mathématiques
P2T
Echecs 13 par Vasimolo
26-08-2012 Enigmes Mathématiques
P2T
Echecs 15 par Vasimolo
30-09-2012 Enigmes Mathématiques
P2T
Echecs 17 ( lombrics ) par Vasimolo
09-10-2012 Enigmes Mathématiques
15-03-2008 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete