Subscribe via feed.

Divisible by 99

Posted by Karl Sharman on June 15, 2010 – 6:21 am

Find the smallest number that is made up of each of the digits 1 through 9 exactly once and is divisible by 99.


This post is under “MathsChallenge” and has 12 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

12 Responds so far- Add one»

  1. 1. John24 Said:

    123475869

    http://www.mixpod.com/playlist/28931537

  2. 2. Nimble1 Said:

    The brainless approach would be:
    123456789 mod 99 = 27
    123456789 – 27 = 123456762
    123456762 / 99 = 1247038

  3. 3. John24 Said:

    Better answer.

    To determine if a number is divisible by 99 it needs to be divisible by 9 and 11, both of which are simple tests.

    Divisible by 9 test. If sum of digits is divisible by 9 then the number is divisible by 9.
    Divisible by 11 test. If sum of ODD positioned digits minus the sum of the EVEN positioned digits is divisible by 11 then the number is divisible by 11.

    1+2+3+4+5+6+7+8+9 = 45 which is divisible by 9.
    123456789 is also the smallest integer containing all digits 1-9 exactly once.
    Sum of odd positioned digits (1, 3, 5, 7, 9) = 25 minus sum of even positioned digits (2, 4, 6, 8) = 20.
    25 – 20 = 5 which is not divisible by 11

    45 which is the sum of the digits contains only 1 possible value divisible by 11 (22, 33, 44 cannot exist using the above sum logic where the sum = 45 and the difference of the sum of odd positioned digits minus sum of even positioned digits = 22). So we need to find a set of numbers where the difference is equal to 11. In this case we need to add 6 to our current difference. This can be accomplished by adding 3 to the odd positioned digits and subtracting 3 from the even positioned digits thru swapping of digits. Either 1&4, 3&6, or 5&8.

    Combinations after swapping digits.
    (4, 3, 5, 7, 9) (2, 1, 6, 8)
    (1, 6, 5, 7, 9) (2, 4, 3, 8)
    (1, 3, 8, 7, 9) (2, 4, 6, 5)

    Smallest number in each grouping
    314256789
    125364789
    123475869

    The smallest of these 3 is…123475869.
    123475869 / 99 = 1247231

  4. 4. Nimble1 Said:

    I posted too fast without really looking at my results. My hat’s off to John24.

  5. 5. Gary Holmes Said:

    Karl,

    I posted a Question 4u on May-28 Riddle, “How Tall the Fish Is?”

    Have not received response yet…?

    If u prefer not to respond on Internet, pls send eM to garyfan@hotmail.com? Tks.

    Gary Holmes

  6. 6. Chris Said:

    Hi Gary. I’ve posted a response for you.

  7. 7. Chris Said:

    If the sum of the digits of a number is divisible by 9, then the original number is divisible by 9 also. As 1+2+…+9 is divisible by 9, any combination of 123456789 is also divisible by 9.

    Because 99 = 9 * 11 and 9 is coprime to 11, we only have to find the smallest number that is divisible by 11.

    The trick way to see if a number is divisible by 11, is to add the units, subtract the tens, add the hundreds, subtract the thousands etc. E.g. for 123456789 we find 9-8+7-6+5-4+3-2+1 = 5. Note that 123456789 = 5 (mod 11). Note that you get 5 either way, this is not a coincidence, it is always the same value whichever way you calculate the remainder.

    This means that swapping e.g. the numbers in the units and the hundreds, will not change the remainder mod 11. The same applies if you swap any pair of evenly spaced digits. If we swap an adjacent pair, or any oddly spaced digits, the remainder of the new number will change the remainder by 0, or twice the difference between the values of the selected pair. We need to either swap digits to subtract 16, as 5-16 = -11 = 0 (mod 11), or to add 6, as 5+6 = 11 = 0 (mod 11), to the remainder.

    Adding 6 sounds like the best bet. We also want to try to do this using only the unit and nearby digits. We’d also like an oddly spaced pair with a difference of 3.

    The simplest (one step move is) to swap the 5 and the 8 to get 123486759 = 0 (mod 11 and 99). Now swap 8 with 7 to get 123476859. Swap the 5 with the 6 to get 123475869.

    I’ll post an update if I can find a better solution than 123476859.

  8. 8. Chris Said:

    Sorry, I made an editing error:

    “If we swap an adjacent pair, or any oddly spaced digits, the remainder of the new number will change the remainder by 0, or twice the difference between the values of the selected pair.”

    should have read

    “If we swap an adjacent pair, or any oddly spaced digits, the remainder of the new number will change the remainder by twice the difference between the values of the selected pair.”

  9. 9. Chris Said:

    How weird,! Despite the times of posting, I hadn’t seen John24’s post. We both got 123475869, so that’s interesting.

    I can’t think of a strategy to ensure the swaps are guaranteed to provide the best solution. But my instinct tells me that 123475869 is the best solution – but I’m very intoxicated and very tired.

    8 Aug 2015: O me o my. John had a better answer that mine. I didn’t check carefully.

  10. 10. Karl Sharman Said:

    Gary – fish up side up…. sometimes it’s just luck, like buttered toast falling off the table…..

  11. 11. Chris Said:

    I don’t think I’ve shown why the trick way of checking that a decimal number is divisible by 11 works. So here’s why: I’ll use a six digit number for illustration (as that avoids difficulties with notation for the general case).
    Let the number, n, be represented as FEDCBA. That means
    n = A + 10B + 100C + 1000D + 10000E + 100000F
    If n is divisible by 11, then n = 0 (mod 11). Now 10 = – 1 (mod 11)
    and so 100 = 10*10 = (-1) * (-1) = 1 (mod 11). 1000 = -1 (mod 11), etc.
    So n = A – B + C – D + E – F (mod 11), hence the trick.

  12. 12. Shiv ranga Said:

    If a number 653 xy is Divisible by 99. Then ( x+y)=?

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0