Zig a entre les mains la figurine noire d’un roi(1) d’échecs avec laquelle il visite une fois exactement toutes les cases d’un échiquier(2) de dimensions 20 x 20. Diophante lui demande de minimiser le nombre de fois que le roi change de couleurs durant son parcours. Soit N_min cette valeur minimale.
Puce opère de la même manière avec la figurine blanche d’un roi d’échecs sur un échiquier de dimensions plus petites (k x k) et obtient paradoxalement un minimum de N_min + 1 changements de couleurs.
Déterminer N_min et k.
Nota
(1) Sur un échiquier, le roi se déplace en ligne verticale ou horizontale et en diagonale d'une seule case à la fois.
(2) Cet échiquier comme tout échiquier traditionnel contient des cases noires et blanches en alternance.

 Solution