Browse · MathNet
Print51st Ukrainian National Mathematical Olympiad, 4th Round
Ukraine counting and probability
Problem
There is a number of toy kittens in a box. Each kitten has its head and tail painted with one of 2011 colors, not necessarily the same. One can take some kittens out of the box to form a collection. A collection is called "right", if it consists of exactly 2011 kittens so that their heads are painted with different colors, and their tails are also painted with different colors. We know that one can choose a "right" collection of kittens from the box in more than one way. Prove that some kittens (maybe none) can be removed from the box so that there are exactly two ways to choose a "right" collection of kittens from the remaining ones.
Solution
Enumerate the colors with the natural numbers from to . Construct a graph with the vertices . For each kitten we draw an edge in the graph in the following way. If its head is painted with the color , and the tail – with the color , then the edge will join the vertices and . This way, for each kitten there is a corresponding edge in the graph. A "right" collection of kittens corresponds to a subset of edges such that no two edges are adjacent to the same vertex. We call this a "right" subset of edges. What we need is to remove several (or none) edges from the graph in such a way that there will be exactly two "right" subsets of edges in the remaining graph.
By the problem condition, there exist two "right" subsets in the graph. Remove all the edges that do not belong to any of these two subsets. For every "right" subset and every vertex of the graph, we have exactly one edge in the subset that is adjacent to this vertex. So, in the remaining graph, for each vertex we either have an adjacent edge that belongs to both "right" subsets, or we have two adjacent edges, one from each of the "right" subsets. Now, if we have exactly one edge adjacent to a vertex , then the other vertex adjacent to this edge does not have any other adjacent edges. So, the graph is composed of the cycles and isolated edges that do not have common vertices with other edges. Note that every such cycle will have an even length because the edges from the first and the second "right" subsets have to alternate.
Every "right" subset has the following form: it contains all isolated edges, and a half of the edges from each cycle so that these edges do not have common vertices. There are exactly two ways to choose edges from a cycle for a "right" subset. The graph contains at least one cycle, because otherwise there are no two different "right" subsets. If there is more than one cycle, we remove half of the edges (so that the remaining edges have no common vertices) from all of the cycles except one. Clearly, the remaining graph will have exactly one cycle, and hence, exactly two "right" subsets.
By the problem condition, there exist two "right" subsets in the graph. Remove all the edges that do not belong to any of these two subsets. For every "right" subset and every vertex of the graph, we have exactly one edge in the subset that is adjacent to this vertex. So, in the remaining graph, for each vertex we either have an adjacent edge that belongs to both "right" subsets, or we have two adjacent edges, one from each of the "right" subsets. Now, if we have exactly one edge adjacent to a vertex , then the other vertex adjacent to this edge does not have any other adjacent edges. So, the graph is composed of the cycles and isolated edges that do not have common vertices with other edges. Note that every such cycle will have an even length because the edges from the first and the second "right" subsets have to alternate.
Every "right" subset has the following form: it contains all isolated edges, and a half of the edges from each cycle so that these edges do not have common vertices. There are exactly two ways to choose edges from a cycle for a "right" subset. The graph contains at least one cycle, because otherwise there are no two different "right" subsets. If there is more than one cycle, we remove half of the edges (so that the remaining edges have no common vertices) from all of the cycles except one. Clearly, the remaining graph will have exactly one cycle, and hence, exactly two "right" subsets.
Techniques
Matchings, Marriage Lemma, Tutte's theorem