The trick ?
Add the top left number of each of the card chosen by the audience member who identified them as containing the number she had in mind.
Kudos to Laurent Jacques and an anonymous commenter on finding the solution.
It looks like this is a compressive sensing problem in the same way the 12-balls problem is. In effect, the results of the measurements are 0 (not there) or 1 (there) for each card (measurement). The solution is a whole lot simpler than most linear programming techniques for sure.
My take is the trick looks like magic because the measurement process is non-adaptive. The issue of the number of measurements is not even important. You could easily find that number through a bisection process i.e. by repeatedly halving a guess and it would also take five measurements (one less than the proposed solution) to find the culprit. Since these examples are probably a good way of introducing the subject of compressive sensing to a wider audience, I have made a list of these kinds of problems and their resolution in the CS Games page.
No comments:
Post a Comment