# Ranking teacher salaries in the Republic of al'Alghaz

and welcome to the Republic of al'Alghaz!

This is the International School of al'Alghaz (ISA), the best (and most expensive) school in the country. It's built for all the children of expats, royals, diplomats, and any other snob-nosed foreign children those parents have too much money.

But you see, there's a problem. There are two kinds of teachers in ISA, foreign teachers ($F$) and Alghazi teachers ($A$). We suspect that foreign teachers are paid salaries that are much higher than us local teachers, but we cannot find out for sure - because discussing salaries is forbidden. However, we'd like to find some way to rank salaries - even if we cannot know the actual salaries themselves.

How can we find out the ranking of salaries for teachers, without knowing the actual salaries themselves?

• You may not ask a teacher about their salary in relation to others (they don't know anyone elses salary apart from themselves)
• You may ask any other question, and they will answer 100% honestly.

Naturally, we'd come up with a solution to this problem ourselves, but you see - the only Math teacher here is the second cousin to the Dean's sister, and ah... well, that's a problem in our country...

For the sake of simplicity, assume that there are 6 subjects, each taught by a single teacher:

• $E$nglish
• $G$erman
• $M$athematics
• $P$hysics
• $H$istory
• $D$ance
• So, are there 6 teachers who are a mix of foreign of Alghazi, or are there 6 foreign + 6 Alghazi teachers? – Phylyp Jan 18 '18 at 1:10
• I think we could do with more precision about what counts as asking a teacher "about their salary"... – Gareth McCaughan Jan 20 '18 at 2:48

It's not perfectly clear to me what's supposed to be allowed and what isn't. But perhaps the following is permitted under al'Alghazi law?

Take two teachers A and B, and a third party Z. Z picks a very large random number and tells it secretly to A. A adds her salary to that number and tells the result secretly to B. B subtracts her salary from that and tells the result secretly to Z.

Now

our third party doesn't know anything about either salary -- but does know the difference between them and which is larger. And the two teachers, provided Z doesn't tell them what he learned, learn nothing about one another's salaries. We can repeat this procedure for other pairs of teachers, and find out all the pairwise salary differences. Finally, Z can reveal the rank order, or the average difference between native and foreign salaries, or whatever.

This procedure

doesn't require any teacher to reveal her salary, but does require them to provide other people with some salary information. I don't know whether this is meant to be permitted or forbidden...

• I feel like this wouldn't be allowed under a broad interpretation of point one, but (rot13) V'z fher gung gur fbyhgvba vaibyirf n mreb xabjyrqtr cebbs – Jay Jan 18 '18 at 1:35