Jeu de société 2 - Lycée Blaise Pascal (Orsay)

Bob a inventé un nouveau jeu de société. Il dispose sur la table n^2 billes, où n ≥ 3, en remplissant les coordonnées entières d’un carré de taille n × n. Il explique les règles à Alice : tout d’abord,
elle doit sélectionner un sous-ensemble de billes S. Puis, pour chaque couple de billes contenues dans S, elle doit retirer toutes les billes du carré qui sont sur la droite les reliant.
Le but pour Alice est de choisir S tel qu’elle puisse retirer toutes les billes de la grille. Comme le jeu est trop facile (il suffit de prendre S l’ensemble de toutes les billes de la grille), Bob demande à Alice de choisir un ensemble S contenant le moins de billes possibles. Pouvez-vous l’aider ?