16th Chinese 2001 Problem B2 24 points are equally spaced on a circle so that the distance between any two adjacent points is 1. How many different ways can be choose 8 points so that the arc length between any two chosen points is not 3 or 8. Solution
: 258 Label the points 1 to 24 (with 1 and 24 adjacent). Consider the following arrangement: 1 9 17 4 12 20 7 15 23 10 18 2 13 21 5 16 24 8 19 3 11 22 6 14 The 8 rule is equivalent to the requirement that we can have at most one number from each row. The 3 rule is equivalent to the requirement that we cannot have two adjacent numbers from the same column (we consider the first and last rows as adjacent). There can be at most 4 numbers from the first column. Suppose there are 4. Then they must be 1, 7, 13, 19 or 4, 10, 16, 22. In either case, we can then choose freely from the second and third columns for the remaining 4 rows, because none of the remaining rows are adjacent. So this gives 2 x 2 4 = 32 possibilities. Suppose there are 3 numbers from the first column. There are 8 possibilities such as 1, 7, 13 and 8 possibilities such as 1, 7, 16. In each case the remaining rows form 3 groups of adjacent rows. For each group we have just two choices (because we have to alternate between the second and third columns for adjacent rows). Thus there are 16 x 2 3 = 128 possibilities. Suppose there are 2 numbers in the first column. There are 8 possibilities with a difference of 6 (such as 1, 7), another 8 with a difference of 9 (such as 1, 10), and 4 with a difference of 12 (1, 13 or 4, 16 or 7, 19 or 10, 22). In each case the other rows are divided into two groups of adjacent rows. So there are 20 x 2 2 = 80 possibilities. Suppose there is 1 number in the first column. There are 8 possibilities. The remaining rows are all adjacent, so we get 8 x 2 = 16 possibilities. Suppose there is no number in the first column. This gives 2 possibilities. Adding, we get a final total of 258 possibilities. 16th Chinese 2001 © John Scholes jscholes@kalva.demon.co.uk 5 June 2002