HMMT 十一月 2015 · THM 赛 · 第 7 题

英文解析

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 otherwords, f (1) , f (2) , . . . , f (7) are each (not necessarily distinct) integers from 1 to 7. In the top row ofthe grid, the numbers from 1 to 7 are written in order; in every other square, f ( x ) is written where x isthe number above the square. How many functions have the property that the bottom row is identicalto 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 andonly if f ( i ) = j . Since the bottom row is equivalent to the top one, we have f ( x ) = x . Therefore, the 6
   graph must decompose into cycles of length 6, 3, 2, or 1. Furthermore, since no other row is equivalentto 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 assignwhich vertices will belong to which cycle (we divide by two to avoid double-counting the cycles of 2
   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 .