# My Solution to jd2718’s divisiblity puzzle (SPOILER)

Last week jd2718 posted this interesting and challenging divisibility puzzle.

The challenge was to prove or disprove the statement:

Every three-digit number is a multiple of 11 or can be turned into a multiple of eleven by changing one digit.

This turned out to be a very fascinating problem, and I’d encourage you to at least think about whether you believe it to be true of false, and why, before reading my solution below or the other discussions on jd’s blog.

Spoiler solution follows..

** Lemma**:

A number is divisible by 11 iff the alternating sum of its digits is divisible by 11.

**Handwaving Proof of Lemma:**

For simplicity I’ll prove only the three-digit version of this lemma. Consider a three-digit number N consisting of the digits ABC, so that N = 100A + 10B + C.

Then N = 99A + A + 11B – B + C

= 11(9A + B) + A – B + C

Clearly 11(9A+B) is a multiple of 11. And the sum of two multiples of 11 is also a multiple of 11. Thus N is a multiple of 11 iff A – B + C is also a multiple of 11.

Using the lemma, the challenge becomes finding a way of converting every three-digit number into a number whose alternating digit sum is a multiple of 11. I approached this by casework, first considering the different possible sums of A+C. 1<=A<=9 and 0<=C<=9 so 1<= A+C <= 18

**Case 1: **11<= A+C <= 18

In this case, you can choose B, 0 <= B <= 7 such that A -B + C = 11

**Case 2: **1 <= A+C <= 9

In this case, you can choose B = A+C so that A – B + C = 0

**Case 3:** A+C = 10

In this case, you would have to set B to something from among the set {…, -12, -1, 10, 21, …} in order to get A – B + C = a multiple of 11 by changing B. Since this is not possible, we must consider changing A or C instead

Case 3a:A+C = 10 and 0<= B <= 3In this case, if we increase the smaller of A or C by (B+1) we will get (assume wlog that we increase C): A – B + (C + B + 1) which is equal to A+C+1 = 11. Since A+C = 10, at least one of them will be less than or equal to 5 and thus may be increased by up to 4 without a problem.

Case 3b:A+C = 10 and B=4In this case, to use the trick above, we’d have to increase A or C by 5. As long as either A or C is less than 5, this still works. But now we could have some trouble, because if both A and C are 5, we can’t use that approach. So the number

545is starting to look like a potential counterexample of the statement.

Proof that 545 is a counterexample:

Part A: Consider changing A and leaving B and C alone. Then we need A-4+5 = A+1 to equal a member of the set {…, -11, 0, 11, …} Thus A would have to be chosen from the set {…, -12, -1, 10, …} and none of these is a valid digit, so we can’t change 545 to a multiple of 11 by changing the first digit.

Part B:Consider changing B and leaving A and C alone. We’ve already shown that we can’t get A-B+C to sum to 11 in this case, but let’s check the other multiples of 11 for completeness. A-B+C = 5-B+5 = 10-B. So we need 10-B to equal a member of the set {…, -11, 0, 11, …} Thus B would have to be chosen from the set {…, 21, 10, -1, …} and again none of these is a valid digit, so we can’t change 545 to a multiple of 11 by changing the middle digit.

Part C:C is equivalent to A in this problem, except that C is permitted to be zero and A is not. However, by the same logic used in part A above, B would have to be chosen from the set {…, -12, -1, 10, …} and none of these is a valid digit, so we can’t change 545 to a multiple of 11 by changing the last digit.

At this point, I originally stopped working, since proving a single counterexample disproves the conjecture.

However, then I got curious as to whether or not it was the only counterexample, so I finished out the casework thus:

Case 3c:A+C=10 and B=5In this case we can reduce A or C by 5, in which case we would have (assume wlog that we changed C): A – 5 + (C – 5) = A+C-10 = 0. If A and C are both 5, we must choose C to reduce (since A cannot be reduced to zero); otherwise one will be larger than 5 and we must choose that one to reduce.

Case 3d: A+C=10 and 6<=B<=9In this case we can reduce the larger of A or C by (10-B) which will be between 1 and 4 (inclusive) and this will always be possible. Then (assume wlog that C is changed) A-B+C = A – B + (C – (10-B)) = A – B + C -10 + B = A + C -10 = 0.

So 545 is the only counterexample, and the various cases show a method of change for any other number.

Mathmom, your solution is a lengthy one. It is simpler to first recognize that all the 3-digit, base-10 numbers (100 through 999), taken in sequence, will yield “remainders” of 0 through 10, repeating sequentially and continuously. To alter any of these three-digit numbers with remainders 0 through 9 such that they would be evenly-divisible by 11, all you have to do is reduce them to the next-previous evenly divisible value. That is to say, you ignore remainders 0 through 9. To accomodate the numbers whose remainders are 10, you merely bump the 10-value digit by 1.

Oops, scratch that.

To alter any of these three-digit numbers with remainders 0 through 9 such that they would be evenly-divisible by 11, all you have to do is reduce them to the next-previous evenly divisible value.If I’m understanding what you’re saying correctly, this isn’t necessarily (or even usually, I don’t think) a single-digit change. 654 has a remainder of 5 mod 11. The next previous multiple of 11 is 649. You can’t get from 654 to 649 by changing a single digit. However, you can change the hundreds digit from 6 to 1, to get 154, which is a multiple of 11.

I think you mean that for a remainder of 10 you could bump the 1-value digit by 1, which would normally work, unless it is already 9. For example 989 has a remainder of 10 but it’s a 2-digit change to increase it to 990 which is the next multiple of 11.

Finally, do you think the statement is true? Because it is not. Read my solution more carefully, as there is a proven counter-example in there!

ah, I was busy replying to your first comment when the second arrived…