The "boxes in boxes" problem actually turns out to be true in much greater generality, using a different solution: https://math.stackexchange.com/questions/1909085/suppose-a-b...
Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
11–20 of 146 posts
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#12Previous discussion: https://news.ycombinator.com/item?id=12380879
Some additional fun ones in the comments there.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#13I 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.…
"If we take ε to be huge" just means "let's analyze the growth rate as ε goes to infinity". More formally, what's going on is that you have a function which is polynomial in ε and which is always positive; therefore the leading coefficient must be positive, as if it were negative, the polynomial would be eventually negative. The question "what if it isn't huge" makes no sense; we can pick ε, it's not some external gi…
Thanks. Nice explanation. It's been a while (18 years) since I've read maths proofs.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#14The 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.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#15Love 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.
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
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#16Love 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.
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
“anything sent through the mail will be stolen unless it is enclosed in a padlocked box”
That’s why — A’s open padlock will be stolen.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#17Love 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.
Or just attach a lock that needs a combo (ex: 3,7,15) instead of a key to open it, then tell her the combination after she gets it and the risk of theft is zero.
The problem specifically says they are communicating using the internet, so why not?
"Hey, I sent you a box. It's locked with a combo lock. Call me when you get it: I want to be talking to you when you see the surprise! I'll tell you the combo on the phone!"
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#18Love 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.
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.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#19Love 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.
[deleted]
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#20Awesome post! I kind of want to find more of these types of things (solutions to seemingly complex questions). If anyone has recommendations would love to hear
I read quite a bit of books of that kind when I was young. I didn't read in English, but "One hundred thousand whys" - maths in Chinese was a great one, and this [1] in Vietnamese is a great one. They are all old books and some have solutions we can figure out by using a computer, but in general, they are really cool.
My personal favorite that has an English translation available, although it's not on Maths is "Physics for entertainment" by Perelman -- you can get it on Amazon right now. It was published 100+ years ago and problems are still relevant now. It discussed questions such as "When you jump out of a train, should you jump forward or backward?" "Who is wetter, a person standing in the rain or a person running in the rain?"
I guess basic maths and science hasn't changed that much, or maybe I was reading them when I was young, so I might not have known any better.
1: http://khoia0.com/PDF-Files/80-BAI-TOAN-THONG-MINH_handuc_v2...