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

How should teachers rank their students' performance?

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.

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

Dennis Shasha is at the Courant Institute of Mathematical Sciences, New York University. His most recent puzzle book Puzzles for Programmers and Pros, was published in May 2007 by John Wiley and Sons/Wrox.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Magazine | 1 hour ago

### What to Do about the Flu?

• Scientific American Magazine | 3 hours ago

### Orphaned Chimpanzees Play Rougher Than Their Mother-Reared Counterparts

• Scientific American Magazine | Dec 7, 2013

### Teenage Flu Scientist Shares His Recipe for Prizewinning Research

• Scientific American Magazine | Dec 7, 2013

• Cocktail Party Physics | Dec 7, 2013

More »

## Latest from SA Blog Network

• ### Sunday Species Snapshot: Fijian Monkey-Faced Bat

Extinction Countdown | 17 minutes ago
• ### Right now, there's a giant blue chicken in Trafalgar Square

Tetrapod Zoology | 1 hour ago
• ### The bacteria in breast milk

Lab Rat | 1 hour ago
• ### Stream of Thought Description of Teaching James's "Stream of Thought": A Work of Faction

Cross-Check | 23 hours ago
• ### Physics Week in Review: December 7, 2013

Cocktail Party Physics | Dec 7, 2013

## Science Jobs of the Week

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

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X