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

31–40 of 146 posts

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

#31

Post by millstone »

cortesoft wrote: post #25
millstone wrote: post #21

In the Dot-town suicides, say the stranger says "Alice has a blue dot." Alice then kills herself. Why would the other residents die? I think this satisfies the requirements: there's certainly some number of blue dots for which the statement would be false, namely zero.

Yeah, I was thinking about if the stranger said something like, “not all the dots are blue.” This is non-trivial by the definition given, and no one would have to kill themselves at all.

I think that statement is still subject to the proof given. "Not all the dots are blue" just initialize K to {n}, and the induction proceeds as written.

The flaw in the proof is that it assumes that townsfolk only learn their dot color based on counting arguments. If the stranger's "anything non-trivial" statement includes information beyond just a raw count, then a townsfolk may learn their dot-color prematurely (e.g. by being told in the statement) and the proof fails.

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

#32

Post by gowld »

millstone wrote: post #21

In the Dot-town suicides, say the stranger says "Alice has a blue dot." Alice then kills herself. Why would the other residents die? I think this satisfies the requirements: there's certainly some number of blue dots for which the statement would be false, namely zero.

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 information (It's equivalent to "There is at least one blue dot", and Alice has a blue dot"), and that extra information is critical in that, even though it adds some information, it removes useful information by reducing the information entropy of the situation, which stymies efforts to make inferences.

The problem wording is (arguably) ambiguous on that point.

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

#33

Post by gowld »

cortesoft wrote: post #30
uiri wrote: post #27

Earlier quoted context omitted.

"not all the dots are blue" - in the case where there are n people with n-1 blue dots and 1 red dot, the person with the red dot kills themself, and then everyone else kills themselves because they know that the red dot person killed themself because they did not see any red dots.

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”

By induction and perspective-taking, 1 person dies each time everyone sits and thinks for a while.

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

#34

Post by oh_sigh »

scrooched_moose wrote: post #7
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.

To get super pedantic, even if that was the case you could use a lock out tag out type device to still attach two locks. https://www.media-partners.com/upload/i20121017160441/img1.j...

Unfortunate that they don't show multiple locks in that image.

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

#35

Post by gowld »

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

Turn the "suicides" into escaping prisoners, so being smart enough makes them survive.

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

#36

Post by gowld »

readams wrote: post #14

The nice thing about this is that we can use Dot-town as a halting oracle, which can then be used to solve any specific undecidable problem we'd want to solve. Make the machine output a set of dots after running some unknown computation, such as a search for twin primes. The residents will kill themselves depending on the results.

How so?

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

#37

Post by anyfoo »

cortesoft wrote: post #30
uiri wrote: post #27

Earlier quoted context omitted.

"not all the dots are blue" - in the case where there are n people with n-1 blue dots and 1 red dot, the person with the red dot kills themself, and then everyone else kills themselves because they know that the red dot person killed themself because they did not see any red dots.

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 knows there has to be at least one red dot, so if he only saw blue dots, the red dot must have been him, so he would have killed himself.

But he didn't, so that means he has seen at least one red dot, which isn't him, and isn't anybody else Ruth has seen because she only saw blue dots otherwise.

Oh no, it must be Ruth with the second red dot!

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

#38

Post by gowld »

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

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

#40

Post by zawerf »

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)

Post reply on HN