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

How should teachers rank their students' performance?

One hundred students are competing for college scholarships. They come from 10 schools (10 students per school). From each school, one student has declared physics as a major; one has declared chemistry; one, biology; one, psychology; one, mathematics; one, economics; one, anthropology; one, linguistics; one, English; and one, history. So, the group has 10 students for each of these majors.

Each of three judges is going to rank the students in 10 ranks from best (rank 1) to worst (rank 10). That is, each judge is to assign ten 1s, ten 2s, and so on up to ten 10s. So, each judge will assign one rank per student.

In previous years, some of the losing students have alleged that the judges were biased, so we want to ensure two "fairness" constraints that will require some planning on the part of the judge. In the rankings done by each judge:

1. Each school will receive 10 different ranking scores.
2. Each major will receive 10 different ranking scores.

So, among the economics majors, for example, each judge should assign one 1, one 2, one 3, and so on up to one 10. Similarly, among the students from Pleasanttown High School, each judge should assign one 1, one 2, and so on up to one 10.

Each student's three scores (one from each judge) will be averaged.

Our problem is to ensure that each judge obeys the constraints but without our knowing how that judge voted. That is, out of respect for the privacy of the judging, we want to know for certain that the judges obeyed the constraints but nothing more.

To show you that this is at least conceivable, suppose we imagine a variant of Monty Hall's game show, Let's Make a Deal, using cards in which all of them are worth zero except one that is worth \$10,000. The Master of Ceremonies begins the game by arranging the cards face down. The contestant could choose one, which the MC would turn over and then give the corresponding reward. If the contestant loses, he or she might then challenge the MC to see whether there is in fact one card that is worth \$10,000. To prove this, the MC could take the cards, shuffle them in front of the contestant, and then reveal them. The net effect is that the MC has proved that he has not cheated. At the same time, he has not revealed the original position of the prize card.

Problem:
Imagine that each judge is given 100 opaque cards that hold the name, school and major of the student on one side and are blank on the other. Each judge also has 100 adhesives, ten identical 1s, ten identical 2s, and so on up to ten 10s. Can you design a protocol to ensure that each judge meets the constraints, but without allowing anyone to infer a judge's votes?

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

• News | 7 hours ago | 2

### Hopes Dashed for HIV Cure with Bone Marrow Transplant

• Reuters | 10 hours ago | 1

### Winter Storm Pushes Up U.S. East Coast after Deep-Freeze in the South

• Reuters | 12 hours ago | 2

### As Keystone Ruling Nears, Canada Short on Time for Climate Plan

• Reuters | 13 hours ago | 10

### Arctic Thaw Tied to European, U.S. Heatwaves and Downpours

• Reuters | 13 hours ago

More »

## Latest from SA Blog Network

• ### Gag Me With a Spoon: "Val-Speak" Takes Over SoCal

Cocktail Party Physics | 6 hours ago
• ### Nerds and Words: Week 49

Overthinking It | 13 hours ago
• ### Photoblogging: Muppet or Flamingo?

MIND
The Thoughtful Animal | 15 hours ago
• ### Sunday Species Snapshot: Fijian Monkey-Faced Bat

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

Tetrapod Zoology | 17 hours ago

## Science Jobs of the Week

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

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