On peut échanger les chapeaux et les sans-chapeaux en 15 déplacements. ( Exemple).
Comment prouver qu'on ne peut pas faire mieux donc que 15 est le nombre minimum de déplacements ?

Description de la situation initiale à l'aide de trois "compteurs".	Effet des déplacements sur les compteurs.	Description de la situation finale à l'aide des mêmes compteurs.
Au départ, les hommes à chapeaux sont tous à gauche de l'espace vide. Un premier compteur : Combien y a-t-il d'hommes à chapeaux à droite de l'espace vide ? Aucun. On pose C1 = 0. Un deuxième compteur : Combien y a-t-il d'hommes sans chapeaux à gauche de l'espace vide ? Aucun. On pose C2 = 0. Un troisième compteur: Combien y a-t-il de couples (chapeau, sans chapeau) où l'homme à chapeau se trouve à droite de l'autre ? Aucun. On pose C3 = 0. Au départ, C1 + C2 + C3 = 0	Une translation augmente C1 ou C2 de 1 sans changer C3. Un saut augmente C3 de 1 sans changer C1+C2. Chaque déplacement augmente donc C1+C2+C3 de 1.	Les trois hommes à chapeaux sont maintenant à droite de l'espace vide : C1 = 3. Les trois hommes sans chapeaux sont tous à gauche de l'espace vide : C2 = 3. Pour chacun des 9 couples (chapeau, sans chapeau), l'homme à chapeau se trouve placé à droite de l'autre : C3 = 9. Au final, C1+C2+C3 = 15.

Généralisons !

Cette solution se généralise facilement au cas de n hommes à chapeaux échangeant leurs places avec m hommes sans chapeaux. Avec les conventions ci-dessus, la somme des trois compteurs doit passer de 0 à n + m + nm, ce qui donne le nombre minimal de déplacements.
Attention, s'il y a plus d'un espace vide au milieu, il faut changer les compteurs C1 et C2, et compter les positions des couples (chapeau, espace), (sans chapeau, espace).