Question

设N=2n（n∈N*，n≥2），将N个数x1，x2，…，xN依次放入编号为1，2，…，N的N个位置，得到排列P0=x1x2…x

设N=2n（n∈N*，n≥2），将N个数x1，x2，…，xN依次放入编号为1，2，…，N的N个位置，得到排列P0=x1x2…xN．将该排列中分别位于奇数与偶数位置的数取出，并按原顺序依次放入对应的前N2和后N2个位置，得到排列P1=x1x3…xN-1x2x4…xN，将此操作称为C变换，将P1分成两段，每段N2个数，并对每段作C变换，得到P2，当2≤i≤n-2时，将Pi分成2i段，每段N2i个数，并对每段作C变换，得到Pi+1，例如，当N=8时，P2=x1x5x3x7x2x6x4x8，此时x7位于P2中的第4个位置．（1）当N=16时，x7位于P2中的第______个位置；（2）当N=2n（n≥8）时，x173位于P4中的第______个位置．

Answer 1

（1）当N=16时，P₀=x₁x₂…x₁₆．由C变换的定义可得P₁=x₁x₃…x₁₅x₂x₄…x₁₆，
又将P₁分成两段，每段

N

2

个数，并对每段作C变换，得到P₂，故P₂=x₁x₅x₉x₁₃x₃x₇x₁₁x₁₅x₂x₆x₁₀x₁₄x₄x₈x₁₂x₁₆，由此知x₇位于P₂中的第6个位置；
（2）考察C变换的定义及（1）计算可发现，第一次C变换后，所有的数分为两段，每段的序号组成公差为2的等差数列，且第一段序号以1为首项，第二段序号以2为首项；第二次C变换后，所有的数据分为四段，每段的数字序号组成以4公差的等差数列，且第一段的序号以1为首项，第二段序号以3为首项，第三段序号以2为首项，第四段序号以4为首项，依此类推可得出P₄中所有的数字分为16段，每段的数字序号组成以16为公差的等差数列，且一到十六段的首项的序号分别为1，9，5，13，…，由于173=16×10+13，故x₁₇₃位于以13为首项的那一段的第11个数，由于N=2ⁿ（n≥8）故每段的数字有2^n-4个，以13为首项的是第四段，故x₁₇₃位于第3×2^n-4+11=3×2^n-4+11个位置．
故答案为3×2^n-4+11