INMO 2005 problem
All possible digit numbers in each of which the digits occur in non-increasing order(from left to right )are written as sequence in increasing order. Find number in this sequence
The answer is 864110.
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.
1 solution
6 digit numbers with initial digit :
T(n) : T 1 + T 2 + T 3 + T 4 + T 5 + T 6
T(1) : 1 + 1 + 1 + 1 + 1 + 1 = 6 numbers
[100000,110000,111000,111100,111110,111111]
T(2) : 6 + 5 + 4 + 3 + 2 + 1 = 21 numbers
[200000,210000,211000,211100,211110,211111]
[220000,221000,221100,221110,221111]
[222000,222100,222110,222111]
[222200,222210,222211]
[222220,222221]
[222222]
Similarly
T(3) : 21 + 15 + 10 + 6 + 3 + 1 = 56 numbers
From this we could understand that all sequences will follow the same order ie
T(n) : = T(n-1) + [T(n-1) - T 1 ] + [T(n-1) - T 1 − T 2 ] ... [T(n-1) - T 1 − T 2 − T 3 − T 4 − T 5 ]
From the increase in no:of possibilities at each place as initial digit increases.
Similarly considering up to 7 digits we get a total of : 1715 numbers
Now consider 6 digit numbers with initial digit 8 and we get 864110 as the 290th term ie 2005th term in the sequence