EPTMath Puzzle - School Clubs Problem - Page 2
| Blogs > Slithe |
|
Valkynaz
Estonia4 Posts
| ||
|
Slithe
United States985 Posts
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. | ||
|
Soleron
United Kingdom1324 Posts
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. | ||
|
ymir233
United States8275 Posts
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... | ||
|
KillerPenguin
United States516 Posts
| ||
|
Valkynaz
Estonia4 Posts
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. | ||
|
Cruncharoo
United States136 Posts
| ||
|
Slithe
United States985 Posts
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. | ||
|
Cruncharoo
United States136 Posts
On November 22 2011 07:18 Slithe wrote: 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. | ||
|
Deadeight
United Kingdom1629 Posts
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. | ||
|
blankspace
United States292 Posts
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) | ||
|
Slithe
United States985 Posts
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? | ||
|
Deadeight
United Kingdom1629 Posts
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  | ||
|
rkffhk
474 Posts
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) | ||
|
Valkynaz
Estonia4 Posts
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... | ||
|
rkffhk
474 Posts
On November 22 2011 21:38 Valkynaz wrote: 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] | ||
|
Slithe
United States985 Posts
On November 23 2011 08:32 rkffhk wrote: 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. | ||
|
rkffhk
474 Posts
| ||
|
Hidden_MotiveS
Canada2562 Posts
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 | ||
| ||
