The Puzzle Toad | Hacker News Reader

The Puzzle Toad

cs.cmu.edu

86 pointsjstrieb9 comments

Puzzle 1 contains a great example in knowing your audience:

> The problem confronting the FBI interrogation team is to separate the people into these two classes, so that all the managers can be locked up and all the engineers can be freed.

Well all the managers have been shredding documents, apparently, so maybe either check everyone's clothes for particulates from shredding and trust the person with the least agreeing particulates on them?

Or, DNA swab the shredders, discount the testimony of anyone who comes up?

They should reduce the number of questions needed.

I know that's not the game here.

I've always hated these kinds of problems because I'm so terrible at them, yet they have a strange appeal to me - like a magic trick I can't figure out.

After clicking on a few of the solutions, I discovered that the even the solutions aren't very helpful for me. What would be cool is a video where two people talk through how to think about coming up with solutions, white boarding as necessary. Maybe these specific problems are too advanced to be explained in a way accessible to the math-challenged.

If anyone knows of a resource that starts with these kinds of relatable problems but then thinks different approaches through out loud, I'd love a link.

Art of problem solving has techniques, books, videos, etc. https://artofproblemsolving.com/resources

There's also http://brilliant.org which is useful

I wonder if Arrows Impossibility Theorem has something to do with the puzzle.

My money on that it is possible to solve it without knowing AIT and most likely there is a way to construct a counter example using a script.

I'm guessing this comment is about puzzle 13?

I'd expect this to be about the Caterer's Problem (i.e. the current problem, which shows up on the linked page).

I think the 1024 (2^10) count is more important. We're not really looking for a community-wide preference -- instead, we're essentially looking to identify the size of the biggest possible Smith set [0], as defined for Condorcet methods.

[0] https://en.wikipedia.org/wiki/Smith_set

(This is nominally different from the general "smallest dominating set" problem, in that we have the preference ordering constraints.)

I'd expect the solution to somehow turn the selection process into a binary search so that each element in L is chosen such that (at least) half of the remaining people must satisfy some criterion. But, I haven't thought through exactly how that'd work.

Yes, that's almost exactly how it works. First option can be chosen to beat at least 511 others, second option to beat 255 others of the remaining, and so on. Just add up total number of group preferences among each subset and divide by number of options to show that.

The number of people is irrelevant. This works with a million people just as well. Ignore people, only look at group pairwise preferences.

Reply on news.ycombinator.com