Author |
Topic: There are 120 members (Read 500 times) |
|
Radiohead_man
Junior Member
Gender: 
Posts: 74
|
 |
There are 120 members
« on: Dec 6th, 2004, 8:04am » |
 Quote  Modify
|
There are 120 members in the Israeli parliament, and 40 committees. A committee can be assembled only when the number of committee members that are now present in the parliament hall, is odd (so that votes would be decisive). Show a way to assign the parliament members to committees, so that in all times, except for when the hall is completely empty, there would be at least one committee that can be assembled, or show that it is impossible.
|
|
 IP Logged |
I'm a reasonable man
get off my case, get off my case.
|
|
|
Radiohead_man
Junior Member
Gender:
Posts: 74
|
|
Re: There are 120 members
« Reply #1 on: Dec 7th, 2004, 8:39am » |
Quote Modify
|
is it that hard?
|
|
IP Logged |
I'm a reasonable man
get off my case, get off my case.
|
|
|
asterix
Guest
|
No, it's not nearly putnam level difficulty.
To be possible, every single combination of members present would have to give you a different parity of committees with an odd number of members present. If any two subgroups without any members in common both resulted in the same committees being odd, then the combination of those two subgroups would make all committees even. If they have any members in common, then the common members can go home, and the two subgroups will still have the same parity, so it still makes an all even combined group.
However, the number of possible parities (combinations of committees with an odd number, 2^n-1) is the same as the number of combinations of people who could be present, 2^p-1, so it's not possible if there are more people than there are committees. I think.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: There are 120 members
« Reply #3 on: Dec 7th, 2004, 12:47pm » |
Quote Modify
|
on Dec 7th, 2004, 9:18am, asterix wrote:| No, it's not nearly putnam level difficulty. |
|
And T&B's latest additions are? I've found two of them to be almost trivial. I think this one is appropriately placed. To solve it requires some insight.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
asterix
Guest
|
Sorry, I didn't mean to criticize the question. I thought it was a very good question maybe for the medium category (I'm also sorry I didn't add the hide tags before hitting post). But I understand putnam to be for advanced concepts. In other words, if I can even understand the question, it probably doesn't belong in this category. Yes, I kind of think a couple of T & B's questions to be miscategorized.
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: There are 120 members
« Reply #5 on: Dec 7th, 2004, 9:32pm » |
Quote Modify
|
on Dec 7th, 2004, 12:47pm, Icarus wrote:
And T&B's latest additions are? I've found two of them to be almost trivial. |
|
I agree with you that the basketball one is rather easy.
But if they are hard enough for Putnam 2004, they are hard enough for me!
|
| « Last Edit: Dec 7th, 2004, 9:34pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Radiohead_man
Junior Member
Gender:
Posts: 74
|
|
Re: There are 120 members
« Reply #6 on: Dec 8th, 2004, 7:35am » |
Quote Modify
|
lol
|
|
IP Logged |
I'm a reasonable man
get off my case, get off my case.
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: There are 120 members
« Reply #7 on: Dec 9th, 2004, 11:50am » |
Quote Modify
|
I guess the insight that Icarus was talking about is:
Linear Algebra.
We can get an equation AX=0, with A being a 40x120 matrix with entries in F_2. Accordind to a standard theorem, this has a non-trivial solution, which corresponds to an assembly where no committee can be formed.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove