返回题库

HMMT 二月 2017 · 冲刺赛 · 第 29 题

HMMT February 2017 — Guts Round — Problem 29

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 17 ] Yang has the sequence of integers 1 , 2 , . . . , 2017. He makes 2016 swaps in order, where a swapchanges the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . Howmany different sequences of swaps can Yang do to achieve his goal?
解析

英文解析

  1. [ 17 ] Yang has the sequence of integers 1 , 2 , . . . , 2017. He makes 2016 swaps in order, where a swapchanges the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . Howmany different sequences of swaps can Yang do to achieve his goal?
    Proposed by: Yang Liu
    2015
    Answer: 2017
    Let n = 2017 . The problem is asking to write a cycle permutation of n integers as the product of n − 1
    transpositions. Say that the transpositions Yang uses are ( a , b ) (i.e. swapping the a -th integer ini i ithe sequence with the b -th integer in the sequence). Draw the graph with edges ( a , b ). One cani i ishow that the result is a cycle if and only if the resulting graph is acyclic, so it must be a tree. Theren − 2
    are n trees by Cayley’s formula, and for each tree, it can be made in ( n − 1)! ways (any orderingn − 2
    of the edges). So the total number of ways to end with a cycle is n · ( n − 1)! . By symmetry, eachcycle can be made in the same number of ways, so in particular the cycle 2 , 3 , . . . , n, 1 can be made inn − 2
    n · ( n − 1)!
    n − 2 = n ways.
    ( n − 1)!