Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # 5th round (5x5x5x5x5)
- If we split the 25 hourses into groups of 5 and have each group race among themselves,
- we'd be able to establish the ranking inside each group:
- ```
- group: 1 2 3 4 5
- 1st finisher: a b c d e
- 2nd finisher: f g h i j
- 3rd finisher: k l m n o
- 4th finisher: p q r s t
- 5th finisher: u v w x y
- ```
- With this we can elimite the 4th and 5th placers from each group because it is obvious
- that there are atleast 3 horses faster than them.
- Eliminated: `p q r s t u v w x y` (10 horses, 15 left)
- Note that we cannot eliminate _across_ groups because we do not have ordering information
- about horses _between_ groups just yet. So the 5th placer in one group might actually be
- faster than the 1st placer in another group.
- # 6th round
- Now that we have intra-group ordering information, the next step is trying to establish
- inter-group ordering. So we have the 1st placers from each group race each other. We use
- the 1st placer because they provide the highest number of eliminations (since there are
- atleast 2 horses that are slower than them.)
- ```
- Race: a b c d e
- a1 b2 c3 d4 e5
- f g h i j
- k l m n o
- ```
- Assuming finishing placements as tagged above, we can eliminate 9 more horses which
- have evidence that there are atleast 3 horses faster than them:
- Eliminated:
- * `d`, `e`, `i`, `j`, `n` and `o` - because the fastest in their group is just eliminated.
- * `h` and `m` - because they are slower than `c` and thus slower than `b` and `a` as well.
- * `l` - because he is slower than `g` and thus slower than `b` and `a`
- # 7th round
- With the previous round we are left with 6 horses:
- ```
- a b c
- f g
- k
- ```
- Summarizing what we know so far:
- * `a` > `f` > `k`
- * `b` > `g`
- * `a` > `b` > `c`
- * thus `a` > [`b`, `c`, `f`, `g`, `k`]
- Now from the above we can infer that `a` is definitely the fastest horse. And we are left
- with exactly 5 horse with partial ordering information so we just need one more race to
- determine the 2nd and 3rd placers.
- So assuming the resulting placement is `b` > `c` > `f` > `g` > `k`, we now have all
- information necessary to determine the 3 fastest horse:
- * **`a` > `b` > `c`** > `f` > `g` > `k`
- And we are done.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement