Trenchant_Troll
ad hominid
Registered: Mar 2004
Location: USA
Posts: 24302 |
Re: can some of you smart asses tell me how this works
quote:
Originally posted by r1burden
http://digicc.com/fido/
1. The 7up number game asks you to pick a 4-digit number. For example: 9384
2. You then scramble the 4 digits into a 2nd 4-digit number. 3894
3. Next you subtract the lesser number from the greater. 9384 - 3894 = 5490
4. Finally, you circle one of the 4 digits, any digit you wish to choose except a zero, then you reveal the other 3. 5(4)90 -- revealing 590
5. The guesser determines the circled digit. (4)
How does this work? What the guesser does is add up the digits you gave him. The hidden digit is the difference between that sum and the next highest multiple of 9.
For example, given 590:
5 + 9 + 0 = 14
The next highest multiple of 9 is 18, so
18 - 14 = 4.
By the way, there's nothing magical about 3 or 4 digit numbers. This will work with any string of digits, no matter how long.
I've seen this done before where people pick the year they were born as the 4 digits. Same trick.
But why is it that subtracting these numbers always leaves a number divisible by 9? To state the problem more exactly, can you prove that the absolute value of the difference of any two distinct permutations of digits in a 4-digit number will be divisible by 9?
[A permutation is just a fancy word for putting things in a different order. So each time you shuffle a deck of cards, you're creating a permutation of the deck].
One way to prove this is by enumeration. You can do this by writing out all of the possible permutations of all of the 4-digit numbers (there are 9,990 of them, if you leave out 0000, 1111, 2222, 3333, ... 9999 which cannot be used because all permutations are identical). But there are 23 pairs of permutations of each of these numbers (fewer when you consider that some numbers use the same digit more than once), so that means you'd have to perform calculations on nearly 230,000 pairs of numbers.
[23 pairs because you have 24 permutations of 4 digits and each of the 9,990 usable 4-digit numbers needs to get paired with its other 23 permutations -- therefore 23 pairs. We know there are 24 permutations of 4 digit numbers because for any 4 things, whether apples, handguns, or jelly beans, there are 4! different ways you can arrange them in a straight line. 4! means 4 factorial, which is 4 * 3 * 2 * 1 = 24. Notice that we use * to indicate multiplication, rather than x].
Still, you could write a simple computer program to do this, and that would prove that subtracting any two permutations would result in a number divisible by 9 (also called a multiple of 9).
But such a computer program would only prove the point for 4-digit numbers, and I said that this trick will work for any string of numbers, no matter how many. So to prove that you'd need to do an algebraic proof.
Now, an algebraic proof for n digits is still pretty wordy, so I'll just do a proof for a string of 4 digits and expand the proof at the end.
Consider the number abcd, where a,b,c and d are digits, that is: a,b,c and d are each numbers from 0 to 9 and at least one of them is different from at least one of the others.
Then the number
abcd =
a * 1000
+ b * 100
+ c * 10
+ d * 1
Now consider the reverse permutation of this number, say:
dcba =
d * 1000
+ c * 100
+ b * 10
+ a * 1
Subtracting these two, we get
(a * 1000) - (a * 1)
+ (b * 100) - (b * 10)
+ (c * 10) - (c * 100)
+ (d * 1) - (d * 1000)
By the distributive property of equality, we can rewrite this as
a * (1000 - 1)
+ b * ( 100 - 10)
+ c * ( 10 - 100)
+ d * ( 1 - 1000)
[I had to use the distributive property in order to bring the common factors out of the terms being subtracted].
Which, after doing the subtraction, equals
a * (999)
+ b * (90)
+ c * (-90)
+ d * (-999)
Which, by factoring, equals
a * (9 * 111)
+ b * (9 * 10)
+ c * (9 * -10)
+ d * (9 * -111)
Which, by the associative & commutative properties equals
9 * (a * 111)
+ 9 * (b * 10)
+ 9 * (c * -10)
+ 9 * (d * -111)
[I had to use both the associative & commutative properties because I changed both the order and grouping of the multiplication operations].
Using the distributive property again, we get
9 * [ (a * 111)
+ (b * 10)
+ (c * -10)
+ (d * -111) ].
As you can see, the number is divisible by 9. We don't know what the number is, because we don't know what the values of a,b,c or d are. But that doesn't matter, we know it is divisible by 9, no matter what a,b,c or d are, right?
But, if you were watching carefully, you'll notice that I've only proven this for abcd and dcba, which is only one out of the 23 pairs of permutations.
As I said before, I could prove this point by enumeration the other 22 pairs of permutations (e.g. abcd - abdc, abcd - acbd, ..., abcd - dcab), but that's a lot less fun than figuring out the general case, right? Besides, we want to prove the point for numbers with more than just 4 digits.
Here's how I would prove that the difference between any two permutations will be divisible by 9. Consider the 4-digit numbers again. There are only 4 positions or "places" in a 4-digit number:
The ones place 0001
The tens place 0010
The 100s place 0100
The 1000s place 1000
Now when those digits a,b,c or d are shuffled to make another permutation, each of them moves from one position to another (say, from the ones place to the tens place, or the 1000s place to the 100s place). And each of these "places" is 10 multiplied by itself some number of times, or 10 to the nth power (written 10n).
So the difference of the a digit in the first permutation minus the a digit in the second permutation is always
(a times 10 to some power) - (a times 10 to another power).
We can write this as:
(a * 10m) - (a * 10n)
where m and n are integers ranging from 0 to one less than the number of digits in our number.
In our example, this means that
m = 0, 1, 2 or 3
and also
n = 0, 1, 2 or 3.
Using the distributive property, we can rewrite this as:
(a * 10m) - (a * 10n)
= a * (10m - 10n).
Putting a, b, c and d together, we get
abcd = a * (10ma - 10na)
+ b * (10mb - 10nb)
+ c * (10mc - 10nc)
+ d * (10md - 10nd) .
We assert that if the a term is divisible by 9, and likewise are the b, c and d terms, then the whole expression, which represents the difference of any two permutations, is also divisible by 9, because (given some unknown integers ia, ib, ic, and id),
a * (9 * ia)
+ b * (9 * ib)
+ c * (9 * ic)
+ d * (9 * id)
, by the associative and distributive properties,
= 9 * [ (a * ia)
+(b * ib)
+(c * ic)
+(d * id) ]
Now here's something that will simplify our proof from here on out. We said that a was an arbitrary digit, any digit from 0 to 9 and we don't know which and it doesn't matter which. That means that this digit is not necessarily evenly divisible by 9 (in fact, only 0 and 9 are evenly divisible by 9). That means that the rest of the expression, (10m - 10n) has to be divisible by 9 or we can't prove our point. So that means that we can ignore the value of a from here on out (and that goes for the b, c and d values as well).
In fact, we can divide any or all terms of our expression by some constant integer and if each term still turns out to be divisible by 9, then we've proven our point. So from now on, we'll only worry about proving that (10m - 10n) is divisible by 9.
Let's break up the possible terms into 3 cases. By this, I mean that one of three statements is true about m and n, either:
Case 1: m = n
Case 2: m > n
Case 3: m < n.
When does m = n? That case occurs when we don't move the digit from its original place. For example, given the two numbers 4321 shuffled into 4123, the digits 4 and 2 did not change place. So they belong to Case 1 terms.
Digit 3 moves from the 100s place to the ones place, or from 102 to 100. So its m is 2, and its n is 0. So the 3 digit falls into a Case 2 term, because 2 is greater than 0 (m > n).
Digit 1 moves from the ones place to the 100s place, or from 100 to 102. So its m is 0, and its n is 2. So the 1 digit falls into a Case 3 term, because 0 is less than 2 (m < n). Subtract and you get:
4321
-4123
=====
(4-4) * 103 = 0 * 1000
(3-1) * 102 = 2 * 100 = 200
(2-2) * 101 = 0 * 10
(1-3) * 100 = (-2) * 1 = -2
=====
0198
As an aside, notice that 0198 is divisible by 9, and its digits added together are divisible by 9. But we want to go beyond this specific example. Let's go back to considering a 4-digit number, abcd, or even an arbitrarily long, n-digit number, abcdefg.... When we shuffle these digits, we said there could be 3 possible cases for any digit. We'll use a in our expression, but what we say about a is true of any and all digits in our n-digit number.
In Case 1, since m = n, we can rewrite our expression as
a * (10m - 10n)
= a * (10m - 10m)
= a * 0 = 0.
We see from this that this term is not going to add anything to our final result -- it's zero -- it's always going to be zero. And, that's fine because zero is divisible by every digit, including 9. [This is why our trick doesn't work for numbers where all the digits are the same (e.g. 1111, 2222, 3333, etc.), and this is why we required that at least one digit be different from another. Because if all the digits are the same, they will all be Case 1 digits and our final result would be 0000.... Then the trick doesn't work!]
Now, Case 2 and Case 3 are really only trivially different, and that's because of the following fact: For any real numbers r and s
r - s = -1 * (s - r).
This means that for any value of m and n,
10m - 10n = -1 * 10n - 10m.
Remember that we said that we could ignore any integer factors that we find in our expression so long as the remaining factors end up divisible by 9. This means that we can safely ignore -1. Hence, we can treat all Case 3 terms as if they were Case 2 terms. And if we prove that all Case 2 terms are divisible by 9, we're done.
So consider
a * (10m - 10n) where m > n.
We can safely factor out the a digit itself, leaving
(10m - 10n).
Now we divide this expression by 10n to yield
(10m-n - 1).
It's a good guess that subtracting 1 from any power of 10 is going to yield a bunch of 9s. But mathematical proofs cannot rely on good guesses or intuition. Still, first, let me give a simple example of this assertion: that 10n - 1 is divisible by 9. Consider 104 - 1, this can be rewritten as
104 - 1 = (103*10) - 1
Continuing in this pattern we get...
= (103*(9+1)) - 1
= ((103*9)+(103*1)) - 1
= (103*9)+(102*10) - 1
= (103*9)+(102*(9+1)) - 1
= (103*9)+((102*9)+(102*1)) - 1
= (103*9)+(102*9)+(101*10) - 1
= (103*9)+(102*9)+(101*(9+1)) - 1
= (103*9)+(102*9)+((101*9)+(101*1)) - 1
= (103*9)+(102*9)+(101*9)+(9+1) - 1
= (103*9)+(102*9)+(101*9)+ 9 + 0
= 9 * (103 + 102 + 101 + 1)
You'll notice that this is divisible by 9. So we're done!
Now, the formal statement of this pattern is that subtracting 1 from any power of 10,
10m - 1, for any integer m >= 3
= (10m-1*9)+(10m-2*9)+...+(101*9)+(9+1) - 1
= (10m-1*9)+(10m-2*9)+...+(101*9)+ 9
=[ (10m-1*1)+(10m-2*1)+...+(101*1)+ 1 ] * 9.
QED
[spoiler] And no, I am not that smart.
http://milkchaser.tripod.com/trick.html
__________________
Politicians are like diapers, they should be changed often, and for the same reason.
Last edited by Trenchant_Troll on 11-16-2006 at 11:54 PM
Report this post to a moderator |
IP: Logged
|
![[new thread]](/images/vb/button_newthread_off.png "Post New Thread")
![[post reply]](/images/vb/button_newreply_off.png "Post A Reply")
11-16-2006 04:54 PM
