Q:

Intersection with even cardinality

For any natural $n \geq 2$ find the smallest integer $k$, such that from any $k$ different subsets of $\lbrace1,2, \dots, n \rbrace$ with even cardinality, exist at least two, with intersection which cardinality is even.

I'm trying to do that with friend, but we can't find any way.
It looks, like answer is $n$ or $n+1$, depending on the rest of the division $n$ by two. But the point is to prove it. Have you any idea for it? Everything which seems to be that, what should work - disappointing.

I spend long time on induction proof, but it's road to Perdition. In fact, attempt with proof for odd only was hopeful, especially, that as far I know, friend proved, if it is correct for odd numbers it's correct for any number.  But on the end still way to nowhere.
I tried use combinatorics, but I caught up on using this thesis in proof. So I know, if it's correct it is correct.
Apparently it is easy example of some theorem, but I'm not mathematician, just a hobbyist, who is bothered by the above question. Do you know this theorem, or just know how to prove it? I will be glad for explanation.

It is former question from LXVI OM [PL].

A:

In the comments Steve Kass has shown that $n$ is a lower bound for $k$ when $n$ is even, and that $n+1$ is a lower bound for $k$ when $n$ is odd.
I will say that a finite set is even if its cardinality is even, and odd if its cardinality is odd. Also, I use $\mathbin{\triangle}$ for symmetric difference.

Lemma. Let $n\in\Bbb Z^+$, and let $A_1,\ldots,A_m$ be subsets of $[n]$. Let $A=A_1\mathbin{\triangle}\ldots\mathbin{\triangle}A_m$. Then $A$ is even iff $\sum_{i=1}^m|A_i|$ is even.
Proof. For each $k\in[n]$ let $a_k=|\{i\in[m]:k\in A_i\}|$. Then $\sum_{k\in[n]}a_k=\sum_{i\in[m]}|A_i|$: both are simply the number of ordered pairs $\langle k,A_i\rangle$ such that $k\in A_i$. Thus, $\sum_{i\in[m]}|A_i|$ is even iff $\sum_{k\in[n]}a_k$ is even, which is the case iff the number of odd terms $a_k$ is even. But $a_k$ is odd iff $k\in A$, and the result follows. $\dashv$

Suppose that $n$ is even, and let $A_1,\ldots,A_n$ be even subsets of $[n]$. Suppose that for each non-empty $I\subseteq[n]$, $\triangle_{i\in I}A_i\ne\varnothing$. Each $A_i$ is even, so $\sum_{i\in I}|A_i|$ is even, and by the lemma $\triangle_{i\in I}A_i$ is even. There are more non-empty sets $I\subseteq[n]$ than there are even subsets of $[n]$, so there are distinct $J,K\subseteq[n]$ such that $\triangle_{i\in J}A_i=\triangle_{i\in K}A_i$. Let $I=J\mathbin{\triangle}K\ne\varnothing$. Then
$$\triangle_{i\in I}A_i=(\triangle_{i\in J}A_i)\mathbin{\triangle}(\triangle_{i\in K}A_i)=\varnothing\;.$$
Suppose first that $I$ is even. Fix $i_0\in I$, and for $i\in I$ let $B_i=A_{i_0}\cap A_i$. Suppose that some $k\in[n]$ belongs to an odd number of the sets $B_i$. Then $k\in A_{i_0}=B_{i_0}$, so $k$ is in an even number of the sets $B_i$ with $i\ne i_0$ and hence in an even number of the sets $A_i$ with $i\in I\setminus\{i_0\}$. But then $k$ is in an odd number of the sets $A_i$ with $i\in I$, so $k\in\triangle_{i\in I}A_i=\varnothing$, which is absurd. Thus, every $k\in[n]$ belongs to an even number of the sets $B_i$, and $\triangle_{i\in I}B_i=\varnothing$. The lemma then ensures that $\sum_{i\in I}|B_i|$ is even, and since $B_{i_0}=A_{i_0}$ is even, it follows that
$$\sum_{i\in I\setminus\{i_0\}}|B_i|=\sum_{i\in I\setminus\{i_0\}}|A_{i_0}\cap A_i|$$
is even. Finally, $I\setminus\{i_0\}=|I|-1$ is odd, so at least one of the $|I|-1$ sets $A_{i_0}\cap A_i$ with $i\in I\setminus\{i_0\}$ must be even.
Now suppose that $|I|$ is odd. Then $|I|\ne n$, since $n$ is even, so there is an $i_0\in[n]\setminus I$. For $i\in I$ let $B_i=A_{i_0}\cap A_i$. For each $k\in[n]$ we know that $k$ is in an even number of the sets $A_i$ with $i\in I$; thus, either $k\notin A_{i_0}$, in which case $k\notin B_i$ for any $i\in I$, or $k\in A_{i_0}$, in which case for each $i\in I$ we have $k\in B_i$ iff $k\in A_i$. In either case $k$ is an even number of the sets $B_i$, so $\triangle_{i\in I}B_i=\varnothing$. Thus, $\sum_{i\in I}|A_{i_0}\cap A_i|=\sum_{i\in I}|B_i|$ is even, and since $|I|$ is odd, there must be at least one $i\in I$ such that $A_{i_0}\cap A_i$ is even.
This shows that for even $n$, $n$ sets are always sufficient.
Finally, suppose that $n$ is odd, and that $A_1,\ldots,A_{n+1}$ are even subsets of $[n]$. Then $A_1,\ldots,A_{n+1}$ are also even subsets of $[n+1]$, and the result follows from the even case. Thus, for odd $n$, $n+1$ sets are always sufficient.

