Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

math.dartmouth.edu

Post reply on HN
Print view View original

81–90 of 146 posts

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#81

Post by conorh »

OscarCunningham wrote: post #73
pyk wrote: post #68

Earlier quoted context omitted.

After writing this one out, this reminds me of the Monty Hall problem. In this case my guess is that you use a prior -- assume the two unknown numbers are A & B, and then assume a random integer yourself C. From there, if A (the first revealed number) is less than C, then that narrows the remaining cases giving you a 2/3 chance. If A is greater than C, that also narrows the remaining cases and gives you a 2/3 chance…

This works, but you don't get a probability of 2/3, because the cases aren't equally likely. There isn't a probability distribution for C such that for any A and B the probability of A<C<B is 1/3. We would have to have P(0<C<10)=1/3 and P(10<C<20)=1/3 and P(0<C<20)=1/3, which is impossible.

Why does this work with probability 2/3 then?

https://jsfiddle.net/q4qbewp1/

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#82

Post by konschubert »

tomp wrote: post #55

Another very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on slips of paper and holds one out in each hand in a fist. You choose a hand and reveal a number. You must then guess whether the other number is higher or lower than the revealed one, winning $1 if you guess right and losing $1 otherwise.

Is the range of integers limited? Does she choose them randomly?

If the range isn't limited, hoe would we even define a normalized probability distribution?

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#83

Post by jakear »

quickthrower2 wrote: post #8

I loved this. Some comments. Not really spoilers I hope... For "Unwanted Expansion" the answer is technically correct but I am displeased that it doesn't prove there wont be any infinite loops. Whereas analyzing invariant in the tree should prove that. For Boxes in Boxes it says "But, if we take ε to be huge", but how big is huge, and what if it isn't huge? Seems like something in the proof is being hand waved over.…

I was is similarly displeased with "Unwanted Expansion". I'd prefer some sort of fixpoint algorithm, which could then be a applied to the case with "-", which their version couldn't.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#84

Post by OscarCunningham »

conorh wrote: post #81
OscarCunningham wrote: post #73

Earlier quoted context omitted.

This works, but you don't get a probability of 2/3, because the cases aren't equally likely. There isn't a probability distribution for C such that for any A and B the probability of A<C<B is 1/3. We would have to have P(0<C<10)=1/3 and P(10<C<20)=1/3 and P(0<C<20)=1/3, which is impossible.

Why does this work with probability 2/3 then? https://jsfiddle.net/q4qbewp1/

Because of the particular distributions that you happen to have chosen. Alice doesn't have to pick uniformly at random. Since 0^p=0 and 1^p=1 we can experiment with different distributions by using "Math.pow(Math.random(),p)" in place of "Math.random()". For example:

  var prior = Math.pow(Math.random(),1);
  var hand1 = Math.pow(Math.random(),10);
  var hand2 = Math.pow(Math.random(),10);
  > Win probability: 0.5757182
and

  var prior = Math.pow(Math.random(),1);
  var hand1 = Math.pow(Math.random(),0.1);
  var hand2 = Math.pow(Math.random(),10);
  > Win probability: 0.9026432
But the win probability will always be >0.5 so long as the "prior" probability distribution has a nonzero probability of being between Alice's two numbers.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#85

Post by Semkas »

tomp wrote: post #55

Another very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on slips of paper and holds one out in each hand in a fist. You choose a hand and reveal a number. You must then guess whether the other number is higher or lower than the revealed one, winning $1 if you guess right and losing $1 otherwise.

Assume that the range of integers is limited by the largest positive or negative number that can be written on the limited space of the paper. Whenever the largest positive or negative number comes up your answer will be certain. Turn a profit over a few billion years.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#86

Post by [deleted] »

conorh wrote: post #81
OscarCunningham wrote: post #73

Earlier quoted context omitted.

This works, but you don't get a probability of 2/3, because the cases aren't equally likely. There isn't a probability distribution for C such that for any A and B the probability of A<C<B is 1/3. We would have to have P(0<C<10)=1/3 and P(10<C<20)=1/3 and P(0<C<20)=1/3, which is impossible.

Why does this work with probability 2/3 then? https://jsfiddle.net/q4qbewp1/

[deleted]

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#87

Post by raverbashing »

deathanatos wrote: post #5

Love in Kleptopia needs to be explained better. The problem can only be solved if you can afix two padlocks onto a box, and I was presuming the lock box had a single, normally shaped padlock eye, which would make such a thing impossible. I find this happens a lot with "thought" problems: I can't solve it (and can often prove that) because the rules of the problem are inadequately explained.

Yeah, underdetermined/badly explained problems are just irritating. Especially since you don't know what level is the person targeting, or come with a smug answer about some detail that was not specified.

I don't waste much time with them to be honest.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#88

Post by johnc1231 »

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#89

Post by mundo »

sirclueless wrote: post #61
mulur wrote: post #60

Earlier quoted context omitted.

Hmm I'm not exactly good with maths (or puzzles for that matter) but here is a blind stab: By break even, I think you mean that the game is played multiple times, as long as necessary. If you are not following a martingale like strategy (edit: you can't anyways, the bets are fixed) and respond randomly (or with full faith that this is your lucky day, doesn't matter really), you are expected to break even with 50% cha…

You can do better than that. You can guarantee there is > 50% chance you win on the first guess.

> You can guarantee there is > 50% chance you win on the first guess.

You mean "greater than" and not "greater than or equal to"?

The latter is easy; lots of naive strategies accomplish that. But the former implies that you can declare a strategy and the puzzle offerer cannot then pick a distribution that defeats it. It's hard to imagine how you could get >50% for example if the puzzler's strategy is to pick N and N+1 for very large N.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#90

Post by jameshart »

cabaalis wrote: post #71
mtreis86 wrote: post #69

Earlier quoted context omitted.

Those problems always bothered me. I think that for any sequence of numbers there is an infinite number of next-in-sequence solutions regardless of the sequence length or numbers contained. One may be more obvious but you can put any number next and find a pattern that matches. Example - what if those are a sequence of digits in pi.

I think "What comes next?" is an incomplete question, without any context. "What comes next in the sequence of (blah)?" is a complete question with full context. But that question wouldn't make anybody feel superior. "Identify as many sequences as you can which fit this set of numbers, and tell me the next number in each sequence" is the non-trick actually being asked.

I think the only sane approach is to apply a Kolmogorov-shaded Occam's Razor, and select, from the set of possible sequences which fit the pattern, the one which has the simplest generating function.
Post reply on HN