Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf] • Hacker News Board

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

#141

Post by ccvannorman » Mon, May 07, 2018, 6:28 AM UTC

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.

This is actually funny. I would argue the solution is invalid, except that due to mortality it actually works.

The problem lies in the assumption about how Alice thinks.

The set of integers is countably infinite, so your probability to guess a specific number N is zero if the distribution is uniform (e.g. there isn't a higher likelihood of picking "smaller / closer to zero" numbers.) [1]

But because it would take a lot of mortal time to describe arbitrarily large numbers, you MUST assume that because Alice is mortal, she'll pick a number she could describe in her lifetime.

Therefore, the question is not valid. Alice does not truly have a domain over all the integers to choose from. She only has the ability to pick numbers she could write down on a slip of paper within her lifetime.

Since the paper is limited in how much information it can contain anyway, it therefore cannot represent any arbitrary integer from the infinite set.

So the question is re-written: Alice picks two integers from a finite pool..

[1] https://math.stackexchange.com/questions/30619/probability-o...

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

#142

Post by ChristianGeek » Mon, May 07, 2018, 7:31 AM UTC

Moodles wrote: post #57

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.

Reminds me of this: 1, 2, 3, 4, 5, 6, 7, 8, 9,... What comes next? 10 if it's the sequence of natural numbers 13 if it's the sequence of N such that N=2^n for natural numbers n, where N does not contain a 0 153 if it's sequence of N such that the the sum of the digits of N each raised to the power of the number of digits in N equals N.

A if you’re counting in hexadecimal.

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

#143

Post by chronolitus » Mon, May 07, 2018, 2:45 PM UTC

learnstats2 wrote: post #114

The Dot Town Suicides appears to be incorrect as stated. Suppose there are 100 residents and 2 blue dots. The stranger tells everyone "there are not 98 blue dots" This meets the condition of the question's "non-trivial" but the residents can relax: nobody has learned anything new. The proposed induction is broken, in my opinion.

Unless "There are not 98 blue dots" also means "There are not 2 red dots"? Then the process starts and months later all red dots leave.

This requires that everyone know only blue or red eyes are allowed.

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

#144

Post by neaden » Mon, May 07, 2018, 4:23 PM UTC

millstone wrote: post #41

gowld wrote: post #32

Earlier quoted context omitted.

That's not what the author intended by "anything about the number of blue dots". The author means "anything about the number of blue dots, but not who has them", because the proof of the solution relies on the fact that each person ("Alice") doesn't know whether their own dot is in the set the stranger speaks about but everyone else does know whether "Alice" is in the set. "Alice has a blue dot" adds extra informatio…

I think that's right. So the author's description of "anything non-trivial" is weakened to "anything non-trivial maintaining information symmetry", which feels constricting, certainly no longer "frighteningly general." This also reveals a strategy for townsfolk who wish to survive: simply inform a blue-dot of their color, breaking the logic chain. That winning move ought to factor into the strategy of these perfect l…

I suppose then they will all simultaneously do it and all die. Or perhaps being perfect logicians they will hold a lottery and inform the winner of their state causing them to die alone for the good of the group.

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

#145

Post by derefr » Tue, May 08, 2018, 6:46 PM UTC

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.

Also, given that

1. these are regular padlocks;

2. Alice and Bob already have a secure communications channel along which information, but not objects, can flow (the Internet);

...then the puzzle has a "cheese" solution: just communicate the metrics of the key along your secure channel, and have your counterparty reproduce the key using them! Padlock keys are essentially number sequences :)

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

#146

Post by sirclueless » Sun, May 13, 2018, 9:46 AM UTC

OscarCunningham wrote: post #107

tomp wrote: post #105

Earlier quoted context omitted.

> if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. No because you pick the hand (i.e. it’s essentually random), so you still have 50% chance of first revealing 20 and gettingit right.

Good point. So our methods are similar, but yours puts the randomness in the choice of hand rather than the choice of integer. But in the (10,20) case your method gets exactly 50% and not more than 50%.

This is why your choice of threshold matters. Your strategy should be to choose a threshold randomly from any distribution that is non-zero everywhere (such as a normal distribution), then choose a hand uniformly at random.

Choosing zero as a threshold deterministically does not work for all choices that Alice can make because, as you say, for some choices such as (10,20) it gives you exactly 50% chance to win. But as long as there is always a non-zero chance that you chose a threshold between Alice's numbers, then there is a > 50% chance that you win the game.