Voila la solution que je vois, peu vérifiée ... En tout cas, je suis certain qu'elle est utile, même si il y a une erreur.
Préliminaire:
Clique majeure: taille 2m.
On considère les deux pièces A et B.
Etat initial: les 2m éléments de la clique majeure dans la pièce B et le reste des éléments dans la pièce A.
Processus:
Etape 1: on déplace des éléments de la pièce B à la pièce A un à un. Par conséquent, la plus grande clique de la pièce B diminue de 1 à chaque étape et la plus grande clique de la pièce A augmente de 0 ou 1 à chaque étape.
On note A(k) (resp B(k)) la taille de la plus grande clique de la pièce A (resp. la pièce B) à la k-ième étape (après k déplacements de la pièce B vers la pièce A)
On remarquera, en particulier, que B(0) = 2m, B(k) = 2m -k.
L'étape 1 s'arrête dans l'un des deux cas suivants
i) Soit quand A(k) = B(k) (on a alors gagné)
ii) Soit quand A(k) + 1 = B(k)
Il est facile de s'assurer que l'on se trouvera forcément dans l'une des deux configurations à un moment donné (A(k) est croissant et B(k) est décroissant, et ils varient de 1 au maximum...)
Etape 2: On se trouve donc dans la configuration pour laquelle A(k) + 1 = B(k).
Là, ca se complique. Si l'on déplace un élément de plus de B vers A, deux cas possibles:
i) A(k+1) = A(k) et dans ce cas on a gagné car B(k+1) = B(k) - 1 = A(k) = A(k+1).
ii) le cas chiant: A(k+1) = A(k) + 1. la taille de la(les) clique(s) de plus grande taille de la pièce A a augmenté de 1 et on a A(k+1) ) = B(k) = 1 + b(k+1).
Il va falloir faire un nouveau déplacement, cette fois de A vers B!!!!
La remarque qui débloque tout:
Si l'une des cliques (il peut y en avoir plusieurs) de taille A(k+1) à l'étape k+1 ne contient pas l'intégralité des k+1 éléments de la clique majeure initiale passés de B à A, alors on a gagné car il suffit de renvoyer cet élément de A à B et la clique en question restera de taille A(k+1) (car le passagé de cet élément de A à B ne change rien vu qu'elle ne le contenait pas!) et la clique de la pièce B sera de nouveau de taille A(k+1).
Par conséquent, on peut supposer que toutes les cliques de taille A(k+1) dans la pièce A à l'étape k+1 contiennent les k+1 éléments de la clique majeure initiale passés de B à A. On y est presque!!
Soit q le nombre de cliques de la pièce A, de taille A(k+1) à l'étape k+1. On choisit un élément dans chacune de ces cliques (il peut y en avoir qui appartiennent à plusieurs des q cliques, peu importe) et on les fait passer dans la pièce B. Par conséquent, la clique de plus grande taille dans la pièce A devient A(k+2) = A(k+1) -1 (clair!).
Qu'en est t-il de B(k+2)? on espère qu'il reste égal à B(k+1) = A(k+1) - 1 = A(k+2)... Eh bien, c'est le cas. en effet, qu'a-t-on dans la pièce B à l'étape k+2?
- les 2m - (k+1) éléments de la clique majeure initiale +
- q (ou moins) éléments venus de chacune des cliques de la pièce A dont on a parlé plus haut. On remarquera que tous ces éléments sont amis avec les k+1 éléments provenant de B ...
supposons que l'on arrive à former une clique de taille strictement plus grande que B(k+1) = 2m - (k+1). Dans ce cas, si on associe cette clique avec les k+1 éléments initiaux de la clique majeure qui sont dans la pièce A, on obtient une clique de taille strictement supérieure à 2m (voir la remarque en gras au dessus) . D'où la contradiction.
Accueil 
