Fun with numbers

4 Responses to “Fun with numbers”

1. Baron on October 8th, 2005 20:02

   Never to be one to back down on a good math challenge, I took a shot at it. I have most of the details, but I’m missing something to put a whole proof together. It doesn’t help that my mathematical induction/proof skills have been unused in a good 3 years along with math relations and identities.

   Some definitions:
   Let x be the number you pick with digits a0, a1, … , aN
   Let y be the number with digits b0, b1, … , bN that is rearranged digits from x
   The difference would be z=|x-y| made up of digits c0, c1, …, cN; cN = |aN - bN|

   A bunch of random test cases show that the sum of the digits of z is always divisble by 9. ie: (c0 + c1 + … + cN) mod 9 = 0. So, given all the digits except 1, you can always figure out the missing digit.

   Now any of you remember, a number is divisible by 9 iff the sum of its digits is divisible by 9. The same property holds for the number 3. So in our case, z = |x-y| must be a multiple of 9.

   Here’s where I’m stuck. Why is z with digits cN divisible by 9? I’ll sleep on it and see if something comes to me… Yes, I dream math. At least I don’t own a pocket protector. *cough* http://www.nesser.org/blog/archives/8 *cough*

2. Baron on October 8th, 2005 22:12

   Damn you Mark. I couldn’t stop scribbing out a mess of algebraic notation on my little scrap piece of cardboard. It even caused my mom to ask “What the hell is that mess?” But I think I got it. Plain HTML text is gonna make this a mess so hopefully it’s readable.

   Extending my notation above,
   Let x = (aN * 10^N) + … + (a1 * 10^1) + (a0 * 10^0)
   Let y = (bN * 10^N) + … + (b1 * 10^1) + (b0 * 10^0)
   -> we are just breaking down a number into sums of their place value. For example, 1234 = (1 * 1000) + (2 * 100) + (3 * 10) + (4 * 1).

   Define a function sigma(m, n, expression) such that you take the summation of the expression where m is from 0 to n. So then, we have:
   x = sigma(j, N, (aj * 10^j))
   y = sigma(j, N, (bj * 10^j))

   Let’s assume x is bigger than y such that z = x - y >= 0. Just so we don’t have to deal with absolute values. So here’s the math:
   z = x - y
   = sigma(j, N, [aj * 10^j]) - sigma(j, N, [bj * 10^j])
   = sigma(j, N, [(aj * 10^j) - (bj * 10^j)])
   = sigma(j, N, [(aj - bj) * 10^j])

   Now, 10^N can be rewritten as [1 + (N-1 number of 9’s)]. For example, 100 = 1 + 99. Generally, this is 10^N = 1 + sigma(j, N-1, [9 * 10^j]). Substituting this into our x-y expression gives:
   = sigma(j, N, [(aj - bj) * (1 + sigma(i, N-1, [9 * 10^i]))])
   = sigma(j, N, [aj - bj]) + sigma(j, N, [(aj - bj) * sigma(i, N-1, [9 * 10^i])])

   For the second term, we can factor out the constant 9 out of the nested sigmas giving:
   9 * sigma(j, N, [(aj - bj) * sigma(i, N-1, 10^i)])
   This is obviously divisible by 9 so we look at the first term.

   We need sigma(j, N, [aj - bj]) to be divisible by 9 as well for z=x-y to be divisible by 9. But remember we defined the digits bj to be rearranged digits of aj? Therefore, the sum of aj is the same as the sum of bj and the sigma evaluates to 0.

   So z = 0 + 9 * (some big sigma evaluation)
   and we’re done! z is always divisible by 9 no matter what digits you pick in your original number. The Fido flash program then takes the digits you feed it, sums it, takes a mod 9, and spits out your answer!

   Think clearly.

3. Baron on October 9th, 2005 14:57

   So I was bored while sitting here waiting and smelling the turkey in the oven and came back to double-check last night’s math. Everything still seems in order, a non-math explaination that I made.

   “10^N can be rewritten as [1 + (N-1 number of 9’s)]” is not true. It should read “10^N can be rewritten as [1 + (N number of 9’s)]”. The math though is correct. In my example, 100 = 1 + 99 which is 10^2 = 1 + (2 9’s). And in case the next step where I put it into sigma notation isn’t clear, 1 + 99 = 1 + 9*10^1 + 9*10^0. Which is where the N-1 typo spawned from.

   I don’t know why I suddenly had this obsession. Someone please check my work so I can forget about this ;)

4. mhp on October 12th, 2005 11:12

   Well since Baron was the only one to attempt solving the puzzle.. I guess you are the only one that still reads my blog :) … I will post the solution.

   Now Baron, it must have been the case that the combination of a long-weekend and lots of food and drink made you ramble. The sigma method in comment #2 was an interesting way of expressing the solution. I think it overcomplicated your solution, but result is still correct up to the algorithm to determine the missing number.

   In short, the solution is show that the difference of the numbers you chose, and those numbers jumbled is a factor of nine (Baron, you did this). Then using the property that you correctly mentioned in Comment #1, Any multiple of 9 has its digits sum to a multiple of 9.

   Where your brain was working faster than your fingers was the line:
   The Fido flash program then takes the digits you feed it, sums it, takes a mod 9, and spits out your answer!

   If this were correct, then I take my result of 432, circle 2, sum 4 + 3 = 7. 7mod9 = 7 –> not 2.
   So you’ve got the pieces, just didn’t put them together correctly, therefore the correct algorithm is:

   9 - (sum remaining digits)mod 9 = circled digit

   Thanks for your efforts Baron. Enjoy impressing friends with your mind reading capabilities.
   I’ll post another one soon.

Leave a Reply