Even and Odd Towns
by yayups, Aug 3, 2017, 5:41 AM
Attached is a nice pdf format of the writeup.
We will discuss two problems, one of Odd town, and one of Even town.
Odd town
We have a town of
people that is divided into 
clubs 
. Every club has an odd number of people, and the intersection of any two clubs has an even number of people. We are trying to find the maximum number of clubs that Odd town can have. In fact, we have the following theorem.
Theorem 1.1
There can be at most clubs, i.e. 
.
Note that this is sharp, since we can take the clubs to be of one person each.
We will now prove Theorem 1.1 using a most surprising technique: Linear Algebra. More specifically, we will be doing linear algebra over the vector space
. The way we will associate clubs with vectors is by using the \textit{characteristic vector} 
of 
, i.e. the 
th component of is 
if 
, and 
otherwise.
Proof of Theorem 1.1
All equalities in this proof are in
.
The key idea is to show that the vectors
are linearly independent. This would imply the theorem, since we can have at most linearly independent vectors in a vector space of dimension , which in this case is . The way to do this is to consider dot products. Note that
![\[v_i\cdot v_j=\sum_{k=1}^n(v_i)_k(v_j)_k=|C_i\cap C_j|.\]](//latex.artofproblemsolving.com/5/9/a/59a1db45304e7acf5e4c5ba85a6c580394c3c302.png)
Thus, 
if 
(since the sizes of the intersections of the clubs are even), and 
(since the sizes of the clubs are odd).
Now, assume that
![\[\sum_{k=1}^m \alpha_k v_k=0.\]](//latex.artofproblemsolving.com/6/1/b/61b7c5512893b8ea2c1c3e10d1150bae1c4c3f6d.png)
The goal is to show that 
for all 
. We do this by taking the dot product with of the above equation. This gives us that
![\[v_i\cdot\sum_{k=1}^m \alpha_k v_k=0\]](//latex.artofproblemsolving.com/b/1/2/b12b1e94e5e957d9668df75bfcb66fc50f871aa7.png)
or
![\[\sum_{k=1}^m\alpha_k v_i\cdot v_k=0\]](//latex.artofproblemsolving.com/c/a/b/cab00b5e182f3d7787a15f1f5781dc1dfbd4332b.png)
which means that since the only term that survives in the above sum is the one where 
. This shows that all the 
are , so the characteristic vectors of the clubs are linearly independent, which as we saw above, completes the proof. 
Even town
We have a town of
people that is divided into clubs . Every club now has an \textit{even} number of people, and the intersection of any two clubs has an even number of people. We are trying to find the maximum number of clubs that Even town can have.
The first observation is that Even town can have a lot more clubs than Odd town. The way to see this is to divide Even town into couples, and require that couples must be together in clubs. This satisfies the constraints, and we have 
clubs, one for each subset of the couples. In fact, we have the following theorem.
Theorem 2.1
There can be at most clubs, i.e. 
.
To prove this theorem, we need some preliminaries from linear algebra.
Definition 2.2
Let
be a subspace of 
. Then, define
![\[V^\perp = \{w\in W : w\cdot v=0\text{ for all }v\in V\}.\]](//latex.artofproblemsolving.com/0/1/f/01f3c41e96b3649d1b850f26032d183c4d3e222e.png)
Lemma 2.3
Let be a subspace of . Then, 
.
Proof of Lemma 2.3
Let
and 
. Then, choose a basis 
of such that 
is a basis of . Then, define the projection map
We note that 
and 
, so the rank-nullity theorem implies the lemma.
We can now prove theorem 2.1.
Proof of Theorem 2.1
We define the vectors
the same way as in the proof of theorem \ref{main_odd}. Now, since the size of any club is even, we have that \textit{for all} and (even possibly equal). Now, define to be the span of the vectors . Then, the dot product condition gives us that is a subspace of 
. Thus, 
. Now, by lemma \ref{rn}, we have that
![\[\dim V+\dim V^\perp = 2n\]](//latex.artofproblemsolving.com/b/a/7/ba7743ba89d3fc8ac5c58cc2debcf88285d2879d.png)
so
![\[2n\ge 2\dim V\]](//latex.artofproblemsolving.com/4/9/a/49a66f8669afa882188a280cbb066915870bdd74.png)
which means that 
. Thus, has at most elements, but clearly all the are in . Thus, , proving the theorem.
We will discuss two problems, one of Odd town, and one of Even town.
Odd town
We have a town of
people that is divided into 
clubs 
. Every club has an odd number of people, and the intersection of any two clubs has an even number of people. We are trying to find the maximum number of clubs that Odd town can have. In fact, we have the following theorem.Theorem 1.1
There can be at most
clubs, i.e. 
.Note that this is sharp, since we can take the clubs to be of one person each.
We will now prove Theorem 1.1 using a most surprising technique: Linear Algebra. More specifically, we will be doing linear algebra over the vector space
. The way we will associate clubs with vectors is by using the \textit{characteristic vector} 
of 
, i.e. the 
th component of is 
if 
, and 
otherwise.Proof of Theorem 1.1
All equalities in this proof are in
.The key idea is to show that the vectors
are linearly independent. This would imply the theorem, since we can have at most linearly independent vectors in a vector space of dimension , which in this case is . The way to do this is to consider dot products. Note that![\[v_i\cdot v_j=\sum_{k=1}^n(v_i)_k(v_j)_k=|C_i\cap C_j|.\]](http://latex.artofproblemsolving.com/5/9/a/59a1db45304e7acf5e4c5ba85a6c580394c3c302.png)
Thus, 
if 
(since the sizes of the intersections of the clubs are even), and 
(since the sizes of the clubs are odd).Now, assume that
![\[\sum_{k=1}^m \alpha_k v_k=0.\]](http://latex.artofproblemsolving.com/6/1/b/61b7c5512893b8ea2c1c3e10d1150bae1c4c3f6d.png)
The goal is to show that 
for all 
. We do this by taking the dot product with of the above equation. This gives us that![\[v_i\cdot\sum_{k=1}^m \alpha_k v_k=0\]](http://latex.artofproblemsolving.com/b/1/2/b12b1e94e5e957d9668df75bfcb66fc50f871aa7.png)
or![\[\sum_{k=1}^m\alpha_k v_i\cdot v_k=0\]](http://latex.artofproblemsolving.com/c/a/b/cab00b5e182f3d7787a15f1f5781dc1dfbd4332b.png)
which means that since the only term that survives in the above sum is the one where 
. This shows that all the 
are , so the characteristic vectors of the clubs are linearly independent, which as we saw above, completes the proof. 
Even town
We have a town of
people that is divided into clubs . Every club now has an \textit{even} number of people, and the intersection of any two clubs has an even number of people. We are trying to find the maximum number of clubs that Even town can have.The first observation is that Even town can have a lot more clubs than Odd town. The way to see this is to divide Even town into
couples, and require that couples must be together in clubs. This satisfies the constraints, and we have 
clubs, one for each subset of the couples. In fact, we have the following theorem.Theorem 2.1
There can be at most
clubs, i.e. 
.To prove this theorem, we need some preliminaries from linear algebra.
Definition 2.2
Let
be a subspace of 
. Then, define![\[V^\perp = \{w\in W : w\cdot v=0\text{ for all }v\in V\}.\]](http://latex.artofproblemsolving.com/0/1/f/01f3c41e96b3649d1b850f26032d183c4d3e222e.png)
Lemma 2.3
Let
be a subspace of . Then, 
.Proof of Lemma 2.3
Let
and 
. Then, choose a basis 
of such that 
is a basis of . Then, define the projection map
We note that 
and 
, so the rank-nullity theorem implies the lemma. We can now prove theorem 2.1.
Proof of Theorem 2.1
We define the vectors
the same way as in the proof of theorem \ref{main_odd}. Now, since the size of any club is even, we have that \textit{for all} and (even possibly equal). Now, define to be the span of the vectors . Then, the dot product condition gives us that is a subspace of 
. Thus, 
. Now, by lemma \ref{rn}, we have that![\[\dim V+\dim V^\perp = 2n\]](http://latex.artofproblemsolving.com/b/a/7/ba7743ba89d3fc8ac5c58cc2debcf88285d2879d.png)
so![\[2n\ge 2\dim V\]](http://latex.artofproblemsolving.com/4/9/a/49a66f8669afa882188a280cbb066915870bdd74.png)
which means that 
. Thus, has at most elements, but clearly all the are in . Thus, , proving the theorem. This post has been edited 3 times. Last edited by yayups, Oct 3, 2017, 7:25 AM
April 2021
September 2020