Puzzling Adventures: The Fair Way to Get a College Scholarship: Let's Make a Deal Solution

How should teachers rank their students' performance?

Each judge places all the students from one school in a single row and all the students of each major in a single column. The judge assigns ranks by affixing the appropriate rank to the blank side of each card. Then the judge turns the cards over so that the name, high school and major are showing.

To verify that the judge is telling the truth, a "verifier" first makes sure that each row represents a single school and each column represents a single major. Then the verifier points to a row or column. The judge takes the cards from that row or column. Under an opaque sheet, the judge flips the cards and shuffles. The judge then shows the verifier that all 10 rank numbers are present.

This can be done for each row and each column one at a time to ensure that the fairness constraints are met.

Back to Puzzling Adventures

Thanks to Michael Rabin for this approach to demonstrating knowledge without revealing secrets. He used it to form a "zero-knowledge" proof for Sudoku.

Share this Article:



Celebrate our 170th Anniversary with us!

Get 2 years of All Access for just $170

Save $28 now! >


Email this Article