red and blue segments, key pressing, computer screen
Source: Brazilian Mathematical Olympiad 1988 P5
July 26, 2018
combinatoricsgame strategyColoring
Problem Statement
A figure on a computer screen shows points on a sphere, no four coplanar. Some pairs of points are joined by segments. Each segment is colored red or blue. For each point there is a key that switches the colors of all segments with that point as endpoint. For every three points there is a sequence of key presses that makes the three segments between them red. Show that it is possible to make all the segments on the screen red. Find the smallest number of key presses that can turn all the segments red, starting from the worst case.