PUMaC 2013 · 组合（A 组） · 第 8 题
PUMaC 2013 — Combinatorics (Division A) — Problem 8
题目详情
- [ 8 ] Eight all different sushis are placed evenly on the edge of a round table, whose surface can rotate around the center. Eight people also evenly sit around the table, each with one sushi in front. Each person has one favorite sushi among these eight, and they are all distinct. They find that no matter how they rotate the table, there are never more than three people who have their favorite sushis in front of them simultaneously. By this requirement, how many different possible arrangements of the eight sushis are there? Two arrangements that differ by a rotation are considered the same. 1
解析
- [ 8 ] Eight all different sushis are placed evenly on the edge of a round table, whose surface can rotate around the center. Eight people also evenly sit around the table, each with one sushi in front. Each person has one favorite sushi among these eight, and they are all distinct. They find that no matter how they rotate the table, there are never more than three people who have their favorite sushis in front of them simultaneously. By this requirement, how many different possible arrangements of the eight sushis are there? Two arrangements that differ by a rotation are considered the same. 8! Solution Under rotation, there are totally different arrangements. We find the answer by 8 subtracting the cases where more than 3 people can match their favorite sushi by rotation. Take an example of the case where maximum exactly 4 people can match their favorite sushi by some rotation. (Cases of more than 4 people are even simpler.) Suppose we have already rotated the table to the optimal position, when 4 people get matched. ( ) 8 There are ways of choosing these 4 people. The other 4 people must be all mismatched at 4 this moment. This is the number of “Error Permutation” and can be calculated with recursive relation f ( n ) = ( n − 1)( f ( n − 1) + f ( n − 2)), or simply by enumeration. It turns out to be 9. But some arrangements are counted twice. These are the cases when the mismatched 4 people can all get matched by another rotation. If we number the sushis from 1 to 8 by the order of positions around the table, suppose 4 people are matched to their favorite sushi at one moment, and ( a, b, c, d ) ( a < b < c < d ) are the ones that are mismatched. If under some rotation, all of ( a, b, c, d ) get matched, then originally the favorite sushi of the people in front of ( a, b, c, d ) must be ( b, c, d, a ), ( c, d, a, b ) or ( d, a, b, c ). So either ( b − a ) ≡ ( c − b ) ≡ ( d − c ) ≡ ( a − d ) (mod 8) or ( b − a ) ≡ ( d − c ) (mod 8) ( c − b ) ≡ ( a − d ) (mod 8) ( b − a ) 6 ≡ ( c − b ) (mod 8) In the first case, ( a, b, c, d ) = (1 , 3 , 5 , 7) or (2 , 4 , 6 , 8), and 3 arrangements are counted twice. In the second case, ( a, b, c, d ) = (1 , 2 , 5 , 6) or (2 , 3 , 6 , 7) or (3 , 4 , 7 , 8) or (1 , 4 , 5 , 8), and 2 ar- rangements are counted twice. So in total there are 5 extra counts. The answer is ( ) ( ) ( ) ( ) 8! 8 8 8 8 − − − × 2 − × 9 + 5 = 4274 8 8 6 5 4 3