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 - 05-03-2011 00:47:10

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

Echcs 8

Bonsoir à tous smile

La série lancée par gasole dans le forum logique m'a donné envie de reprendre celle que j'avais commencée il y a quelques temps . Je rappelle qu'il n'est pas nécessaire de connaître les règles du jeu , ici l'échiquier sert uniquement de terrain pour se détendre .

On place des piles de pièces de 1€ sur les cases d'un échiquier , chaque pile  pouvant contenir 0 , 1 , 2 , ... pièces . On suppose en plus qu'on dispose d'une réserve suffisante de pièces de 1€ pour s'adonner au jeu suivant ...

On peut poser ou enlever une pièce sur deux cases voisines ( partageant un même côté ) et ceci autant de fois que l'on veut dans l'espoir de vider l'échiquier .

Un exemple avec initilement 10 pièces placées ( on a utilisé 4 pièces supplémentaires ) .

http://img848.imageshack.us/img848/8744/picessurunchiquier.jpg

Peut-on toujours vider l'échiquier et si non dans quels cas celà est-il possible et comment ???????

Merci d'avance pour la participation smile

Vasimolo

PS : C'est un problème personnel , la solution est donc assez simple smile



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 05-03-2011 01:10:25

thedoums
Professionnel de Prise2Tete
Enigmes résolues : 23
Messages : 223

Ehcecs 8

je dirais qu'il faut que le nombre de départ soit pair et ce sera possible... et vice versa, impair impossible! non?

 #3 - 05-03-2011 01:26:15

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Echces 8

On peut d'emblée voir que il faut qu'il y ai autant de pièces sur les cases noires que sur les cases blanches pour que ce soit possible.

Si cette condition est remplie, on peut vider l'échiquier.

piste de démo :
on prend un carré de 4 cases, il est possible de vider les 2 cases de gauches g1 et g2 (en les prenant initialement comme cases voisines pour en mettre une (disons g1) à zéro, puis en utilisant la case de droite d2 (au besoin complétée auparavant avec d1) au niveau de g2 pour vider g2.
De proche en proche, on n'aura plus que 2 colonnes adjacente non vide.
On prend alors successivement les 7 carrés de haut en bas (dont on vide les 2 cases du haut) : il ne reste plus que des pièces sur les 2 cases de droite de la ligne du bas.

Chacune d'elles possède autant de pièces (condition initiale + conservation de l'écart à chaque tour). Donc on les vide.

cqfd.

 #4 - 05-03-2011 01:48:35

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

EEchecs 8

Soit un échiquier avec l lignes et c colonnes.
On peut voir cet échiquier avec des pièces dessus comme une matrice de taille l*c avec des coefficients entiers naturels.
Soit A une telle matrice et a[i,j] les coefficients de A.
Soit I(A) le nombre suivant:
[TeX]
I(A)=\sum_{i=1}^{l}\sum_{j=1}^{c}(-1)^{i+j}.a_{i,j}
[/TeX]
C'est facile de voir que I(A) est invariable par les transformations qui consistent à ajouter ou soustraire une pièces sur deux cases voisines de l'échiquier.
Ainsi, si on veut espérer vider l'échiquier, il faut au moins que I(A) soit nul.

Réciproquement, si I(A) est nul alors il est possible de vider l'échiquier. En effet, on peut facilement, après quelques ajouts ou soustractions de pièces, se ramener à un échiquier avec des pièces sur une seule des cases. Comme I(A) est nul, le nombre de pièces sur cette case l'est aussi et donc il n'y a aucune pièce sur l'échiquier.
Alors comment se ramener à un échiquier avec des pièces sur une seule des cases? On peut numéroter les cases de l'échiquier comme un serpent, ça donne ça par exemple pour un échiquier 4*3:

Code:

---------------------
|  1 |  2 |  3 |  4 |
---------------------
|  8 |  7 |  6 |  5 |
---------------------
|  9 | 10 | 11 | 12 |
---------------------

On vide d'abord la case 1 de la manière suivante: on rajoute des pièces sur les cases 2 et 3 jusqu'à ce que le nombre de pièces sur la case 2 soit supérieur ou égal au nombre de pièces sur la case 1. On vide alors la case 1 grâce à la case 2. On procède de même sur les cases 2, 3 et 4 pour vider la case 2. Et ainsi de suite, on vide toutes les cases sauf les 2 dernières. On enlève alors des pièces sur ces deux dernières cases jusqu'à ce qu'il ne reste des pièces que sur une seule.



Donc on peut vider l'échiquier ssi I(A) est nul.

PS @ Vasimolo:
On peut voir aussi I(A) comme la nombre de pièces sur toutes les cases noires moins le nombre de pièces sur toutes les cases blanches. C'est moins formel et c'est vrai que c'est plus agréable à comprendre.

 #5 - 05-03-2011 02:27:48

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

zchecs 8

Il est évident qu'on ne peut pas vider l'échiquier avec un nombre impair de pièces au départ big_smile
Je cherche encore pour le critère permettant de caractériser les positions où on peut tout vider ...

 #6 - 05-03-2011 09:09:45

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Ehecs 8

Edit : c'est idiot ce que je viens de dire, ça voudrait dire que ça ne marche que si les deux cases du bout sont égales.

Bon, je prends le problème  autrement : Si on rajoute/enlève une pièce sur une case noire, on fait de même sur une case blanche. Donc, le total de pièces sur les cases noire doit être le même que celui sur les cases blanches.

Cela suffit-il ? Oui.

De case en case, il est facile de ramener l'échiquier à deux cases voisines seulement qui contiennent des pièces. Le nombre de pièces dans chacune de ces cases est alors le même. On peut les enlever.

 #7 - 05-03-2011 09:54:29

clementmarmet
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1329
Lieu: I'm in spaaaace!!

Echec s8

si l'on se retrouve avec

         2     1

isolé  on a obligatoirement une pièce restante


eki eki eki pa tang!!

 #8 - 05-03-2011 11:17:02

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

echrcs 8

Bonne réponse de Dylasse et Irmo .

Vasimolo

PS @ Irmo : Ne peut-on pas envisager un formalisme un peu plus simple en utilisant une particularité des cases de l'échiquier ?

 #9 - 05-03-2011 11:54:32

debutant1
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 116

Echhecs 8

si il n'y a qu'une pièce je n'arrive pas à l'enlever, je pense qu'il faut que le nombre soit pair .

 #10 - 05-03-2011 12:57:19

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

rchecs 8

Si j'ai bien compris la règle et si dans la position initiale il n'y a qu'une case avec des pièces ils est évident qu'on ne pourra jamais tout ramasser... right ? (c'est juste pour vérifier ma compréhension du problème)

 #11 - 05-03-2011 13:46:37

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

checs 8

A vue de nez je dirais que cela est possible si et seulement si la somme des pièces initiales est paire.
Faute de quoi il restera toujours une pièce seule qu'aucun ajout de pourra résoudre.


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #12 - 05-03-2011 14:49:00

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3761
Lieu: hébesphénorotonde triangulaire

evhecs 8

Bonjour,

Je pense que la condition nécessaire et suffisante pour arriver à vider l'échiquier est qu'il y ait initialement autant de pièces sur les cases blanches que sur les cases noires.

Si une case blanche possède n pièces, il est facile de déplacer cette pile de pièces sur une case blanche adjacente par le coin : il suffit de poser une double pile de n nouvelles pièces sur une case noire et une case blanche adjacentes, puis de supprimer la pile initiale de n pièces sur la case blanche d'origine et celle sur la case noire adjacente.
Grâce à cette méthode, on peut rassembler sur une seule case blanche toutes les pièces réparties sur les cases blanches et sur une seule case noire adjacente toutes les pièces réparties sur les cases noires. On enlève alors d'un seul coup toutes les pièces de l'échiquier.

Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #13 - 05-03-2011 18:10:05

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

Echecs

Bonne réponse de Gwen et Klimrod .

Globalement beaucoup ont trouvé facilement la condition nécessaire mais peinent à expliquer pourquoi c'est suffisant smile

Vasimolo

PS : Gasole tu as bien compris le problème , maintenant la solution ...

 #14 - 06-03-2011 19:54:19

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

EEchecs 8

J'avoue, je galère... je ne vois rien de simple...

 #15 - 06-03-2011 21:07:41

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

echecd 8

Deux cases "voisines" sont de couleurs opposées, une blanche et une noire.
A chaque étape, on fait varier de la même quantité le nombre de pièces sur cases blanches et le nombre de pièces sur cases noires.
La différence entre ces nombres restera constante, on ne peut espérer vider l'échiquier que si elle est nulle au départ.

On peut alors se fixer une case quelconque comme case finale objectif, et vider de proche en proche en commençant par les cases les plus éloignées.

La notion de case éloignée peut se définir par la distance deltax+deltay entre cases.

Au besoin, on "ira chercher" la case en apportant des pièces dans ses voisines depuis des cases plus proches de la case objectif.

Il n'y aura pas besoin de revenir sur ces cases distantes vidées, cela réduit donc le nombre de cases "utiles" de l"échiquier.

Au bout d'un nombre fini d'étapes, il ne restera plus que deux cases voisines ayant le même nombre de pièces, ce qui permettra de terminer.

 #16 - 06-03-2011 23:28:22

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Echecs

Pour pouvoir vider l’échiquier, il faut le nombre de pièces initialement disposées soit pair car on ajoute ou retranche deux pièces à la fois.

J'ai comme l’idée qu'on va me dire que j'ai rien compris... big_smile


The proof of the pudding is in the eating.

 #17 - 07-03-2011 00:32:17

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

zchecs 8

Bonne réponse de Halloduda , Franck , t'as rien compris lol

Vasimolo

 #18 - 07-03-2011 01:40:48

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

echecq 8

J'ai un truc raisonnable. Par raisonnable, s'entend : qui ne revient pas, de près ou de loin, à essayer toutes les possibilités via un test qui nécessite un temps de calcul exponentiel. J'ai un test quadratique.

En s'autorisant des valeurs négatives, on va "pousser" les valeurs non nulles vers la droite d'abord (elles n'occuperont plus que 2 colonnes), puis vers le bas (il restera 2 lignes de 2 colonnes). 

"Pousser vers la droite" consiste à poser des pièces sur les deux cases de droite d'une case non nulle, de façon à ce que sa voisine lui soit égale... et recommencer jusqu'à atteindre le bord droit.
Au total, on constate que ça revient à faire la somme des cases paires, et à soustraire cette somme à la somme de la première (la 1) et la dernière (la 7) case impaire.

Ensuite, on fait pareil, mais verticalement. On se retrouve au pire avec un carré 2x2 de pièces, pour lequel il est facile de conclure.

Ce n'est évidemment pas optimal en nombre de pièces posées...

Exemple :

3,2,0,0 va devenir 0,0,1,0 (= on a posé 1 pièces en case 2 et 3 et ramassé 1 et 2)
0,1,0,1 va devenir 0,0,-1,1 (= on a posé -1 pièce en case 2 et 3)


Formellement, l'échiquier est une matrice aij en l'occurrence 8x8.

Pour chaque ligne i, on calcule b la matrice à 2 colonnes et 8 lignes telle que :

bi1 = ai1 + a7i - (ai2+ai4+ai6) et bi2 = ai8

Pour chaque colonne j, on calcule c la matrice à 2 colonnes et 2 lignes telle que :

c1j = bi1+bi7- (bi2+bi4+bi6) et c2j=b8j

Il nous reste un carré c11, c12, c21, c22.

On peut tout enlever si  c12+c21 = c11 + c22.

NB : la complexité de ce test est en O(n^2)
---------------------------
Condition suffisante c'est sûr, mais nécessaire?

En y réfléchissant, s'il y a une solution, ma méthode aboutira, mais pas simple à expliquer... C'est dû au fait que l'ordre dans lequel on pousse vers la droite ou vers le bas ne change rien à la conclusion.

PS : on peut éviter les valeurs négatives si nécessaire en ajoutant suffisamment de pièces sur le jeu.

 #19 - 07-03-2011 17:29:56

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

echexs 8

Tout d'abord, on ajoute ou retire les pièces 2 par 2. Dans ce cas, si on utilise un nombre impair de pièces, il est impossible de tout retirer.

Plus précisément, un échiquier étant composé de cases blanches et noires, on ajoute ou retire autant de pièces sur des cases blanches que sur des cases noires. Il faut donc qu'il y ait autant de pièces sur les cases blanches que sur les cases noires initialement (ce qui permet par ailleurs d'affirmer alors que leur nombre est pair).

Cette condition suffit.
Démonstration par récurrence forte : supposons qu'un plateau contienne un certain nombre 2X de pièces, X étant sur des cases blanches et X sur des cases noires.
Si X = 0, alors l'échiquier est vide et donc vidable.
Sinon on suppose que pour tout x<X, l'échiquier est vidable.
Il existe forcément une case blanche et une case noire non vide. On en prend une de chaque, contenant a et b pièces avec a inférieur ou égal à b.
De ces deux cases, on peut tracer un chemin horizontal puis vertical qui les relie. Ce chemin passe par autant de cases blanches que noires qui se touchent 2 à 2: on peut donc regrouper toutes ces cases intermédiaires en paires, sur lesquelles on va ajouter a pièces (peut importe que les cases soit vide où non).
On va ensuite retirer a pièces à chacune de ces cases, en incluant cette fois ci les cases de départ et d'arrivée. Toutes les cases du chemin sont donc inchangées, la première est vide et la seconde contient b-a pièces.
Conclusion : une telle transformation permet d'obtenir un nouveau plateau de 2X-a pièces, nombre strictement inférieur à 2X, et donc notre échiquier est vidable par récurrence, CQFD.

 #20 - 07-03-2011 17:55:26

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Echecss 8

Je pense que la condition nécessaire et suffisante est qu'il y ait le même nombre de pièces sur les cases noires que sur les cases blanches.

Supposons une situation qui permet de vider l'échiquier.
Alors en partant à l'envers, depuis l'échiquier vide, on le remplit au fur et à mesure (en ajoutant ou enlevant des pièces), mais chaque mouvement ajout ou enlève le même nombre de pièces aux cases noires et aux cases blanches. C'est le cas quand il n'y a plus de pièces (0 = 0), ça sera le cas en revenant à la position initiale.
C'est donc une condition nécessaire

Est-elle suffisante ?
Me reste ça à démontrer ...

 #21 - 07-03-2011 23:47:37

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

echevs 8

Bon je lève le voile avant d'aller me coucher smile

Il y a ce que les mathématiciens appellent un invariant : la différence entre le nombre de pièces sur les cases blanches et le nombre de pièces sur les cases noires . Pour qu'on puisse vider le jeu il faut que cet invariant soit nul au départ car il est nul à l'arrivée ( je sais c'est très bête ) . Si c'est le cas comment être sûr de pouvoir récupérer toutes les pièces ? Il y a plusieurs stratégies dont certaines ont été évoquées plus haut , le serpent d'Irmo , le déplacement de piles de Klimrod , la récurrence de Scarta ... Personnellement j'avais envisagé de gaver la  ligne 2 pour vider la 1 puis la ligne 3 pour vider la 2 , ... Quand il ne reste plus que la ligne 8 , on gave les colonnes 2 et 3 pour vider la 1 , les colonnes 3 et 4 pour vider la 2 , ... et quand il ne reste qu'un domino les deux cases contiennent forcément le même nombre de pièces et c'est fini .

Merci pour la participation et pour la grande fidélité de certains qui se reconnaitront smile

Vasimolo

 #22 - 08-03-2011 09:11:37

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

echzcs 8

J'ai complètement zappé le côté bicolore de l'échiquier qui permet d'exprimer un invariant en quelques mots. Quel couillon ! big_smile

 #23 - 08-03-2011 09:21:05

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Ecehcs 8

Eh Vasimolo, elles sont où les couleurs sur ton exemple ?? c’était pour que ce soit plus difficile, n'est-ce pas. Vilain petit cachottier lol


The proof of the pudding is in the eating.

 #24 - 08-03-2011 22:52:51

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

Echecss 8

Vasimolo a écrit:

Ne peut-on pas envisager un formalisme un peu plus simple en utilisant une particularité des cases de l'échiquier ?

Je ne vais quand même pas tout vous dire smile

Mais bon , il m'arrive aussi  ( de plus en plus ) d'être un peu pervers lol

Vasimolo

 #25 - 09-03-2011 00:30:59

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

echexs 8

@Franck : On est inexcusables, tout le monde connaît l'astuce du recouvrement d'un échiquier privé de 2 coins opposés...

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 19 bis par Vasimolo
02-11-2012 Enigmes Mathématiques
P2T
Echecs 2 par Vasimolo
11-08-2010 Enigmes Mathématiques
P2T
Echecs 16 par titoufred
05-10-2012 Enigmes Mathématiques
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques
P2T
Echecs 3 par Vasimolo
16-08-2010 Enigmes Mathématiques
P2T
Echecs 17 ( lombrics ) par Vasimolo
09-10-2012 Enigmes Mathématiques
P2T
Echecs 21 par Vasimolo
14-11-2012 Enigmes Mathématiques
P2T
Echecs 12 par Vasimolo
01-06-2012 Enigmes Mathématiques
P2T
Echecs 6 par Vasimolo
11-09-2010 Enigmes Mathématiques
P2T
Echecs 14 par Vasimolo
03-09-2012 Enigmes Mathématiques

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