Working in a problem in analysis I came across this combinatorial/discrete probability question. I would appreciate if someone knows how to approach this problem or knows if this problem is related with something else.
Let $X=\left\{ x_{1},x_{2},...,x_{N}\right\} $ and $m<M.$ We denote the subsets of size $m$ as $S_{1},...,S_{\binom{N}{m}}.$ Assume $P$ is a real function such that $\sum_{i=1}^{_{\binom{N}{m}}}P(S_{i})=1.$ Now we define $p(x_{j})=\sum_{S_{i}\ni x_{j}}P(s_{i}).$
The question is does there exist $m$ points $x\in X$ such that $p(x)\geq m/N?$ (if it is not true what if we write $2^{-N/m}$ instead of $m/N$)
$$\sum_{j=1}^{N}{p(x_j)} = \sum_{i=1}^{\binom{N}{m}}{m P(S_i)} = m.$$
The first equality is because each $P(S_i)$ appears in exactly $m$ of the $p(x_j)$ terms (since each $S_i$ has $m$ members).
Dividing both ends of the equation by $N$, we see the average of $p(x_j)$ is $\dfrac{m}{N}$. Therefore, for some $j,\; p(x_j) \geq \dfrac{m}{N}$.
Edit #1: A simple counterexample: $N=3, m=2, X=\{1,2,3\}$.
\begin{eqnarray*} S_1 = \{1,2\} && P(S_1) = 1/2 \\ S_2 = \{1,3\} && P(S_2) = 1/2 \\ S_3 = \{2,3\} && P(S_3) = 0. \\ && \\ \therefore \frac{m}{N} = \frac{2}{3} &&\text{ but } p(1) = 1,\; p(2) = \frac{1}{2},\; p(3) = \frac{1}{2}. \end{eqnarray*}
Edit #2: A more complete answer to the question of does there exist a given number of points $x$ such that $p(x) \geq $ some value.
Firstly, we know that the average of all the $p(x)$ is $\frac{m}{N}$ and also that numbers are in the interval $[0,1]$. If we arrange the $N$ $P(x)$ values in ascending order and they had the following values:
$$\underbrace{a,a,\ldots,a}_{N-k \text{ times}},\underbrace{1,1,\ldots,1}_{k \text{ times}}.$$
then we could say that there exists $k+1$ points $x$ with $p(x) \geq a$ for any arrangement where the numbers had that average and those upper and lower bounds.
Since the average is $\dfrac{m}{N}$, we must have $a = \dfrac{m-k}{N-k}$. This is as long as $k \leq m$, otherwise we get $a \lt 0$.
Note that such an arrangement is achievable in terms of the $P(S_i)$ values as follows. Assume $k \leq m$ and nominate a given $k$ elements of $X$. There are $\binom{N-k}{m-k}$ sets $S_i$ containing all $k$ nominated elements since we need to choose the remaining $m-k$ elements of $S_i$ from $N-k$ choices. Set $P(S_i) = \binom{N-k}{m-k}^{-1}$ for each of these. For all other $S_i$, set $P(S_i) = 0$. Then, if $x$ is one of the $k$ nominated elements, we have $p(x) = 1$. If $y$ is not one of the $k$ nominated elements, it appears in exactly $\binom{N-k-1}{m-k-1}$ of the $S_i$ with positive probability since such an $S_i$ contains the $k$ nominated elements and also $y$ and there are $\binom{N-k-1}{m-k-1}$ ways to choose the remaining $m-k-1$ elements. Therefore $p(y) = \binom{N-k-1}{m-k-1} \bigg/ \binom{N-k}{m-k} = \dfrac{m-k}{N-k}$. This completes the above arrangement.
$\\$
To address your particular question, setting $k=m-1$, we get $a = p(y) = \dfrac{m-(m-1)}{N-(m-1)} =\dfrac{1}{N-m+1}$. Therefore, we can say that, for any assignment of the $P(S_i)$ values, there exists $m$ points $x$ such that $p(x) \geq \dfrac{1}{N-m+1}$.