The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
Consider $2n$ committees, each having at least $2n$ persons, formed from a group of $4n$ persons. Prove that there exists at least one person who belongs to at least $n$ committees.
asked in Others by Junior (667 points)
edited by | 145 views

1 Answer

+4 votes
Best answer

This problem is modeled as a bipartite graph.

  1. $2n$ vertices represent $2n$ committees.
  2. $4n$ vertices represent $4n$ people.

We have,

$$\begin{align*} &\Rightarrow \sum d_i = 2E \\ &\Rightarrow {\color{red}{\sum d_{x_i}}} + {\color{blue}{\sum d_{y_i}}}= 2E \\ &\Rightarrow {\color{red}{\sum d_{x_i}}} + {\color{blue}{\sum d_{y_i}}} = 2.{\color{red}{\sum d_{x_i}}} \\ &\Rightarrow {\color{blue}{\sum d_{y_i}}} = {\color{red}{\sum d_{x_i}}} \\ &\Rightarrow {\color{blue}{\sum_{\;}^{4n} d_{y_i}}} = \left ( 4n^2 \right )_{\text{min}} \\ &\Rightarrow 4n.\left ( d_{\text{people}} \right )_{\text{average}} = \left ( 4n^2 \right )_{\text{min}}\\ &\Rightarrow \left ( d_{\text{people}} \right )_{\text{average}} = n_{\text{min}} \\ \end{align*}$$

$$\begin{align*} &\Rightarrow \exists y \in {\text{\{People\}}} \text{ such that } d_y \geq n \\ \end{align*}$$

answered by Veteran (56.6k points)
selected by

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,136 questions
43,587 answers
42,832 users