HMMT 十一月 2015 · THM 赛 · 第 7 题
HMMT November 2015 — THM Round — Problem 7
题目详情
- Consider a 7 × 7 grid of squares. Let f : { 1 , 2 , 3 , 4 , 5 , 6 , 7 } → { 1 , 2 , 3 , 4 , 5 , 6 , 7 } be a function; in other words, f (1) , f (2) , . . . , f (7) are each (not necessarily distinct) integers from 1 to 7. In the top row of the grid, the numbers from 1 to 7 are written in order; in every other square, f ( x ) is written where x is the number above the square. How many functions have the property that the bottom row is identical to the top row, and no other row is identical to the top row?
解析
- Consider a 7 × 7 grid of squares. Let f : { 1 , 2 , 3 , 4 , 5 , 6 , 7 } → { 1 , 2 , 3 , 4 , 5 , 6 , 7 } be a function; in other words, f (1) , f (2) , . . . , f (7) are each (not necessarily distinct) integers from 1 to 7. In the top row of the grid, the numbers from 1 to 7 are written in order; in every other square, f ( x ) is written where x is the number above the square. How many functions have the property that the bottom row is identical to the top row, and no other row is identical to the top row? Proposed by: Alexander Katz Answer: 1470 Consider the directed graph with 1 , 2 , 3 , 4 , 5 , 6 , 7 as vertices, and there is an edge from i to j if and 6 only if f ( i ) = j . Since the bottom row is equivalent to the top one, we have f ( x ) = x . Therefore, the graph must decompose into cycles of length 6, 3, 2, or 1. Furthermore, since no other row is equivalent to the top one, the least common multiple of the cycle lengths must be 6. The only partitions of 7 satisfying these constraints are 7 = 6 + 1 , 7 = 3 + 2 + 2, and 7 = 3 + 2 + 1 + 1. If we have a cycle of length 6 and a cycle of length 1, there are 7 ways to choose which six vertices will be in the cycle of length 6, and there are 5! = 120 ways to determine the values of f within this cycle (to see this, pick an arbitrary vertex in the cycle: the edge from it can connect to any of the remaining 5 vertices, which can connect to any of the remaining 4 vertices, etc.). Hence, there are 7 · 120 = 840 possible functions f in this case. 7 5 ( )( ) 2 2 If we have a cycle of length 3 and two cycles of length 2, there are = 105 possible ways to assign 2 which vertices will belong to which cycle (we divide by two to avoid double-counting the cycles of length 2). As before, there are 2! · 1! · 1! = 2 assignments of f within the cycles, so there are a total of 210 possible functions f in this case. Finally, if we have a cycle of length 3, a cycle of length 2, and two cycles of length 1, there are ( )( ) 7 4 = 210 possible ways to assign the cycles, and 2! · 1! · 0! · 0! = 2 ways to arrange the edges within 3 2 the cycles, so there are a total of 420 possible functions f in this case. Hence, there are a total of 840 + 210 + 420 = 1470 possible f .