Author |
Topic: Simple Combinatorics (Read 683 times) |
|
anonymous
Guest
|
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.
|
|
 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 4th, 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 (n2-n+2)(n-1) + 1 = n3 - 2n2 + 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
|
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.
|
|
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 5th, 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
|
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.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Simple Combinatorics
« Reply #5 on: Mar 8th, 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 n2-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 (n2-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 Ci, 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=Ci\{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 8th, 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 8th, 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 8th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove