wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Simple Combinatorics
        
(Message started by: anonymous on Jun 4^th, 2003, 3:54pm)

Title: Simple Combinatorics
Post by anonymous on Jun 4^th, 2003, 3:54pm

Let n be an integer greater than 1. In a school there are n^2-n+2 clubs and each club has exactly n members. Each pair of clubs has exactly one member in common.

Count the total number of distinct members in all the clubs.

Title: Re: Simple Combinatorics
Post by Icarus on Jun 4^th, 2003, 6:13pm

If it's "given" that there is a unique answer, then it is easy to obtain:
[hide]If there is one person who is a member of all the clubs, and all the others are members of a single club only, this satisfies the problem conditions. So, there must be (n²-n+2)(n-1) + 1 = n³ - 2n² + 3n -1 distinct members.[/hide]

Of course the hard part is showing this number is unique.

Title: Re: Simple Combinatorics
Post by anonymous on Jun 5^th, 2003, 5:03am

Actually you can prove that there is an unique answer. Try to prove that (n-1)(n^2-n+2)+1 is the only solution.

Title: Re: Simple Combinatorics
Post by Icarus on Jun 5^th, 2003, 6:59pm

Now you shouldn't be changing the problem after the fact! You only asked for the number and I gave it. Everything else is just details! ;)

(Note that I didn't doubt that it was unique - instead I made use of the fact without proof.)

Title: Re: Simple Combinatorics
Post by anonymous on Jun 5^th, 2003, 7:51pm

The original problem ask for this: "show that there is one student belongs to all of the clubs". I think this give away too much information, reducing the difficulty of the problem. Therefore I change the statement into a more open-ended statment "count the total number of distinct members in all the clubs". This way I can hide the important fact that "there is a student that belongs to all of the clubs", the solver is required to discover this own his/her own, thus increasing the difficulty of the problem.

Also, when a problem ask to "evaluate", "find" or "count" a number, the problem not only ask for that number, the problem also ask for a complete proof that there are no other answer. For example Putnam 1995 B4 ask for the evaluation of a continued fraction. If the solver only give the answer, then only partial credits is awarded. But if the solver give the complete proof, then full credits is awarded.

Title: Re: Simple Combinatorics
Post by ecoist on Mar 8^th, 2007, 10:56am

Here's a proof that Icarus's solution is the only solution.

Let C be any one of the clubs. Then each of the remaining n²-n+1 clubs have exactly one member in common with C. Hence the average number of clubs having the same member in common with C is (n²-n+1)/n, which equals n-1+1/n. Thus, some member of C, say a, belongs to at least n other clubs. Assume, by way of contradiction, that a is not a member of all clubs. Then there is a club C* which does not have a as a member. Let C_i, for i=1,...,n be n clubs other than C that have a as a member. Then the n+1 sets, C\{a} and C'_i=C_i\{a}, are pairwise disjoint. Since C* must have a member in common with each of these n+1 sets, it follows that C* must contain at least n+1 members, contradiction. Hence a is a member of all clubs.

Title: Re: Simple Combinatorics
Post by Icarus on Mar 8^th, 2007, 4:37pm

Digging in the archives, I see. I had totally forgotten about this problem, and the fact that I had left it unfinished.

Title: Re: Simple Combinatorics
Post by ecoist on Mar 8^th, 2007, 8:11pm

I wondered why a complete solution for this problem went unposted for so long! I had thought that those problems I had posted that still remain unsolved were too trivial to entice someone to post a solution. Thanks to you, Icarus, I realize now that some problems are simply forgotten.