On the size of intersection of subsets I want to prove/disprove the following statement: 
Consider $s+1$ arbitrary sets $A_i\subseteq \{1,2,\dots,s\}$, $i\in\{1,2,\dots,s+1\}$. There always exist a set $P\subseteq\{1,2,\dots,s+1\}$ such that $$\Big|\bigcap_{i\in P}A_i\Big|=|P|-1$$
I tried small value of $s$(up to 6) and showed that such $P$ does always exist. I wonder if the above statement can be proved/disproved for general case.
Thanks in advance!
 A: The statement in question is true, and this is how it can be proven.
For convenience, let $B=\{b_1,b_2,\dots,b_s\}$ be the base set on which the sets $A_1,A_2,\dots,A_{s+1}$ are defined (instead of $\{1,2,\dots,s\}$ in original statement). First of all, note that if $A_i=\varnothing$ for some $i$, then $P=\{i\}$ is a suitable subset of indices. Thus, we can consider only the case when all of $A_i$ are nonempty. Let's apply induction on $s$.
The base case, $s=1$, is clear: $A_1=A_2=\{b_1\}$ and we can take $P=\{1,2\}$.
To apply the inductive step for any $s>1$, we need the following lemma.
Lemma. Let $A_1,A_2,\dots,A_m$ be nonempty subsets of some finite set $B=\{b_1,b_2,\dots,b_n\}$. If $\langle b \rangle \stackrel{\text{def}}= \left|\left\{j \mid b \in A_j \right\}\right|$ for any $b \in B$, then there exists a pair $(b_i, A_j)$ such that $b_i \in A_j$ and $$\frac m n \le \frac {\langle b_i \rangle}{|A_j|}.$$
Proof of lemma. Consider the matrix $X_{n \times m} = (x_{ij})$, where
$$x_{ij} = \begin{cases}
\dfrac 1 {|A_j|}, & b_i \in A_j \\
\phantom{-} 0, & b_i \notin A_j
\end{cases}$$
As each $A_j$ is nonempty, the sum of each column's elements of this matrix equals to $1$ (it is the sum of $|A_j|$ identical elements). Thus, the sum of all elements in $X$ is exactly $m$.
On the other hand, counting this sum by rows, we should obtain the same result. Let $i$ be the index of the row having the largest sum in it. This sum is not less than the average of all row sums: $$\frac m n \le \sum_{j\,:\,b_i \in A_j} \frac 1 {|A_j|},$$and of course it is not empty, therefore taking $j$ with the smallest $|A_j|$ among all $j$'s such that $b_i \in A_j,$ we get the right side of the last inequality bounded by $\frac {\langle b_i \rangle}{|A_j|}$, just what we need. $\blacksquare$
Returning to the proof of main statement, we can apply the lemma to $n = s$, $m = s + 1$, thus finding an element $b_i$ and a set $A_j$ containing it, such that $$1 < \frac {s+1} s \le \frac {\langle b_i \rangle}{|A_j|}.$$ This means that the number of sets containing $b_i$ is strictly greater than the size of one of them, $A_j$. Let $t = |A_j|$. We have a set $A_j$ containing $b_i$ and at least $t$ other sets containing it, so there is a set of indices $K \!\not\owns j$ such that $|K|\! = t$ and $\forall k \in K \!\!: b_i\in A_k$.
The case $t = 1$ is obvious: $P = \{j\} \cup K$.
Let $t>1$. Since $t+1 \le s+1 \implies t-1<s$, we can apply the statement to $s' = t - 1$, $B' = A_j \setminus \{b_i\}$ and $\{A'_1,A'_2,\dots,A'_{s'+1}\}=\{A_k \cap B' \mid k \in K\}$. This gives us $P' \subseteq \{1,2,\dots,t\}$ such that $|\bigcap_{q \in P'}A'_q|=|P'|-1$. Now take $P = \{j\} \cup P''$, where $P''$ is a subset of $K$ corresponding to $P'$ (i.e. $q \in P' \leftrightarrow k \in P'', A'_q = A_k \cap B'$), and note that $$\bigcap_{k \in P}A_k = \{b_i\} \cup \bigcap_{q \in P'}A'_q,$$where the union is disjoint, just like in $P = \{j\} \cup P''$. Thus, $$|\bigcap_{k \in P}A_k| = 1 + (|P'| - 1) = |P'| = |P''| = |P| - 1.$$
