6
$\begingroup$

This problem may seem challenging:

We have $3n$ people, and circles of interest. In every circle there is an odd number of members. The number of common members to every $2^{n-1}+1$ circles is even. Prove that there are no more than $2^n+n2^{n-1}$ circles.

  • 0
    I will reformulate this in meantime. Let $n\in\mathbb{Z}_+$, $|X|=3n$ and $S\subset 2^X$ such that: $\forall( A\in S\Rightarrow |A|$ is odd) and $\forall( B\subset S\wedge |B|=2^{n-1}+1\Rightarrow |\bigcap B|$ is even). Prove that $|S|\leq 2^n+n2^{n-1}$.2011-08-01

1 Answers 1

6

This a special case of Theorem 1.2 in this paper, with $n$ and $k$ in the paper $3n$ and $2^{n-1}+1$ in the question, respectively. The conditions for the first part of the theorem, which provides an equality, are fulfilled, and indeed Construction A preceding the statement of Theorem 1.2 (p. 3) provides an explicit solution attaining the bound.

I have an incomplete proof that might turn out a bit simpler than the one in the paper; if it does, I'll post it here.