+0

# Please explain very well in this question

0
1272
4

The numbers  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,  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  are possible?

Guest Mar 5, 2015

#3
+889
+11

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
Sort:

#1
+91436
+5

I have no idea where to start.

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

Melody  Mar 5, 2015
#2
+26399
+11

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!

.

Alan  Mar 5, 2015
#3
+889
+11

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
+91436
+5

Thanks Alan and Bertie,

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

Melody  Mar 7, 2015

### 17 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details