I will be on instragram:

We, Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram

-------------------------------------

This is the answer to the problem posted in the last post which was a guest post by David Marcus. This post is also a guest post by him.

We restate the problem:

-------------------------------------------------

PICK THE LARGEST NUMBER:

There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number.

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want.

Is there a strategy that will win with probability > 1/2.

CLARIFICATIONS:

1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

-------------------------------------------------

There is a strategy. In fact, we give two.

STRATEGY ONE

Before looking at any number, pick a number x on your own from the reals according to a distribution with full support (every open interval has prob greater than 0). Then pick a number from the box (prob 1/2-1/2), which we call y. If x<y then keep y. If y\le x then take the other number.

If x is between the two numbers, then the strategy works. If not then the strategy does not hurt, so the prob in that case is 1/2. Hence you do better than 1/2.

STRATEGY TWO

Let f: R--> (0,1) be strictly increasing. Pick a number from the box, call it y. Keep it with prob f(y).