We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
2738
4
avatar

The numbers $1,2,3,4,5,6,7,8,9$ are arranged in a list so that each number is either greater than all the numbers that come before it or is less than all the numbers that come before it. For example, $4,5,6,3,2,7,1,8,9$ is one such list: notice that (for instance) the 6 is greater than all the numbers that come before it, and the 2 is less than all the numbers that come before it.

How many such lists of the numbers $1,2,3,4,5,6,7,8,9$ are possible?

 Mar 5, 2015

Best Answer 

 #3
avatar+890 
+13

The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example  and some of those to the left will be bigger, and some smaller.)   Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on.  There will only one choice left for the first digit, so 2 to the eight or 256 possibles

 Mar 6, 2015
 #1
avatar+102763 
+5

I have no idea where to start.

Some of the permutations are obvious but how you would count them I have no idea

 Mar 5, 2015
 #2
avatar+28125 
+12

I conjecture that the answer is 256 (= 29-1) based on extrapolating results for sets {1,2}, {1,2,3} and {1,2,3,4}.  However, I have yet to find an elegant proof!

 

Partial reasoning:

If we have a number of arrangements for the set A = {1,...,n-1} then we can immediately get that many again for the set B = {1, ...,n} by simply putting n after all the arrangements for A.  Any extra arrangements for B must end in 1, because if they end in anything other than 1 or n, the end value will be bigger than 1 and smaller than n, violating the criteria.  It seems that there are just as many arrangements ending in 1 as there are ending in n, hence, since there are just 2 arrangements, for the set {1.2} each extra digit doubles the number of arrangements.  There must be a simple proof of the fact that there are just as many arrangements ending in 1 as there are ending in n (if it's true!), but I'm having a mental block trying to see it!

.

 Mar 5, 2015
 #3
avatar+890 
+13
Best Answer

The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example  and some of those to the left will be bigger, and some smaller.)   Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on.  There will only one choice left for the first digit, so 2 to the eight or 256 possibles

Bertie Mar 6, 2015
 #4
avatar+102763 
+5

Thanks Alan and Bertie,

I finally get it!  I think that I do anyway.   I never would of by myself.  Thanks!

 Mar 7, 2015

11 Online Users

avatar
avatar
avatar