|
It's been over a year since I've posted my last math puzzle. Hopefully you guys will enjoy this one.
+ Show Spoiler [The Problem] +
There are 100 students at a school, and they want to start a bunch of clubs. However, the school has the following policy about club membership:
1) All clubs must have an odd number of members.
2) If you take any two clubs, the intersection of their members must be an even number.
The students want to create as many clubs as possible, while still following the rules of the school. What's the maximum number of clubs that can be created? Provide a proof.
Clarification:
1) A student can be a member of multiple clubs.
Since the solution requires a proof, there are probably many ways to prove the answer. I have a proof myself, and I think it's sound, but I'm not 100% sure. Also, it's very hard to write the proof in a legible way in text form, so apologies in advance for anyone that tries to read through it.
+ Show Spoiler [Slithe's Proof] +
My approach uses linear algebra. I represent each club as a 100-dimensional vector, where each entry is 1 or 0 to denote that a person is in that club.
I want to prove that if a set of club vectors maintains the Club Property (all clubs must have an odd number of people, there must be an even number of common members between any two clubs), then the set must be linearly independent. Therefore, there can't possibly be more than 100 clubs that satisfy the property since the space is only 100-dimensional.
My way of showing linear independence is by proving that you can always turn a set of club vectors into an equal size set of non-zero orthogonal vectors by way of the Gram-Schmidt Process. The important thing we need to verify is that no generated vector is a zero vector, which I do through induction.
The tl;dr version of the proof is that I leverage the following facts, which are a direct consequence of the Club Property.
1) the inner product of any two distinct club vectors results in an even number.
2) the inner product of a club vector with itself results in an odd number.
The rest of the proof is a lot of vector arithmetic to prove that the generated orthogonal vectors are non-zero.
----------------------------------------
PROOF
Given a Club Set W = {w_1, w_2, ..., w_k}, I will show that it is possible to generate an orthogonal set V = {v_1, v_2, ..., v_k}
Notation:
e = even integer
o = odd integer
----------
Base Case
v_1 = w1
v_1 is trivially non-zero.
----------
Inductive Step
We will generate v_k from the previous vectors {v_1, v_2, ..., v_k-1} using Gram-Schmidt
v_k = w_k - sum(i=1:k-1, (<w_k, v_i> / (||v_i||^2)) * v_i)
Definition of Property P: A vector v_i satisfies property P if the following are true:
1) v_i is a linear combination of W that can be written as such [ v_i = w_i + (e_1/o_1)*w_1 + (e_2/o_2)*w_2 + ... ].
2) v_i is a non-zero vector (This property actually comes as a byproduct of property 1, explained in the appendix)
Assuming that all v_i, i=1:k-1, satisfy property P, then we can show that v_k will also satisfy property P.
First, I assert 2 things (proof in the appendix):
1) the inner product <w_k, v_i> can always be represented as a fraction e/o. Also the inner product is non-zero.
2) the inner product <v_i, v_i> can always be represented as a fraction o/o. Trivially, the inner product is non-zero.
From this, we can derive that (<w_k, v_i> / (||v_i||^2) results in a fraction e/o.
Now let's look at what happens to the whole equation:
v_k = w_k - (e_1/o_1)*v_1 - (e_2/o_2)*v_2 - ...
We can expand out all the v_i terms, but the point is that the resulting v_k will have property P. Therefore, it's always possible to generate an orthogonal set of vectors, proving that W is linearly independent, and that the maximum number of clubs is 100. QED I think...
----------------------------------------
APPENDIX
Proof of non-zero property
First we start with this:
v_i = w_i + (e_1/o_1)*w_1 + (e_2/o_2)*w_2 + ...
Now the important thing to observe is that all the terms except for the first are e/o. the first vector has some number of elements with a value of 1. The corresponding elements in v_i will never be zero, since [1 + e/o != 0].
1 + e/o = o/o + e/o = o/o != 0
Proof of 1st assertion
inner_product = <w_k , v_i>
inner_product = <w_k , w_i + (e_1/o_1)*w_1 + (e_2/o_2)*w_2 + ...>
inner_product = <w_k , w_i> + (e_1/o_1) * <w_k, w_1> + (e_2/o_2) * <w_k, w_2> + ...
I'm tired of typing, but basically you can see that the inner product will result in a e/o fraction.
Proof of 2nd assertion
inner_product = <v_i , v_i>
inner_product = <(w_i + (e_1/o_1)*w_1 + (e_2/o_2)*w_2 + ...) , (w_i + (e_1/o_1)*w_1 + (e_2/o_2)*w_2 + ...)>
Once again, the math is rather tedious so I'm not gonna type it out, but the basic idea is that <w_i, w_i> results in a o/o fraction, while all the rest of the fractions are even fractions, so the resulting value is also an odd fraction.
+ Show Spoiler [Simplified Proof by munchmunch] +On November 21 2011 07:03 munchmunch wrote:Hi Slithe, I think your proof can be simplified by doing linear algebra over Z/2. + Show Spoiler +Consider the vector space V = (Z/2)^100. There is a correspondence between subsets of {1,...,100} and vectors of V, given by sending a subspace S to the vector v whose ith entry is 1 if i is an element of S, and 0 otherwise.
Suppose you have a set of subsets S(1),...,S(n) each of odd cardinality, such that the intersections are of even cardinality. Define a bilinear pairing V x V --> Z/2 using the usual dot product formula. Let v(i) be the vector corresponding to S(i). Then the dot product of v(i) with v(j) is 1 if and only if i=j. To show that v(1),...,v(n) are linearly independent, suppose a(1) v(1) + ... + a(n) v(n) = 0, where a(1),...,a(n) are elements of Z/2. Then the dot product of v(i) with the left hand side is a(i), so a(i) must be zero.
Conclusion: any set of subsets satisfying the required conditions corresponds to a linearly independent set of vectors of V.
|
Isn't the answer 100?
Having 100 clubs = 1 student per club = 1 club + 1 club = 2, an even number = 100, the answer?
|
That is some hectic mathematics there lol. I just skimmed through this blog for interest's sake, and I definitely had no chance to provide a proof. Read through your proof though, and it still baffles me. What level of mathematics does this problem assume the solver should master? I am only in high school to be honest.
|
|
|
@MonkSEA
You have not really proved anything here. You have just asserted that 100 is the most clubs you could possibly create, without showing that it is actually the maximum.
@NethZOR
My proof involves linear algebra, which is generally college level for most people. Some more prodigious individuals may learn some linear algebra in high school.
|
On November 21 2011 06:34 Slithe wrote:
@MonkSEA
You have not really proved anything here. You have just asserted that 100 is the most clubs you could possibly create, without showing that it is actually the maximum.
@NethZOR
My proof involves linear algebra, which is generally college level for most people. Some more prodigious individuals may learn some linear algebra in high school.
how is monksea's answer not a proof?
a club must have an odd number of people, the minimum such number is 1 since you can't have negative members and 0 is even. So the maximum number of clubs you can possibly make, even disrespecting rule #2 is 100.
And if you make 100 such clubs, intersection of any of the two clubs is 0 since each person is only a part of one club.
|
On November 21 2011 06:39 JeeJee wrote:Show nested quote +On November 21 2011 06:34 Slithe wrote:
@MonkSEA
You have not really proved anything here. You have just asserted that 100 is the most clubs you could possibly create, without showing that it is actually the maximum.
@NethZOR
My proof involves linear algebra, which is generally college level for most people. Some more prodigious individuals may learn some linear algebra in high school. how is monksea's answer not a proof? a club must have an odd number of people, the minimum such number is 1 since you can't have negative members and 0 is even. So the maximum number of clubs you can possibly make, even disrespecting rule #2 is 100. And if you make 100 such clubs, intersection of any of the two clubs is 0 since each person is only a part of one club.
How do you know there isn't another configuration that can involve more than 100 clubs? Are you assuming that each person can only be part of one club?
|
That proof is second year university maths for me, although the intuition to do it that way without prompt will be beyond the majority of maths students.
|
On November 21 2011 06:41 Slithe wrote:Show nested quote +On November 21 2011 06:39 JeeJee wrote:On November 21 2011 06:34 Slithe wrote:
@MonkSEA
You have not really proved anything here. You have just asserted that 100 is the most clubs you could possibly create, without showing that it is actually the maximum.
@NethZOR
My proof involves linear algebra, which is generally college level for most people. Some more prodigious individuals may learn some linear algebra in high school. how is monksea's answer not a proof? a club must have an odd number of people, the minimum such number is 1 since you can't have negative members and 0 is even. So the maximum number of clubs you can possibly make, even disrespecting rule #2 is 100. And if you make 100 such clubs, intersection of any of the two clubs is 0 since each person is only a part of one club. How do you know there isn't another configuration that can involve more than 100 clubs? Are you assuming that each person can only be part of one club?
yeah.. isn't that a given?
edit: saw your edit. nevermind then
|
On November 21 2011 06:44 JeeJee wrote:Show nested quote +On November 21 2011 06:41 Slithe wrote:On November 21 2011 06:39 JeeJee wrote:On November 21 2011 06:34 Slithe wrote:
@MonkSEA
You have not really proved anything here. You have just asserted that 100 is the most clubs you could possibly create, without showing that it is actually the maximum.
@NethZOR
My proof involves linear algebra, which is generally college level for most people. Some more prodigious individuals may learn some linear algebra in high school. how is monksea's answer not a proof? a club must have an odd number of people, the minimum such number is 1 since you can't have negative members and 0 is even. So the maximum number of clubs you can possibly make, even disrespecting rule #2 is 100. And if you make 100 such clubs, intersection of any of the two clubs is 0 since each person is only a part of one club. How do you know there isn't another configuration that can involve more than 100 clubs? Are you assuming that each person can only be part of one club? yeah.. isn't that a given? edit: saw your edit. nevermind then
I'm rather insulted that you thought my problem would be so simple 
|
Hi Slithe, I think your proof can be simplified by doing linear algebra over Z/2.
+ Show Spoiler +Consider the vector space V = (Z/2)^100. There is a correspondence between subsets of {1,...,100} and vectors of V, given by sending a subspace S to the vector v whose ith entry is 1 if i is an element of S, and 0 otherwise.
Suppose you have a set of subsets S(1),...,S(n) each of odd cardinality, such that the intersections are of even cardinality. Define a bilinear pairing V x V --> Z/2 using the usual dot product formula. Let v(i) be the vector corresponding to S(i). Then the dot product of v(i) with v(j) is 1 if and only if i=j. To show that v(1),...,v(n) are linearly independent, suppose a(1) v(1) + ... + a(n) v(n) = 0, where a(1),...,a(n) are elements of Z/2. Then the dot product of v(i) with the left hand side is a(i), so a(i) must be zero.
Conclusion: any set of subsets satisfying the required conditions corresponds to a linearly independent set of vectors of V.
|
err it's pretty easy to show that the set of vectors should be linearly independent:
suppose v_1...v_k are your vectors. If sum( a_iv_i) = 0, we may assume that not all a_i are even. But taking the dot product with v_i results in a_i |v_i|^2 = 0 mod 2, since |v_i|^2 is odd then a_i = 0 mod 2 for all i, contradiction.
|
On November 21 2011 07:05 blankspace wrote:
err it's pretty easy to show that the set of vectors should be linearly independent:
suppose v_1...v_k are your vectors. If sum( a_iv_i) = 0, we may assume that not all a_i are even. But taking the dot product with v_i results in a_i |v_i|^2 = 0 mod 2, since |v_i|^2 is odd then a_i = 0 mod 2 for all i, contradiction.
I'm not following where the assumption that not all a_i are even is coming from. Can you clarify that for me?
|
Why wouldn't you do everything over $\mathbb{F}_2$?
|
On November 21 2011 07:30 Muirhead wrote:
Why wouldn't you do everything over $\mathbb{F}_2$?
Your notation is foreign to me, but I"m guessing you're talking about working on a field modulo 2? It looks like munchmunch does that, and it certainly makes proving it a lot simpler. The thought didn't cross my mind, because I'm not super good at these puzzles.
I think blankspace is also working along the same lines?
|
You can get to 100 without any fancy math. Each student forms his/her own club. No intersection. Zero is an even number (http://en.wikipedia.org/wiki/Parity_of_zero).
|
On November 21 2011 13:45 Frozenhelfire wrote:
You can get to 100 without any fancy math. Each student forms his/her own club. No intersection. Zero is an even number (http://en.wikipedia.org/wiki/Parity_of_zero).
The "fancy math" is needed to show that you can't get higher than 100. The other half of the problem is to show you can get to 100, which you did .
It's been a while since you posted these Slithe. I remember some roadrunner problem pretty well .
Most folks use F_p for the field with p elements, because Z_p often refers to the p-adic integers. There's a rather large group of these Putnamesque problems in combinatorics that center around using linear algebra modulo 2. I assumed you grabbed it from a list of similar problems... especially since it's a rather large leap to decide to use linear algebra in the first place if you haven't seen something like this before.
It's not so often in combinatorics that you see a problem like this in which the optimum bound (100) can be achieved in so many different ways. When you have intuition that the optimum bound in a problem shows is achieved nearly 100% of the time from random configurations it is often the case that there is algebraic structure in the problem.
|
On November 21 2011 14:18 Muirhead wrote:Show nested quote +On November 21 2011 13:45 Frozenhelfire wrote:
You can get to 100 without any fancy math. Each student forms his/her own club. No intersection. Zero is an even number (http://en.wikipedia.org/wiki/Parity_of_zero). The "fancy math" is needed to show that you can't get higher than 100. The other half of the problem is to show you can get to 100, which you did . It's been a while since you posted these Slithe. I remember some roadrunner problem pretty well . Most folks use F_p for the field with p elements, because Z_p often refers to the p-adic integers. There's a rather large group of these Putnamesque problems in combinatorics that center around using linear algebra modulo 2. I assumed you grabbed it from a list of similar problems... especially since it's a rather large leap to decide to use linear algebra in the first place if you haven't seen something like this before. It's not so often in combinatorics that you see a problem like this in which the optimum bound (100) can be achieved in so many different ways. When you have intuition that the optimum bound in a problem shows is achieved nearly 100% of the time from random configurations it is often the case that there is algebraic structure in the problem.
I heard the problem from a friend, and it's very possible that he got it from a math competition, Putnam or otherwise. I personally have not competed much in math competitions, so I'm usually learning something new with each puzzle. In hindsight, it seems pretty obvious that working in F_2 would make things much simpler
|
On November 21 2011 07:23 Slithe wrote:Show nested quote +On November 21 2011 07:05 blankspace wrote:
err it's pretty easy to show that the set of vectors should be linearly independent:
suppose v_1...v_k are your vectors. If sum( a_iv_i) = 0, we may assume that not all a_i are even. But taking the dot product with v_i results in a_i |v_i|^2 = 0 mod 2, since |v_i|^2 is odd then a_i = 0 mod 2 for all i, contradiction.
I'm not following where the assumption that not all a_i are even is coming from. Can you clarify that for me?
well if a_i all share a common factor you could just factor out that common factor and get a set of b_i who share no common factor. So in particular you can assume 2 doesn't divide all a_i. (if 2x_1+6x_2 = 0, then x_1 + 3x_2 = 0).
Edit: Oops sorry I actually used a result that I didn't state -_-
Fact: since v_i...v_k all have rational coordinates, if there is a linear dependence sum(a_iv_i) = 0 where a_i are in R, then there exists a linear dependence sum(k_iv_i) where k_i are in Z. This isn't too hard to prove. Then we can use the argument above
Hmm I might as well prove it. Suppose a_iv_i = 0 where not all a_i are zero. Let M be the matrix with v_i as its columns, so the vector a is a non-trivial solution to Ma = 0. Let's say we have n vectors with m coordinates, so M is mxn. Then M is a linear map from R^n -> R^m with non trivial kernel, so by the rank nullity theorem, rank(M) < n.
Call the first n-1 rows of the matrix M', so there is a solution to the system M'x = v_n. Since all coordinates are rational, the row reduction algorithm has no steps involving irrationals.
Now once you get a linear dependence in Q, just clear denominators to get it in Z.
|
100 clubs and each student is only in their own club
each club only has 1 member
the intersection of any 2 clubs is 0, an even number
your all over complicating this!
|
|
|
|
|
|
EPT
