In a television series about incidents in a conspicuous town there are $n$ citizens staging in it, where $n$ is an integer greater than $3$. Each two citizens plan together a conspiracy against one of the other citizens. Prove that there exists a citizen, against whom at least $\sqrt{n}$ other citizens are involved in the conspiracy.
Problem
Source: MOP 2005 Homework - Red Group #10
Tags: function, combinatorics unsolved, combinatorics
thepurplelefant
18.05.2014 16:41
I don't thik this is true. If we have 5 persons then we would need one to have 3 against him. so we assign to the pairs: (1,2)=5 (1,3)=2 (1,4)=3 (1,5)=4 (2,3)=1 (2,4)=3 (2,5)=4 (3,4)=5 (3,5)=1 (4,5)=2 So every one is the target of exactly 2 conspiracies and no one is the target of 3.
manuel153
18.05.2014 17:06
thepurplelefant wrote: I don't thik this is true. If we have 5 persons then we would need one to have 3 against him. so we assign to the pairs: (1,2)=5 (3,4)=5 But in your example there are $4>\sqrt{5}$ citizens involved in the conspiracy against citizen #$5$.
AnonymousBunny
02.09.2014 08:22
There are $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ pairs, so by PHP at least $\dfrac{n-1}{2}$ of them must conspire against a particular citizen. Then we clearly have $\dbinom{N}{2} \geq \dfrac{n-1}{2}$ where $N$ denotes the number of people conspiring against that particular citizen. From here we easily get that $N >\sqrt{n}$ (simply note that the function $f(x) = x(x-1)$ is strictly increasing in $\mathbb{R}^+$ and $f(\sqrt{n}) = n - \sqrt{n} < n-1$). $\blacksquare$
Abra_Kadabra
25.12.2020 01:27
Since there are $\binom{n}{2}$ total conspiracies, there are at least $\frac{\binom{n}{2}}{n}=\frac{n-1}{2}=x$ conspiracies against a particular person (this is the average number of conspiracies against a person)(if it doesn't make sense why there should be a person with at least $x$ conspiracies against them, consider the alternative). If $\sqrt{n}<x$, then we are done.
Solving the given inequality:
$\sqrt{n}<x=\frac{n-1}{2}$
$4n<n^{2}-2n+1$
$0<n^{2}-6n+1=(n-3)^{2}-8$
$8<(n-3)^{2}$
$n-3>\sqrt{8}$ (since $n>3$)
$n>3+\sqrt{8}$
$n \ge 6$ (since $n$ is an integer)
It's easy to check that $n=4$ works, but unfortunately $n=5$ does not work (I think there is a typo in the problem).
n=4Assume to the contrary (that every person has at most 1 conspiracy against them (because $\sqrt{4}-1=1$)). This is a contradiction because then, there are at most 4 total conspiracies (1 for each person), but there are $\binom{4}{2}=6$ total conspiracies.
Vitriol
03.01.2021 08:34
Assume for the sake of contradiction the contrary. Then for each citizen $C$, there are fewer than $\sqrt{n}$ other citizens in a conspiracy against them, so fewer than $\binom{\sqrt{n}}{2}$ conspiring pairs. It follows that there are fewer than $n\binom{\sqrt{n}}{2}$ pairs in total, so \[ \frac{n(n-1)}{2} = \binom{n}{2} < n\binom{\sqrt{n}}{2} = \frac12 n \cdot \sqrt{n} (\sqrt{n} - 1) = \frac{n(n-\sqrt{n})}{2},\]id est $\sqrt{n} < 1$, contradiction. $\blacksquare$