3
$\begingroup$

Consider all the six digit numbers that can be formed using the digits 1, 2, 3, 4, 5 and 6, each digit being used exactly once. Each of such six digit numbers have the property that for each digit, not more than two digits smaller than that digit appear to the right of that digit.

The examples of such numbers are 315426, 135462, 234651 ect. Number of the six digit numbers having desired property is:

$\endgroup$
9
  • $\begingroup$ I don't know even how to start solving this problem. no hint or idea in my mind. $\endgroup$
    – Priyanka Vithani
    Jul 12, 2017 at 13:09
  • $\begingroup$ question might be phrased wrong but what did you try ? $\endgroup$
    – user451844
    Jul 12, 2017 at 13:10
  • $\begingroup$ counterexample 654321 . $\endgroup$
    – user451844
    Jul 12, 2017 at 13:22
  • $\begingroup$ @RoddyMacPhee I think the OP wants to count the numbers with that property, not disprove the statement that all numbers have that property. $\endgroup$
    – Arthur
    Jul 12, 2017 at 13:28
  • 1
    $\begingroup$ Judging from your comments to the posted solutions below, I think we need clarity in the definition. All the solvers (and I ) read the condition this way: a good string has the property for each digit, $1,\cdots, 6$ , at most two digits to the right of it are smaller than it. Thus $234651$ is good. Let's check: The first digit to check is $4$...the digits less than $4$ are $3,2,1$ and of these only $1$ is to the right. East to check $5,6$ as well. If you are reading the definition differently, then you should clarify. $\endgroup$
    – lulu
    Jul 12, 2017 at 14:10

3 Answers 3

Reset to default
3
$\begingroup$

Hint: How many different places can the $6$ go? Once the $6$ is placed, how many different places can the $5$ go? Then keep going.

$\endgroup$
2
$\begingroup$

Let it be that $s_n$ denotes the number when this is asked for digits $1,2,\dots,n$. Then for $n>3$ the following relation can be deduced:$$s_n=3s_{n-1}$$

This because as utmost left digit only $1,2,3$ are allowed, and if the utmost left digit is placed then the same problem arises for $1$ digit less.

Next to that it also obvious that $s_3=3!=6$ so we arrive at:$$s_6=3s_5=3^2s_4=3^3s_3=3^3\cdot6=162$$

$\endgroup$
7
  • $\begingroup$ sorry but i didn't understand what you want to say. $\endgroup$
    – Priyanka Vithani
    Jul 12, 2017 at 13:39
  • $\begingroup$ Same solution, but derived differently: The largest digit ($n$) must be one of the last three digits. Then: There are bijections between the five-digit numbers formed with 1, 2, 3, 4, 5 that have the property and the six-digit numbers that have the property, with 6 in the last position. Also bijection to the six-digit numbers that have the property, with 6 in the fifth position. And the same with 6 in the fourth position. So $s_6=3s_5$, etc. $\endgroup$
    – user325968
    Jul 12, 2017 at 13:39
  • $\begingroup$ @PriyankaVithani Do you agree that the utmost left digit can only be one of $1,2,3$? $\endgroup$
    – drhab
    Jul 12, 2017 at 13:43
  • $\begingroup$ but 654321 has the desired property $\endgroup$
    – Priyanka Vithani
    Jul 12, 2017 at 13:46
  • $\begingroup$ What makes you think that? First digit of $654321$ is $6$ and there are $5$ smaller digits at the right of that digit. At most $2$ are allowed. $\endgroup$
    – drhab
    Jul 12, 2017 at 13:49
0
$\begingroup$

Following the hint of @Artur
6 can be only at one of the last three places. 3 possibilities
Irrespective of where 6 is 5 can also come only in one of the last 3 remaining places.
Continuing similarly we get
Total number of possibilities are: $3^4\times2=162$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .