Creating a periodic sequence from a given subsequence

229 Views Asked by At

You are given the odd elements of an infinite binary sequence:

$$ a_1, a_3, a_5, \dots $$

You have to add even elements $a_2,a_4,a_6,\dots$ such that the resulting sequence is periodic (i.e, a binary representation of a rational number).

Is this always possible?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose the resulting sequence is periodic with period $T$. Consider a shift of $2T$: being even, it puts odd elements to odd positions, that is, works as a shift on our initial subsequence $a_1, a_3, a_5, \dots$, which consequently must itself be periodic. If it is not, then the resulting sequence can't be either.

The countability argument by @almagest is indeed much stronger. Say, you'd start with a subsequence of numbers at quadratic positions $a_1,a_4,a_9,a_{16}\dots$, or better yet, at positions which are powers of 2: $a_1,a_2,a_4,a_8\dots$; then what? Would you always be able to complete this into a periodic sequence? No, you won't.