Lisa and Bart are playing a game. A round table has n lights evenly spaced around its circumference. Some of the lights are on and some of them off; the initial configuration is random. Lisa wins if she can get all of the lights turned on; Bart wins if he can prevent this from happening.

Lisa can take as many turns as she needs to win, or she can give up if it becomes clear to her that Bart can prevent her from winning.

  • Show that if n = 7 and initially at least one light is on and at least one light is off,

then Bart can always prevent Lisa from winning.

  • Show that if n = 8,  then Lisa can always win in at most 8 turns.

Solution