1988 IMO Problems/Problem 2
Problem
Let be a positive integer and let be subsets of a set .
Suppose that
(a) Each has exactly elements,
(b) Each contains exactly one element, and
(c) Every element of belongs to at least two of the .
For which values of can one assign to every element of one of the numbers and in such a way that has assigned to exactly of its elements?
Solution
Answer: All such that
We first make the following claims:
Claim : Each element of union belongs to exactly subsets.
Proof:
Consider a subset . Assume that some element also . There are elements remaining in and there are subsets to choose from. By pigeon hole principle, at least of the remaining elements in must or . This contradicts the assumption that any subsets have only element in common.
Claim :
Proof:
Now, since each element in exactly other subset, total number of elements present in the union = . If each subset must have elements assigned a value of , the total number of elements assigned value of = . Thus must divide .
Now we make our final claim:
Claim : is a sufficient condition to assign every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly zeros.
Proof:
Consider a regular polygon consisting of vertices where each line joining two vertices represents the element which . Clearly there are a total of such lines representing the total number of elements of the union where each vertex is connected to vertices, meaning each of the elements of is part of other subset.
Starting with , let us start coloring all lines joining vertices , with color Red, all lines joining , with color White, , with color Red, , with color White and so on ... , with color White.
Clearly each line from vertex alternates Red, White for first lines and then alternates White, Red for remaining lines implying that we could have exactly red lines emanating from each vertex . But these lines represent elements of each subset which could each be assigned a value of . This completes the proof.
- Kris17
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1988 IMO (Problems) • Resources | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |