In Oddtown with $n$ citizens, $m$ clubs are formed. Every club has an odd number of members and also each two clubs have an odd number of members in common. Given that no two clubs have exactly the same members, find the largest possible value of $m$.

As mavropnevma said Here, The other three cases, "odd clubs with even pairwise intersections", "even clubs with even pairwise intersections", and "even clubs with odd pairwise intersections are discussed in Bollobas's book, The Art of Mathematics, but not this one, so I'm intrested to see it's answer.

P.S: The topic in AoPS got no answers, so I'm posting it here.....


This case can be reduced to the one with even clubs and even intersections.

Let's call the maximal number of clubs in the odd/odd and even/even cases $o_n$ and $e_n$, respectively. Gerry has already shown $e_{n-1}\le o_n\le e_{n+1}$. To see that in fact $o_n\le e_n$, consider the clubs as vectors in $\mathbb F_2^n$, indexed by the citizens, pick some club $c$, and form a set $S$ of clubs by adding $c$ to all clubs (including $c$ itself). The resulting vectors are even and have even intersections.

As shown in Bollobas' book, $e_n=2^{\lfloor n/2\rfloor}$. Thus the bounds in $e_{n-1}\le o_n\le e_n$ coincide for odd $n$, so for this case we have $o_n=2^{(n-1)/2}$. For even $n$, note that $S$ does not contain the componentwise complement of any of its elements, since the original clubs corresponding to an element of $S$ and its complement would also be complements of each other, and would thus have even intersection. Thus we can double the size of $S$ by adding the complements of all its elements, and all vectors will still be even and have even intersections (since $n$ is even). Thus in this case $o_n\le e_n/2=2^{n/2-1}$, so that $2^{n/2-1}$ is both a lower and upper bound. In summary, $o_n=2^{\lfloor(n-1)/2\rfloor}$ for either parity of $n$.

  • $\begingroup$ Your construction with adding $c$ implies $o_{n} - 1 \le e_n$ not $o_n \le e_n$. Because you will end up with one less club ($c + c$ is empty). $\endgroup$ – user320254 Oct 27 '16 at 7:18

Solve the problem for $n-1$ citizens, even clubs, even pairwise intersections, then make citizen $n$ a member of every club, and you have a lower bound for the $n$ citizen odd/odd problem.

Given a set of odd/odd clubs, bring in a new citizen, sign that new citizen up to every club, and you are in the even/even situation, so the even/even solution for $n+1$ citizens gives an upper bound for the $n$ citizen odd/odd problem.

OK, it doesn't solve the problem, but it gets you some nontrivial bounds.

  • $\begingroup$ The condition requires every club to have at least one member, and there can be at most one singleton (the intersection of these has to be non-empty). For each choice of singleton we get the even-even case for $n-1$ citizens - as the singleton must be a member of every club. $\endgroup$ – Mark Bennet May 6 '12 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.