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]

#51

Post by ezrast » Sat, May 05, 2018, 7:20 AM UTC

gowld wrote: post #38

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.…

Yes, the solution to "Unwanted Expansion" is simply "because we assume that math works". It's begging the question. If you don't know what he's assuming, you don't know what proofs are "interesting". You could just as well say, "Because it's a finite" expression. "Boxes in Boxes" doesn't really fit the theme. It's a complicated elementary math problem that's hard to solve, but not "tricky" in way that makes it seem i…

The unstated observation made in Unwanted Expansion is that if every variable is equal to 2, then every operation in the expression must increase the total by at least 2 (note that only addition and multiplication are allowed, not subtraction or division). In other words, an expression with n terms or factors will always evaluate to at least 2n. This puts an upper bound on how far any finite-valued expression can be expanded.

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

#52

Post by ImSkeptical » Sat, May 05, 2018, 7:33 AM UTC

millstone wrote: post #18

IshKebab wrote: post #15

Earlier quoted context omitted.

I haven't looked at the solution but I don't see why it requires a box that can have two padlocks attached. A sends their open padlock and a box to B. B puts their open padlock in the box, and locks it with A's padlock and sends it back. A opens his padlock, puts the ring inside, locks it with B's padlock and sends it back. Maybe it was just too hard for you? :P

In this solution the open padlock would be stolen, because it is not in a locked box.

If that's true then shouldn't the double padlocked box be stolen as it is not a padlocked box but is instead a double padlocked box?

(Here I'm assuming the "correct" solution is A mails locked box containing ring to B. B adds a lock and returns the box to A. A unlocks lock A and returns the box to B which is locked only with lock B that can be undone by B.)

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

#53

Post by Deestan » Sat, May 05, 2018, 7:40 AM UTC

anyfoo wrote: post #37

cortesoft wrote: post #30

Earlier quoted context omitted.

Right, but if there were two red dots the town is fine. In a one red dot town, you could say “there is at least one blue dot”

Would they be fine? So let's say there are two people with red dots, let's name them Ruth and Rudy. Ruth now knows that "not all dots are blue" (which is equivalent to "there is at least one red dot"). She sees Rudy with the red dot: Fine, here's the person with the red dot. But wait a minute, why is Rudy not killing himself? If Rudy is the only person with a red dot, he should have seen only blue dots... however he…

Given 2 red dots, they would already know that not all dots are blue even before the stranger comes. At their first town meeting, everyone would know "not all dots are blue" and they would know that everyone else knew that information too.

Would this mean the colony would self-implode?

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

#54

Post by Deestan » Sat, May 05, 2018, 7:49 AM UTC

cortesoft wrote: post #42

anyfoo wrote: post #37

Earlier quoted context omitted.

Would they be fine? So let's say there are two people with red dots, let's name them Ruth and Rudy. Ruth now knows that "not all dots are blue" (which is equivalent to "there is at least one red dot"). She sees Rudy with the red dot: Fine, here's the person with the red dot. But wait a minute, why is Rudy not killing himself? If Rudy is the only person with a red dot, he should have seen only blue dots... however he…

Ok now it is making sense. The same would be true if you went to three dots.... the third person would think, “wait, why aren’t the two blue dotted people killing themselves? There must be a third blue dot... wait, the third blue dot must be me” That makes sense. What about the other commenter, who said something like “Alice has a blue dot.” Wouldn’t that not lead to everyone’s death?

In your three dots logic, this would have a red dot person kill themselves if there are two blue dots: The two blue dotted people aren't killing themselves because they are still thinking "wait, why isn't he killing himself" about the other.

I feel like some timing procedures need to be defined.

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

#55

Post by tomp » Sat, May 05, 2018, 9:27 AM UTC

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.

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

#56

Post by joosters » Sat, May 05, 2018, 10:06 AM UTC

anyfoo wrote: post #37

cortesoft wrote: post #30

Earlier quoted context omitted.

Right, but if there were two red dots the town is fine. In a one red dot town, you could say “there is at least one blue dot”

Would they be fine? So let's say there are two people with red dots, let's name them Ruth and Rudy. Ruth now knows that "not all dots are blue" (which is equivalent to "there is at least one red dot"). She sees Rudy with the red dot: Fine, here's the person with the red dot. But wait a minute, why is Rudy not killing himself? If Rudy is the only person with a red dot, he should have seen only blue dots... however he…

But how would they know how long to wait before they kill themselves? What if Rudy hasn't killed himself yet because he's slightly slower at solving logic problems?

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

#57

Post by Moodles » Sat, May 05, 2018, 10:07 AM 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.

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.

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

#58

Post by rwmj » Sat, May 05, 2018, 10:11 AM UTC

zawerf wrote: post #40

Where can I find more of these? Do you guys recommend this author's books such as https://www.amazon.com/Mathematical-Puzzles-Connoisseurs-Pet... ? (It's hard to find the right search term for this that doesn't return a lot of non-mathematical brainteasers or stuff aimed at kids)

I quite like William Poundstone's books. In this case these two are relevant: https://www.amazon.co.uk/How-Would-Move-Mount-Fuji/dp/031677... https://www.amazon.co.uk/Prisoners-Dilemma-Neumann-Theory-Pu...

Edit: These are not puzzle books specifically, but books about puzzles.

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

#59

Post by brownbat » Sat, May 05, 2018, 10:18 AM UTC

As to the dots, I enjoyed this variation from xkcd, where I first encountered it: https://xkcd.com/blue_eyes.html

It massively improved our play at Hanabi: https://boardgamegeek.com/boardgame/98778/hanabi

Probably would be a useful puzzle for improving your Spades or Bridge game, or any game you play with a partner with limited information.

Also, it gets much worse than The Random Native. George Boolos has a variation called "the hardest logic puzzle ever." It goes like this:

“Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language in which the words for ‘yes’ and ‘no’ are ‘da’ and ‘ja’, in some order. You do not know which word means which.”

There's an ongoing effort out there to make this variation even harder: https://arxiv.org/abs/1206.1926

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

#60

Post by mulur » Sat, May 05, 2018, 10:26 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.

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% chance.

How can we improve and make better than 50%?

'A' chooses two distinct integers each time. They can choose among infinite number of integers. For the first guess, I can't do better than 50% chance but if I start to keep history of the numbers that were picked it feels to me like I can do better than chance if I assume A chooses their distinct integers uniformly random by expecting a uniform distribution. I don't have much ideas about how to judge uniformness in an unbounded set of integers though but maybe something like: if first hand is less than the average of all previous numbers, I'd say "other number is higher", otherwise I'd say "other number is lower". I feel like this would improve my chances to more than 50% in the very long term (at infinite plays perhaps?) but am not able to prove it.

If A is not choosing their numbers randomly with a true RNG then I'd play many games at 50% chance then run their choices through a neural network to extract patterns then I'd do better than random for sure.