Discovery Cafe Day 2. Guest Post by Hanbo Xiao

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_n is the largest amongst them.

Take the finite list of prime numbers p₁, p₂, ..., p_n and let P be the product of all the prime numbers in the list: P = p₁p₂...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” 

Until next time………………