Puzzle – what’s your divisibility quotient?
July 19, 2007 pm31 1:39 pm
Consider this statement:
Every three-digit number is a multiple of 11 or can be turned into a multiple of eleven by changing one digit.
eg 832 is not divisible by 11, but 834 836 is. Again 265 is not, but 165 is.
- Will you first try to prove or disprove this?
- What will your first approach be?
After a few answers come in, I will share how I attacked this one, and why I chose that approach.
(this is one of several vacation posts. They will be spotty. They may be strange. And no pictures or images until I get back)
20 Comments
leave one →
JD2718 
um … 834/11 \not\in {\Bbb Z}.
you mean 836?
I understand why this works — I’m having trouble with a succinct explanation… It has to do with the way multiples of 11 cycle through “last digits,” hitting 9 of them each “century.”
Vlorbik – oops! You are correct.
And rdt, do you think it is true? (then how would you approach proving it?) Or do you think it is false? (then how would you approach disproving it?)
Well, I think it is true. Having difficulty explaining it elegantly (hence, didn’t say “I know it is true”).
First thought is proof by cases.
If the three digit number is divisible by 11, it is congruent to 0 mod 11 and we’re done.
If the three digit number is not divisible by 11, then it is congruent to 1, 2, 3, …, 10 mod 11. now have to figure out a way to succinctly say the rest. Something along the lines of – if the units digit differs by the remainder mod 11…Any ideas?
Often, I approach “prove or disprove” type questions by trying to find a counter-example, and when I see what it is that is preventing me from finding one, that informs the method of a proof.
In this case, I decided to start with an algebraic approach (the 3-digit number ABC = 100A+10B+C), realized I was coming up with a proof of why the “divisibility by 11” trick works (100A+10B+C = 99A+A+11B-B+C…), and then decided to work with the divisibility by 11 rule and a little casework to do the proof. And then I hit a glitch in my casework.
I am pretty sure it is false and I think I have a counter-example that came from where I first hit a glitch in my casework. (Actually, I think I have at least 2 counterexamples.) I won’t say more yet to avoid spoiling the problem for others.
Hmm, ok mathmom, I’m interested in seeing your counterexamples!
Mathmom – so as not to spoil it for others, would you mind emailing me the counterexamples? jackie1618 at gmail dot com
jackie, I emailed you my counterexamples
Mathmom, thanks! Off to play with them…
This is an interesting problem, because usually finding a counterexample is the definitive disproof of the theorem. But in this case, demonstrating that a counterexample is indeed a counterexample is also non-trivial. Very interesting. (I believe I can indeed “prove” that my counterexamples are indeed counterexamples.) Looking forward to chatting about this problem more…
Thanks for the problem, JD, and I hope you are enjoying your vacation even though you didn’t take our advice to go to Iceland. ;-)
JD, great problem! Nice reminder that I shouldn’t make a claim that a statement is true based upon, “well, I tried it for 3 or 4 numbers and it seems to hold.!
Mathmom, I’m looking forward to your proof that the counterexample holds (only only the first does – the second doesn’t (thanks to vlorbik for pointing this out via email).
oh, you’re right, the second doesn’t hold. oops…
In fact, I believe, but cannot yet prove, that the first counterexample I sent may be the only one.
The jist of my proof of my counter example is to use the divisibility by 11 rule: if the number has digits ABC, then ABC is divisible by 11 iff A-B+C is divisible by 11. so, do the 3 cases: plug in two of the numbers and see if there’s any number between 0 and 9 that can make A-B+C equal to 0 or 11 (the only possibilities in this 3-digit case). The first and last digit cases are the same, except that you can’t (I don’t think) permit 0 for A but you can permit it for C. For the number I sent you, it turns out that for each of the digits, you’d have to change it to -1 or 10 in order to make the alternating sum work out to a multiple of 11, and since neither of those is a valid digit, it can’t be done.
Hello JD,
I think I’ve found the solution. I posted it here:
http://www.physicsforums.com/blogs/edgardo-22482/a-nice-3-digit-puzzle-1020/
My answer is that the statement is not true.
Edgardo,
looks like you have it. I will wait a bit more, and post my approach. It’s probably not ideal, but deciding how to tackle something can be the interesting part.
I like how conscious you are of your decisions along the way. It really helps, in the long run.
A weird generalization:
Every k-digit number is a multiple of 11 or can be turned into a multiple of eleven by changing exactly one digit, if k is even. If k is odd, there is exactly one k-digit number that does not satisfy this property.
I have been able to do this for k=2 (trivial), k=3 as shown by Edgardo and others above, k=4…7 by exhaustive search. Haven’t tried other k yet.
Clueless
As shown by the snippet above, I posted my solution to this puzzle on my blog here.
Only now it’s 6pm and there’s no dinner. The sacrifices a math mom’s family has to make sometimes….
I did prove that there is only one counterexample.
Clueless’ generalization is quite interesting!
Thanks for the fascinating puzzle and discussion everyone!
If I have not made a mistake in my programming, these are the higher-digit numbers for which the conjecture does not work:
27272, 1818181, 636363636 …..
Wow, thanks for thinking this was a good question. It’s a better discussion…. You guys are impressive.
Clueless, wow, those counterexamples are fascinating. Seeing them, can we generalize why they (don’t) work, and figure out what the pattern is for higher numbers of digits?