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.

  • 2
    Actually, do you the answer to this? What have you tried so far?2011-07-26
  • 1
    Are these actual circles in the plane, or just sets? The members are the people, I assume...2011-07-26
  • 0
    @Robert I think you know well ;) The problem is written in common language like in elementary school, people tend to forget about this colorfull (non strict) method at universities.2011-07-26
  • 0
    @user13763 I have the same question that Robert asked, and unfortunately, your comment did not clarify the answer for me. So, are these actual circles or plain sets? :-)2011-07-27
  • 0
    There are sets, never attend to math circle ?! :)2011-07-27
  • 0
    I'm pretty sure by circles they just mean (sub)sets. No geometry involved. Because the sets have odd cardinality we know the answer is already limited to $\binom{3n}{1}+\binom{3n}{3}+\binom{3n}{5}+...$ which is actually $2^{3n-1}$, half of the power set. Then you have to use the rest of the information to reduce it further.2011-07-29
  • 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.