Advertisement
Guest User

Untitled

a guest
May 28th, 2015
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.12 KB | None | 0 0
  1. # 5th round (5x5x5x5x5)
  2.  
  3. If we split the 25 hourses into groups of 5 and have each group race among themselves,
  4. we'd be able to establish the ranking inside each group:
  5.  
  6. ```
  7. group: 1 2 3 4 5
  8. 1st finisher: a b c d e
  9. 2nd finisher: f g h i j
  10. 3rd finisher: k l m n o
  11. 4th finisher: p q r s t
  12. 5th finisher: u v w x y
  13. ```
  14.  
  15. With this we can elimite the 4th and 5th placers from each group because it is obvious
  16. that there are atleast 3 horses faster than them.
  17.  
  18. Eliminated: `p q r s t u v w x y` (10 horses, 15 left)
  19.  
  20. Note that we cannot eliminate _across_ groups because we do not have ordering information
  21. about horses _between_ groups just yet. So the 5th placer in one group might actually be
  22. faster than the 1st placer in another group.
  23.  
  24. # 6th round
  25.  
  26. Now that we have intra-group ordering information, the next step is trying to establish
  27. inter-group ordering. So we have the 1st placers from each group race each other. We use
  28. the 1st placer because they provide the highest number of eliminations (since there are
  29. atleast 2 horses that are slower than them.)
  30.  
  31. ```
  32. Race: a b c d e
  33.  
  34. a1 b2 c3 d4 e5
  35. f g h i j
  36. k l m n o
  37. ```
  38.  
  39. Assuming finishing placements as tagged above, we can eliminate 9 more horses which
  40. have evidence that there are atleast 3 horses faster than them:
  41.  
  42. Eliminated:
  43.  
  44. * `d`, `e`, `i`, `j`, `n` and `o` - because the fastest in their group is just eliminated.
  45. * `h` and `m` - because they are slower than `c` and thus slower than `b` and `a` as well.
  46. * `l` - because he is slower than `g` and thus slower than `b` and `a`
  47.  
  48. # 7th round
  49.  
  50. With the previous round we are left with 6 horses:
  51.  
  52. ```
  53. a b c
  54. f g
  55. k
  56. ```
  57.  
  58. Summarizing what we know so far:
  59.  
  60. * `a` > `f` > `k`
  61. * `b` > `g`
  62. * `a` > `b` > `c`
  63. * thus `a` > [`b`, `c`, `f`, `g`, `k`]
  64.  
  65. Now from the above we can infer that `a` is definitely the fastest horse. And we are left
  66. with exactly 5 horse with partial ordering information so we just need one more race to
  67. determine the 2nd and 3rd placers.
  68.  
  69. So assuming the resulting placement is `b` > `c` > `f` > `g` > `k`, we now have all
  70. information necessary to determine the 3 fastest horse:
  71.  
  72. * **`a` > `b` > `c`** > `f` > `g` > `k`
  73.  
  74. And we are done.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement