In the Flower-city there are $ n$ squares and $ m$ streets, where $ m \geq n + 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.
Problem
Source: Russia 1994
Tags: combinatorics unsolved, combinatorics
pythag011
08.10.2008 03:03
Consider the number of street namings for which it is possible to get the namings from an initial naming where all the streets are named the same thing. We will show this number is less than the total number of street namings.
For each square, consider the number of times the square has been selected. If it is odd, call the square ON. if it is even, call the square OFF.
Note that the state of each square automattically determines the naming given the initial naming. This is because, if we assign numbers to every street so that streets are red if and only if their integer is odd, changing the state of a square is really just adding 1 to every street next to it, changing the state twice will not change any of the streets.
Therefore, the number of namings starting from an initial position (and being able to get back to the initial position) is equal to 2*2^n (The two is because we have two possible initial positions: all red and all blue.)
The total number of namings is (n+1)!, which is greater than 2*2^n when n is greater than or equal to 3.
If n is 1, then there can be no streets, and 0 < 1+1
If n is 2, then there can only be 1 street, and 1 < 2+1.
outback
08.10.2008 17:37
pythag011 wrote: The total number of namings is (n+1)!, I don't agree with this. Each street is named either "blue" or "red"...
pythag011
09.10.2008 01:17
Oops. Change it to 2^(n+1) But the number of street namings for which it is possible to get the namings from an initial naming where all the streets are named the same thing is less than this. I claim it is less than or equal to 2*(2^n-1) this is because when everything is on, it is the same naming as when everything is off.
parmenides51
26.08.2024 10:18
solved also here