Maths Olympiad Prep

Library / /65 of 69

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Mongolia

A number whose digits first increase and then decrease is called a *mountain-shaped number*. For example, 13101310 is mountain-shaped, while 13311331, 12341234, 43214321, and 34123412 are not mountain-shaped. How many four-digit mountain-shaped numbers are there in total?

Solution

Let the four-digit number be abcdabcd, where aa, bb, cc, dd are its digits and a0a \neq 0.

A four-digit mountain-shaped number must satisfy:
- The digits first increase, then decrease.
- That is, there exists an index kk (2k42 \leq k \leq 4) such that a<b<<xa < b < \cdots < x (up to position kk), then x>y>x > y > \cdots (from position kk onward).

But since there are only four digits, the only possible way is:
- a<b<c>da < b < c > d (the peak is at cc), or
- a<b>c>da < b > c > d (the peak is at bb).

But in the problem, 'first increase then decrease' means the digits strictly increase, then strictly decrease, and the peak is not at the first or last digit.

So, the only possible form is a<b<c>da < b < c > d.

Let us count the number of such numbers.

Let aa, bb, cc, dd be digits such that a<b<ca < b < c and c>dc > d.

Since aa is the first digit, a1a \geq 1.

Let us fix a<b<ca < b < c first. The digits aa, bb, cc are distinct and increasing, and a1a \geq 1, bb, cc are digits from 00 to 99.

Let us choose aa, bb, cc such that a<b<ca < b < c and a1a \geq 1.

The number of ways to choose aa, bb, cc with a<b<ca < b < c, a1a \geq 1 is (93)\binom{9}{3}, since aa can be 11 to 77, bb and cc are larger digits, and all three are distinct.

For each such triple, dd is a digit such that d<cd < c (since c>dc > d), and dd can be any digit from 00 to 99, except that dd can be equal to aa or bb (since otherwise the digits would not first increase then decrease), but the problem does not specify that all digits must be distinct, only that the digits first increase then decrease.

But let's check: For a<b<c>da < b < c > d, is it allowed for dd to be equal to aa or bb? Let's look at the example: 13101310 is mountain-shaped, and 11 repeats. So, digits can repeat, except that the sequence must first strictly increase, then strictly decrease.

So, a<b<ca < b < c (strictly increasing), c>dc > d (strictly decreasing from cc to dd), but dd can be equal to aa or bb.

So, for each choice of a<b<ca < b < c, dd can be any digit from 00 to c1c-1 (since d<cd < c), including possibly aa or bb.

Therefore, for each a<b<ca < b < c, the number of possible dd is cc (since d=0,1,,c1d = 0, 1, \ldots, c-1).

So, the total number is:

a=17b=a+18c=b+19c \sum_{a=1}^{7} \sum_{b=a+1}^{8} \sum_{c=b+1}^{9} c

Let us compute this sum.

Let us fix aa, bb, cc with a<b<ca < b < c, a1a \geq 1, c9c \leq 9.

For aa from 11 to 77:
- bb from a+1a+1 to 88
- cc from b+1b+1 to 99

Let us compute the sum:

For each aa, bb, cc, add cc.

Let us fix aa and bb.
For each cc from b+1b+1 to 99, sum cc.

The sum S=a=17b=a+18c=b+19cS = \sum_{a=1}^{7} \sum_{b=a+1}^{8} \sum_{c=b+1}^{9} c

Let us compute for each aa:

For a=1a=1:
- bb from 22 to 88
- For b=2b=2: cc from 33 to 99 (i.e., 3,4,5,6,7,8,93,4,5,6,7,8,9)
- For b=3b=3: cc from 44 to 99 (4,5,6,7,8,94,5,6,7,8,9)
- For b=4b=4: cc from 55 to 99 (5,6,7,8,95,6,7,8,9)
- For b=5b=5: cc from 66 to 99 (6,7,8,96,7,8,9)
- For b=6b=6: cc from 77 to 99 (7,8,97,8,9)
- For b=7b=7: cc from 88 to 99 (8,98,9)
- For b=8b=8: c=9c=9

Let us sum cc for each bb:
- b=2b=2: 3+4+5+6+7+8+9=423+4+5+6+7+8+9=42
- b=3b=3: 4+5+6+7+8+9=394+5+6+7+8+9=39
- b=4b=4: 5+6+7+8+9=355+6+7+8+9=35
- b=5b=5: 6+7+8+9=306+7+8+9=30
- b=6b=6: 7+8+9=247+8+9=24
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 42+39+35+30+24+17+9=19642+39+35+30+24+17+9=196

Now, a=2a=2:
- bb from 33 to 88
- b=3b=3: c=4c=4 to 99: 4+5+6+7+8+9=394+5+6+7+8+9=39
- b=4b=4: 5+6+7+8+9=355+6+7+8+9=35
- b=5b=5: 6+7+8+9=306+7+8+9=30
- b=6b=6: 7+8+9=247+8+9=24
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 39+35+30+24+17+9=15439+35+30+24+17+9=154

a=3a=3:
- b=4b=4: 5+6+7+8+9=355+6+7+8+9=35
- b=5b=5: 6+7+8+9=306+7+8+9=30
- b=6b=6: 7+8+9=247+8+9=24
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 35+30+24+17+9=11535+30+24+17+9=115

a=4a=4:
- b=5b=5: 6+7+8+9=306+7+8+9=30
- b=6b=6: 7+8+9=247+8+9=24
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 30+24+17+9=8030+24+17+9=80

a=5a=5:
- b=6b=6: 7+8+9=247+8+9=24
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 24+17+9=5024+17+9=50

a=6a=6:
- b=7b=7: 8+9=178+9=17
- b=8b=8: 99

Sum: 17+9=2617+9=26

a=7a=7:
- b=8b=8: c=9c=9

Sum: 99

Now, sum all these:
196+154=350196+154=350
350+115=465350+115=465
465+80=545465+80=545
545+50=595545+50=595
595+26=621595+26=621
621+9=630621+9=630

Therefore, the total number of four-digit mountain-shaped numbers is 630630.

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 and solution reproduced as published; topic and difficulty added by this site.