memory and answers

Visualisation of the (countable) field of alge...

Image via Wikipedia

I attended a public lecture yesterday by Professor E.Victor Flynn on some fields within Algebraic Geometry…It was incredibly fascinating. Although maybe 20% of it went over my head, it did feel like i’d simply have to jump up to be able to reach it. So when I got home, I decided to google some of the ideas that had been expressed.

I always knew number theory was a diverse field, but I never realised HOW diverse it was. At one point, I had 6 or 7 tabs open, with each one linking to one of the others, sharing ideas and definitions – you could not read any one page completely without knowing content from the others. Most of the time, it was simply a case of definitions – when talking about an algebraic number field, you need to know about field extensions, fields and Rational numbers, and knowing the definitions of these terms allows you to understand the definition of an algebraic number field – and so this bought up some interesting questions for me.

Before I’d started looking into these ideas, I’d done my normal routine of checking 20 or so math based blogs for new content. one blog –  “Godel’s lost letter and P=NP” – spoke about the importance of memorisation. Now, if you’ve read my previous blogs, you may notice that I find memorisation of theorems and definitions to be a complete waste of time.

I think now I am beginning to see the error of my ways…

without knowing definitions, we cannot hope to know other definitions that depend on the earlier ones. If an algorithm F works because algorithm G works, we need to know how G works to show F works.

On analysing these thoughts (and ideas expressed by others), I re-evaluated what I thought and why. I think one of the comments on the other blog found the real issue – ‘rote’ memorisation.

however, my thoughts are still developing on this front, and maybe at another point I shall come back to the idea. I agree – and think I have thought this way for some time, but failed to notice it –   that knowing definitions and theorems etc are incredibly important. I think what I have issue with is how we learn them, and how we learn to apply them.

now, moving on to the questions from the last post:

I still don’t have much of an idea for the second question – in truth I’m a  bit bored of it, so I’m just going to leave it.

but as for the first, this one appeals to me!

so: what do we know?
the number plate is only 4 digits long and contains 2 unique digits, so it’s of the form aabb or abba or abab. As the eldest child is 9 years old, it must be divisible by 9, so

9|(2a+2b)

⇒ 9|(a+b) with  0 ≤ a,b ≤ 9

⇒a+b=9

now, what else do we know? 8 children, each with a different age. the eldest is 9, which means that the other 7 children are either 1,2,3,4,5,6,7 or 8. therefore, there is either a child of 4, or a child of 8, which means the number is divisible by 4.

this tells us the number plate was one of:

9900, 1188,7272,2772, 3636,6336 or 5544.

this gives my smith an age of 00, 88, 72, 36 or 44. logic would dictate that 00 is impossible, 88 and 72 highly improbable. we shall include them for now, but we won’t include 00.

now notice that none of these possible numbers are divisible by 5, which means the children’s ages are 1,2,3,4,6,7,8 and 9. so the number must be divisible by 504=(9*8*7).

simple calculation gives:

1188 mod 504=180

7272 mod 504=216

2772 mod 504=252

3636 mod 504=108

6336 mod 504=288

5544 mod 504=0 (504*11=5544)

so the number plate was 5544, the children’s ages were 1,2,3,4,6,7,8,9 and Mr Smith is a (presumably) very tired 44-year-old.

Advertisements

1089 (, 495 and 6174) and all that

Take any 3 digit number where the first and last digit areat least 2 apart. (1st number)
Reverse it. (2nd number)
Minus the smaller number from the larger one. (3rdnumber)
Reverse it (4th number)
Add the 3rd and 4th number together.
Your result is 1089.
 This problem i first discovered in the book “1089 and all that”…an awesome little book!
Now, take any 3 digit number, with the only requirementbeing that all 3 numbers are not equal (so the number 001 is allowed)
Now, using these three digits, rearrange the numbers to makethe smallest and biggest possible numbers.
Now subtract the smaller number from the larger one.
Repeat this process. After a few steps you will reach 495.
Now do the same process for 4 digit numbers….you get 6174.
The great thing about these processes is they seem magicalto someone who has never heard of it before. Try the 1089 trick on a 10 yearold, you’ll convince them you’re magical!
These ‘tricks’ are – to me – some of the most interesting ‘tricks’around – well, when it comes to mathematics at least.  So what I thought I’d do in this post isexplore these numbers and why these methods work, and then see what othernumbers we can find etc.
So starting off with 1089:
Lets say your three numbers are x,y,z in that order. Lets alsosay that x is greater than z. so our two numbers are xyz and zyx. Subtracting thesegives:
(x-z) (y-y) (z-x)
Now, as z is less than x, we need to ‘borrow’ a 1 from they, so we actually have
(x-z)(y-1-y)(10+z-x)
But we also need to ‘borrow’ a 1 from the x
(x-1-z)(10+y-1-y)(10+z-x)
As we’re working mod 10, and if we let x-z =c, then we have
( c-1 ) (9) (10-(x-z))
Which is
( c -1) (9) (10-c)
Now we reverse this number
(10-c) (9) ( c-1)
+             ( c-1 )(9) (10-c)
=             ( 9)   (18) (9)
=             (9+1) (8) (9)
=             1089
This is always true.
What about 495?
Lets take the number x,y,z where x>y>z
Then we have
x    y      z
         z     y      x
= (x-z)(y-y)(z-x)
Again, z<x so need to ‘borrow’ a 1 from the y, whichmeans we’ll need to borrow a 1 from the x. again, let x-z=c
(c-1)(9)(10-c)
If c were 1, we would have the number 990 and 099 for thenext round. If c were 0, it would mean that x=z and as x<y1
If c >5, then 10-c<c-1, so we will first look at when1<c<6
the biggest number will be
(9) (10-c)  (c-1)
And the smallest
(c-1) (10-c) (9)
Now, subtracting them gives
(9-c+1) (10-c-10+c) (c-1-9)
Again, we have to ‘borrow’ so
(9-c) (9) ( c )
With c being 2,3,4 or 5
If we did the same thing when c>5 , we would end up with( c ) , (9 ) , (11-c)
 With c being, 6,7,8or 9.
If c is 2
We have 792, so
972-279=693, which is what we get if c is 3.
693 gives us
963-369=594, which is what get if c is 4…and  if c is 5, we get the number 495, which isthe magic number!
To confirm, 594 is 954-459=495.
If c is 6
We have 695 which is
965-569
396 which is the same as 693
If c is 7
We have 794 which is
974-479=495, which is the magic number
If c is 8
We have 893 which is
983-389=594 the magic number almost
If c is 9
We have 992 which is
992-299=693 which we’ve already done.
Quickly looking at c=1
990-099=891 which is
981-189=792 which we’ve already done.
This shows that it works for all numbers, unless all 3digits are the same.
A similar method can be used to show that for four digits,you get the number 6174, and this number is called the Kaprekar number.
What interests me is: what happens if you have n digits? Whathappens if you use repeated different operations (so using addition andsubtraction, but in different orders…maybe you subtract, subtract, add,subtract, subtract, add…)?
You could classify a sequence of operations as a binary operation.You could do operations on reversed numbers, or operations on biggest numberthat can be made from those digits and the smallest.
Any of these methods could yield some interesting observationsin number theory. Applications of these observations could be used in chaostheory or cryptography….but the point of doing number theory is that there areseldom applications!
In a way, these tricks remind me of collatz conjecture. EvenWikipedia thinks so, as the wiki page on 495 and 6174 both link through tocollatz. Interesting correlations.
I’ll end this post by looking at the Kaprekar routine fornumbers with 2 digits.
xy, with x>y
we have xy-yx=(x-y-1) (10-(x-y))
let x-y=c
we have (c-1) (c)
so we have (c) (c-1)-(c-1)(c)=(c-c+1-1)(c-1-c+10)=9
repeatedly subtracting the smallest possible number from thebiggest possible number from a set of digits for n digits:
digits     result
2              9
3              495
4              6174
5              ?

Do you want a mathematician or a computer?

Recently I have been applying to a couple of jobs for next year, and have beenquite fascinated by the anxiety other people express over the whole applicationprocess. It seems everyone is so intent on being perfect for the job they’reapplying for, that they don’t seem to notice that if they have to ‘change’ whothey are to get the job, the job probably won’t suit them. So they doctor uptheir C.V’s and buy different clothes and attend the interviews readyingthemselves to answer in such a way that their weaknesses become strengths….

The best one I’ve heard from this is: “what is your biggest weakness?”
“I’m dedicated to my work, so I often work straight through a lunch break”.

Yeah right.
Anyways, a Game theorist wrote a lot more on this here : http://mindyourdecisions.com/blog/2008/08/28/job-interviews-you-don%E2%80%99t-have-to-be-perfect/?dhiti=1

an awesome blog to read, and the articles make you think.

My favourite part of interviews are the questions that makeyou think. Asking what I would do in a given situation is boring, but asking mehow to solve an abstract idea – that’s fun.
My girlfriend had an interview a few months ago, and one ofthe questions was:

using square tiles that have an area of 1 unit squared, how can you lay thetiles such that the number of tiles used is twice the number of tiles in theperimeter?

the way people approach this is fascinating. Most of us will start writing outequations, so perimeter of a rectangle is 2 x (width+length) and the area iswidth x length, so, using w,l to denote width, length respectively,

4(w+l)=wl
4+4l/w=l
which isn’t easily solved. It would probably be best to start throwing integersinto the equation, and see what comes out.
So if we define w as 8, we get 4+l/2=l4=l/2 8=l so a square of 8 by 8 works! Right?
Wrong.
We forgot to notice that thecorner tiles are counted twice. The perimeter calculation should actually be2*(w+l-1) (but the area still stays the same).
so
4(w+l-1)=wl
4+4(l-1)/w =l

again, try values of w

W=8
4+(l-1)/2=l
8+l-1=2l
7=l
Which gives a perimeter of 28tiles and an area of 56, which works.
But to do this in an interviewwhere people are stressed out….that’s a bit more tricky. You’ll forget todouble the perimeter. You’ll forget the repeated tiles. And you won’t noticethat if you tile around the equator, you simply need to place 4 rows of tiles,one above the other, to satisfy the requirements…
There are quite a few questionslike this.  
Here’s another one from the blog Ilisted before:

http://mindyourdecisions.com/blog/2011/09/05/monday-puzzle-paying-an-employee-in-gold/

the solution is awesome.

An alternative solution is tocreate a gold cutting device that has 6 knives. Then you just need one cut.
Now, from my limited experience ofinterviews and applications, it seems that most companies claiming to belooking for mathematicians are actually looking for a computer or a softwaredeveloper (which is good news to software developers!). Almost all graduatejobs base part of the application on marks attained at university.  Interestingly, those marks are made up ofexams, tests and assignments. Assignments seldom give more than 20%  towards the final mark. Roughly 40% of theassignments are based on an ability to think like a mathematician.  The rest is rote learning/memorisation or useof a method.  Unfortunately, the examsand tests are also based on this.  This meansthat most courses have at most 10% of the course based on the ability to think,and 90% on being able to memorise proofs and theorems and methods. 
This is all well and good…except for a little thing called the internet. Throughthe use of google, wolframalpha and Wikipedia, that 90% of the course can bedone by someone with no previous knowledge of the course.  I would also guess that they can do it moreaccurately, and faster.
So to base your applicants ontheir university scores seems to me to be a waste of time. If that is all youwanted, you’d be better off getting a software developer or simply using thosethree sites – this way will be much cheaper! If you ever come across a problemyou can’t solve using those sites…well, then there isn’t a high chance yourgraduate with straight A’s could have solved it either…

But enough of that. It’s fairly obvious I have crap marks and think I’m abetter mathematician than those marks show, but that’s my opinion. I likesolving problems, and this is a taster of the next post:

what do the numbers 1089 and 495 have in common?

prime-ative codes, cryptic quantums.






It’s come up a couple of times in conversations and my thoughts over the last few days, so I’ve decided to scrape together my memory and use some induction and try to explain to you how maths ensures your credit card numbers aren’t stolen when you buy things online…

To begin, it will probably be easiest to use an example given by Ian Stewart in one of his books. Imagine you’re standing at a rather quiet party, and there’s someone on the other side of the room that you’re trying to share confidential information with. For reasons of illustration you’re unable to cross the room – all the information you share has to be public.

So how do you do it?

Obviously a code is the best way, so if you were able to meet up before the party and devise a code so you could say anything without anyone knowing what you were on about.

Let’s make it more difficult, and say you weren’t able to meet up – in fact, you’ve never met the person before, you just know they’ll be wearing a bright purple jacket. We’ll call them M for fun.

That is a rather hard task, so we’ll make it a little easier by stating that the information you’re trying to convey is merely a number. and now suddenly your life is easy….given that M knows you’re trying to convey a number, and that M has ‘their’ hands on a couple of helpful algorithms.

Now, the branch of maths that deal with these type of algorithms is under number theory, and (in this example) falls mostly under cryptography.

I’m not going to say too much more about these branches of maths. Whilst I am happy to say I like number theory a lot, I have not yet been exposed to enough of it to give you a decent definition of what it entails.
Now, back to the party.

M shouts across the room “take your secret number and multiply it by 3”
“square your new number”
“add 25 to it”
“tell me your answer”
and you shout back “1321”.
M smiles and walks off, knowing the secret number is 12.
how?
by solving a simple equation:
9x^2+25=1321.
This is a very simplistic form of coding, and anyone in the room who is listening in and can do a bit of algebra can solve this problem. What is needed then is a very complex set of instructions that are very difficult to reverse, and an easy set of instructions that undoes the complex ones. That’s kind of wordy. Perhaps another example is worthwhile at this point:

Back to the party, except now the number you’re trying to convey is 6 digits long. Before we go any further, I need to introduce a deceptively simple function called the modulus, or mod. The mod function takes a number, divides it by another and gives you the remainder. Thus 15 mod 2 is 1, 12 mod 7 is 5, 16 mod 8 is 0. The reason it’s deceptively simple is that there are some cool theorems associated with the mod function, none of which I can currently remember! However, these theorems are what we could use to convey out message.

Lets also state that only you and M know your number is 6 digits long, and lets assume that M is the only one who knows the algorithm to reduce your eventual output back to the original input. Also, lets say that our number has the property that the sum of the 1st, 3rd, and 5th digits minus the sum of the rest has to equal 0, mod 11 (this is often used in bar-coding actually, so that the computer can work out if the barcode is correct, and so we can find the correct digit if one is missing), and that only M knows this property.

This is actually very easy to convey in secret if all these conditions are met. Before the party, M knows that your number is of the form abcdef, where (a+c+e-b-d-f) mod 11 = 0, whereas a counter ‘spy’ only knows you have a number that needs transmitting.
If M asks you too many questions, the spy can work out your code. M therefore needs to ask just enough questions such that the spy gets no information, but M gets all of it. Lets say M asks the following questions:

1)   What is the sum of all the odd digits?
2)   Minus the second number from the second to last number.
3)   What is the sum of digits 2 and 4?
4)   What is the sum of the first and last number?
5)   What is the sum of the last 2 digits?

Question 1 tells M a+c+e
Question 2 tells M e-b
Question 3 tells M b+d
Question 4 tells M a+f
Question 5 tells M e+f

Now, if we take ans 1 ,a+c+e, which is the first half of the mod 11 requirement above. Ans 3 tells us what b+d is. If we minus this from what we’ve just done, we get a+c+e-b-d, which is the majority of the mod requirement. We can use this to find f. We use this along with ans 4 to find a, and ans 5 to find e. These 2 ans with ans 1 tell us c, and e with ans 2 tells us b which with 3 tells us d.  

That can be quite difficult to follow, so we’ll use an example. Say our number is 763290.
Ans 1 will be 7+3+9=19
Ans 2 will be 9-6=3
Ans 3 will be 6+2=8
Ans 4 will be 7+0=7
Ans 5 will be 9+0=9

Ans 1=Ans 3 =11, which (as we’re working with mod here) is the same as 0, hence the last digit is 0. This means that a is 7, e is 9, c is 3, b is 6 and d is 2, which gives the answer 763290, which is correct!


Now this is just one type of coding, and, as I’m sure you can see, it is only as safe as the knowledge is. The more people who know about the algorithm and/or conditions, the easier it is to break the code. Even complex equations can be broken, and with today’s computers it is relatively easy to perform difficult calculations. A different type of coding is described here, but it is likely you will have needed to have studied second year maths to understand it.

A crucial part to coding is prime numbers, as prime numbers are the factors that are used to confuse the e output from hackers – for example, what are the factors of 30? 210? 9 699 690? don’t know? 30 >2,3,5 210>2,3,5,7 9 699 690 > 2*3*5*7*11*13*17*19. now, algorithms can be designed to chug through the different primes and see which ones factor your number, but we’re not talking 6 or 7 digit numbers. we’re talking numbers with anything up to a thousand digits (and we can go bigger, the biggest know prime is 12,978,189 digits long…ok, i feel like getting distracted. average book, about 600 words a page, each word average four letters – make it 5 for the spaces. 3000 letters per page. divide 12 978 189 by that….4 326 pages. the bible is 1200 pages roughly. so the biggest prime in the world, if written down, would take up as many books as 3 and 3/4 bibles. that’s kinda big!)

The bigger you go, the more tricks needed to cut down on the leg work done by the algorithm. It needs shortcuts, otherwise the system will take forever to try and solve the prime factors.

There are quite a few other techniques out there to use on encryption, techniques that, when piled on top of each other, can make it seem almost impossible to crack. Sadly though, they’re not impossible.

But it’s not all bad news!!!!

The encryption processes we use now are far from secure. Hopefully with the current development of incredible computers around the corner, new branches of mathematics will begin to open up, allowing cryptography further chances to strengthen itself, no longer using exhaustion to defeat it’s foes, but perhaps something slightly more intelligent and beautiful.