blinkdagger

MMM #25: Monotonous Monday Math Madness

02 Feb 2009 Quan Quach 3 comments 110 views

3 Responses to “MMM #25: Monotonous Monday Math Madness”

1. on 09 Feb 2009 at 9:56 pm 1Ravi Krishnan Unni

   This is a direct method.
   – All numbers between 1 and 9 (both including), are monotonically increasing. So we have 9 numbers.
   – Between 10 and 100 we have, 8 + 7 + 6 + … + 2 + 1 = 36 monotonically increasing numbers.
   – Between 100 and 200 we have 7 + 6 + 5 + … + 2 + 1 = 28.
   Between 200 and 300 we have 6 + 5 + … + 2 + 1 = 21. So on…
   So total number of monotonically increasing numbers between 100 and 1000 = 84
   Going on similarly…
   – Between 1000 and 10,000 = 126
   – Between 10,000 and 1,000,00 = 126
   – Between 1,000,00 and 1,000,000 = 84

   So, TOTAL number of monotonically increasing numbers between 1 and 1,000,000 is
   9 + 36 + 84 + 126 + 126 + 84 = 465.

   So the probability that the number will be monotonically increasing, given that a number is randomly select between 1 and 1,000,000 = 465 / 1,000,000…

   Here is the MATLAB code:

   positive = 0;
   for i = 100000:1000000
       no = i;
       key = true;
       % extracting individual from a number
       for j = 1:6
           if floor(no/10^j) == 0
               break;
           end
       end
       digits = zeros(1, j);
       for k = 1:j
           digits(j-k+1) = rem(no, 10);
           no = floor(no/10);
       end
       % check for monotonically increasing characteristic
       for k = 1:j-1
           if digits(k+1) <= digits(k)
               break;
           end
           if k == j-1
               positive = positive + 1;
           end
       end
       if j == 1
           positive = positive + 1;
       end
   end
   % the result
   % for 1,000,000 the result is 465
   display(positive);

2. on 11 Feb 2009 at 9:32 pm 2Michaluk

   You can think about this problem using combinations. You can’t use any digit more than once in constructing a number, and for a given set of digits (3,4,1,6 for example), there is always exactly one way to order them to get a monotonically increasing (MI) number (1346 in this example).

   0 1 2 3 4 5 6 7 8 9
   Pick N different digits: this is an N digit MI number.

   So for N digits, the number of MI numbers is 10 choose N, and you can just add up all the results for N=1, 2, … 6.

   You have to be careful not to double count numbers this way. For instance, there are 10 one digit MI numbers (9 since we’re not counting 0), and 10 choose 2 is 45. But those 45 2 digit numbers include 9 one digit numbers (01, 02, 03 etc.).

   Similarly, the 6 digit numbers include all 5 digit numbers except those that start with 0 (since these would start with 00 for the 6 digit numbers), but of course these were already counted in the 4 digit numbers)

   In the end, rather than making all these modifications its easier to do the sum backwards:

   6 digit numbers -> 10 choose 6 = 210
   Now we’ve already counted all 5 except those starting with 0 (which are really 4 digit numbers), so we can jump straight to 4 digits

   4 digit numbers -> 10 choose 4 = 210
   Similarly, we go to 2 digit numbers

   2 digit numbers -> 10 choose 2 = 45

   For a total of 465, which is the same result as Ravi got above, but in a slightly more elegant manner. Also, this would scale much better if you ramped up to a higher number of digits.

3. on 12 Feb 2009 at 7:29 pm 3jewkulak

   Darn, I messed up, wasn’t using enough common sense. It seems so obvious now. As in the above comments it’s simply (9 nCr 8)+(9 nCr 7)+(9 nCr 6)+(9 nCr 5)+(9 nCr 4)+(9 nCr 3) to put it even more shortly. (I’m using calculator notation.)

Leave a Reply

Include MATLAB code in your comment by doing the following:

<pre lang="MATLAB">

%insert code here

</pre>

Name

Mail (hidden)

Website