Maximiser le nombre de sommes (1) - Lycée Scheurer-Kestner (Thann)

On choisit n cases d'un pavage en damier, puis on les colorie en rouge. On numérote ces cases rouges de 1 à n et on calcule la somme des numéros pour chaque paire de cases qui partagent un côté commun.
Etant donné une disposition des cases rouges, comment choisir la numérotation pour maximiser le nombre de sommes différentes ?