25
$\begingroup$

The idea for this puzzle came from my friend Jan. The puzzle is based on real world events from the Tokyo Olympics.

The Olympic rock climbing preliminary round has 20 climbers. Each climber competes in 3 separate events, where they rank from 1st to 20th. The final score of a climber is the product of their rankings from the 3 events, where lower is better. For example, if a climber finishes 5th, 3rd and 10th then their final score will be $5*3*10 = 150$.

What can be a climber's largest score that guarantees that they finish in the overall top 8 and qualify to the final?

$\endgroup$
12
  • 1
    $\begingroup$ I was watching the rock climbing last night and found the competition very interesting, especially the product scoring formula. The commentators said that the climbers will need to score about xxx overall to qualify to the final. At this point, my puzzling brain started thinking, what is that actual score required. $\endgroup$ Aug 4 at 7:41
  • 3
    $\begingroup$ How are ties resolved ? $\endgroup$
    – Evargalo
    Aug 5 at 10:13
  • 2
    $\begingroup$ @TylerH I think he was talking about tied scores. For example Alice might get 1rst, 2nd, and 3rd. Bob might get 2nd, 3rd, and 1st. Both have a score of 6 (1*2*3) $\endgroup$ Aug 5 at 14:45
  • 1
    $\begingroup$ @Evargalo Ah, in the case of a tie in positioning for final tallies, I believe they give the edge to whoever completed the categories (all 3 combined) in less time... but I'm not 100% sure on that. However, it's worth noting that the Olympics does do ties... meaning they sometimes hand out two gold medals and no silver, for example. For qualifying for a finals run, I could easily see them saying "OK, positions #10 and #11 tied in qualifying score, so we will have 11 competitors instead of 10". Hard to know for sure unless it actually happens. $\endgroup$
    – TylerH
    Aug 5 at 14:48
  • 3
    $\begingroup$ You might be interested in solving my puzzle :) $\endgroup$
    – zhoraster
    Aug 6 at 8:06
14
$\begingroup$

The number we want is

either 70 or 71, depending on exactly how we interpret the wording at the end of the question. If "What can be a climber's largest score ..." is intended to indicate that only actually possible scores are acceptable, then the answer is 70. If it's just a slightly flowery way of asking "what's the largest number such that ...", then the answer is 71. In fact, OP has clarified in comments that the first interpretation was intended, so the answer we need is 70.

EDITED to add: There is another question of interpretation here!

See Albert Lang's answer. If you take the question to mean "what is the largest score such that, if you get at most that score, you are guaranteed to qualify?", then (unless I have made some mistake I haven't yet noticed) this answer is correct. But if instead you take it to mean "what is the largest score such that, if you get exactly that score_, you are guaranteed to qualify?" then my reasoning is wrong, my answer is probably wrong, and Albert Lang's answer is probably right. (I haven't checked it.) In particular, Albert argues that if you get exactly 77 points then you can be sure that there were not as many as 8 people ahead of you; the key point is that if you get 77 then you must have come first in one event.

We want to know

what the best possible 9th-place score is. (Then the answer we want will be the largest actually-possible score below that, with the first interpretation of the question above; or the largest integer below it, with the second.)

I claim we can safely assume that

our 9 contestants place 1st to 9th in the three events, in some order. (If not, there's an event in which someone does worse than that and one of those top 9 places are taken by someone else. Assign that top-9 place to the "someone"; this will not increase any scores, so in particular it will not increase the 9th-smallest.)

Now

the product of all 9 contestants' rank-products is just (1x...x9)^3, so their geometric mean is (1x...x9)^(1/3) ~= 71.3, so the worst rank-product is at least 72. Perhaps we can achieve exactly this? Let's see. Three contestants could be 1,8,9 in some order for a rank-product of 72. Three could be 2,5,7 in some order for a rank-product of 70. The others will be 3,4,6 in some order for ... yes, 72 again. Win!

To be more explicit,

if nine contestants' places are 189, 891, 918, 257, 572, 725, 346, 463, 634, then the ninth-best of them scores 72; therefore a score of 72 is not low enough to guarantee 8th place or better; but the ninth-best score is (by the geometric-mean argument above) always at least 72, so a score of 71 is low enough to guarantee 8th place or better; so 71 is the number we're after. Except that with the first of the two interpretations of the question, we must note that a score of 71 isn't actually possible (it's prime, hence not a product of three numbers <= 20) but 70 is (as seen above).

Credit where due

to Stiv for pointing out in comments that the question can be interpreted so as to ask only for possible scores.

$\endgroup$
13
  • 3
    $\begingroup$ I like this argument, but that particular score wouldn't ever be mathematically achievable as a product of 3 numbers (it's prime) - so should the answer actually be one less than that, since that score can be achieved? $\endgroup$
    – Stiv
    Aug 4 at 9:02
  • 1
    $\begingroup$ OK, done. And since I see that one of the people preferring the "only actually possible scores" interpretation is the person who actually posted the question, I have given preference to the corresponding answer :-). Thanks @Stiv! $\endgroup$
    – Gareth McCaughan
    Aug 4 at 9:21
  • 1
    $\begingroup$ Maybe I misunderstand, but with contestants at 189, 891, 918, 257, 572, 725, 346, 463, 634, it seems there is a tie for 4th place of 6 contestants. Depending on the rock climbing rules this might still give contestant nine a place in the final $\endgroup$ Aug 4 at 9:52
  • 3
    $\begingroup$ I am not persuaded by your argument that it is safe to assume that the 9 contestants all place 1st to 9th in the three events. It is true that given a set of scores in which that is not the case, it is possible to find another set in which at least one of the top nine scores is lower and none is higher. But that does not imply that in a case where some competitor achieves the 8th-place score from the original set, there is a way to arrange the remaining scores so that eight other competitors all score better. $\endgroup$ Aug 4 at 18:43
  • 2
    $\begingroup$ It doesn't matter what the rule for breaking ties is, as long as the final is not expanded to include all that tied with eighth place. If you have nine contestants with three 70s and six 72s one of the 72s will be left out, so 72 does not guarantee a place in the final. $\endgroup$ Aug 5 at 0:18
13
$\begingroup$

Thanks to @Daniel Mathias for spotting an idiotic mistake in an earlier version of this.

The largest score that guarantees a place in the final is

78

To show off the principal argument without distraction by technical subtleties let us first demonstrate that number is at least

76

Indeed, this number can either come from rankings

19,1,4 or 19,2,2 In either case the product of rankings of the remaining best 8 is at least $8!^3\times9^2/4$ which averages out at about 77.7 per contestant. Not all of them can therefore score better than 76.

We can refine this argument to push the lower boundary to

78

This score can only be the result of rankings

1,6,13 or 2,3,13 The product of scores of the remaining best 8 is therefore at least $8!^3\times9^2/6$. With ranks no worse than 9th, the nearest possible scores below 78 are 75 and 72. As there are only 3 factors of 5 available, 75 can occur at most once. But we can check that $75\times72^7<8!^3\times9^2/6$. Therefore not all 8 can be better than 78. (And since 78 cannot be built from ranks maxing out at 9th at least one must, in fact, be worse.)

It remains to show that we cannot do better. The next possible scores are

80,81,84,85

As the first three can be built from small ranks (<10th) they can be ruled out by @Gareth's calculation.

This leaves the other case (not all small ranks) for

85 or larger. In that case we cannot guarantee a product of the best remaining 8 larger than $8!^3\times9^2/5$. These can always be distributed like 3x 7,4,3, 1x 9,9,1 2x 8,5,2 1x 6,6,2 1x 8,6,1 or better.

$\endgroup$
11
  • 5
    $\begingroup$ @DmitryKamenetsky There is no nice way of saying it: The other answer is incorrect. It overlooks the fact that we can sneak in one poor ranking and compensate by two very good rankings. By taking away these two good rankings it pushes the best other 8 scores up. $\endgroup$ Aug 4 at 11:09
  • 2
    $\begingroup$ @DmitryKamenetsky I guess it depends on whether "largest score that guarantees a top 8 place" is interpreted to mean "largest value such that any score of this value or lower guarantees a place" or "largest value such that a score of exactly this value guarantees a place". Gareth's answer is the former, this answer is the latter. $\endgroup$ Aug 4 at 11:21
  • 5
    $\begingroup$ Another subtlety is that it does not only depend on the score but also how it was achieved. For example: 72 = 3x4x6 does not guarantee the final but 72 = 2 x 2 x 18 does. $\endgroup$ Aug 4 at 11:29
  • 2
    $\begingroup$ That interpretation never occurred to me! But I agree it's entirely possible, and if it's what OP meant then indeed my answer is wrong (and probably this one is right, but I haven't checked). However, I disagree with Albert's first comment here: if my answer is wrong, it's because I misunderstood the question, not because my analysis of the question I thought I was answering was incorrect :-). Or, at least, nothing I've read so far indicates anything wrong in that analysis, given how I understood the question. $\endgroup$
    – Gareth McCaughan
    Aug 4 at 18:39
  • 3
    $\begingroup$ The next possible score is 78 = 1 x 6 x 13 = 2 x 3 x 13. You might want to investigate... :o) $\endgroup$ Aug 5 at 22:26
1
$\begingroup$

There is a third possible interpretation of the question - the largest possible score with particular subscores that guarantees the finals. This is the highest possible score that gets a candidate to the finals no matter how others arrange their scores. But it isn't just the score that guarantees the finals - subscores need to be just right.

As an example, subscores 2,2,20 with total score of 80 guarantees us the spot.

The first obvious observation - we assign some scores to our candidate. Then, 8 competitors want to be tied or ahead (to possibly cut candidate out of the finals), and we assign the lowest remaining numbers to those 8. It is obvious that there is no reason to pick any higher number - so picking numbers 1-9 is sufficient for these candidates.

To simplify some math, trivial observation is that you are interested in geometric mean instead of the final score. Final score is a cube of geometric mean of individual scores.

So, these mentioned subscores have a geomean of 4.31. Remaining subscores to be assigned (3x1-8 except 2, 2x9, 1x 2) have a geomean of 4.27. Uh oh, trouble. However, let's try to assign these scores to people. Obviously, we pair 1 with 8 and 9 twice, then pair last 1 with 8 and 7 - say 189, 918, 871. Now, the remaining scores have geomean of 4.41 = we are on the safe side because geometric mean of remaining scores is at least 85 and something, so not all can be ahead of our candidate.

Now, what is the highest possible score where that is possible?

We have 3 triplets - 189, 257, 346 with scores 72, 70, 72. We need to break them up somehow to squeeze in some higher number. There are two options - we remove 1 subscore 1-3 or we remove 2. (it is plainly obvious that removal of just say 2x 4 simply means one final triplet will be 336 and the other 346)

Let's first check the easier case:

Removal of one subscore. If we remove 2 digits from same triplet, we didn't do anything useful, so we need to remove from 2 different triplets. But if we say removed 3 and 5, one of that 5 is replaced by 4 present in 346 triplet we eliminated. There are 2 reasonable cases - 24x and 1 + 5-7.

Let's check that out

Removal of 7 is trivial, replace with 8 for score 80, so we are at best matching already achieved score. Removal of 6 requires 347 (and 258) with score 84. But 1,6,13 is 78 and 1,6,14 is same 84, so this doesn't work. Finally, removal of 5 offers scores of either 80 and 85 and it is easy to arrange for score 84 (189x2, 258, 257, 266, 346, 347x2).

So,

What remains are possibilities 23x, 24x and 33x. 24x is not going to work, it is possible to get 8 scores under or equal to 84, so 88 is out of the question while 80 has been achieved already. 23x offers 84, but other combinations 189 x3 + 267 x2 + 355 + 445 + 346 sink the option. Finally, 339 offers score 81. To remove 1s, we use 189 x3, for removal of 2 we take 257 x2 and 266 and we are left with 3, 3x4, 5, 6; which we arrange to 346, 445, which score 72 and 80. So, 339 is also impossible.

Therefore, the first 2,2,20 is the highest score of 80 that guarantees the spot in the finals. (there might be other combinations with the same score that also guarantee spot in the finals - but it is easy to see that 445 does not - 189x3, 266, 257x2, 346, 337 are all lower)

$\endgroup$
2
  • $\begingroup$ What about 2*3*13 = 78? $\endgroup$ Aug 5 at 14:28
  • $\begingroup$ I haven't checked whether it works, because it is lower than 80 - so it can't be the top score. $\endgroup$ Aug 5 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.