2nd ASU 1968 Problem 15 9 judges each award 20 competitors a rank from 1 to 20. The competitor's score is the sum of the ranks from the 9 judges, and the winner is the competitor with the lowest score. For each competitor the difference between the highest and lowest ranking (from different judges) is at most 3. What is the highest score the winner could have obtained? Solution
: 24. At most 4 competitors can receive a rank 1. For a competitor with a rank 1 can only receive ranks 1, 2, 3 or 4. There are only 36 such ranks available and each competitor with a rank 1 needs 9 of them. If only one competitor receives a rank 1, then his score is 9. If only 2 competitors receive a rank 1, then one of them must receive at least five rank 1s. His maximum score is then 5.1 + 4.4 = 21. If 4 competitors receive a rank 1, then they must use all the 36 ranks 1, 2, 3, and 4. The total score available is thus 9(1 + 2 + 3 + 4) = 90, so at least one competitor must receive 22 or less. Thus the winner's maximum score is at most 22. If 3 competitors receive a rank 1, then the winner's score is maximised by giving all three competitors the same score and letting them share the 27 ranks 1, 3 and 4. That gives a winner's score of 9(1 + 3 + 4)/3 = 24. That can be achieved in several ways, for example: each competitor gets 3 1s, 3 3s and 3 4s, or one competitor gets 4 1s and 5 4s, another gets 3 1s, 3 3s and 3 4s, another gets 2 1s 6 3s and one 4. Note that it is trivial to arrange ranks for the remaining 17 competitors. For example: give one 5 2s and 4 5s total 30, one 4 2s and 5 5s total 33, and then one 9 6s, one 9 7s and so on. Thus the answer is 24, with three joint winners. If there is required to be a single winner, then the answer is 23. 2nd ASU 1968 © John Scholes jscholes@kalva.demon.co.uk 12 Nov 1998