|
|
#1
10-02-2007, 12:41 PM
|
|||
|
|||
Math Olympiad problem (Oct-2)
I like this problem:
Determine the number of different arrangements a_1,a_2,a_3,...,a_10 of the integers 1,2,3,....,10 such that: 1) a_i > a_2i 2) a_i > a_2i+1 
|
|
#2
10-02-2007, 01:40 PM
|
|||
|
|||
|
Re: Math Olympiad problem (Oct-2)
I don't know any combinatorics or whatever this may be, but it looks intuitive so I'll take a stab at it. My approach is just logic.
There are two "branches" here, the a_2+ and the a_3+. a_2+: a_1>a_2>a_4>a_8 a_1>a_2>a_4>a_9 a_1>a_2>a_5>a_10 a_3+: a_1>a_3>a_6 a_1>a_3>a_7 a_1 = 10 because it's bigger than everything. The a_2 and a_3 branches involve no overlap, so any of the 9 remaining values can be tossed into either branch (since > and < are the only operators we're using now). So any 6 numbers can go in a_2+ and the other 3 will go in a_3+. Now I show my ignorance of combinatorics, but 6 and 3 seems to make a little triangle with 84 permutations? Number of arrangements for a_2+ and a_3+ so now we just multiply the permutations of a_2+, the permutations of a_3+, and 84. a_3+ is easy. a_3 is the biggest number in that branch, then a_6 and a_7 can have either of the two smaller ones. So that's just 2 permutations in a_3 once the numbers are selected. a_2 is also the biggest number, then a_4+ and a_5+ are new sequences and it doesn't matter which numbers go into which. It's 2 and 3 this time, so 10*1*2=20 permutations for a_2+. So overall it's 20*2*84=3360 valid arrangements. Kick my ass if I'm being dumb. And obviously I'm assuming that for numbers a_6 and up, the conditions don't apply (there is no a_12 or a_13...).
|
|
#4
10-02-2007, 05:52 PM
|
|||
|
|||
|
Re: Math Olympiad problem (Oct-2)
Very interesting problem. Good solution madnak.
|
|
#6
10-02-2007, 07:40 PM
|
|||
|
|||
|
Re: Math Olympiad problem (Oct-2)
madnak,
Your solution looks good (and like the logical approach). Here is a good free probability book which has a chapter on basic combinatorics: http://math.dartmouth.edu/%7Eprob/prob/prob.pdf
|
|
#7
10-03-2007, 08:56 PM
|
|||
|
|||
|
Re: Math Olympiad problem (Oct-2)
if you want to generalize, i think it's best to view it in light of prufer codes which is a bijective mapping between sequences satisfying a particular condition to number of binary trees.
|
 |
|
|
Linear Mode
