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

161–170 of 220 posts

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

#161

Post by kens »

I like Cheryl's transfinite logic puzzle, which takes logic puzzles to a ridiculous extreme.

http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...

The puzzle is inspired by Cantor's transfinite ordinal numbers, which are pretty cool. You don't need to know anything about transfinite numbers to solve the puzzle, but they are interesting in their own right. The simplified idea is suppose you count 1, 2, 3, ... up to infinity (ω). Everyone knows adding 1 to infinity doesn't get you anywhere, but suppose you can do it and get ω+1, ω+2, ... The limit is 2ω. But then you can go 3ω, 4ω, ... Which obviously :-) gets you to ω*ω = ω^2. Then you can keep going with bigger and bigger infinities. See https://en.wikipedia.org/wiki/Ordinal_number

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

#162

Post by x1798DE »

tiglionabbit wrote: post #155
JoeAltmaier wrote: post #149

Earlier quoted context omitted.

The clock is certainly necessary. But for information, I think its as easy as "somebody has blue eyes!" said once. If only one person has blue eyes, they see no one else with blue eyes so kill themselves. If two people have blue eyes, they see the other guy and think "maybe its only him". Next day, that guy is still alive; they now know the only remaining blue-eye is themselves; midnight comes and they both suicide.…

If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes.

> If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes.

The new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.

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

#163

Post by hexane360 »

gambiting wrote: post #52
phkahler wrote: post #39

Earlier quoted context omitted.

I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)

Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes. The crucial part here is that it's not guaranteed to work - but i…

If each prisoner has their own ordering, it's exceedingly likely that one of those orderings will have a 51-cycle.

This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together.

If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.

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

#164

Post by bzbarsky »

cousin_it wrote: post #160
bzbarsky wrote: post #152

Earlier quoted context omitted.

> Therefore the "perimeter" of the inner box can't be greater than the sum of its projections. What definition of "perimeter" are you using here?

See response to pfedak.

I'm still not quite following. Is the "perimeter" here the sum of the lengths of projections of the edges, then how is that different from "the sum of its projections"?

Anyway if you define "perimeter" that way then for the outer box the "perimeter" is in fact 4 * (a+b+c), where a, b, c are the dimensions of the box. I also agree that for the inner box the "perimeter" is at least 4 * (a'+b'+c'), by the triangle inequality.

What is not at all clear to me is why the "perimeter" of the inner box is no larger than the "perimeter" of the outer box in this setup. You say it's easy to check, but it doesn't seem very obvious to me.

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

#165

Post by hexane360 »

CPLX wrote: post #60
agf wrote: post #50

Earlier quoted context omitted.

I think you're referring to this puzzle: http://datagenetics.com/blog/december12014/index.html The version you gave is missing information and so can't be solved as stated.

I had to read that like 11 times before I started to get the underlying principle. That's amazing.

In a very similar vein, try this one: https://youtu.be/N5vJSNXPEwA

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

#166

Post by andrepd »

posterboy wrote: post #147
andrepd wrote: post #137

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Singular_they

Good grief. If you want to write objective, do so, and ommit personal pronouns all together, but don't employ this archaic, confusing grammatical quirk. I'd like to point out to you, ekke's comment was much better understandable and shorter. Edit: Did you even read what you linked? > One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as se…

You seem to be very angry with a feature of English grammar. Using they/them/their is a perfectly reasonable, consistent and well-understood way to refer in the third person to someone of unknown gender.

How would you rewrite the sentence "If the light is on when F gets to the room, they turn the light off, and they increment their counter." without using they?

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

#167

Post by 5tk18 »

SilasX wrote: post #90
dsugarman wrote: post #83

Earlier quoted context omitted.

>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me aw…

>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't…

I think dsugarman meant "at least once over any FINITE amount of time", in which case each prisoner might visit again an infinite number of times, but it can be arbitrarily many turns in the future.

So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.

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

#168

Post by Tloewald »

evanb wrote: post #93
iliis wrote: post #79

Ah, I love these kind of puzzles! Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance. There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room…

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if…

Why does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.

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

#170

Post by aiiane »

Tloewald wrote: post #168
evanb wrote: post #93

Earlier quoted context omitted.

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if…

Why does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.

If the initial state of the light is known to F then you only need once per person.

However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached.

The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 times, for a total of 197 "on" count, with 198 guaranteeing 99 people involved, but if the light starts off the 99 people will turn it on 198 times as well.

Post reply on HN