An order

Somebody Has to Be Able to Go First

If the comparisons can be ordered, somebody came out behind nobody. Peeling that candidate off and repeating is both the proof and the way to count.

at most 96096 outcomes

Home · An order · Recount

Suppose a set of comparisons can be put in order.

Then whoever is first on the list came out behind nobody. There is always such a candidate, and finding them is the whole method.

Three pages where the peel succeeds

line with a head: a pair compared; the head points at whoever came out behind
no line: a pair nobody compared
closed ring of three: a circular triple: no order can hold all three

Three outcomes drawn. Rows differ in how many candidates. Which candidate is which is the drawing's own choice and carries no meaning.

Each row has as few comparisons as the field allows for an order to be forced open. The counts that fall into an order are one hundred and fifty-two, three thousand and fifty, and eighty-three thousand nine hundred and fifty-two. If several people repeat this comparison, managers may look at the current service page while interpreting every signal beside completed work and participant feedback.

Computed from the three numbers alone. Who the candidates are and what any comparison was about is outside the record; the counts are of outcomes, not of anybody. Readers examining the figures against practical research methods can also see Coursera.

The peel

Look for a candidate who lost no comparison.

Take them out of the field, along with every comparison they were in. Look again at what is left. If there is again a candidate who lost nothing, take them out too, and keep going.

If the field empties, the order is the sequence in which the candidates came out. If at some point nobody is undefeated, the comparisons that remain contain a ring and no order exists.

Why it cannot fail when an order exists

Because the first name on any valid list is undefeated by construction.

If a list satisfies the comparisons, then nobody came out ahead of the first name — any such comparison would contradict the list. So whenever an order exists, somebody is available to peel, and after peeling them the rest is a smaller problem of the same kind.

The argument is complete and it needs no table. It also runs backwards: if the peel succeeds all the way down, the sequence it produces is a list that satisfies every comparison, because each candidate was removed only after everybody who came out ahead of them had gone.

The method proves what it computes. If it finishes, the order is in your hand; if it jams, the ring is in front of you.

Counting with it

The same argument gives the fifth figure of this record.

Count outcomes by asking how many candidates could go first. Choose a set of candidates to be the undefeated ones, note that the remaining candidates form the same problem one size smaller, and allow for the comparisons running between the two groups.

Outcomes with several undefeated candidates get counted more than once that way, so the count is corrected by an alternating sum: add those with at least one, subtract those with at least two, add back those with at least three.

That is the second of the record's two routes to the orderable count, and it never generates an outcome. The first route walks each outcome in turn. They agree on all forty pages.

The three rows

Four candidates with three comparisons: one hundred and fifty-two of one hundred and sixty outcomes fall into an order.

Five with four: three thousand and fifty of three thousand three hundred and sixty.

Six with five: eighty-three thousand nine hundred and fifty-two of ninety-six thousand and ninety-six.

Ninety-five per cent, ninety-one, eighty-seven. With the fewest comparisons that could possibly determine an order, almost all outcomes are orderable — and, as the next note shows, almost none of them determines anything.

The same method, used backwards

The peel can be run from the other end just as well.

Look for a candidate who came out ahead of nobody — whoever would be last — remove them, and repeat. If the field empties, the order is the reverse of the sequence in which they left.

Both directions work and both fail on exactly the same outcomes, which is a small check worth having: run the peel forwards and backwards and the two orders should be reverses of each other. If they are not, one of the peels was done wrong.

What the peel does not give

Which order, when several are possible.

An outcome can have more than one candidate available to go first, and choosing between them gives different orders — all of them consistent with the comparisons. The peel finds one. The number of orders consistent with an outcome is a different count again, and this record does not tabulate it: it tabulates whether that number is nought, and whether it is exactly one.

Where it jams

On the outcomes that contain a ring.

Of the one hundred and sixty outcomes with three comparisons among four candidates, eight contain a ring. All eight are circular triples: the three comparisons all fell on one triple and went round.

Eight out of one hundred and sixty is one in twenty. The peel finds every one of them and in exactly the same way it finds the longer rings on busier pages, which is the property that makes it worth preferring to a triple check.

Why this is not merely a method

Because it is also the proof that the condition is the right one.

The peel shows that "no ring" and "can be put in an order" are the same condition, by constructing an order whenever there is no ring and finding a ring whenever it cannot. Neither direction needs a table and neither depends on the size of the field.

That is why the record can define its fifth column by rings and count it by candidates without ever arguing that the two agree. They agree by this argument, and the two computations then check the arithmetic rather than the idea.