Round 3:
1 3
2 4
5 7
6 8
…

Round 4:
3 5
4 6
7 9
8 10
…
[/spoiler]

The last question you ask is interesting, it’s like sorting algorithms where all the comparisons need to be specified ahead of time: Sorting Networks.

But I think it has a rather different answer… [spoiler]
You need to compare every possible pair of coins.

If there are any two coins A and B which are not compared with each other, then suppose all other coins (call them “class C coins”) are equal to each other but unequal to A or B. In this case you cannot know whether A and B are the same or not.
[/spoiler]
Would it help if you are told there is at least one of each type of coin?

The problem statement refers to “passes”, for which certain properties are listed (sounding like clarifications rather than an exhaustive list of properties). A very natural unlisted property for a pass would be that the comparisons in a pass are essentially simultaneous, so in particular you cannot use results from the “first part” of a pass to decide what coins to compare “later” in that same pass.  This property is natural if you think of a pass as being done in one step on a parallel computer, and of course you want to minimize the number of passes because comparisons take a long time and you want to minimize the time of the parallel algorithm.  Indeed, without this property, it seems much less natural to want to try to minimize the number of passes.  (Do you have a data structure that decays each time it gets compared?)

(If I were to ask this question in an interview, and the applicant used this loophole, I would ask them for an example of when their interpretation could be relevant!)

In any event, Stephen’s nice and tight analysis prompts the non-loophole version of the same question:

How many parallel passes does it take to separate all the coins by type into three piles?

I don’t see the objection.  Could you provide specifics?  Perhaps lay out the five coins in order assuming you match from left to right.  For instance, one combination is:

GGSSG which has the two matches.  You’d match the first two and retain.  You’d match the second two and retain.  And you always retain the odds.  So you have a majority of gold.

To finish the algorithm, you’d then match pair one (GG) to pair two (SS) and they don’t match so you’d discard them.  At this point, you have one coin and you know it is gold because in removing you removed at least as many non-gold as gold and you started witha  gold majority.

I know this doesn’t necessarily ansswer your objection as you may have a different ordering in mind.  Show us how.

In the worst case, I believe you need n-1 comparisons (for n elements).

You could also do the standard probabilistic approach:
1. Pick C random coins (with replacement).
2. Find the majority among them.
3. Output that as the answer.

Unfortunately if you have just slightly more than half of one type and just slightly less than half of the other, this doesn’t work so well. But if you know that there is a fixed proportion of the gold coins (e.g., 50.01%) then you only need to make a *constant* number of comparisons.