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

In 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=4

In 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 545 is 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=5

In 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<=9

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