Difference between revisions of "2008 USAMO Problems/Problem 6"
Parityhome (talk | contribs) (→Solution 4 (proving only existence of solution)) |
|||
(3 intermediate revisions by 2 users not shown) | |||
Line 2: | Line 2: | ||
(''[[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 <math>2^k</math> for some positive integer <math>k</math>). | (''[[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 <math>2^k</math> for some positive integer <math>k</math>). | ||
− | + | == Solutions == | |
− | |||
=== Solution 1 (linear algebra) === | === Solution 1 (linear algebra) === | ||
Make the obvious re-interpretation as a [[graph]]. Let <math>f : G \to \{0,1\}</math> be an [[indicator function]] with <math>f(v) = 0</math> if a vertex is in the first [[partition]] and <math>f(v) = 1</math> otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at <math>f</math> as a function into the [[field]] with two elements, <math>F_2</math>. Let <math>V</math> be the [[vector space]] of all such functions. Define the linear operator <math>A : V \to V</math> as | Make the obvious re-interpretation as a [[graph]]. Let <math>f : G \to \{0,1\}</math> be an [[indicator function]] with <math>f(v) = 0</math> if a vertex is in the first [[partition]] and <math>f(v) = 1</math> otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at <math>f</math> as a function into the [[field]] with two elements, <math>F_2</math>. Let <math>V</math> be the [[vector space]] of all such functions. Define the linear operator <math>A : V \to V</math> as | ||
Line 27: | Line 26: | ||
This, of course, was all assuming <math>I</math> existed and was in the group. | This, of course, was all assuming <math>I</math> existed and was in the group. | ||
+ | === Solution 3 === | ||
+ | Let <math>n</math> be the number of participants at the conference. We proceed by induction on <math>n</math>. | ||
+ | |||
+ | If <math>n = 1</math>, then we have one participant who can eat in either room; that gives us a total of <math>2 = 2^1</math> options. | ||
+ | |||
+ | Let <math>n\geq 2</math>. The case in which some participant, <math>P</math>, has no friends is trivial. In this case, <math>P</math> can eat in either of the two rooms, so the total number of ways to split <math>n</math> participants is twice as many as the number of ways to split <math>(n - 1)</math> participants besides the participant <math>P</math>. By induction, the latter number is a power of two, <math>2^k</math>, hence the number of ways to split <math>n</math> participants is <math>2\times 2^k = 2^{k+1}</math>, also a power of two. So we assume from here on that every participant has at least one friend. | ||
+ | |||
+ | We consider two different cases separately: the case when some participant has an odd number of friends, and the case when each participant has an even number of friends. | ||
+ | |||
+ | '''Claim:''' Some participant, <math>Z</math>, has an odd number of friends. | ||
+ | |||
+ | Remove <math>Z</math> from consideration and for each pair <math>(X,Y)</math> of <math>Z</math>'s friends, reverse the relationship between <math>X</math> and <math>Y</math> (from friends to strangers or vice versa). | ||
+ | |||
+ | '''Claim.''' The number of possible seatings is unchanged after removing <math>Z</math> and reversing the relationship between <math>X</math> and <math>Y</math> in each pair <math>(X,Y)</math> of <math>Z</math>'s friends. | ||
+ | |||
+ | ''Proof of the claim.'' Suppose we have an arrangement prior to <math>Z</math>'s departure. By assumption, <math>Z</math> has an even number of friends in the room with him. | ||
+ | |||
+ | If this number is 0, the room composition is clearly still valid after <math>Z</math> leaves the room. | ||
+ | |||
+ | If this number is positive, let <math>X</math> be one of <math>Z</math>'s friends in the room with him. By assumption, person <math>X</math> also has an even number of friends in the same room. Remove <math>Z</math> from the room; then <math>X</math> will have an odd number of friends left in the room, and there will be an odd number of <math>Z</math>'s friends in this room besides <math>X</math>. Reversing the relationship between <math>X</math> and each of <math>Z</math>'s friends in this room will therefore restore the parity to even. | ||
+ | |||
+ | The same reasoning applies to any of <math>Z</math>'s friends in the other dining room. Indeed, there will be an odd number of them in that room, hence each of them will reverse relationships with an even number of individuals in that room, preserving the parity of the number of friends present. | ||
+ | |||
+ | Moreover, a legitimate seating without <math>Z</math> arises from exactly one arrangement including <math>Z</math>, because in the case under consideration, only one room contains an even number of <math>Z</math>'s friends. | ||
+ | |||
+ | '''End Claim''' | ||
+ | |||
+ | Thus, we have to double the number of seatings for <math>(n - 1)</math> participants which is, by the induction hypothesis, a power of 2. Consequently, for <math>n</math> participants we will get again a power of 2 for the number of different arrangements. | ||
+ | |||
+ | '''Case 2:''' Each participant has an even number of friends. | ||
+ | |||
+ | In this case, each valid split of participants in two rooms gives us an even number of friends in either room. | ||
+ | |||
+ | Let <math>(A,B)</math> be any pair of friends. Remove this pair from consideration and for each pair <math>(C,D)</math>, where <math>C</math> is a friend of <math>A</math> and <math>D</math> is a friend of <math>B</math>, change the relationship between <math>C</math> and <math>D</math> to the opposite; do the same if <math>C</math> is a friend of <math>B</math> and <math>D</math> is a friend of <math>A</math>. Note that if <math>C</math> and <math>D</math> are friends of both <math>A</math> and <math>B</math>, their relationship will be reversed twice, leaving it unchanged. | ||
+ | |||
+ | Consider now an arbitrary participant <math>X</math> different from <math>A</math> and <math>B</math> and choose one of the two dining rooms. [Note that in the case under consideration, the total number of participants is at least 3, so such a triplet <math>(A, B; X)</math> can be chosen.] Let <math>A</math> have <math>m</math> friends in this room and let <math>B</math> have <math>n</math> friends in this room; both <math>m</math> and <math>n</math> are even. When the pair <math>(A, B)</math> is removed, <math>X</math>'s relationship will be reversed with either <math>n</math>, or <math>m</math>, or <math>m + n - 2k</math> (for <math>k</math> the number of mutual friends of <math>A</math> and <math>B</math> in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only <math>A</math>, only <math>B</math>, both, or neither). Since <math>m</math> and <math>n</math> are both even, the parity of the number of <math>X</math>'s friends in that room will be therefore unchanged in any case. | ||
+ | |||
+ | Again, a legitimate seating without <math>A</math> and <math>B</math> will arise from exactly one arrangement that includes the pair <math>(A, B)</math>: just add each of <math>A</math> and <math>B</math> to the room with an odd number of the other's friends, and then reverse all the relationships between a friend of <math>A</math> and a friend of <math>B</math>. In this way we create a one-to-one correspondence between all possible seatings before and after the <math>(A,B)</math> removal. | ||
+ | |||
+ | Since the number of arrangements for <math>n</math> participants is twice as many as that for <math>(n - 2)</math> participants, and that number for <math>(n - 2)</math> participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for <math>n</math> participants. The problem is completely solved. | ||
+ | |||
+ | === Solution 4 (proving only existence of solution) === | ||
+ | By induction on the number of mathematicians, assuming solution exists for <math>n\leq k</math> mathematicians. For <math>n=k+1</math> mathematicians, if each of them has even degree then we're done. Otherwise, let <math>v</math> be a node with odd degree, and denote its neighbors by <math>N(v)</math>. We form a new graph <math>G'</math> by deleting <math>v</math> and flipping all edges between members of <math>N(v)</math>. That is, for each pair of <math>a</math> and <math>b</math> in <math>N(v)</math>, they're connected in <math>G'</math> if and only if they're not in <math>G</math>. By induction we know a solution <math>S'</math> exists for <math>G'</math>, and it is easily verifiable that the similar solution <math>S</math> exists in <math>G</math> by adding <math>v</math> to the side in <math>S'</math> with even number of neighbors in <math>N(v)</math>. | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | == See | + | == See also == |
− | {{USAMO newbox|year=2008|num-b=5|after=Last | + | * <url>viewtopic.php?t=202908 Discussion on AoPS/MathLinks</url> |
+ | |||
+ | {{USAMO newbox|year=2008|num-b=5|after=Last Question}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 14:37, 11 July 2016
Contents
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
).
Solutions
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.
Solution 3
Let be the number of participants at the conference. We proceed by induction on
.
If , then we have one participant who can eat in either room; that gives us a total of
options.
Let . The case in which some participant,
, has no friends is trivial. In this case,
can eat in either of the two rooms, so the total number of ways to split
participants is twice as many as the number of ways to split
participants besides the participant
. By induction, the latter number is a power of two,
, hence the number of ways to split
participants is
, also a power of two. So we assume from here on that every participant has at least one friend.
We consider two different cases separately: the case when some participant has an odd number of friends, and the case when each participant has an even number of friends.
Claim: Some participant, , has an odd number of friends.
Remove from consideration and for each pair
of
's friends, reverse the relationship between
and
(from friends to strangers or vice versa).
Claim. The number of possible seatings is unchanged after removing and reversing the relationship between
and
in each pair
of
's friends.
Proof of the claim. Suppose we have an arrangement prior to 's departure. By assumption,
has an even number of friends in the room with him.
If this number is 0, the room composition is clearly still valid after leaves the room.
If this number is positive, let be one of
's friends in the room with him. By assumption, person
also has an even number of friends in the same room. Remove
from the room; then
will have an odd number of friends left in the room, and there will be an odd number of
's friends in this room besides
. Reversing the relationship between
and each of
's friends in this room will therefore restore the parity to even.
The same reasoning applies to any of 's friends in the other dining room. Indeed, there will be an odd number of them in that room, hence each of them will reverse relationships with an even number of individuals in that room, preserving the parity of the number of friends present.
Moreover, a legitimate seating without arises from exactly one arrangement including
, because in the case under consideration, only one room contains an even number of
's friends.
End Claim
Thus, we have to double the number of seatings for participants which is, by the induction hypothesis, a power of 2. Consequently, for
participants we will get again a power of 2 for the number of different arrangements.
Case 2: Each participant has an even number of friends.
In this case, each valid split of participants in two rooms gives us an even number of friends in either room.
Let be any pair of friends. Remove this pair from consideration and for each pair
, where
is a friend of
and
is a friend of
, change the relationship between
and
to the opposite; do the same if
is a friend of
and
is a friend of
. Note that if
and
are friends of both
and
, their relationship will be reversed twice, leaving it unchanged.
Consider now an arbitrary participant different from
and
and choose one of the two dining rooms. [Note that in the case under consideration, the total number of participants is at least 3, so such a triplet
can be chosen.] Let
have
friends in this room and let
have
friends in this room; both
and
are even. When the pair
is removed,
's relationship will be reversed with either
, or
, or
(for
the number of mutual friends of
and
in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only
, only
, both, or neither). Since
and
are both even, the parity of the number of
's friends in that room will be therefore unchanged in any case.
Again, a legitimate seating without and
will arise from exactly one arrangement that includes the pair
: just add each of
and
to the room with an odd number of the other's friends, and then reverse all the relationships between a friend of
and a friend of
. In this way we create a one-to-one correspondence between all possible seatings before and after the
removal.
Since the number of arrangements for participants is twice as many as that for
participants, and that number for
participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for
participants. The problem is completely solved.
Solution 4 (proving only existence of solution)
By induction on the number of mathematicians, assuming solution exists for mathematicians. For
mathematicians, if each of them has even degree then we're done. Otherwise, let
be a node with odd degree, and denote its neighbors by
. We form a new graph
by deleting
and flipping all edges between members of
. That is, for each pair of
and
in
, they're connected in
if and only if they're not in
. By induction we know a solution
exists for
, and it is easily verifiable that the similar solution
exists in
by adding
to the side in
with even number of neighbors in
.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=202908 Discussion on AoPS/MathLinks</url>
2008 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.