Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1995 USAMO Problems/Problem 5"

m (→‎See Also)
(→‎Solution)
 
(2 intermediate revisions by one other user not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Consider the graph with two people joined if they are friends.
 +
 
 +
For each person <math>X</math>, let <math>A(X)</math> be the set of its friends and <math>B(X)</math> the set of its foes. Note that any edge goes either: from <math>X</math> to <math>A(X)</math> (type 1), from <math>A(X)</math> to <math>B(X)</math> (type 2) or from a point of <math>B(X)</math> to another (type 3), but there's no edge joining two points of <math>A(X)</math> (since they would form a triangle with <math>X</math>). Let the number of type 1, type 2, type 3 edges of <math>X</math> be <math>x_1, x_2, x_3</math> respectively, so that <math>x_1</math> is the degree of <math>X</math> and we want to show that for some <math>X</math>, we have <math>x_3 \leq q(1-4q/n^2)</math>.
 +
 
 +
Since each edge is of one of those types, we have <math>x_1+x_2+x_3=q</math>. Thus
 +
<cmath> x_3 \leq q(1-4q/n^2) \Longleftrightarrow \\ x_3 \leq q-4q^2/n^2 \Longleftrightarrow \\ q-x_1-x_2 \leq q-4q^2/n^2 \Longleftrightarrow \\ x_1+x_2 \geq 4q^2/n^2. </cmath>
 +
That is, what we want is equivalent to proving that for some vertex <math>X</math>, the set of edges touching either <math>X</math> or a vertex joined to <math>X</math> is at least <math>4q^2/n^2</math>. Obviously now we'll sum <math>x_1+x_2</math> over all vertices <math>X</math>. In the resulting sum, an edge joining <math>X, Y</math> is counted once for each edge that <math>X, Y</math> have, that is, it is counted <math>D(X)+D(Y)</math> times, where <math>D(X)=x_1</math> is the degree of <math>X</math>. Thus each vertex <math>X</math> contributes to the overall sum with <math>D(X)</math> for each edge it has, and since it has <math>D(X)</math> edges, it contributes with <math>D(X)^2</math>. Thus the considered sum is equal to
 +
<cmath> \sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n. </cmath>
 +
(That's Cauchy.) Since we are summing over <math>n</math> vertices, one of the summands is at least <math>4q^2/n^2</math> by pigeonhole, which is what we wanted to prove.
 +
 
 +
{{alternate solutions}}
  
 
==See Also==
 
==See Also==

Latest revision as of 20:56, 12 November 2023

Problem

Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a foe of the other. Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.

Solution

Consider the graph with two people joined if they are friends.

For each person $X$, let $A(X)$ be the set of its friends and $B(X)$ the set of its foes. Note that any edge goes either: from $X$ to $A(X)$ (type 1), from $A(X)$ to $B(X)$ (type 2) or from a point of $B(X)$ to another (type 3), but there's no edge joining two points of $A(X)$ (since they would form a triangle with $X$). Let the number of type 1, type 2, type 3 edges of $X$ be $x_1, x_2, x_3$ respectively, so that $x_1$ is the degree of $X$ and we want to show that for some $X$, we have $x_3 \leq q(1-4q/n^2)$.

Since each edge is of one of those types, we have $x_1+x_2+x_3=q$. Thus \[x_3 \leq q(1-4q/n^2) \Longleftrightarrow \\ x_3 \leq q-4q^2/n^2 \Longleftrightarrow \\ q-x_1-x_2 \leq q-4q^2/n^2 \Longleftrightarrow \\ x_1+x_2 \geq 4q^2/n^2.\] That is, what we want is equivalent to proving that for some vertex $X$, the set of edges touching either $X$ or a vertex joined to $X$ is at least $4q^2/n^2$. Obviously now we'll sum $x_1+x_2$ over all vertices $X$. In the resulting sum, an edge joining $X, Y$ is counted once for each edge that $X, Y$ have, that is, it is counted $D(X)+D(Y)$ times, where $D(X)=x_1$ is the degree of $X$. Thus each vertex $X$ contributes to the overall sum with $D(X)$ for each edge it has, and since it has $D(X)$ edges, it contributes with $D(X)^2$. Thus the considered sum is equal to \[\sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n.\] (That's Cauchy.) Since we are summing over $n$ vertices, one of the summands is at least $4q^2/n^2$ by pigeonhole, which is what we wanted to prove.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1995 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_USAMO_Problems/Problem_5&oldid=202843"