HMMT 二月 2012 · TEAM1 赛 · 第 10 题

英文解析

10. [ 40 ] For positive odd integer n , let f ( n ) denote the number of matrices A satisfying the followingconditions:
    • A is n × n .
    • Each row and column contains each of 1 , 2 , . . . , n exactly once in some order.
    • A = A . (That is, the element in row i and column j is equal to the one in row j and column i ,Tfor all 1 ≤ i, j ≤ n .)
    n !( n − 1)!
    Prove that f ( n ) ≥ .
    ϕ ( n )
    Answer: see below We first note that main diagonal (the squares with row number equal tocolumn number) is a permutation of 1 , 2 , . . . , n . This is because each number i (1 ≤ i ≤ n ) appearsan even number of times off the main diagonal, so must appear an odd number of times on the maindiagonal. Thus, we may assume that the main diagonal’s values are 1 , 2 , . . . , n in that order. Call anymatrix satifsying this condition and the problem conditions good . Let g ( n ) denote the number of good
    ( n − 1)!
    matrices. It now remains to show that g ( n ) ≥ .
    ϕ ( n )
    Now, consider a round-robin tournament with n teams, labeled from 1 through n , with the matchesspread over n days such that on day i , all teams except team i play exactly one match (so there aren − 1
    pairings), and at the end of n days, each pair of teams has played exactly once. We consider twosuch tournaments distinct if there is some pairing of teams i, j which occurs on different days in the 2
    tournaments. We claim that the tournaments are in bijection with the good matrices.
    Proof of Claim: Given any good matrix A , we construct a tournament by making day k have matchesbetween team i and j for each i, j such that A = k , besides ( i, j ) = ( k, k ). Every pair will play somei,jday, and since each column and row contains exactly one value of each number, no team will playmore than once a day. Furthermore, given two distinct good matrices, there exists a value (off themain diagonal) on which they differ; this value corresponds to the same pair playing on different dates,
    so the corresponding tournaments must be distinct. For the other direction, take any tournament.
    Make a matrix A with the main diagonal as 1 , 2 , . . . , n , and for each k , set A = k for each i, j suchi,jthat teams i, j play each other on day k . This gives a good matrix. Similarly, given any two distincttournaments, there exists a team pair i, j which play each other on different days; this corresponds to a differing value on the corresponding good matrices.
    ( n − 1)!
    It now suffices to exhibit distinct tournaments. (It may be helpful here to think of the days inϕ ( n )
    the tournament as an unordered collection of sets of pairings, with the order implictly imposed by theteam not present in the set of pairings.) For our construction, consider a regular n -gon with center
    O . Label the points as A , A , . . . , A as an arbitrary permutation (so there are n ! possible labelings).
    1 2 n
    The team k will be represented by A . For each k , consider the line A O . The remaining n − 1 verticesk kn − 1
    can be paired into groups which are perpendicular to this line; use these pairings for day k . Ofcourse, this doesn’t generate n ! distinct tournaments– but how many does it make?2
    Consider any permutation of labels. Starting from an arbitrary point, let the points of the polygonbe A , A , . . . , A in clockwise order. Letting π (0) = π ( n ) and π ( n + 1) = π (1), we note thatπ (1) π (2) π ( n )
    π ( i − 1) and π ( i + 1) play each other on day π ( i ). We then see that any other permutation of labelsrepresenting the same tournament must have A A = A A for all i . Thus, if A isπ ( i − 1) π ( i ) π ( i ) π ( i +1) π (1)
    k vertices clockwise of A , then A is k vertices clockwise of A , and so on all the way upπ (0) π (2) π (1)
    to A being k vertices clockwise of A . This is only possible if k is relatively prime to n ,soπ ( n − 1) π ( n )
    there are ϕ ( n ) choices of k . There are n choices of the place to put A , giving nϕ ( n ) choices ofπ (1)
    permutations meeting this condition. It is clear that each permutation meeting this condition providesthe same tournament, so the n ! permutations can be partitioned into equivalence classes of size nϕ ( n )
    n !
    each. Thus, there are distinct equivalence classes, and we are done.
    nϕ ( n )
    Team A