HMMT 二月 2018 · 团队赛 · 第 3 题
HMMT February 2018 — Team Round — Problem 3
题目详情
- [ 30 ] Michelle has a word with 2 letters, where a word can consist of letters from any alphabet. Michelle k performs a switcheroo on the word as follows: for each k = 0 , 1 , . . . , n − 1, she switches the first 2 k letters of the word with the next 2 letters of the word. For example, for n = 3, Michelle changes ABCDEF GH → BACDEF GH → CDBAEF GH → EF GHCDBA in one switcheroo. In terms of n , what is the minimum positive integer m such that after Michelle performs the switcheroo n operation m times on any word of length 2 , she will receive her original word?
解析
- [ 30 ] Michelle has a word with 2 letters, where a word can consist of letters from any alphabet. Michelle k performs a switcheroo on the word as follows: for each k = 0 , 1 , . . . , n − 1, she switches the first 2 k letters of the word with the next 2 letters of the word. For example, for n = 3, Michelle changes ABCDEF GH → BACDEF GH → CDBAEF GH → EF GHCDBA in one switcheroo. In terms of n , what is the minimum positive integer m such that after Michelle performs the switcheroo n operation m times on any word of length 2 , she will receive her original word? Proposed by: Mehtaab Sawhney n Let m ( n ) denote the number of switcheroos needed to take a word of length 2 back to itself. Consider n a word of length 2 for some n > 1 . After 2 switcheroos, one has separately performed a switcheroo on the first half of the word and on the second half of the word, while returning the (jumbled) first half of the word to the beginning and the (jumbled) second half of the word to the end. After 2 · m ( n − 1) switcheroos, one has performed a switcheroo on each half of the word m ( n − 1) times while returning the halves to their proper order. Therefore, the word is in its proper order. However, it is never in its proper order before this, either because the second half precedes the first half (i.e. after an odd number of switcheroos) or because the halves are still jumbled (because each half has had fewer than m ( n − 1) switcheroos performed on it). It follows that m ( n ) = 2 m ( n − 1) for all n > 1 . We can easily see that m (1) = 2 , and a straightforward n proof by induction shows that m = 2 .