Difference between revisions of "2008 USAMO Problems/Problem 6"
(→Resources: --> see also) |
(→See Also: removed link) |
||
Line 32: | Line 32: | ||
== See Also == | == See Also == | ||
{{USAMO newbox|year=2008|num-b=5|after=Last Problem}} | {{USAMO newbox|year=2008|num-b=5|after=Last Problem}} | ||
− | |||
− | |||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Revision as of 12:58, 6 June 2011
Problem
(Sam Vandervelde) At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form for some positive integer
).
Contents
Solution
Solution 1 (linear algebra)
Make the obvious re-interpretation as a graph. Let be an indicator function with
if a vertex is in the first partition and
otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at
as a function into the field with two elements,
. Let
be the vector space of all such functions. Define the linear operator
as
where denotes adjacency. (Note that we can also think of
as a matrix, which is essentially the adjacency matrix where the diagonal is changed to be
whenever the degree is odd; in more technical terms, it is the Laplacian of
over
). Then
is a valid partition iff
, where
is the degree of
, for all
(this is taken over
). So we want all solution to
. Note that if
, then
, so
is in the nullspace. Thus in particular the number of solutions, if non-zero, is the size of the nullspace of
, which is
by considering all linear combinations of any basis of
over
. Also let
be such that
for all
. Then clearly
, so
, establishing that the number of ways to do this is
,
. Thus we need only prove the existence of a solution.
Since we can add a new vertex connected to exactly one previously existing vertex without changing the problem, without loss of generality all vertices have odd degree. Then we want to show that . But it is a well-known fact in linear algebra that
since
is symmetric. Thus we need to show that if
,
is perpendicular to
and we will be done. So let
. Take the submatrix of
consisting of the rows and columns
such that
. Then, since
, the sum of each row in this submatrix must be
in
. Thus the total number of
s in this submatrix is even. But since it is symmetric, the total number of
s off of the diagonal is even, so the total number of
s on the diagonal is even. But since every vertex has odd degree, the entire diagonal of
consists of
s, so this says that the size of the diagonal of this submatrix is even. But this is also the number of
such that
, so
for an even number of
, thus is perpendicular to
, and we have our result.
Solution 2 (group theory)
Define an order to be a set of instructions, one instruction given to each mathematician. Each mathematician is told to either move or to stay (we can think of this as stay is , and move is
). Now take some good configuration. Consider the set of all orders which, when performed on this configuration, give us another good configuration. Note the identity order,
, is in this set. We claim this set is an abelian group under composition.
Proof: Clearly each is its own inverse, there is the identity, and the operation is clearly associative and commutative (because it's equivalent to addition of n-dimensional vectors ). So it suffices to show this set of orders is closed under composition.
Consider any mathematician. If, in one of these orders, he is told to stay, then the number of his friends who are told to move must be even. Similarly, if he is told to move, then the number of his friends who are told to stay must be even. Now just consider two orders and
and you can show that in
the same property will hold using parity.
Now that we've shown it is a group (which we will call ), we'll prove it has order two. Let
be the identity.
Let , where
is some element of
. Now pick an element
of
which is not in
. Notice that because the elements of
are distinct, the elements of
are distinct (if two elements of that set were the same, multiply by each on the right by
and you have a contradiction). Now notice that for any
, if we were to have
, then
. Therefore,
and
are disjoint and of the same size. Moreover, the product of any element in the first group and any element in the second group is a member of the second group. Therefore, these two groups together form a group of order
. Call this
. You progressively build larger and larger subgroups of
until you get to
itself, whose order must then be a power of two. Therefore, the number of good configurations of the mathematicians was a power of two.
This, of course, was all assuming existed and was in the group.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
2008 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |