Rock and weight level weight problem?

Question

Given 5 rocks of different weight and level scales in 7 tests determine the order the rock by weight.

So I have 5 rock that is 120 possible ways of ordering them. The rock are named

(A,B,C,D,E)

So my first step is

$A<B$ then I do $ C<D $ and I then I do

$ C<A$

This gives me the following 3 permuations CABD CADB CDAB Now I add the letter E to get 15 permutations

ECABD CEABD CAEBD CABED CABDE

ECABD CEABD CAEDB CADEB CADBE

ECDAB CEDAB CDEAB CDAEB CDAEB

But I am not sure what compare next in order to get 7 tests?

Answer 1

Hint: 7 comparisons give you 7 bits of information (128 different values), this is enough to cover the 5! = 120 different permutations of the 5 rocks. They key is to find a set of comparisons such the the 7 binary results are distinct for each distinct permuation.

Answer 2

First we measure $A > B$ and $C > D$. Next we measure the two heavier ones and determine that $A > C$. This conveniently leaves us with only $3$ arrangements for the stones $A$, $B$, $C$ and $D$. Namely: $ABCD$, $ACBD$ and $ACDB$.

Note that stone $C$ is nicely in the middle, either as no. $2$ or no. $3$. Therefore we measure stone $E$ versus $C$. If $E$ is found to be the heavier one, then we measure it versus $A$. If $E$ is the lighter one, we measure it versus stone $D$.

This measurement schedule can lead to four different results.

$(1)$ $E > C$ and $E > A$. This leaves us with three possibilities: $EABCD$, $EACBD$, $EACDB$. We can easily resolve this in the two remaining measurements, for example by measuring $B$ versus $C$ in measurement $6$. If $C > B$ then we measure $B$ versus $D$ on the last turn.

$(2)$ $E > C$ and $A > E$. This leaves us with four possibilities: $AEBCD$, $ABECD$, $AECBD$, $AECDB$. We observe that in $2$ out of $4$ possibilities $B > C$. So the critical sixth measurement is stone $B$ versus $C$. The seventh measurement is then trivial.

$(3)$ $C > E$ and $E > D$. This leaves us with four possibilities: $ABCED$, $ACEBD$, $ACBED$, $ACEDB$. We see that in $2$ out of $4$ possibilities $B > E$. Therefore the sixth measurement must be stone $B$ versus $E$. The seventh measurement is easy.

$(4)$ $C > E$ and $D > E$. Once again we are left with four possibilities: $ABCDE$, $ACBDE$, $ACDEB$, $ACDBE$. In $2$ out of $4$ possibilities we see that $B > D$, hence as sixth measurement we take $B$ versus $D$. Once again the last measurement is straightforward.