naming streets
Source: Russia 1994
October 7, 2008
combinatorics unsolvedcombinatorics
Problem Statement
In the Flower-city there are squares and streets, where m \geq n \plus{} 1. Each street connects two squares and does not pass through other squares.
According to a tradition in the city, each street is named either blue or red. Every year, a square is selected and the names of all streets emanating from that square are changed. Show that the streets can be initially named in such a way that, no matter how the names will be changed, the streets will never all have the same name.