返回题库

HMMT 二月 2018 · 团队赛 · 第 3 题

HMMT February 2018 — Team Round — Problem 3

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

题目详情

英文原题

  1. [ 30 ] Michelle has a word with 2 letters, where a word can consist of letters from any alphabet. Michellekperforms a switcheroo on the word as follows: for each k = 0 , 1 , . . . , n − 1, she switches the first 2
    letters of the word with the next 2 letters of the word. For example, for n = 3, Michelle changesk
    ABCDEF GH → BACDEF GH → CDBAEF GH → EF GHCDBAin one switcheroo.
    In terms of n , what is the minimum positive integer m such that after Michelle performs the switcheroonoperation m times on any word of length 2 , she will receive her original word?
解析

英文解析

  1. [ 30 ] Michelle has a word with 2 letters, where a word can consist of letters from any alphabet. Michellekperforms a switcheroo on the word as follows: for each k = 0 , 1 , . . . , n − 1, she switches the first 2
    letters of the word with the next 2 letters of the word. For example, for n = 3, Michelle changesk
    ABCDEF GH → BACDEF GH → CDBAEF GH → EF GHCDBAin one switcheroo.
    In terms of n , what is the minimum positive integer m such that after Michelle performs the switcheroonoperation m times on any word of length 2 , she will receive her original word?
    Proposed by: Mehtaab Sawhneyn
    Let m ( n ) denote the number of switcheroos needed to take a word of length 2 back to itself. Considerna word of length 2 for some n > 1 . After 2 switcheroos, one has separately performed a switcheroo onthe first half of the word and on the second half of the word, while returning the (jumbled) first halfof 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) timeswhile 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 hadfewer 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 straightforwardnproof by induction shows that m = 2 .