4 ms·

The Puzzle Toad

86 points by jstrieb 6y ago

sellyme 6y ago
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.
- pbhjpbhj 6y ago
  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.
mitko 6y ago
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.
- pronoiac 6y ago
  I'm guessing this comment is about puzzle 13?
  - vitus 6y ago
    I'd expect this to be about the Caterer's Problem (i.e. the current problem, which shows up on the linked page).
- vitus 6y ago
  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 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.
  - deleted 6y ago
    [deleted]
  - ikeboy 6y ago
    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.
mrandish 6y ago
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.
- ikeboy 6y ago
  Art of problem solving has techniques, books, videos, etc. https://artofproblemsolving.com/resources https://artofproblemsolving.com/resources There's also http://brilliant.org http://brilliant.org which is useful

86 points by jstrieb 6y ago

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.

pbhjpbhj 6y ago
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.

mitko 6y ago

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.

pronoiac 6y ago
I'm guessing this comment is about puzzle 13?
- vitus 6y ago
  I'd expect this to be about the Caterer's Problem (i.e. the current problem, which shows up on the linked page).
vitus 6y ago
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 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.
- deleted 6y ago
  [deleted]
- ikeboy 6y ago
  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.

mrandish 6y ago

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.

ikeboy 6y ago
Art of problem solving has techniques, books, videos, etc. https://artofproblemsolving.com/resources https://artofproblemsolving.com/resources There's also http://brilliant.org http://brilliant.org which is useful