This week we had another 3 fascinating
topics brought up.

They are:

- Euclid’s proof of infinite primes

- The formulation of the quadratic formula

- The “Passengers on a Plane” Problem

What we can conclude from our journey into
these topics is that problems that are shocking, ie that are very non
intuitive, are actually quite simple with the proper point of view. Sometimes
when we are stumped, if something seems impossible to prove, a slight out of
the box thinking brings the problem to light, which turns into a light bulb
moment leaving us with that warm and fuzzy feeling. So, as I have discovered
for myself, if there ever is a time where something seems impossible, don’t be
afraid to do something random. Perhaps it can open the door to something that
no one has thought of before!

__Infinite Primes__

This proof, brought up by Euclid in 300BC,
is one of the most extraordinary examples of ingenuity. His proof that
there exist an infinite number of primes, he offered in his book
“Elements”. He did so by contradiction:

First we need to establish a fact: Any
integer can be broken down into a product of primes. As we have learned in
grade school a number tree not only looks cool, it provides us with apples and
those apples are the prime factors

With that in mind we can continue……….

Suppose there exist an infinite number of
primes and

*p*is the largest amongst them._{n}
Take the finite
list of prime numbers

*p*_{1},*p*_{2}, ...,*p*and let_{n}*P*be the product of all the prime numbers in the list:*P*=*p*_{1}*p*_{2}...*p*._{n}
Let

*Q*=*P*+ 1. Then,*Q*is either prime or not:
1
If Q is a prime, then Q would
be the largest prime and thus concludes the proof

2
If

*Q*is not prime then some prime factor F divides Q. And the proof is that this F cannot be in the list of primes that we’ve already established.
See the simplicity in this proof? Neat eh?

__Passengers on a Plane__
Question:
An airplane has 100
seats and is fully booked. Every passenger has an assigned seat. Passengers
board one by one. Unfortunately, passenger 1 loses his boarding pass and can't
remember his seat. So he picks a seat at random (among the unoccupied ones) and
sits on it. Other passengers come aboard and if their seat is taken, they
choose a vacant seat at random. What is the probability that the last passenger
ends up on his own seat?

Think about this question for a while before reading forward

You may think the answer involves a massive beast of a series and
you’re right! If you’ve tried to calculate this series……you are a hero. You
should have gotten ½, this is the correct answer, which does make some sense.
But here’s the funny thing: no matter how many people there are in this
question: 100 people or 1000 people or 10000000 people. The last person who
steps on the plane will be faced with two possibilities: either the last vacant
seat is his own seat, or the vacant seat belongs to the first person who
stepped on the plane. No other seat is a possibility.

My question is: does this make any intuitive sense? I will leave
that up to you to think about…….

Thus concludes another day in the Discovery CafĂ©. Some very
interesting things have appeared before our eyes. What I want to end with is
this conclusion: Once a problem is solved, the problem becomes simple. But
before we can see the path to the solution, even easy problem seems rather hard. This mirrors life. Things only become “easy” when we know the
solution, but this rarely happens. My advice is to change your point of view,
change your attitude and perhaps you will come up with something ingenious. And
when you do share it with the rest of the world, it will make life “easier”

Great post! I especially liked the Airplane question!

ReplyDeleteVery interesting and it kept me captivated! Keep up the good work Hanbo!

ReplyDelete