Solution to Problem 35

Congratulations to this week's winner

Mike Fitzpatrick and Ray Kremer

Correct solutions were also received from Jeffrey Downin, Jan Siwanowicz and William V. Webb.

The number of integers satifying the conditions is 2d - 1. One method of soulution is the following:

Look at the left most digit, call it L. The digits less than L must follow in decreasing order while those greater than L must follow in increasing order. If L = d, there are no digits larger than L; if L = d - 1, there is one digit larger than L and it can appear in any of d - 1 places; if L = d - 2, there are two digits larger than L and they take up two of the following d - 1 places; and so on. This gives the total number to be

C(d - 1,0) + C(d - 1,1) + C(d - 1,2) + ... + C(d - 1,d - 2) + C(d - 1,d - 1),

where C(d-1,k) is the number of ways to select a subset of size k from a set of size d - 1. The above sum is the desired number given above.

You are visitor number 2977 to this page.
Page last updated 24 April 1998.