The Hardest Logic Puzzles • Hacker News Board

Re: The Hardest Logic Puzzles

#41

Post by peterderivaz » Sat, Jul 27, 2013, 9:10 PM UTC

crondee wrote: post #32

gweinberg wrote: post #26

The Martin Gardner doesn't really seem to fit, since it is trivial to solve using brute force. Even if using a computer is considered cheating, there are shortcuts to use to keep from having to try everything. For example, having a "1" digit gets you nowhere, a "0" kills you, and a "5" and any even digit also kills you (and the 5 will persist at the end if you don't have an even digit, so it will probably kill you ne…

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.

In particular, I think you'll find the solution to 2 does not fit in your scheme. At least, not as far as I understand it. I'd like to see your scheme for enumerating possible questions fleshed out in more detail, but I don't think I believe you.

And you haven't answered about 4. Or 9.

Re: The Hardest Logic Puzzles

#43

Post by GhotiFish » Sat, Jul 27, 2013, 9:40 PM UTC

ColinWright wrote: post #40

GhotiFish wrote: post #38

Earlier quoted context omitted.

I have no idea how you'd make a scoring system that worked well with a hill climbing algorithm. You could check each word for a match in the dictionary, but with a substitution cipher you could essentially turn one word into any other word of the same length (excluding words with the same letter in them). Without a way to check for "close" words, you wouldn't be able to climb the hill. would "pello" score a 0.7 and "…

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…

...

that is a really good idea...

Turns out there's also a fair amount of data to use as well.

http://www.cse.chalmers.se/edu/year/2010/course/TDA351/ass1/...

I was thinking too rigidly. Thanks!

Re: The Hardest Logic Puzzles

#44

Post by ColinWright » Sat, Jul 27, 2013, 9:41 PM UTC

GhotiFish wrote: post #43

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…

... that is a really good idea... Turns out there's also a fair amount of data to use as well. http://www.cse.chalmers.se/edu/year/2010/course/TDA351/ass1/... I was thinking too rigidly. Thanks!

Norvig has made n-gram data available:

http://norvig.com/ngrams/

Re: The Hardest Logic Puzzles

#45

Post by GhotiFish » Sat, Jul 27, 2013, 9:59 PM UTC

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). That's the only circumstance I can see where someone could take action.

As much as that page insists that there is no word trickery going on, I'm inclined to think I've misunderstood the situation.

Re: The Hardest Logic Puzzles

#46

Post by Avshalom » Sat, Jul 27, 2013, 10:16 PM UTC

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…

the version of this I've seen before every one has blue eyes (except maybe the guru). day one some body with blue eyes looks around and knows there's at least one other person with blue eyes, so maybe the guru was talking about that person. day two no one has left so they know there's at least two people with blue eyes or else the blue eyed would have figured it out day one. of course they can still see at least two people with blue eyes, so no problem. Etc... day N hits and they come to the inescapable conclusion that they all have blue eyes and they all leave.

I'm not sure how that translates to two eye colors though. I'd guess basically the same, but I'd need to think some more.

Re: The Hardest Logic Puzzles

#47

Post by ProblemFactory » Sat, Jul 27, 2013, 10:38 PM UTC

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…

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 colour - the guru could have been thinking of the other one. So both blue people stay on the island on the first night. The other one staying on the island is information to the each of the blue people. Because the other blue one didn't leave on the first night, they must be also unsure - and therefore they must have blue eyes themselves. Both leave on second night.

Re: The Hardest Logic Puzzles

#48

Post by jules » Sat, Jul 27, 2013, 10:56 PM UTC

ColinWright wrote: post #42

jules wrote: post #33

Earlier quoted context omitted.

You can solve 2 with a computer by enumerating all possible questions. The gods can be in 3! = 6 configurations, and either da means yes or da means no. So there are 12 configurations in total. A question you can pose to a god will, as far as I can tell, always be of the form "are we in configuration A or configuration B or configuration C ...". So there are 2^12 questions you can pose. You can enumerate all of those…

How does the traditional "double-ask" question: If I were to ask you if you are the truth-telling god, would you say "da"? fit in your scheme? In particular, I think you'll find the solution to 2 does not fit in your scheme. At least, not as far as I understand it. I'd like to see your scheme for enumerating possible questions fleshed out in more detail, but I don't think I believe you. And you haven't answered about…

If I'm not mistaken, a question of the form "If I asked you Q, would you say A?" is the same as asking "Q xor (A means yes) xor (you are speaking the truth)". That is a direct question, which is part of the enumeration.

> And you haven't answered about 4. Or 9.

Umm...yes? I didn't intend to. But if you insist, 4 is not a logic puzzle, and 9 is easily solved in principle but possibly prohibitively long to calculate in practice. Compared to humans, computers are relatively less bad at finding a guaranteed winning move than at playing Go well, so you can't necessarily conclude that because humans play Go better than computers, they would also be able to solve that puzzle faster than computers.

Re: The Hardest Logic Puzzles

#49

Post by anonymous » Sat, Jul 27, 2013, 11:28 PM UTC

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…

CAUTION THIS IS PROBABLY A SPOILER:

Well, the simplest explanation is that the proof involves thinking about hypothetical worlds and each agent modelling everybody's behaviour in each hypothetical world, including what hypothetical-hypothetical worlds can arise, and hypothetical³ and so on. The Guru's statement exist in every world, no matter how hypothetical it is, while the subjective observation that there are blue-eyed people disappears in some of them.

Re: The Hardest Logic Puzzles

#50

Post by just2n » Sat, Jul 27, 2013, 11:29 PM UTC

ColinWright wrote: post #40

GhotiFish wrote: post #38

Earlier quoted context omitted.

I have no idea how you'd make a scoring system that worked well with a hill climbing algorithm. You could check each word for a match in the dictionary, but with a substitution cipher you could essentially turn one word into any other word of the same length (excluding words with the same letter in them). Without a way to check for "close" words, you wouldn't be able to climb the hill. would "pello" score a 0.7 and "…

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