1
$\begingroup$

There are n people in a city and each person has 1000 friends (friendship is mutual - if A is a friend of B, then B is a friend of A). Prove that it is possible to choose a group S of people such that at least $$\frac{n}{2023}$$ people from S have exactly 2 friends in S.

I need to solve it using probabilistic method, now I just think that it is not necessary all outcomes to be equally probable, we can group people in S with some probability p, choosing this p correctly..? But I am really stuck with this problem...

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose that we form the random set $S \subseteq [n]$ by picking each person $i \in [n]$ to be in $S$ independently with probability $p > 0$ (to be chosen later). For each $i \in [n]$, let $X_i$ be the random variable counting the number of friends of $i$ that are in $S$. Note that $X_i \sim \mathrm{Binomial}(1000, p)$ for all $i$ (but also note that they are not independent!)

To apply the probabilistic method, we would like to show that probability of our desired event -- i.e. the random set $S$ is such that at least $n / 2023$ people in $S$ have exactly 2 friends in $S$ -- is positive, or with our notation, the following event holds with positive probability: $$ \sum_{i \in [n]} 1_{i \in S, X_i = 2} \geq \frac{n}{2023} . $$ This obviously looks quite complicated to compute exactly, but the key observation is that this event holds with positive probability if we can show a simpler relationship, namely that the expected number of people in $S$ with exactly two friends in $S$ is at least $n / 2023$. (In what follows, I'll assume that $n$ is divisible by $2023$ to simplify away the discreteness of the problem, but some slight modifications can be used for general $n$.)

By linearity of expectation, our aim is to show that $$ \mathbb{E}\left[\sum_{i \in [n]} 1_{i \in S,\, X_i = 2}\right] = \sum_{i \in [n]} \mathbb{P}\left( i \in S, X_i = 2 \right) \geq \frac{n}{2023} $$ Since the two events $i \in S$ and $X_i = 2$ are independent, $\mathbb{P}\left( i \in S, X_i = 2 \right) = \mathbb{P}\left( i \in S \right) \mathbb{P} \left(X_i = 2 \right)$. Hence, by symmetry, this is the same as showing that (for any $i$) $$ f(p) := \mathbb{P}\left( i \in S \right) \mathbb{P} \left(X_i = 2 \right) \geq \frac{1}{2023} . $$ Now perhaps you can try to verify that you can indeed choose $p \in (0, 1)$ such that this holds (hint: $p = 3 / 1001$ works) and wrap up the proof.

$\endgroup$
2
  • $\begingroup$ am I right in assuming that P(X_i = 2) of random variable X_i equals to $${n \choose 2} * p^2 * (1 - p)^{998}$$? $\endgroup$
    – jirraffe
    Commented Nov 14, 2023 at 21:16
  • $\begingroup$ Since we are focusing on a fixed person $i$, it should be $\binom{1000}{2}$ instead of $\binom{n}{2}$, otherwise that's right $\endgroup$
    – JKL
    Commented Nov 15, 2023 at 0:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .