Author 
Topic: Simple Combinatorics (Read 692 times) 

anonymous
Guest

Let n be an integer greater than 1. In a school there are n^2n+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.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Simple Combinatorics
« Reply #1 on: Jun 4^{th}, 2003, 6:13pm » 
Quote Modify

If it's "given" that there is a unique answer, then it is easy to obtain: 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^{2}n+2)(n1) + 1 = n^{3}  2n^{2} + 3n 1 distinct members. Of course the hard part is showing this number is unique.


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



anonymous
Guest


Re: Simple Combinatorics
« Reply #2 on: Jun 5^{th}, 2003, 5:03am » 
Quote Modify
Remove

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


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Simple Combinatorics
« Reply #3 on: Jun 5^{th}, 2003, 6:59pm » 
Quote Modify

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.)


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



anonymous
Guest


Re: Simple Combinatorics
« Reply #4 on: Jun 5^{th}, 2003, 7:51pm » 
Quote Modify
Remove

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 openended 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.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Simple Combinatorics
« Reply #5 on: Mar 8^{th}, 2007, 10:56am » 
Quote Modify

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^{2}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^{2}n+1)/n, which equals n1+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.

« Last Edit: Mar 8^{th}, 2007, 2:22pm by ecoist » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Simple Combinatorics
« Reply #6 on: Mar 8^{th}, 2007, 4:37pm » 
Quote Modify

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


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



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Simple Combinatorics
« Reply #7 on: Mar 8^{th}, 2007, 8:11pm » 
Quote Modify

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.


IP Logged 



