Friday puzzle -- pick the largest number

Re: Friday puzzle -- pick the largest number

Lee Schierer McKean, PA

Distract his opponent with food and cheat.

First thought involves 2 piles

Steven Antonucci

haven't been able to figure out if it was statistically relevant, but I'm thinking something like this:

make two equal piles. Pick from pile A. Next, select from pile B until you get a bigger number. Then switch to selecting from Pile A until you get a bigger number. Do this until half of the papers are gone.

I think this gives you about a coin flip since you wil have used half of the papers, and have the biggest number in that half...

steve

Clarification

Alex Y

Steve, turning over 1/2 of the sheets will give you a 50% chance of having turned over the largest. But I may not have been clear on this. You have to stop when you turn over the largest card. You can't go back to a card you turned over earlier. You must claim that the last card you have turned over is the largest .

That'll work ;-)

Alex Y

But there is a strategy that does not include cheating!

Re: Friday puzzle -- pick the largest number

Dan Donaldson

Is the three paper solution related to the Monty Hall puzzle?

"Deal or no deal" logic too?

steve antonucci

It's kind of what I was suggesting (I think), but I can't see it all of the way through...

In "deal or no deal", the first selection has a 1/N % chance of being the biggest prize. As the cases are eliminated, the odds for that selection do not move up or down. The prize may be adjusted to a lower amount, but the odds that the case selected are always 1:N.

At some point, the host offers to switch cases. If there are now only 2 cases, the odds of the other case are 1:2. The original case is still 1:N. I think this problem is somehow a permutation of that logic, with the goal to get down to a coin flip between the one you have and the one left...

Still, I couldn't see how to factor in that you don't know the boundaries.

S

Re: "Deal or no deal" logic too?

Dan Donaldson

Yeah, not quite sure where to go from here.

No connection to Monte Hall

Alex Y

At least that I see.

Re: No connection to Monte Hall

Dan Donaldson

This one has me beat. I can't get anything to come to mind as an approach to solving it ;(

Hint (for Part I)

Alex Y

If you choose the first one turned over, you have a 1/3 chance of picking the highest. So you probably do NOT want to pick that one as a strategy to get a 50% chance. ;-)

OK, a guess.

Dan Donaldson

Turn over the first one. Then turn over the second. If the second one is higher, take it, if not choose the third one.

Correct (Part I)

Alex Y

There are six distinct, equally likely, orders in which you could pick up the three cards:

LMH

LHM

MLH

MHL

HLM

HML

Using your method, you will pick the high card in the second, third, and fourth case, a 50% success rate.

This is a special case of the general solution, which involves letting a certain number be turned over, then picking the first one that exceeds the highest in that first batch.

I'll leave Part II open in case anyone wants to take a stab at guessing the odds of success for a larger set of cards, such as 10, 100, or 1,000.

Part II answer

Alex Y

First for ten cards: Look at the first three, then pick the first one after those three that exceeds the greatest of those three. Probability of success ~40%.

This one will yield to analysis similar to the proof of Dan's answer for three cards, although a computer will help, since there are ~3.6 million possibilities, of which you will pick the highest number in a little over 1.45 million cases.

The really surprising result is that while the probability of success declines with the number of slips of paper, it approaches a lower limit that is not much worse than the case with ten slips of paper. For 1,000, observe the highest number among the first 368 slips of paper, then pick the first one you see higher than that. You will be expected to win 36.8% of the time.

In general, for n slips of paper, observe the highest number that shows up in the first n/e slips, then pick the first one higher than that. You will be expected to win about 1/e times.

Source: Martin Gardner; My Best Mathematical and Logic Puzzles

His answer includes the mathematics of the solution, which involves a little probability and limits of series. PM me if you want me to email it to you.

Re: Part II answer

Dan Donaldson

Statistics is definitely not my strong (or any other;)) suit. I am probably just missing something, but in part of the explanation you used "1/e", but I could not see what "e" was.

Re: Part II answer

Alex Y

e = 2.71828182846...

The base of "natural logarithms".

e = lim as n -> inf of (1+1/n)^n

DOH!

Dan Donaldson

That "e" I know, but for some reason did not connect it with this post. I am really sharp today. (of course if I comb my hair correctly, no one will notice, at least it would work if I had any hair ...... ) ;-)

Alex Y

I was pretty sure you knew what e was, but thought I would spell it out just in case.

BTDT ;-)