## Irrationality

I just started college classes this Thursday. Since I had already taken Calculus III in high school, I was allowed to skip ahead to real analysis. The first day’s assignment had some pretty interesting problems, so I thought I’d share them here.

Preliminaries

Rational numbers are numbers that can be represented as ratio of two integers. Numbers like 1/2, 3/4, 87, and -43/6 and so on. Irrational numbers, then, are numbers which cannot be represented as the ratio between two integers. For a long time it was thought that all things could be measured through rational numbers, and there was no such thing as irrational numbers. To the Pythagoreans, a cult led by the famous mathematician Pythagoras, this belief was sacred. It was so sacred, in fact, that it is rumored that when one of the Pythagoreans, Hippasus, proved that the length of the diagonal of unit square (or the $\sqrt{2}$) was irrational, they bound him up and threw him into the sea. I do not know what methord Hipassus used to prove this, or even whether or not this story is true, but I thought I’d start off by sharing one of my favorite ways I’ve seen this theorem proved.

Proof 1: The Square Root of 2 is irrational

First, assume that the square root of 2 really is rational. That is, it can be written as the ratio of two integers. Thus, we can write

Now comes the interesting part. Remember the fact that all numbers can be represented with a unique prime factorization. So let’s say you know the prime factorization of a, to figure out the prime factorization of $a^2$ you merely multiply all the exponents in a’s prime factorization by two. For example if $a = 2^3*5^2*7$ then $a^2 = 2^6*5^4*7^2$. But since you are multiplying all the exponents by two, they must all end up being even. The same thing goes for the factorization of $b^2$. That means the exponent of “2” in the prime factorization of $b^2$ must be even, but that means that the exponent of 2 in $2b^2$ must be odd. But that means that $2b^2$ can’t possibly be equal to $a^2$ since $a^2$’s factorization has only even exponents. This is a contradiction, and thus we can conclude that $\sqrt{2}$ is indeed irrational.

The great thing about this proof is that it easily extends to any value $\sqrt{n}$ where n  is not a perfect square. Because if n is not a perfect square, it must have an odd exponent in it’s prime factorization, which would mean that $nb^2$ must also have an odd exponent somewhere, which would mean it can’t possibly be equal to $a^2$ as it only has even exponents. Thus, this proof shows that any square root of a number which isn’t a perfect square will result in an in irrational number!

Problems

Now for the problems on my homework assignment. The two problems I want to address are

Prove that $\sqrt{2} + \sqrt{3}$ is irrational
Prove that $\sqrt{2} + \sqrt{3} + \sqrt{5}$ is irrational

If you’d like to, try to prove these on your own before moving on.

The first one is pretty easy if you consider one some pretty obvious facts. If the numbers x and y are rational, then

1. $x+y$ is rational
2. $x-y$ is rational
3. $xy$ is rational

Now, look back at statement 3 . If we let $y = x$ this statement says that if x is rational, then $x^2$ is rational. Which means that if $\sqrt{2} + \sqrt{3}$ is rational, then so is $\left(\sqrt{2} + \sqrt{3}\right)^2 = 5 + 2\sqrt{6}$. Now, statement 2  says that I can subtract two rationals and I’ll get a rational. Thus, if I can drop the five from $5 + 2\sqrt{6}$ and conclude that $2\sqrt{6}$ is rational. Using statement 3 again, we can see that multiplying by $\frac{1}{2}$ would allow us to conclude tthat \sqrt{6} is rational. This is false, as we proved before, and thus a contradiction, thus proving that $\sqrt{2} + \sqrt{3}$ is irrational.

The next one is a bit more tricky. If you just square it you get $10 + 2\left( \sqrt{6} + \sqrt{10} + \sqrt{15}\right)$. Even if you drop the 10 and the 2 there’s still three radicals left, and we’ve only proven that one radical on its own is irrational, so there’s no contradiction with stating that $\sqrt{6} + \sqrt{10} + \sqrt{15}$ is rational so far as we know. But let’s go ahead and drop the 10 and the 2 and conclude that $\sqrt{6} + \sqrt{10} + \sqrt{15}$ is rational, and square it again. This time you get

$31 + 2\left(\sqrt{60} + \sqrt{90} + \sqrt{150}\right)$

Still not much better it seems. Dropping the 31 and the factor of 2 still leaves us with three radicals. However factorizing these numbers reveals something special.

So, by assuming $\sqrt{2} + \sqrt{3} + \sqrt{5}$ was rational, we concluded $\sqrt{60} + \sqrt{90} + \sqrt{150}$ is rational. And that final line allows us to combine these conclusions and declare that is also rational, which is a contradiction as   is obviously not a perfect square.

For some more challenges, try proving the above these statements for general natural numbers a, b, and c. And you could also try proving the irrationality of sums of more than three radicals but I can say from experience that this won’t be as easy as either of these.

## Fun With Omegle

If you haven’t heard, Omegle is a text based chatting site that connects you with random people around the world. It’s basically like Chatroullete except without the penises.  The interesting thing about Omegle is that it’s an incredible simple set up. Now, I’m not very knowledgeable with HTML/AJAX/JavaScript/All that webby stuff, so take what I say with a grain of salt. But it Omegle basically has a bunch of different which follow the pattern “bajor.omegle.com/???”.

The possible values of “???” are
start
typing
send
disconnect
events

“start” gives you a six digit id composed of numbers, letters, sometimes underscores and then finds you a partner. An example of an id number is “4WWFZh”

“typing” is used to inform your partner you are typing. It’s sent automatically when you begin typing. This script takes your omegle id as input, with variable name id. The id is sent with the HTML GET method.

“send”
Sends a message. Takes the id and the message, with variable name msg, as input. Once again, uses GET

disconnect
Disconnects you. Takes the id as input. Uses GET.

“events” is a list of occurrences that happened since you last checked them. That is, it is cleared after you load it each time. The different possible events are “waiting”, “connected”, “gotMessage”, “strangerDisconnected”, “stoppedTyping”, “recaptchaRequired”, “recaptchaRejected”.  Takes id as input. GET.

Using all this information, it is very easy to create a program that interfaces with omegle. So I did. I chose to do it in python because of all the languages I program in, it has the easiest to use web library. Thus, I created this.

It’s a nice simple interface to omegle. You can use it to create any kind of omegle program you want. I thought of two things which I’ll post here. Note that to use them you must create a folder called OmeglePython and place “omegle.py” in it. Then create a new file “__init__.py”, which you can leave empty, in that same folder.

Anyways, first I created a program that connected unsuspecting omeglers to a chatbot. In this case, I connected them to Oliverbot. It’s actually not a very good chatbot, so I’m currently working on one for Cleverbot, which I find models human speech much better.

Secondly, I created a program for all you creepers out there. It creates to omegle clients to connect to two different people, and pass the messages received from each person along so it’s as though each person is talking to the other. That is, if A and B are actual people, and X and Y are the clients made by the program then messages go A-> X -> Y -> B and B -> Y -> X -> A.  You can see the messages as they’re being sent along. If you’re in the mood to troll, you can send a message yourself, impersonating either person. This can lead to rather humorous conversations if you’re lucky.

## The Monkey and The Coconut

I was reading through Martin Gardner’s Colossal Book of Mathematics recently, and thought I’d share an antriguing puzzle he gave and also, what I think to be an interesting way to solve it. The puzzle goes a little something like this

” Five men and a monkey were shipwrecked on a dessert island and they spent the first day gathering cooconuts for food, piled them all up together and then went to sleep for the night.

But during the night, one man wakes up while the others are sleeping. He becomes suspicious of his friends and fears that come morning he won’t get his proper share. So he sneaks off and divides the coconuts into 5 even groups, but finds one left over, so he gives that to the monkey. He takes one of the groups and hides it, puts all the rest of the coconuts back together and goes to sleep. A second man wakes up, also becomes suspicious, and repeats the same procedure, and also having a remainder of one coconut. This happens again with the third, fourth, and fifth men. The next morning they gather round to split the remaining cocounts into five groups, and once again they have a coconut left over, which they give to the monkey. How many coconuts did they start off with?”*

*Actually, Gardner’s version had the last division come out even. The above is the original version of the riddle.

Now, one can use this information to generate a system of equations. Let N be the total number of coconuts, and A, B, C, D, E represent how much each person took as the others slept and let F represent the number distributed to each person at the very end. Using the fact that each was a division of 5 with remainder 1, we can see that.

Using the above equations, one can obtain the following

$1024N = 15,625F + 11,529$

Which, is actually a very simple Diophantine equation with a well known method of solving which involves utilizing the Euclidean Algorithm

However, I noticed that for this particular problem a much simpler and far less computationally intensive approach exists. I thought to myself, what if I had written the number of coconuts in base 5, and performed all division and subtraction in base 5. So, what can you  get from this view point?

Well, firstly, since the first division by 5 leaves a remainder of 1,the number written in base 5 must end with a 1. Yes, that’s all well and good, but that’s not telling us a whole lot. The real advantage of writing in base 5 comes when you go to subtract the first set of numbers the first man hides. First, remember that he gave one coconut to the monkey, changing the last digit 1 into a 0. And then note that dividing by 5 in base 5 simply shifts the digits. Finally, since the second man also gets a remainder of one when trying to divide the coconuts, when one subtracts the number the first man took for himself from the number, the final digit must be 1. Putting all this together, one can determine the second base 5 digit of the solution.

Above is a visual representation of the subtraction. Dashes represent unknown digits involved in the computation. Now, I’m not saying the answer will be 5 digits long. It doesn’t really matter how many dashes you put as the reasoning will be the same. Anyways, what we’re really interested in is the “?”. Now,the question is simple, what can you take from 0 and get 1? Keep in mind that this subtraction is taking place in base 5. If you try 1 you’ll borrow 5 from the next highest digit and subtract to get 4.Similarly, if you try 2 you’ll get 3. Obviously, the only proper value of “?” is 4. Thus,the last two digits of the solution in base 5 are 41.

Now, take a step back and see what we have just concluded. What we have a assumed so far is that two men, one after the other, tried to divide the coconuts into groups of 5, but they each got a remainder of 1 before they took their share. Therefore, what we have just said is that for two men to go through this process and get a remainder of 1,the initial number of coconuts must end in 41 in base 5.

Now, let’s add the third guy in the mix. We know that he too received a remainder of 1. Note that this is the same as saying after the first guy took his share, the next two attempts to divide the coconuts also had a remainder of one. From our conclusion from before, this means that after the first guy takes his coconuts, the remaining number of coconuts must end in 41 base 5.  This information allows us to figure out the the third digit of the answer. Keep in mind that the original number of coconuts must also end in 41, and the the first man removed one coconut before taking his share.

So, what replaces the question mark? One might be tempted to answer “0”, but remember that one must be borrowed from 4 to perform the subtraction. Thus the right replacement for “?” is once again”4″.

By now you should see a pattern cropping up in the base 5 representation of the answer. After the last digit is 1, the following digits are 4 for each attempt to divide the coconut resulting in a remainder of 1. Since there were in total 6 attempts to divide the coconuts, we can conclude that the base 5 representation of the answer is 444441, which is 15,621 in base 10. And that’s that.

Posted in Uncategorized | 2 Comments

## A bit o’ Number Theory

I recently took a trip to Virginia to visit the university I shall be attending for accepted students day. It was everything I was expecting. A beautiful campus, cool teachers, fantastic opportunities, a wonderful library (they even had a library dedicated solely to science. 🙂 ), etc. Anyways, while I was visiting, I took walk down to the Math department. While their, I walked in on a group of students working on their math homework. They mentioned they were stuck on number 6. So, I decided to help them out.

The problem was to prove that the set $\{12a + 25b | a, b \in Z\}$ is equivalent to the set of integers. The way to show two sets A and B are equivalent is to show that A is a subset of B and B is a subset of A. That is, if an item is in set A then it is also in set B, and if it is in set B it is also in set A.

It’s obvious that for any integral a and b, 12a + 25b, is an integer. But now we have to show that we can write any integer in the form of 12a + 25b. This becomes pretty obvious when one notes that 12(-2) + 25(1) = 1, and thus 12(-2N) + 25(N) = (12(-2) + 25)N = N. And, thus, all integers can be represented in this way.

Anyone who likes to play study number theory would have instantly seen that proof. Why?  There is a well known theorem stating that given two integers, x and y, you can write their greatest common divisor as a sum, ax + by, where a and b are integers. A proof of this can be found on wikipedia. It might, however, be a fun exercise to try and prove it yourself.

If you manage to prove it yourself, another similar problem would be to try to find what numbers can be produced when a and b are restricted to being positive or 0. Take for instance 10 and 13. You obviously can’t make the number 12, and can make 26. But can you make 98? 112? 589?. Just something to think about.

## A Storm is brewing

Recently came across this video. I ❤ Tim Minchin.

## Some Fun Puzzles

Just a few really fun puzzles that I’ve come across at one point or another. I really like these ones in particular because they each require some clever thinking to solve effectively.

Puzzle 1: Checkerboard Dominoes

Imagine a checkerboard. It’s easy to see that if you are given 32 1×2 dominoes, you can cover the entire board. However, if I remove two corner pieces as shown, is it possible to cover the remaining board with 31 pieces?

Puzzle 2: Prisoners on Death Row

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can’t see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone’s head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either “black” or “white”. If what he says matches the color of the hat he’s wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy … this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What should they do to save the most lives?
After you have solved the above problem, generalize. There are N prisoners and K different colors of hats.
Puzzle 3: Guess the Number

Two friends are abducted by a gigantic, horned, fire-breathing, man-eating monster named Fred. Now, Fred doesn’t like to eat his victims without giving them a fear fight, so he decides to play a game. In his dungeon he has two rooms, one black and one white. Tomorrow, he will take his stamp maker, and place either a black stamp or a white stamp on each prisoner’s head. The prisoner cannot see the color of the stamp on his own head, but his friend’s. They will be asked to go from their cell into the rooms, one person in each. Now, if either enters the room with the same color as their stamp, they can both go free. But if they both enter the wrong rooms they die. The night before Fred gives them their stamps they are allowed to make a strategy. What strategy should they use to guarantee their life?

And once again, can you generalize to N rooms with N colors?

## Differential Equations

Introduction

Even though I’m only a senior in high school, I’m taking a course in differential equations. We came to the section where we learn to solve high order linear differential equations with constant coefficients. We went over the characteristic polynomial, and the case where it has a repeated root. We learned that if r is a repeated root then, $e^{rt}$ and $te^{rt}$ are both solutions to the differential equation. There was a proof of this using reduction of order. Our teacher also told us that if r is repeated more times, then we can keep multiplying our previous solutions by t for every time r was repeated. This, he said without proof. So, I decided to prove it myself.

Trial 1

So, let’s say you have a differential equation with constant coefficients, second order to make it easy, as shown below:
$y'' + ay' + by = 0$

This is completely general, as, if there was a coefficient in front of the $y''$ term, I could merely divide it out. I haven’t worked with differential operators very much, but I did notice that this could be written as the product of differential operators like this:
$\left(\frac{d}{dt} - c_1\right)\left(\frac{d}{dt} - c_2\right)y = 0$

because, if you multiply that out you get
$\left(\frac{d^2}{dt^2} - (c_1 + c_2)\frac{d}{dt} + c_1c_2\right) y = 0$

which obviously simplifies to the above equation of $-(c_1 + c_2) = a$ and $c_1c_2 = b$.

The advantage of putting it in this form, is that it’s obvious that the solutions to the resulting characteristic equation are $c_1$ and $c_2$. It’s also obvious that higher order equations can be made easily by multiplying by $\left(\frac{d}{dt} - c\right)$ where c will be another solution to the characteristic equation. It’s also worth noting that the order that they’re multiplied in doesn’t matter. You get the same thing.

Now, I considered what happened when $\left(\frac{d}{dt} - c\right)$ is applied to $t^ne^{ct}$. Doing this you get
$\left(\frac{d}{dt} -c\right) t^ne^{ct} = \left(nt^{n-1}e^{ct} + ct^ne^{ct} - ct^ne^{ct}\right) = nt^{n-1}e^{ct}$

Notice that this is very similar to what the normal differentiation operator does to polynomials. It’s exactly the same except that $t^n$ is replaced by $t^ne^{ct}$. Now, it’s obvious why $t^ne^{ct}$ are also solutions. If we take the nth derivative of $t^k$, we get 0 if n >= k. In the same way, if we take $\left(\frac{d}{dt} - c\right)^n t^ke^{ct}$, we get 0 if n>= k.

Generaliziminization
I was satisfied with this result at the time, and didn’t think to take this any further. But recently we started going over Euler Equations. That is,  differential equations of the form:
$x^2y'' + \alpha xy' + \beta y = 0$

Basic solutions are of the form $x^r$, and by substituting that for y you can find the characteristic polynomial and solve it like you would the differential equations with constant coefficients. Repeated roots are treated the same way, except you multiply by $\ln x$ instead.

This diff eq. can also be written as a product of differential operators, but this time of the form
$(x\frac{d}{dx} - c)$

What if one could derive that the natural log was the appropriate choice using  this fact? That is find a function $g(x)$ that causes the above differentiation operator to act on $g(x)^nx^c$ like the regular differentiation operator does on $t^n$. Actually, this is pretty easy to do. Merely solve the equation $(x\frac{d}{dx} - c)g(x)^nx^c = ng(x)^{n-1}x^c$ for $g(x)$.

$(x\frac{d}{dx} - c)g(x)^nx^c = ng(x)^{n-1}x^c$
$\left[x\left(ng(x)^{n-1}g'(x)x^c + cg(x)^nx^{c-1}\right) - cg(x)^nx^c\right] = ng(x)^{n-1}x^c$
$ng(x)^{n-1}g'(x)x^{c+1} = ng(x)^{n-1}x^c$
$g'(x) = 1/x$

Obviously $g(x) = \ln x$ is an appropriate function. To generalize even further if you have any differential equation that can be produced by products of

$(h(x)\frac{d}{dx} - c)$,

and the solutions are of the form $f(x,c)$, solutions to equations with repeated roots can be found by repeatedly multiplying the base solution, $f(x,c)$ by any $g(x)$ that satisfies:
$f(x,c) = e^{c\cdot g(x)}$

For example, with linear differential equations with constant coefficients $f(x,c) = e^{cx}$ and $g(x) = x$. In the case of Euler equations $f(x,c) = x^c$ and $g(x) = \ln x$.

Knowing this probably isn’t very useful but finding connections in mathematics is always interesting. I do wonder, though, if there is a name for this. But whether or not there is, I think this is a fun way to see things.