Puzzling Adventures: The Fair Way to Get a College Scholarship: Let's Make a Deal Solution
How should teachers rank their students' performance?
By Dennis E. Shasha
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Solution:
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.
It’s Time to Stand Up for Science
If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.
I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.
If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.
In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.
There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.
