|
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!
|
Edit: Turns out my solution was wrong as every club does not have to be a group at the beginning of the game.
|
On November 22 2011 01:58 turdburgler wrote:
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!
You've only shown that at minimum you can get 100 clubs. You still need to show what the maximum is.
|
On November 22 2011 01:58 turdburgler wrote:
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!
prove that there can't be 101 or more clubs.
|
lol I really like the solution because yours is relatively straightforward - do linear algebra, 0 or 1 in each slot, apply the rules to the inner product (though I prefer straight bra-ket over random-ass commas, esp. when later on you have shits like probability distributions flying around), then above 100 is disallowed and you make sure that everything below 100 can be straightened out all right.
Probably might have done something like that if I had heard "linear" beforehand, else I might have done something weird.
Mmm-mmm the smell of orthogonal vectors in the morning...
|
As a number of people pointed out, the maximum is not 100, it's infinity. I always hated proofs, I guess if you can find a way in math to say someone can have as many clubs as they want and a club with 1 person satisfies both conditions than u get infinity.
|
On November 22 2011 05:46 KillerPenguin wrote:
As a number of people pointed out, the maximum is not 100, it's infinity. I always hated proofs, I guess if you can find a way in math to say someone can have as many clubs as they want and a club with 1 person satisfies both conditions than u get infinity.
This doesn't work because the intersection of two clubs must be an even number. If one person is the sole member of two different clubs then the intersection of those two clubs is 1 which is an odd number.
|
You cannot have more than 100 groups because the intersection of any "new" group after the 100th and the single groups that it is made up by is 1.
|
On November 22 2011 06:32 Cruncharoo wrote:
You cannot have more than 100 groups because the intersection of any "new" group after the 100th and the single groups that it is made up by is 1.
It is possible to have groups that are not made of singles.
I will demonstrate with a 4 person school, A B C D.
Club 1: A B C
Club 2: A B D
Club 3: A C D
Club 4: B C D
As you can see, each club has 3 people, but we can still create 4 clubs. In the case of 100 clubs things certainly get more complicated, so you cannot simply assume that every club is made of 1 person.
|
On November 22 2011 07:18 Slithe wrote:Show nested quote +On November 22 2011 06:32 Cruncharoo wrote:
You cannot have more than 100 groups because the intersection of any "new" group after the 100th and the single groups that it is made up by is 1. It is possible to have groups that are not made of singles. I will demonstrate with a 4 person school, A B C D. Club 1: A B C Club 2: A B D Club 3: A C D Club 4: B C D As you can see, each club has 3 people, but we can still create 4 clubs. In the case of 100 clubs things certainly get more complicated, so you cannot simply assume that every club is made of 1 person.
edit -- we are talking about different things.
|
EDIT: Answered my own question.
EDIT 2: Ok, no I am having trouble with this one. I was trying, as an exercise, to make a python code to do this. I'm basically making a big matrix with 100 columns, and the rows will be every possible club combination.
The issue I am getting is that the first 100 rows give me this this:
1 0 0 0 . . . 0
0 1 0 0 . . . 0
0 0 1 0 . . . 0
0 0 0 1 . . . 0
As you would expect. But then I am getting:
1 1 1 0 0 0 . . . 0
0 1 1 1 0 0 . . . 0
0 0 1 1 1 0 . . . 0
etc
Clearly this is wrong, because at the end when it checks for the dimension, it will produce an answer far greater than 100, which seems to be the general consensus here. Though looking at the initial conditions I'm not even sure what the above violates.
|
@deadeight
pretty sure that 1,0,0,0,0... and 1,1,1,0,0,0,0 don't share an even number of club members (intersection is 1)
|
@deadeight
if I had to guess, you're probably not comparing each new row pairwise with all the previous possibilities. Perhaps you're only comparing with the immediately preceding row?
|
Yeah you're both right.
I was checking for it in slightly the wrong way. I also think it's not a great way to go about it, because it will give just one possible combination of clubs that could not be made any bigger. It would span correctly, but I'd need to prove linear independence as well for it to be a basis (so that I knew the maximum dimension of a given combination is the same for any other combination).
EDIT: Gave in and looked at the proof in the OP, much better way to do it
|
+ Show Spoiler +The answer is infinity. Each student can be a member of infinitely many clubs where each club contains one person. When you take the intersection of any two of these "clubs", you will get the even number called zero.
Deal with it. B]
(The problem was probably stated incorrectly)
|
On November 22 2011 21:15 rkffhk wrote:+ Show Spoiler +The answer is infinity. Each student can be a member of infinitely many clubs where each club contains one person. When you take the intersection of any two of these "clubs", you will get the even number called zero. Deal with it. B] (The problem was probably stated incorrectly)
No, when you take the intersection of two clubs where for both clubs the same person is the sole member, you get the intersection as 1. This was already discussed earlier as well...
|
On November 22 2011 21:38 Valkynaz wrote:Show nested quote +On November 22 2011 21:15 rkffhk wrote:+ Show Spoiler +The answer is infinity. Each student can be a member of infinitely many clubs where each club contains one person. When you take the intersection of any two of these "clubs", you will get the even number called zero. Deal with it. B] (The problem was probably stated incorrectly) No, when you take the intersection of two clubs where for both clubs the same person is the sole member, you get the intersection as 1. This was already discussed earlier as well...
Nope, because I defined a club to be a set containing only 1 person in the second sentence of that spoiler~
And I can get away with it because the rules said I could (since 1 is an odd number)
Deal with it B]
|
On November 23 2011 08:32 rkffhk wrote:Show nested quote +On November 22 2011 21:38 Valkynaz wrote:On November 22 2011 21:15 rkffhk wrote:+ Show Spoiler +The answer is infinity. Each student can be a member of infinitely many clubs where each club contains one person. When you take the intersection of any two of these "clubs", you will get the even number called zero. Deal with it. B] (The problem was probably stated incorrectly) No, when you take the intersection of two clubs where for both clubs the same person is the sole member, you get the intersection as 1. This was already discussed earlier as well... Nope, because I defined a club to be a set containing only 1 person in the second sentence of that spoiler~ And I can get away with it because the rules said I could (since 1 is an odd number) Deal with it B]
Let me demonstrate the issue with your proposal with a concrete example. Let's say that you have two sets both with the same person in it:
A = { x }
B = { x }
C = A ∩ B = { x }
| C | = 1
As you can see, the intersection of A and B has an odd number of people, which is a violation of the rules.
|
:O my pants have been caught down at my ankles
|
wow... I can't figure it out.
There's a balance point though.
for n students
you want to have a certain number of groups.
and a certain number of students (I think all) overlapping in each group with other groups.
I can kinda see the problem solution intuitively in my head, and to solve it I'd have to use matlab and bruteforce the solution.
I don't think the answer is infinite groups. That's just plain silly :p
|
|
|
|
|
|
EPT
