Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Hardest Logic Puzzles

conceptispuzzles.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: The Hardest Logic Puzzles

#51

Post by Gormo »

DanielRibeiro wrote: post #2

What about making Conway's Game of Life in Conway's Game of Life? http://www.youtube.com/watch?v=xP5-iIeKXE8

This is brilliant. It's not even a "logic puzzle" as much as it is an engineering feat.

And it's not like software engineering, where you're defining the nature of the system as a whole, and then instantiating it, but more like a physical engineering discipline, in which you're juxtaposing already-existing materials against each other such that their pre-existing properties interact with each other to produce the behavior you want.

Re: The Hardest Logic Puzzles

#52

Post by ampersandy »

ProblemFactory wrote: post #47
GhotiFish wrote: post #45

Earlier quoted context omitted.

I'm surprised "no one leaves" the guru really doesn't seem to provide any new information. everyone knew she could see someone with blue eyes. Nor does it seem anyone can act on the information, nor does it seem everyone's inaction be taken as new information. If the guru said. I see someone with red eyes, then everyone would try to leave (or only the guy with red eyes would try to leave if the guru wasn't lying). Th…

The guru does provide very indirect meta-information. Everyone's inaction cannot be taken as information on the first day, but inaction over time can. Consider the case with 100 brown and 1 blue person (+ guru). As soon as the guru speaks, the blue person knows their eye colour and leaves. Consider the case with 100 brown and 2 blue people. After the guru speaks, both of the blue people still don't know their own eye…

Exactly this; ProblemFactory has shown how the guru provides directly actionable information for the simplest case of the problem (1 blue eyed islander) and also highlighted the inductive step that leads to a proof for any number of blue eyed islanders.

Reducing to the simplest scenario and building (as ProblemFactory) has done, makes the result much more intuitive -- as it does in most proofs, really.

Also, the logicians comic is wonderful :)

Re: The Hardest Logic Puzzles

#53

Post by ampersandy »

TallboyOne wrote: post #23
marknadal wrote: post #16

Earlier quoted context omitted.

So I started to work it out, only to discover the link about the problem in the article gives it away - counterfactuals can be used, so might as well read that instead of any thing I come up with. And thus I just wasted a bunch of time trying to figure out which specific one worked (now erased) ... but my hunch was correct! (Although hunches are hardly proofs, tsk tsk) Also, I want to thank you again for helping me o…

What's a counterfactual? can you give a simple explanation of how that solves the problem?

A counterfactual is a statement or question in the form 'If X ... would Y". Y would happen if X were true. Or, would Y be true, given that X were true? [0]

In the case of this puzzle, a counterfactual can be used to embed a question X within your question Y. By doing so (and exploiting the phrasing of the problem), you force the gods to answer in a manner that either reveals their identity as True, False, or Random.

Explaining the actual process through which the counterfactual is used to solve the problem is a bit tedious but the Wikipedia article on the puzzle has a pretty straightforward explanation of the reasoning[1].

[0] http://en.wikipedia.org/wiki/Counterfactual_conditional [1] http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever.

Re: The Hardest Logic Puzzles

#54

Post by javajosh »

GhotiFish wrote: post #34
javajosh wrote: post #21

Earlier quoted context omitted.

That's an interesting insight, and it may be useful as part of the solution, but it doesn't solve the puzzle. The question is how to determine the identity of the three gods with three questions. Personally, I think it's interesting that they are gods. Does this mean that they can answer questions about what WILL happen? E.g. you could ask a god what the next god will answer. If the answer is correct, that's the true…

I suspect they are mentioned to be gods to suggest that they may be asked extremely complicated questions, which they will interpret from a purely logical standpoint. ie. Not human.

Starting from this premise, imagine this sequence of questions (it's not the answer, btw):

1. What is the answer to the next question? A: 1, 0

2. What was the answer to the previous question? B: 1, 0

3. What was the answer to the previous question? C: 1, 0

000-impossible: no false god

001-C is the false god, but can't distinguish the other two

010-impossible: no true god.

011-C is the true god, but you can't distinguish between the false and random god

100-A is the false god, but can't distinguish the other two

101-impossible: no true god.

110-A is the true god, but you can't distinguish between the false and random god

111-impossible: no false god

This is interesting: we have eliminated 4 possibilities, 000, 111, 101 and 010. Not only that, now we have a whole new universe to converse about - we can ask the gods about these patterns!

The remaining possibilities show some symmetry: 001 and 100, 011 and 110.

So, thinking aloud, start with these questions:

1. Will the result of my questioning be either 001 or 100?

2. Will the result of my questioning be either 011 or 110?

The answers won't give us much information because they can be anything. But we can "break symmetry" and ask them like this instead:

1. Will the result of my questioning be either 001 or 011?

2. Will the result of my questioning be either 100 or 110?

...and I feel like I'm very close but I'm missing something.

Re: The Hardest Logic Puzzles

#56

Post by caretcaret »

GhotiFish wrote: post #45
theon144 wrote: post #39

How about xkcd's Blue Eyes puzzle? https://xkcd.com/blue_eyes.html

I'm surprised "no one leaves" the guru really doesn't seem to provide any new information. everyone knew she could see someone with blue eyes. Nor does it seem anyone can act on the information, nor does it seem everyone's inaction be taken as new information. If the guru said. I see someone with red eyes, then everyone would try to leave (or only the guy with red eyes would try to leave if the guru wasn't lying). Th…

I found this difficult to pinpoint, too, until I read about common knowledge. The example here is very relevant: http://en.wikipedia.org/wiki/Common_knowledge_(logic)

At first, the islanders do not know that the other islanders are making the same logical judgments.

The proof relies on the fact that each islander knows what the other islanders have deduced by each day.

By making an announcement to everyone at once, the new information that the guru provides is the common knowledge that (i) there is a blue eyed person, (ii) the islanders know there is a blue eyed person, (iii) the islanders know the other islanders know that there is a blue eyed person, and so on.

Note that if the guru went to each islander one by one and told them individually that there is a blue-eyed person, they do not learn anything new about the other islanders and nobody would leave.

Re: The Hardest Logic Puzzles

#57

Post by gholap »

gweinberg wrote: post #24

#2 is really only difficult because it's easy to misinterpret the rules. Random doesn't randomly answer yes or know, he randomly decides whether to answer truthfully or falsely. So for example if you ask the recursive question "are you answering this current question truthfully" he will answer yes either way. Or rather, his word for yes. Once that rule is clear, the puzzle is pretty straightforward.

I am not sure whether that info has much bearing on the puzzle itself as such. Even in the case when random randomly answers either "yes" or "no", the solution is equally straightforward and simple.

Re: The Hardest Logic Puzzles

#58

Post by gholap »

Regarding #2,

I read Boolos' paper and found that the way the solution was explained wasn't quite to my taste (it did not have discussion on how one would go about thinking of a solution and step-by-step, logically proceed toward a solution). Add to that, the concepts of abstraction, putting away the complexity into a neat-separate function and then forgetting about the internal details, could be applied nicely to the solution in a number of places and I thought it would make the solution much easier to understand. I took an approach where I keep on reducing the problem to a simpler one by abstracting away some details and complications.

Do have a look at my attempt at explaining the solution, especially the process of arriving at the solution (for "The Hardest Logic Puzzle Ever"): http://blog.sujeet.me/2013/07/solving-the-hardest-logic-puzz...

Feedback's welcome!

Re: The Hardest Logic Puzzles

#59

Post by ColinWright »

just2n wrote: post #50
ColinWright wrote: post #40

Earlier quoted context omitted.

Take a frequency chart of all trigrams in English, and take the vector product of the frequency in the decrypt with the frequency in English. So, let E(t) be the frequency of occurrence of the trigram t in English, d(t) be how often it occurs in the decrypted text, and compute: Score = sum( [ E(t)*d(t) for t in decrypt ] ) If common trigrams turn up frequently in the decrypt, this will be "large". If uncommon trigram…

Why not use a residual sum of squares here? https://en.wikipedia.org/wiki/Residual_sum_of_squares

I don't understand your question.

My (admittedly naive) understanding of using RSS is this. I have a model of the data, which in this case will be expected frequencies of my n-grams. Then I compute the actual frequencies of the n-grams, take the difference, square the difference, and add up all the squares. A small number is then indicative of a good fit.

I don't see why this would be better. Not least, this has the problem of all those n-grams that don't turn up in my decrypt. I still have to square their expected frequency and add them into the sum. That contrasts with the method I'm using, where I just take the n-grams that do appear, multiply by the expected frequency, and add that into a running total.

So I guess I don't understand your suggestion.

Re: The Hardest Logic Puzzles

#60

Post by crondee »

peterderivaz wrote: post #41
crondee wrote: post #32

Earlier quoted context omitted.

I dont think it will max out. I brute forced it upto 10 million and I got the following numbers (5, 679) (6, 6788) (7, 68889) (8, 2677889) sure the numbers are exponential but no reason to suspect that a glass ceiling exists.

Interestingly, Wikipedia disagrees. For a radix of 10, there is thought to be no number with a multiplicative persistence > 11: this is known to be true for numbers up to 10 to the power of 50. http://en.wikipedia.org/wiki/Persistence_of_a_number I guess the problem is that when you multiply lots of digits together you become increasingly likely to end up with a 0 digit somewhere.

Thanks for the link, I dug a little more and came across [1] which mentions a contribution by erdos to the effect that persistence might not be bounded. I guess I might spend some time to figure out number 12 :) [1] http://web.archive.org/web/20050214141815/http://www.wschnei...
Post reply on HN