AoPS - Problem

Source:

Tags: algebra proposed, algebra

goodar2006

17.08.2010 13:31

interesting sequence $n$ is a natural number and $x_1,x_2,...$ is a sequence of numbers $1$ and $-1$ with these properties: it is periodic and its least period number is $2^n-1$ . (it means that for every natural number $j$ we have $x_{j+2^n-1}=x_j$ and $2^n-1$ is the least number with this property.) There exist distinct integers $0\le t_1<t_2<...<t_k<n$ such that for every natural number $j$ we have $x_{j+n}=x_{j+t_1}\times x_{j+t_2}\times ... \times x_{j+t_k}$ Prove that for every natural number $s$ that $s<2^n-1$ we have $\sum_{i=1}^{2^n-1}x_ix_{i+s}=-1$ Time allowed for this question was 1 hours and 15 minutes.

houdayfa

18.06.2016 19:39

Can someone check this please?

Pathological

27.10.2019 03:14

Note that since each of the numbers is $\pm1$ , there are at most $2^n$ possible sequences which appear as $n$ consecutive terms of the sequence. However, since $(1, 1, 1, \cdots, 1)$ cannot appear (then the sequence would be all $1$ 's), we know that there can be at most $2^n-1$ possible sequences of $2^n-1$ consecutive terms. We claim that there must be exactly $2^n-1.$ If there were less than $2^n-1$ , then by Pigeonhole, there would exist $1 \le i < j < 2^n$ so that $a_{i + k} = a_{j+k}$ for all $0 \le k < n.$ However this would make $j-i < 2^n-1$ a period of the sequence, which is a contradiction. So each of the $2^n-1$ sequences in $\{-1, 1\}^n$ appears exactly once except for $(1, 1, 1, \cdots, 1)$ which doesn't appear. This makes it obvious that the sum in question is $-1.$ $\square$