Maths Olympiad Prep

Library / /475 of 520

Number theory Difficulty 6.2 National olympiad Prove it

15. (Morse-Thue Sequence) Starting from 0, each time append the "complement sequence" of the current sequence:
0,01,0110,01101001, 0,01,0110,01101001, \cdots
(1) Let the digits of the final sequence be denoted as x(0),x(1),x(2),x(0), x(1), x(2), \cdots. Prove that: x(2n)=x(n)x(2 n)=x(n), x(2n+1)=1x(2n)x(2 n+1)=1-x(2 n);
(2) Prove that: x(n)=1x(n2k)x(n)=1-x\left(n-2^{k}\right), where 2k2^{k} is the largest power of 2 not exceeding nn. Find x(1993)x(1993);
(3) Prove that the sequence is not periodic;
(4) Represent non-negative integers in binary in increasing order: 0,1,10,11,0,1,10,11, \cdots. Now take the sum of the digits of each number modulo 2, resulting in a 010-1 sequence. Prove that this sequence is the Morse-Thue sequence.

Solution

15. (1) Starting from the digit 0, repeatedly applying the transformation T:001,110T: 0 \rightarrow 01, 1 \rightarrow 10, we get T(0)=01,T2(0)=T(01)=T(0)=01, T^{2}(0)=T(01)= 0110,0110, \cdots, thus we obtain the Morse-Thue sequence in another way, where Tn(0)T^{n}(0) represents the first 2n2^{n} digits of the sequence. Applying the transformation TT to the entire sequence leaves it unchanged, which makes (1) almost obviously true, and (2) is the same.
(3) We notice that the adjacent terms x(2n)=x(n)x(2 n)=x(n) and x(2n+1)=1x(n)x(2 n+1)=1-x(n) are always different. If the sequence eventually becomes periodic, and let x(n)x(n) be an element within a period of the sequence, then n+1n+1 must not be a multiple of the period (otherwise x(2n+1)=x(n)x(2 n+1)=x(n), a contradiction). Similarly, it can be proven that n+2,n+3,n+2, n+3, \cdots are also not multiples of the period, but this is impossible.
(4) This conclusion is correct because the (n+1)(n+1)-bit 0-1 sequence is formed by adding a 1 and possibly some 0s in front of the binary numbers up to nn bits.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.