## 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.

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

June 15th, 2010 at 7:41 am

123475869

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

June 15th, 2010 at 8:42 am

The brainless approach would be:

123456789 mod 99 = 27

123456789 – 27 = 123456762

123456762 / 99 = 1247038

June 15th, 2010 at 8:48 am

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, = 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,

(1, 6, 5, 7, 9) (2, 4, 3,

(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

June 15th, 2010 at 9:04 am

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

June 15th, 2010 at 1:41 pm

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

June 15th, 2010 at 5:26 pm

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

June 15th, 2010 at 5:51 pm

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.

June 15th, 2010 at 5:58 pm

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.”

June 15th, 2010 at 6:52 pm

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.

June 16th, 2010 at 1:24 am

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

August 4th, 2012 at 4:34 am

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.

August 7th, 2015 at 6:28 am

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