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

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:

---------------------
|  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.

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.

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 ?

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)

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'avoue, je galère... je ne vois rien de simple...

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...

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.

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 ...

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

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

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

Vasimolo