February 20, 2010
Magician Trick or 1089 the Famous Number
Hi,
When I used to be a ‘magician’, there was a trick I loved particularly : ask a women her ring, put it on a combination padlock and pretend I lost the combination ; when her face eventually turned worried I offered her the possibility to find the combination again together, provided she could perform two little mathematical operations (namely substraction and addition). All she had to do was give me a 3-digit number (for instance 723), ‘mirror’ it, i.e. create the 3-digit number which is composed of the same digits but the first one in third position and the third one in first position (here 723 becomes 327), and perform the substraction between these two numbers (here 723 – 327 is 396). Once again, she had to ‘mirror’ the number she obtained (here 396 turns into 693) and performed an addition this time (here 396 + 693) to get the combination of the padlock, 1089 and get her ring back.
What a luck that I had previously set the combination to be precisely 1089 ? Not really, it’s of course mathematically related, and here is one proof I produced (I’m definitely sure there is a better proof somewhere on the web, but this one is mine, and I remind readers that this blog doesn’t intend to be a reference or something, it’s just stuff I like and find interesting, but if you have comments to do, advice to give me, resources to make me read, … please do tell, I’ll be happy to read them !).
Maths Time
Some Conventions
First of all, let me define a term I’ll use throughout this post -and which will help me be clearer when dealing with numbers : given a 3-digit number, I’ll call ‘mirrored number’ the 3-digit number wihch is composed of the same three digits, but the first in the third position, and the third in the first position, the second doesn’t move, one can see it as a kind of ‘symmetry’. For instance, if our number is 834, then the mirrored number is 438.
Second, as a remainder -because it’s a mathematical convention- I’ll write absolute values with bars ( “|” and “|”), and not “abs()” as it’s sometimes used on other blogs, my opinion is “abs()” notation is for programming languages, and bars notation is for Maths.
The proof itself
Let A = a2.102 + a1.101 + a0.100 be any 3-digit number such that a2 is different from a0
Let A’ be A mirrored : A’ = a0.102 + a1.101 + a2.100
Let B = A – A’ :
a2.102 + a1.101 + a0.100
– a0.102 + a1.101 + a2.100
_____________________________
B = (a2 – (a0 + 1)).102 + (10 + a1 – (a1 + 1)).101 + (10 + a0 – a2).100
B = (a2 – a0 – 1).102 + 9.101 + (10 + a0 – a2).100
Note that if it happens that we have something like 367 – 763 to perform, we’ll actually perform – (763 – 367). It is an important point for our proof, because that implies that a0 is lesser than a2, thus we need to add 10 to a0 (and of course 1 to a1 [from A’]).
Second thing, as we’re working with 3-digit numbers, the second digit of a number and his mirrored is the same, but as we added 1 to a1 [from A’], we have to add 10 to a1 [ from A] (and of course 1to a0 [from A’]).
Let B’ be B mirrored : B’ = (10 + a0 – a2).102 + 9.101 + (a2 – a0 – 1).100 .
Let’s perform B + B’ :
(a2 – a0 – 1).102 + 9.101 + (10 + a0 – a2).100
+ (10 + a0 – a2).102 + 9.101 + (a2 – a0 – 1).100
___________________________________________
= 9.102 + 18.101 + 9.100
= 9.102 + (10 + 8).101+ 9.100
= 10.102 + 8.101 + 9.100
= 1000 + 80 + 9
= 1089
Here’s the result : 1089, always, amazing isn’t it ? Provided that the first and third digit of a 3-digit number are different, by performing these two simple operations, you get 1089 ; so as always, the magician I used to be was cheating ^^
Haskell Time
purify :: (Integral a) => [a] -> [a]
purify nbs = filter isSuitable nbs
where isSuitable n = let firstDigit = n `div` 100
thirdDigit = n `mod` 10
in firstDigit /= thirdDigitcompute1089 :: (Integral a) => a -> a
compute1089 n = let b = abs (n – (mirrored n))
in b + (mirrored b)mirrored :: (Integral a) => a -> a
mirrored n = let firstDigit = n `div` 100
rest = n `mod` 100
first’ = rest `div` 10
second’ = rest `mod` 10
rest’ = second’ * 10 + first’
in rest’ * 10 + firstDigitmain = do
let nbrs = purify (filter (`notElem` [111,222,333,444,555,666,777,888]) [1..998])
let computed = map compute1089 nbrs
let isProoved = not (any ( (/=) 1089) computed)
return isProoved
Well, simple code. I agree with that fact that the proof isn’t proper, but it’s valid : one way of prooving that a predicate works is to test all numbers whose predicate is applied to. Here there are 990 numbers, which is perfectly doable for a computer.
Some quick explanations of this code.
The ‘purify’ function eliminates the numbers whose first and third (last) digits are the same. The first digit is got by doing the euclidean division of our number and 100 while the last one is obtained by performing modulo 10.
The ‘compute1089’ just applies the algorithm to any 3-digit number you pass as a parameter.
The ‘mirrored’ function is the most interesting one I think : it applies the same algorithm we’ve just applied to get the first and third digit of a number, it’s advised to take the example step by step with a number on a sheet of paper.
The main function isn’t that much interesting in itself as it only applies our functions and returns True, to tell us that we prooved the predicate ^^
I hope I was clear enough, it’s not that easy to explain, because of the ax digits, and the definitions of A and A’ . If there is any question, or spot you want me to clarify, please ask !
January 14, 2010
The Towers of Hanoi – Haskell recursivity
Hi all !
This is my very first post, so let me introduce myself very briefly : I’m nearly 19, I study Maths and Physics (for the main part) in a “classe prepa” (= a school that will hopefully lead me to an engineering school in two or three years). I’m French (yeah nobody’s perfect; don’t worry it won’t last any longer ^^), so I apologize for my bad English, please don’t hesitate to correct my mistakes. A very good friend of mine (Alp : http://alpmestan.wordpress.com/ ) introduced me to Haskell, and I fell in love. Really, I love this language so much, well I’m a very beginner, so purists may say I think I love the language without actually knowing him, but well, I’m rather confident.
But enough of me, let’s write my first article (once again : I’m beginning, so every advice is welcome ^^).
__________________
On one evening I came to think of the Towers of Hanoi, a well-known game whose purpose is simple : you have three rods, let’s say A, B and C (from left to right), on the rods A are n disks arranged in ascending order of size; the goal is simple : you have to move the n disks from the left “tower” to the right one, two rules for doing this : you can move only one disk at a time, and a disk of a given size can lay only on a larger disk.
Of course, you will find well documented scripts in any language to solve the problem, but that evening I decided to solve it on my own, here’s what I thought.
I’m able to solve it with two disks easily : moving the two disks from A to C is not hard at all. So let’s say I have three disks now. The key is coming back to a 2-disk problem, indeed : if I’m able to isolate the third disks i.e. the largest one, I can move it to the column C, then, I just have the two other disks to move to C, which I can do it easily. So the solution with three disks is to move the first two from A to B, then move the largest disk from A to C, and at last move the two disks form B to C.
From here on, we can see that the problem is recursive : if we can solve the problem with n disks, then we can solve it with n+1 disks : to move 4 disks from A to C, let’s first move the three first to B, and to achieve this, let’s move the first two to C etc.
Finally here’s my Haskell implementation, it’s very simple : it only displays the steps, without storing them in a list or something, as others did on their own Haskell implementation.
— Let’s handle the case where the user would enter only one disk
hanoi 1 a b c = do
print (“Move from ” ++ a ++ ” to ” ++ c)
— The “base” case : 2 disks
hanoi 2 a b c = do
print (“Move from ” ++ a ++ ” to ” ++ b)
print (“Move from ” ++ a ++ ” to ” ++ c)
print (“Move from ” ++ b ++ ” to ” ++ c)
hanoi n a b c | n <= 0 = error “Negative number of disc !”
| otherwise = do
hanoi (n-1) a c b
hanoi 1 a b c
hanoi (n-1) b a c
The script is rather easy, the order of the columns is that : “hanoi n a b c” means “move the n disks from column a to column c, b being the other column”.
A bit of Maths
Here we’ll talk a little about the number of steps to move the n disks from A to C. Again, same kind of reasonning : let x be the number of steps needed to move n disks from A to C, according to the algorithm, in order to move n+1 disks from A to C, we must move n disks from A to B (which requires x steps), then move the (n+1)th disk from A to C (which consumes one more step) and finally move the n disks from B to C (which requires x another steps). Finally we have x + 1 + x steps, so 2x + 1 steps.
We have a sequence defined like this :
- U0 = 0 (0 disks need … 0 steps ^^)
- For any n in N, Un+1 = 2.Un + 1
Later I’ll publish (if I find the time) an other article to proove that we can compute directly the number of steps needed for n disks, which is 2^n – 1, but I don’t have time this evening to produce a rigorous proof.
Thank you for reading, thank you in advance for commenting, and if you have any advice for me … please give ^^
Schum's Blog 