Comparing numbers

[bonanova]

With a tip of the hat to Gavinksong's that was written by an author that he references, I give one that is of the same type, but simpler. It was included in one of Peter Winkler's books, and it is attributed to Tom Cover in a 1986 publication on open problems in communication and computation. It asks something very similar to choosing apples behind doors, and it may even have inspired that puzzle. Because I have read the solution, I won't contribute anything further in the apples thread.

 

Paula takes two slips of paper and writes an integer on each. There are no restrictions on the two numbers except that they must be different. She then conceals one slip in each hand. Victor chooses one of Paula's hands, which Paula then opens, allowing Victor to see the number on that slip. Victor must now guess whether that number is the larger or the smaller of Paula's two numbers; if he guesses right, he wins $1, otherwise he loses $1.

 

Clearly, Victor can achieve equity in this game, for example, by flipping a coin to decide whether to guess "larger" or "smaller." The question is: Not knowing anything about Paula's psychology, is there any way he can do better than break even?

 

[bonanova]

Before playing, Victor selects a probability distribution on the integers that assigns a positive probability to each integer. One way is to flip a coin until H appears. If he first sees an even number 2k (including 0) of T, he will select the integer k. If he first sees an odd number 2k-1 of T he will select the integer -k. After Paula picks her numbers, Victor selects an integer as just described and adds 1/2 to it. That becomes his threshold t. For example if Victor flips 5 T before his first H, his random integer is -3 and his threshold will be -2 1/2.

When Paula offers her two hands, Victor flips a fair coin to decide which hand to choose, then looks at the number in that hand. If it exceeds t, he guesses that it is the larger number. If it is smaller than t, he guesses that it is the smaller of Paula's numbers.

Why does this work? Because if t is smaller or larger than both of Paula's numbers, Victor will be right with probability 1/2. But, with positive probability t will lie between Paula's two numbers; and then Victor will guess correctly no matter which hand he picks. That gives Victor the edge to beat 50%.

Winkler notes that this strategy cannot guarantee to Victor any fixed winning edge in excess of 50%. Paula can randomly pick two consecutive multiple-digit numbers, and thereby reduce Victor's edge to a smidgen.

[witzar]

How about saying "smaller" with probability (1/2)+(1/2)^n (where n is the number Victor sees)?

[wolfgang]

Let him begin with (

larger) for example.
1- If he was right, so for the next hand he should change to ( smaller).
2- If he was wrong, he should stay by ( larger ) for the next hand.
and so on

[bonanova]

Let him begin with (

larger) for example.

1- If he was right, so for the next hand he should change to ( smaller).

2- If he was wrong, he should stay by ( larger ) for the next hand.

and so on

 

That's a nice idea wolfgang.

I'm not sure that it provides an advantage for Victor.

The way the puzzle is stated, Victor is not permitted to factor into his reasoning the outcome of prior hands.

Nor should we suppose that Paula will be influenced, by previous outcomes, in her choice of numbers.

The solution is a strategy that Victor devises that takes into account only what Paula does, as described in the OP.

[bonanova]

How about saying "smaller" with probability (1/2)+(1/2)^n (where n is the number Victor sees)?

 

It would be interesting to simulate this strategy against a grid of Paula numbers. I can't tell, from analysis or intuition, whether the strategy is effective.

 

I will describe the answer given in the book as to its form: It is probabilistic, but not with respect to the number that Victor sees. That is, Victor does something first. Having done it, when he sees one of Paula's numbers, he knows with certainty whether he will say higher or lower. Which is to say, I guess, he probabilistically sets a threshold.

[gavinksong]

How about saying "smaller" with probability (1/2)+(1/2)^n (where n is the number Victor sees)?

It would be interesting to simulate this strategy against a grid of Paula numbers. I can't tell, from analysis or intuition, whether the strategy is effective.

I will describe the answer given in the book as to its form: It

is probabilistic, but not with respect to the number that Victor sees. That is, Victor does something first. Having done it, when he sees one of Paula's numbers, he knows with certainty whether he will say higher or lower. Which is to say, I guess, he probabilistically sets a threshold.

We must not have the same solution in mind.

[karthickgururaj]

Before playing, Victor selects a probability distribution on the integers that assigns a positive probability to each integer. One way is to flip a coin until H appears. If he first sees an even number 2k (including 0) of T, he will select the integer k. If he first sees an odd number 2k-1 of T he will select the integer -k. After Paula picks her numbers, Victor selects an integer as just described and adds 1/2 to it. That becomes his threshold t. For example if Victor flips 5 T before his first H, his random integer is -3 and his threshold will be -2 1/2.

When Paula offers her two hands, Victor flips a fair coin to decide which hand to choose, then looks at the number in that hand. If it exceeds t, he guesses that it is the larger number. If it is smaller than t, he guesses that it is the smaller of Paula's numbers.

Why does this work? Because if t is smaller or larger than both of Paula's numbers, Victor will be right with probability 1/2. But, with positive probability t will lie between Paula's two numbers; and then Victor will guess correctly no matter which hand he picks. That gives Victor the edge to beat 50%.

Winkler notes that this strategy cannot guarantee to Victor any fixed winning edge in excess of 50%. Paula can randomly pick two consecutive multiple-digit numbers, and thereby reduce Victor's edge to a smidgen.

I don't agree with this it somehow feels wrong, but I'm not able to pin-point where the flaw is.. I'll get back in sometime..

 

And I'm going to post an other puzzle inspired by this one  

[gavinksong]

Before playing, Victor selects a probability distribution on the integers that assigns a positive probability to each integer. One way is to flip a coin until H appears. If he first sees an even number 2k (including 0) of T, he will select the integer k. If he first sees an odd number 2k-1 of T he will select the integer -k. After Paula picks her numbers, Victor selects an integer as just described and adds 1/2 to it. That becomes his threshold t. For example if Victor flips 5 T before his first H, his random integer is -3 and his threshold will be -2 1/2.

When Paula offers her two hands, Victor flips a fair coin to decide which hand to choose, then looks at the number in that hand. If it exceeds t, he guesses that it is the larger number. If it is smaller than t, he guesses that it is the smaller of Paula's numbers.

Why does this work? Because if t is smaller or larger than both of Paula's numbers, Victor will be right with probability 1/2. But, with positive probability t will lie between Paula's two numbers; and then Victor will guess correctly no matter which hand he picks. That gives Victor the edge to beat 50%.

Winkler notes that this strategy cannot guarantee to Victor any fixed winning edge in excess of 50%. Paula can randomly pick two consecutive multiple-digit numbers, and thereby reduce Victor's edge to a smidgen.

Ok then. I noticed that Victor doesn't actually have to choose his threshold before the game. So I guess it actually does have the same concept as Find The Apples, except that only certain probability distributions work with apples.

[bonanova]

Does the order matter?

Victor flips a dumb coin that has no eyes or memory.

The game  "starts" when Victor chooses one of Paula's hands.
It seems Victor could choose his threshold even after he sees the number.