A 5-digit number a b c d e is called decreasing if a > b > c > d > e . A 5-digit number a b c d e is called increasing if a < b < c < d < e . What is the (absolute) difference in the number of increasing and decreasing 5-digit numbers?
Details and assumptions
The number 1 2 = 0 1 2 is a 2-digit number, not a 3-digit number.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice way of explaining the injection and your thought process. Voted up! :)
Nice inclusion of motivation! Will just add a succint solution here for those who don't have time:
Given any group of 5 distinct digits, we can make a unique decreasing integer. There are ( 5 1 0 ) = 2 5 2 increasing integers then. Given any group of 5 distinct digits of which none are 0 , we can make a unique increasing integer. There are ( 5 1 0 ) = 1 2 6 decreasing integers then. Thus, 2 5 2 − 1 2 6 = 1 2 6 .
Log in to reply
I think the second combination should be ( 5 9 ) , and also the words "increasing" and "decreasing" are switched. :P
good solution i did the same way
Good thinking!
A numerical way, based on graph, in this one: Build a table 5x9 and put - in the first line * the possible values of *a * - in the second line * the number * of possible values of *b corresponding to the a on the top - in the third line the number of possible values of c corresponding to the a and b and so on
We have that called (i,j) the element in line i and column j , that: * (i,j) = sum_{k=1}^(j-1) (i-1,k) for i >= 3 * this means that every number in the table is the sum of the number from the first to the immediately previous on the line up * exept for the first two line *. But the first two line are very immediate infact are 1 2 3 4 5 6 7 8 9 // 1 2 3 4 5 6 7 8 9
for the table of decreasing numbers. And 9 8 7 6 5 4 3 2 1 // 0 1 2 3 4 5 6 7 8 for the table of increasing numbers. Now in order to count how many increasing/decreasing number there are we have only to sum the numbers * on the last line *
Excellent solution! I was at a loss for how to do this problem, so I just formulated the following Mathematica command to do it for me.
Length[Solve[1<=a<=9 && 0<=b<=9 && 0 <= c <= 9 && 0 <= d <= 9 && 0 <= e <= 9 && a>b>c>d>e,{a,b,c,d,e},Integers]] - Length[Solve[1<=a<=9 && 0<=b<=9 && 0 <= c <= 9 && 0 <= d <= 9 && 0 <= e <= 9 && a<b<c<d<e,{a,b,c,d,e},Integers]]
Log in to reply
Thanks! I'm glad you liked it.
When I was writing that solution, I wanted to make sure I included everything that went through my head - the thought process, the motivation and how everything unraveled in my mind.
5 -digit decreasing numbers can be formed in 1 0 C 5 ways and 5 -digit increasing numbers can be formed in 9 C 5 ways. So the absolute difference is 1 0 C 5 − 9 C 5 = 1 2 6 .
Note that given any 5 distinct digits, there is exactly 1 way to arrange the digits in decreasing order and 1 way to arrange the digits in increasing order.
Take 19342 for example: the only way to arrange the digits in decreasing order is 94321 and the only way to arrange the digits in increasing order is 12349.
However, when a 0 is in the number, problems occur.
Take 19023 for example: when trying to increase the digits in increasing order, the 0 must go first; therefore, a 4-digit number is formed.
Therefore, the number of decreasing numbers is greater than the number of increasing numbers by [the number of decreasing numbers that include a zero].
Now, it just remains to calculate the number of decreasing numbers that include a zero.
The other 4 digits (not zero) of the decreasing number must be chosen from the digits 1, 2, 3, 4, 5, 6, 7, 8, 9.
There are ( 4 9 ) = 1 2 6 ways to choose this, which is our answer.
Alternatively, note that there are ( x 1 0 ) ways to choose a decreasing number with x digits and ( x 9 ) to choose a increasing number with x digits.
In particular, when x = 5 , the difference is ( 5 1 0 ) − ( 5 9 ) = ( 4 9 ) = 1 2 6
Hadn't thought of the second solution at the bottom. Short and simple - nice work!
We begin with calculating decreasing 5-digit number.
Observe that whatever 5 digits we select, there is always only one way to arrange them. Hence, number of decreasing 5-digit numbers are simply: ( 5 1 0 )
The number of increasing 5-digit numbers are: ( 5 9 ) The reason for above is that we cannot select a zero as it will be placed on the very first position and then it doesn't remain a 5-digit number.
Hence, the difference is: ( 5 1 0 ) − ( 5 9 ) = 1 2 6
Increasing Numbers would have no 0, since a can't be 0.
For each each Increasing Number there exists a Decreasing Number which can be arrived at reversing the sequences of digits.
Thus in the difference these would amount to 0. Only thing we need to count is the excess Decreasing Numbers , i.e. those containing 0.
a > b > c > d > e , thus 0 must come at e and at no other place. Thus we need to calculate number of ways we can have ( a , b , c , d ) such that a , b , c a n d d are element of 1 , 2 , 3 . . . . . 9 and a > b > c > d . Since integers have a natural order, this is same as counting number of ways selecting 4 integers from 1 to 9, which is ( 4 9 ) = 1 2 6
Any increasing number can be reversed to form a decreasing number, and this is an injection (the decreasing numbers obtained from reversing two distinct increasing numbers must be distinct). However, not all decreasing numbers can be reversed to an increasing number; those that end with 0 can't. So our task is reduced to computing the number of decreasing numbers that end with 0 , since all other decreasing numbers are cancelled by the increasing numbers.
For any 4 distinct digits from { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } , we obtain exactly one decreasing number (by sorting the digits from the largest to the smallest and appending 0 to the back). So the number of decreasing numbers that we seek is exactly the number of ways to choose four objects from a collection of nine, or ( 4 9 ) = 1 2 6 .
Any decreasing number (abcde) could be rewritten as an increasing number (edcba) and vice versa. The exception being any number starting with zero, since that would mean the increasing number would be a 4 digit number instead of 5.
Therefore if we calculate all the numbers in the form "abcd0" (where the last digit is zero) we get the difference.
The solution is picking 4 numbers out of possible 9.
C ( 9 , 4 ) = 4 ! ∗ 5 ! 9 ! = 1 2 6
We can see from symmetry that the two counts should be identical, except for the small anomaly of the increasing 5-digit numbers which start with 0. By basic combinatorics, this accounts for
i = 1 ∑ 9 j = i + 1 ∑ 9 k = j + 1 ∑ 9 l = k + 1 ∑ 9 1 = 1 2 6
Let's just say a number a b c d e is increasing number...then its opposite(i.e. e d c b a ) is a decreasing number...
So we have equal number of integers of increasing and decreasing numbers unless e = 0
Because if e = 0 there is no increasing number in a 5-digit number(i.e. 0 d c b a )
So we have to find number of 4-digit numbers a b c d and a > b > c > d > 0
I guess it can be solved making the answer equal to 1 2 6
Since the conditions a > b > c > d > e and a < b < c < d < e for decreasing and increasing numbers all involve the strictly greater/lesser than signs, this means that all the digits of the relevant 5-digit numbers are all distinct.
To form a 5-digit number that is decreasing, we can think of it as picking 5 different numbers from the 10 possible digits (1,2,3,4,5,6,7,8,9 or 0) and rearranging them in decreasing order. This rearranging naturally can only occur in one way. Therefore, the number of decreasing 5-digit numbers is simply the number of ways to pick 5 digits out of the 10 possible digits, which is given as ( 5 1 0 ) .
In the case of increasing numbers, we notice that the first digit a = 0 , as this will mean that the whole number is only 4 digits long. Also, if a = 0 , then b , c , d , e = 0 as that will cause them to be less than a , violating the condition a < b < c < d < e . Thus, there are only 9 numbers (all digits except 0) to choose 5 digits from. And since there is also only 1 way to arrange 5 distinct numbers in increasing order, the number of increasing numbers is ( 5 9 ) .
Hence, the absolute difference in the number of increasing and decreasing 5-digit numbers is:
( 5 1 0 ) − ( 5 9 ) = 1 2 6
If we choose 5 numbers from 10 there is only one way to arrange them in increasing and decreasing order , but while considering increasing 0 should not be considered , therefore Choosing increasing order 9c2=126 Choosing decreasing order 10c2=252 Therefore difference is -126 But absolute value is asked so 126
We can solve this pretty easily with correspondences. If you show me a decreasing number, I can just flip all the digits and give you a corresponding increasing number - unless your number ends in 0. So we just have to count the number of 5-digit decreasing numbers that end in 0.
We need four other digits - so let's simply pick four distinct digits out of nine, and then we can order them so that they are decreasing to get a 5-digit decreasing number! This will give us all our numbers, so our final answer is just 9 choose 4 = 126.
We know that a,b,c,d, and e must be distinct integers. However, for the decreasing number, the value of e can be 0. In the increasing sequence, no value can be 0 because the value of a must be greater than or equal to 1. So the difference between the number of possibilities of increasing and decreasing sequences is the number decreasing sequences with e=0. If we pick any four numbers for the other values, we know there is only one arrangement. Therefore, the answer is the number of ways to pick those four numbers. 9! / (5!)(4!) = 126.
Let's start with counting the number of so-called ''decreasing numbers'':
We have to construct a 5-digit number from the following set of numbers:
{0,1,2,3,4,5,6,7,8,9}
So, let's first select any 5 numbers from this set and the number of ways to do it will be 10C5 (no. of ways to select 5 numbers from a set of 10) .
Now once we have selected the numbers, the question asks to arrange the 5 numbers in the descending order. And, so there's only ONE possible arrangement of these 5 numbers .
(This is because, any 5 distinct numbers can be arranged in the descending or ascending order in only one particular way {take examples and you'll realise it.}
Hence the total number of ''decreasing numbers'' are 9C5.
Now, for the "increasing numbers'', following set is available"
{1,2,3,4,5,6,7,8,9} ->
*No zero, because, if we choose zero, and we arrange it with other 4 numbers in the ascending order, we have to put it as the first digit and no six digit no. can start with a zero. *
So selecting the 5 numbers from the set of 9 -> 9C5 . (And only one possible way of arranging)
Therefore, the (absolute) difference in the number of increasing and decreasing 5-digit numbers is 10C5 - 9C5
= 1 2 6
Consider the string 9876543210 now you have to choose any 5 digits. There are 10c5 methods to do so.For 123456789 there are 9c5 methods.Thus difference is 126.
Problem Loading...
Note Loading...
Set Loading...
When you see this problem, the first thing you'd want to do is: find out the how many decreasing numbers are there, find out how many increasing numbers are there and calculate their difference. Seems easy enough. However, that means going through a lot of case-bashing and ugly calculations. Is there a more elegant way of doing this?
It turns out there is more information hiding in the 'Details and assumptions' section than meets the eye.
Notice that if you flip the order of the digits of a 5 -digit decreasing number, you end up with a 5 -digit increasing number...
unless...
the last digit of the 5 -digit decreasing number is 0 . In that case, when you flip the number, you'll get a 4 -digit increasing number.
So, the only thing we have to do is find the number of 5 -digit decreasing numbers with the units digit equal to 0 [Find the number of a b c d e where e = 0 ]. Because for those decreasing numbers, we won't get a 5 -digit increasing number. So, the difference in the number of increasing 5 -digit numbers is equal to the number of 5 -digit decreasing numbers with the units digit equaling zero.
Now if you pick any 4 numbers from the set { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } and arrange them in descending order, you'll get a , b , c and d respectively. We can pick any 4 numbers from the set in ( 4 9 ) = 1 2 6 ways.
So, 1 2 6 is our desired result.