USAMO 1985 #4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

USAMO 1985 #4

G H J

Reveal topic tags

ceiling function

algebra unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5123 posts

#1 h Jul 26, 2011, 7:11 PM • 2 Y

Y by Adventure10, Mango247

There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\left\lfloor\frac{n}{2}\right\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Assume that knowing is a symmetric relation, and that $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$ .

This post has been edited 1 time. Last edited by djmathman, Dec 20, 2016, 9:07 PM
Reason: Replaced this with @tenniskidperson's wording (which according to the official contest problem booklet is correct)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#2 h Jul 27, 2011, 11:25 AM • 2 Y

Y by Adventure10, Mango247

For each vertex $v$ there are $d = \deg v$ neighbours and $n-1-d$ non-neighbours. Together they account for $\binom {d} {2} + \binom {n-1-d} {2} \geq \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil$ configurations of interest.
Thus in total there are at least $n \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil$ such configurations. Since there are $\binom {n} {2} = \dfrac {n(n-1)} {2}$ ways to choose points $A,B$ , to at least one pair correspond at least $\dfrac {n \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil} {\dfrac {n(n-1)} {2}} = \left \lfloor \dfrac {n-2} {2} \right \rfloor$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4594 posts

1=2

#3 h Sep 17, 2012, 6:46 PM • 1 Y

Y by Adventure10

This problem is a restatement of this problem. Which problem is the real #4?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#4 h Sep 18, 2012, 1:27 AM • 1 Y

Y by Adventure10

This on page 2 has the problem as

There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\left\lfloor\frac{n}{2}\right\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Assume that knowing is a symmetric relation, and that $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$ .

It's a different problem statement from Kalva, so it's probably right, but I don't know if I'd trust it enough to put it in the contest section.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

396 posts

#5 h Feb 16, 2021, 3:04 AM

Y by

Mrdavid445 wrote:

There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\left\lfloor\frac{n}{2}\right\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Assume that knowing is a symmetric relation, and that $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$ .

Can anyone tell some good solution??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4214 posts

#7 h Today at 4:48 AM • 2 Y

Y by Leo.Euler, Amkan2022

@above i gotchu lil bro

Let two people knowing each other be denoted by an edge in a graph.

Then, every group of $3$ people falls into one of the four categories below:

https://i.postimg.cc/NM2QbN0C/image.png

where a "+1" indicates a pair of people who gain a person who knows both or neither of them.

Then, we wish to show that $3A+B+C+3D> \binom{n}{2}(\lfloor \frac{n}2\rfloor-2)$ .

Clearly, $A+B+C+D=\binom{n}{3}$ so $3A+3B+3C+3D=3\binom{n}3=(n-2)\binom{n}2$ .

Therefore, we wish to prove that $2B+2C<\binom{n}2(n-\lfloor \frac{n}2\rfloor)$ .

Note that every group of $3$ which falls in category $B$ or $C$ has $2$ people which each know exactly one of the other $2$ people in the group.

Therefore, $2(B+C)=\sum_v (\deg v (n-1-\deg v))$ .

When $n=2k+1$ , $2(B+C)=\sum_v (\deg v (n-1-\deg v))\le (2k+1)k^2<(2k+1)k(k+1)=\binom{n}2(n-\lfloor \frac{n}2\rfloor)$ .

When $n=2k$ , $2(B+C)=\sum_v (\deg v (n-1-\deg v))\le (2k+1)(k-1)k<k(2k-1)k=\binom{n}2(n-\lfloor \frac{n}2\rfloor)$ .

Note that $(2k+1)(k-1)k<k(2k-1)k$ because $\frac{2k+1}{2k-1}<\frac{k}{k-1}$ because $\frac{2}{2k-1}<\frac{1}{k-1}$ .

This post has been edited 1 time. Last edited by RedFireTruck, Today at 4:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

73 posts

#8 h 5 hours ago

Y by

Didn't see a Probabilistic solution, so here you go.
Let the sample space be $\Omega$ defined as $\Omega=\{\text{All the unordered pairs of people.}\}.$ Also we define a clever random variable $X:\Omega\to\{0,1,\ldots, n-2\}$ such that
$X\overset{\mathrm{def}}{=} \begin{cases} \parbox{.3\linewidth}{$\#$ People among the remaining $n-2$ people who are acquainted to both or neither.}\\[3ex] \end{cases}$ Our goal is to show that $\mathbb{E}[X]\ge \left\lfloor\frac{n}{2}\right\rfloor-1$ , as it will automatically assure the existence of two such people. But computing $\mathbb{E}[X]=\sum_{v\in V}v\mathbb{P}[X=v]$ seems to be a pain in the as*, not a big deal as linearity of $\mathbb{E}[X]$ is a boon. We shall introduce auxillary random variables $X_i:\Omega\to\{0,1\}$ for $i=1,2,\ldots,n-2$ which will help in the computation, consider
$X_i\overset{\mathrm{def}}{=} \begin{cases} 0 & \parbox{.3\linewidth}{if $i^{\text{th}}$ person among the remaining is acquainted to exactly one of them,}\\[3ex] 1 & \text{otherwise.} \end{cases}$ Notice $\mathbb{P}[X_i=v]=1/2$ . As $\displaystyle X=\sum_{1\le i\le n-2}X_i$ and using the boon we mentioned earilier we have the following,
$\mathbb{E}[X]=\mathbb{E}\left[\sum_{1\le i\le n-2}X_i\right]=\sum_{1\le i\le n-2}\mathbb{E}[X_i]=\sum_{v\in V}v\mathbb{P}[X_i=v]=\cfrac{n-2}{2}\ge \left\lfloor\cfrac{n}{2}\right\rfloor-1.$ And we are done. $\square$

Note. $V$ is a classic way to represent the range of a random variable and $v$ is an element of $V$ .

This post has been edited 2 times. Last edited by anudeep, 5 hours ago

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a