Maths Olympiad Prep

Library / /110 of 121

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it India

Problem:

All possible 6-digit numbers, in each of which the digits occur in non-increasing order (from left to right, e.g., 877550877550) are written as a sequence in increasing order. Find the 20052005-th number in this sequence.

Solution

Solution:

Consider a 6-digit number whose digits from left to right are in non-increasing order. If 11 is the first digit of such a number, then the subsequent digits cannot exceed 11. The set of all such numbers with initial digit equal to 11 is
{100000,110000,111000,111100,111110,111111}. \{100000, 110000, 111000, 111100, 111110, 111111\}.
There are 66 elements in this set.

Let us consider 6-digit numbers with initial digit 22. Starting from 200000200000, we can go up to 222222222222. We count these numbers as follows:

200000200000-211111211111::66
220000220000-221111221111::55
222000222000-222111222111::44
222200222200-222211222211::33
222220222220-222221222221::22
222222222222-222222222222::11

The number of such numbers is 2121.

Similarly we count numbers with initial digit 33; the sequence starts from 300000300000 and ends with 333333333333. We have

300000300000-322222322222::2121
330000330000-332222332222::1515
333000333000-333222333222::1010
333300333300-333322333322::66
333330333330-333332333332::33
333333333333-333333333333::11

We obtain the total number of numbers starting from 33 equal to 5656.

Similarly,

4000004000004333334333335656
4400004400004433334433333535
4440004440004443334443332020
4444004444004444334444331010
44444044444044444344444344
44444444444444444444444411
126126
500000500000544444544444126126
5500005500005544445544447070
5550005550005554445554443535
5555005555005555445555441515
55555055555055555455555455
55555555555555555555555511
252252
600000600000655555655555252252
660000660000665555665555126126
6660006660006665556665555656
6666006666006666556666552121
66666066666066666566666566
66666666666666666666666611
462462
700000700000766666766666462462
770000770000776666776666210210
7770007770007776667776668484
7777007777007777667777662828
77777077777077777677777677
77777777777777777777777711
792792

Thus the number of 6-digit numbers where digits are non-increasing starting from 100000100000 and ending with 777777777777 is
792+462+252+126+56+21+6=1715 792 + 462 + 252 + 126 + 56 + 21 + 6 = 1715
Since 20051715=2902005 - 1715 = 290, we have to consider only 290290 numbers in the sequence with initial digit 88. We have
800000855555:252860000863333:35864000864110:3 \begin{aligned} & 800000 - 855555 \quad: \quad 252 \\ & 860000 - 863333: 35 \\ & 864000 - 864110 \quad: \quad 3 \end{aligned}
Thus the required number is 864110\underline{864110}.

It is known that the number of ways of choosing rr objects from nn different types of objects (with repetitions allowed) is (n+r1r)\binom{n+r-1}{r}. In particular, if we want to write rr-digit numbers using nn digits allowing for repetitions with the additional condition that the digits appear in non-increasing order, we see that this can be done in (n+r1r)\binom{n+r-1}{r} ways.

Now we group the given numbers into different classes and write the number of ways in which each class can be obtained. To keep track we also write the cumulative sums of the number of numbers so obtained. Observe that the numbers themselves are written in ascending order. So we exhaust numbers beginning with 11, then beginning with 22 and so on.

NumbersDigits used other than the fixed partnnrr(n+r1r)\overline{\binom{n+r-1}{r}}Cumulative sum
beginning with 111,01,02255(65)=6\binom{6}{5} = 666
222,1,02,1,03355(75)=21\binom{7}{5} = 212727
333,2,1,03,2,1,04455(85)=56\binom{8}{5} = 568383
444,3,2,1,04,3,2,1,05555(95)=126\binom{9}{5} = 126209209
555,4,3,2,1,05,4,3,2,1,06655(105)=252\binom{10}{5} = 252461461
666,5,4,3,2,1,06,5,4,3,2,1,07755(115)=462\binom{11}{5} = 462923923
777,6,5,4,3,2,1,07,6,5,4,3,2,1,08855(125)=792\binom{12}{5} = 79217151715
from 800000800000 to 8555558555555,4,3,2,1,05,4,3,2,1,06655(105)=252\binom{10}{5} = 25219671967
from 860000860000 to 8633338633333,2,1,03,2,1,04444(74)=35\binom{7}{4} = 3520022002

The next three 6-digit numbers are 864000,864100,864110864000, 864100, 864110.

Hence the 20052005-th number in the sequence is 864110864110.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.