(Last Mod: 27 November 2010 21:40:03 )
As part of a marketing campaign, 7-Up put out the following spot (at least five years ago):
NOTE: Click on the guy in the lower-right corner to advance to the next slide.
This was received in a forwarded e-mail and contained the following claim:
THIS ONE WILL BLOW YOUR MIND!
I know there must be a very logical answer to this, but so far can't figure it out. Can you??
This came to me from a guy who has two masters and one doctorate degree and was a former instructor at the Naval Academy and he couldn't figure out how it was done. So don't write me back asking how they do it.... THIS IS GREAT, TRY IT!!!!!
Can you figure out how this works?
If you don't want to follow the link above, or in case it is no longer active, here is the gist of the puzzle.
Example:
83559392 (First number)
59239853 (Second number formed by scrambling the first)
24319539 (Difference of the numbers above)
3 (the first '3' in the above number is the one picked)
4293195 (The final number formed by shuffling the unpicked digits in the difference)
The last number is the only information provided to the puzzle master, but given only that information, they are able to tell you that the number you picked was 3.
It appears to be truly amazing, but in fact the trick is extremely simple - not withstanding the claim that a Ph.D. instructor at Annapolis couldn't figure it out. In all fairness, while I suspect that the claim is nothing more than made-up hype, it is actually quite plausible if the person happened to be an English, or History, or other fuzzy (non-technical) instructor and, in truth, even most techies would probably have a hard time figuring it out.
The trick is that the digits in the difference of the two numbers must be evenly divisible by nine, which means that the sum of the digits must also be divisible by nine. Since the third party is given all of the digits except one, it is a trivial matter to determine what value the missing digit must be.
Using the example in the description of the puzzle, the puzzle master is given the number 4293195. These digits sum up to 33. The next digit, which must be between 1 and 9 (inclusive) must take this to the next value that is divisible by 9. In this case this would be 36 and hence the value of the digit must be 3.
What if the sum of the digits that is given to the puzzle master is already divisible by nine? Well, in that case the same rule applies. The number that was picked, when added to the sum of the supplied numbers, must result in a value divisible by nine. The only two numbers that can do this would be 0 and 9. But remember that the rules of the puzzle required that a nonzero number be picked, hence the value must be 9. This is why the number picked has to be non-zero.
To see how and why this works, all we need to do is walk through the operations that are involved and observe the behavior step-by-step.
For simplicity, let's say that we pick four digits, {A,B,C,D}, such that not all of them are the same. Note that it is perfectly acceptable for more than one letter to represent the same digit - we only require that they not all be the same. For a concrete example, list say that these map to {9,7,7,3}
Our two numbers can then be any numbers that can be created by stringing these four digits together in any order we want (so long as we produce two different numbers). So let's say that the two numbers we create are:
x = CABD = C x 10^{3} + A x 10^{2} + B x 10^{1} + D x 10^{0} = 7973
y = DACB = D x 10^{3} + A x 10^{2} + C x 10^{1} + B x 10^{0} = 3977
Now consider what we have when we take the difference:
z = x - y = (C-D) x 10^{3} + (A-A) x 10^{2} + (B-C) x 10^{1} + (D-B) x 10^{0} = 7973 - 3977 = 3996
If there were no borrows, the we could write the difference as:
z = x - y = (C-D)(A-A)(B-C)(D-B) = 3996
where each expression in parentheses yielded the corresponding difference.
But, due to what is called the pigeonhole principle, we are actually guaranteed to have at least one borrow. So how is that reflected in the above result? The answer to that is obtained by considering the mechanics of how we perform a borrow - namely if the digit-by-digit subtraction in a particular column results in a negative number, we simply "borrow" from the column to the left by subtracting one from it and adding ten to the column we are working with. In the above case, we had to borrow in each column but the left-most, so our number can be written as:
z = x - y = (C-D-1)(A-A-1+10)(B-C-1+10)(D-B+10) = 3996
Does this actually work out?
(C-D-1) = (7-3-1) = 3
(A-A-1+10) = (9-9-1+10) = 9
(B-C-1+10) = (7-7-1+10) = 9
(D-B+10) = (3-7+10) = 6
So, yes, everything is consistent.
Now let's compute the sum of the digits in the difference, z.
S = (C-D-1)+(A-A-1+10)+(B-C-1+10)+(D-B+10)
Since addition is both commutative and associative, we can rearrange this as follows:
S = (A-A)+(B-B)+(C-C)+(D-D)+(10-1)+(10-1)+(10-1)
Notice that, regardless of which digits we picked, they all cancel out and we are left with
S = 9n
where n is simply the number of times that a borrow was performed. The key thing to note is that, regardless of what the value of n is, S is evenly divisible by 9.
The sum of the digits that the person supplies the puzzle master (call it T) and the digit they held back (call it p) then have the relation
S = T + p = 9n
p = 9n - T
Since p can't be zero, we simply pick the smallest value of T such that 9n is greater than T and we are done.
While the solution just given is complete, somewhat more insight can be gained for those that are familiar with modular arithmetic.
p = (9n - T) mod 9 = -T mod 9
subject to the proviso that if p = 0, then we choose p = 9 (which is perfectly acceptable since 0 and 9 are equivalent in a mod-9 world). This is why we have to place a rule in the puzzle requiring them to pick a nonzero digit - we can't tell the difference between the digit 0 and the digit 9. We could have just as easily requirement them to pick any digit, including zero, that was strictly less than nine, but there isn't a clean way to incorporate that into the banter of the puzzle in such a way as to keep it from being obvious.
To see if you truly understand the solution and how it works:
Can you see why it is critical that the first number selected not consist of a set of digits that are all equal?
Can you see how to remove the restriction that the subtraction be done so as to produce a positive result?
The detailed explanation given above doesn't require the reader to know anything beyond grade-school arithmetic. However, a much more elegant explanation can be given if the a couple of the basic properties of modular arithmetic are exploited.
As a transition between the two approaches, consider the same four digit example used above:
x = CABD = C x 10^{3} + A x 10^{2} + B x 10^{1} + D x 10^{0}
y = DACB = D x 10^{3} + A x 10^{2} + C x 10^{1} + B x 10^{0}
In the prior approach, we grouped terms in the difference according to their weight (i.e., the power of ten by which they were multiplied) as this made the digits in the answer easily identifiable.
z = x - y = (C-D) x 10^{3} + (A-A) x 10^{2} + (B-C) x 10^{1} + (D-B) x 10^{0}
But what if, instead, we forget about summing up the digits in (x-y) for the moment and just look at the properties of the value (x-y)? This means that we are free to expand the above expression and group it according to each digit in the original set of digits.
z = x - y = A x (10^{2}-10^{2}) + B x (10^{1}-10^{0}) + C x (10^{3}-10^{1}) + D x (10^{0}-10^{3})
Notice that each digit in the set is multiplied by the difference of two integer powers of ten. This is key. Now what happens if we reduce z modulo-9? Since modular reduction is distributive, we can reduce each term in the above expression individually and, in turn, reduce each factor in each term individually, before combining all of the terms and performing a final reduction. Hence, in each term we need to reduce a factor that is of the form:
f = (10^{p} - 10^{q}) mod 9
Where p and q are non-negative integers. However, we can again invoke the distributive nature of modular reduction to get the following:
f = ( (10 mod 9)^{p} - (10 mod 9)^{q} ) mod 9
Since 10 mod 9 is equal to 1, we have
f = ( 1^{p} - 1^{q} ) mod 9 = (1 - 1) mod 9 = 0 mod 9 = 0
Hence every term in the above expression for z includes a factor that reduces to zero modulo-9. Therefore:
z mod 9 = 0
(This proof, using summation notation and a more rigorous wording, has been written up by Thomas Eggers in a Word document.)
This means that z must be evenly divisible by nine and, as most people learned in grade school, the sum of the digits of any number divisible by nine is also divisible by nine.
If you have followed the development properly, then you should now be able to prove for yourself that the sum of the digits in any (base-10) number divisible by nine is also divisible by nine and, in fact, that the sum of the digits in any base-B number is divisible by (B-1).
This puzzle is actually a specific example of a process known as "casting out nines," which has been around since at least the third century.
The basic idea behind casting out nines is to provide a quick way of checking the accuracy of a series of arithmetic operations (addition, subtraction, multiplication, and division). It is important to note that casting out nines is only applicable, at least without very careful consideration, to working with integer arithmetic.
The mathematical underpinnings of casting out nines is that two expressions that are equal in the set of infinite integers (our normal, everyday integer world) then they are equivalent in all modular worlds. For instance, let's say that we wanted to perform the following operations:
x = 124 * (78 - 42) + 17
After performing the arithmetic, we get
x = 4481
But is that right? Did we make any stupid math errors? What if we did the math in a mod-7 world? Then we should get the following:
x = ((124 mod 7) * ((78 mod 7) - (42 mod 7)) + (17 mod 7)) mod 7
x = (5 * (1 - 0) + 3) mod 7 = 8 mod 7 = 1
and the answer should be equivalent to this in a mod-7 world.
x = 4481 mod 7 = 1
As an interesting aside, when I originally evaluate the above expression I got 4447 as an answer (using the Windows calculator). It appears I subtracted, rather than added, 17. I caught the error because the answer I got has a residue of 2 (mod 7) instead of 1. So the method really is useful.
Notice that if we make mistakes in our arithmetic and end up with a wrong answer, then one in seven wrong answers will pass our test. But that still means that, roughly, we'll catch about 86% of our mistakes.
But taking things modulo-7 is not the easiest thing in the world and we can make mistakes in doing it so as to get a false indication that we have made an error when, in fact, we might not have. What we want is to use a modulus that makes it very easy and quick to use -- thus encouraging us to actually use it -- and one that makes it less likely that we will make a mistake while performing the check.
This is where using modulo-9 (or, in general, one less than the number base) comes in handy. Because any base-10 number divisible by 9 has the property that the sum of its digits is divisible by 9, we can compute the mod-9 residue of any base-10 number by "casting out nines" and keeping only the excess.
For instance, the mod-9 residue of 8936574 can be found by first "casting out" the '9', the '3' and '6', and the '5' and '4', leaving the '8' and '7'. Adding these gives 15 which becomes 6 (either by adding the digits or taking the residue mod-9, the whole point is that these are equivalent operations).
So the above check, using modulo-9, is very simple to perform:
x = 124 * (78 - 42) + 17
x mod 9 = (7 * (6 - 6) + 8) mod 9 = 8
After performing the arithmetic, we get
x = 4481
x mod 9 = 8
As with mod-7, there is a roughly 1 in 9 chance that an arithmetic error will result in an answer that has the correct mod-9 residue. None-the-less, this will catch nearly 90% of most mistakes.
Notice that you can also perform other checks, such as working with mod-10, which means simply taking the last digit of each number.
x = 124 * (78 - 42) + 17
x mod 10 = (4 * (8 - 2) + 7) mod 10 = (24 + 7) mod 10 = 1
After performing the arithmetic, we get
x = 4481
x mod 10 = 1
If you perform both checks, then the chance of a random error not being detected is only about 1%. For those that are interested, this is due to the properties of the Chinese Remainder Theorem. If you had a computation that you wanted to have a high degree of confidence that it was done correctly, you could do a check using mod-9 and mod-10, which are very easy, followed by checks using mod-7 and mod-11. The last two, while more cumbersome, are still fairly easy to perform. The end result is that you would only expect an incorrect computation to survive all four checks about one time in nearly seven thousand errors made.
It should be noted that the use of mod-10 is actually quite weak since there are many categories of errors that will fail to affect the unit's digit in the answer and hence not be detected. But many common mistakes, such as using the wrong operator or failing to obey operator precedence and parentheses, have a high likelihood of changing the unit's digit and hence being caught..
You might have noticed that it was stated in the previous section that casting out nines would catch 90% of "most" mistakes and that the term "random errors" was used. Not all errors are random. For instance, it is very common to make the mistake of transposing digits within a number. This particular category of error is undetectable using mod-9 as a check.
For instance, let's say that we want to add 345+692+1531 to get 2568. But what if we were seriously dyslexic and instead computed 354+962+5113 and got 6429 instead? In both cases, casting out nines would yield a final excess of 3.
However, this very fact when combined with the standard techniques of double-entry bookkeeping provide a powerful means of identifying such errors.
In double-entry bookkeeping, all transactions are performed in complementary pairs - all credits are offset by equivalent debits. In the end, the sum of all credits should therefore equal the sum of all debits (the infamous Assets = Capital + Liabilities).
But what if they don't? In that case, we know than an error of some type was made somewhere. But what type of error? If we could identify what type of error was made, we might be able to find the actual error more easily. So what if we perform a modulo-9 check and it fails to indicate an error? There are then two obvious possibilities - either the random error just happened to produce a wrong answer that was equivalent to the right answer in a mod-9 world (and there, after all, is a better than 10% chance of exactly that happening) or we made a type of error that is guaranteed to produce a wrong answer that is equivalent to the right answer, such as transposing two digits somewhere in one (or more) of the numbers involved in the computation.
So, if we have two numbers, A and B, that should be equal and aren't, then we could compute the mod-9 residues of each and, if they are equal, assume (at least initially) that we probably transposed two digits someplace and examine our work accordingly. In practice, this is probably the simplest approach, but a more elegant description of the process is to subtract the two numbers, then throw out the nines, and then assume a transposition error if the result is zero.