Browse · MathNet
PrintIRL_ABooklet
Ireland counting and probability
Problem
Let be an odd number and an integer such that . In a sports tournament, players take part in a series of contests. Each contest involves players, and the scores obtained by the players are the numbers in some order. Each possible subset of players takes part together in exactly one contest. Let the final score of player be , for each . Define to be the smallest difference between the final scores of two players, i.e., Determine, with proof, the maximum possible value of .
Solution
First, note that each player will participate in contests. Therefore, the minimum possible score of any player is and the maximum possible score of any player is . Thus the score of each player lies in the range This range contains numbers in arithmetic progression (with common difference ), and this arithmetic progression includes the maximum and minimum values of the range. It follows immediately that the largest value of is given by , if there is an arrangement of contests that can achieve this value.
Next we show that this set of scores is indeed achievable. Here we note that changing the scores to does not change the problem, since it is only the difference between the scores that matters. Consider the case where the scores of the players are in the same order as their labels in , i.e., if players participate in a contest, where , then player obtains score for every . To finish the proof, we need only prove that in this case for every . To prove this, observe that there are exactly contests that involve both players. In each of these contests, player scores one more point than player ; this contributes a total of to the value of . The remaining contribution from contests that involve only one of the players and is equal to zero; this can be explained as follows.
Consider any set of players of size that does not include or ; the contest that involves player and the players in can be paired with the contest that involves player and the players in ; in these two contests, players and have the same ranking and therefore both players achieve the same score. Considering all possible subsets , we find that the contribution from these contests to is equal to zero.
Thus it is indeed possible to have a set of scores where neighbouring scores are separated by , and this completes the proof.
---
Alternative solution.
Same as Solution 1, except that the proof of for every proceeds as follows. Consider the final score of any player . How many times does a score of occur? Each score of arises from choosing as competitors players from the players with a lower ranking than player , and players from the players with a higher ranking than player . Thus, for any and so It follows that Note that here binomial coefficients of the form where are equal to zero. Also, in the third line we have used the fact that , which is valid even when . Also, in the final line we have used the observation that the expression in the penultimate line is counting the number of subsets of size of a set of size , by partitioning according to the number of elements that are chosen from the first elements of .
Next we show that this set of scores is indeed achievable. Here we note that changing the scores to does not change the problem, since it is only the difference between the scores that matters. Consider the case where the scores of the players are in the same order as their labels in , i.e., if players participate in a contest, where , then player obtains score for every . To finish the proof, we need only prove that in this case for every . To prove this, observe that there are exactly contests that involve both players. In each of these contests, player scores one more point than player ; this contributes a total of to the value of . The remaining contribution from contests that involve only one of the players and is equal to zero; this can be explained as follows.
Consider any set of players of size that does not include or ; the contest that involves player and the players in can be paired with the contest that involves player and the players in ; in these two contests, players and have the same ranking and therefore both players achieve the same score. Considering all possible subsets , we find that the contribution from these contests to is equal to zero.
Thus it is indeed possible to have a set of scores where neighbouring scores are separated by , and this completes the proof.
---
Alternative solution.
Same as Solution 1, except that the proof of for every proceeds as follows. Consider the final score of any player . How many times does a score of occur? Each score of arises from choosing as competitors players from the players with a lower ranking than player , and players from the players with a higher ranking than player . Thus, for any and so It follows that Note that here binomial coefficients of the form where are equal to zero. Also, in the third line we have used the fact that , which is valid even when . Also, in the final line we have used the observation that the expression in the penultimate line is counting the number of subsets of size of a set of size , by partitioning according to the number of elements that are chosen from the first elements of .
Final answer
binom(n-2, 2r-1)
Techniques
Counting two waysAlgebraic properties of binomial coefficients