wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> There are 120 members
        
(Message started by: Radiohead_man on Dec 6^th, 2004, 8:04am)

Title: There are 120 members
Post by Radiohead_man on Dec 6^th, 2004, 8:04am

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.

Title: Re: There are 120 members
Post by Radiohead_man on Dec 7^th, 2004, 8:39am

is it that hard?

Title: Re: There are 120 members
Post by asterix on Dec 7^th, 2004, 9:18am

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.

Title: Re: There are 120 members
Post by Icarus on Dec 7^th, 2004, 12:47pm

on 12/07/04 at 09:18:07, 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.

Title: Re: There are 120 members
Post by asterix on Dec 7^th, 2004, 1:14pm

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.

Title: Re: There are 120 members
Post by THUDandBLUNDER on Dec 7^th, 2004, 9:32pm

on 12/07/04 at 12:47:39, 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!

Title: Re: There are 120 members
Post by Radiohead_man on Dec 8^th, 2004, 7:35am

lol

Title: Re: There are 120 members
Post by Aryabhatta on Dec 9^th, 2004, 11:50am

I guess the insight that Icarus was talking about is:
[hide]
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.
[/hide]