Competition problem — Combinatorics

Library / /4 of 10

Combinatorics Difficulty 3.9 AMC 10/12 Prove it North Macedonia

Let every one of the numbers $x_1$ , $x_2$ , ..., $x_n$ be equal to $1$ or $-1$ and also:
$x_1x_2x_3x_4 + x_2x_3x_4x_5 + x_3x_4x_5x_6 + ... + x_{n-2}x_{n-1}x_nx_1 + x_{n-1}x_nx_1x_2 + x_nx_1x_2x_3 = 0$
Prove that $n$ is divisible by $4$ .

Solution

Let $y_k = x_k x_{k+1} x_{k+2} x_{k+3}$ (clearly $y_{n-2} = x_{n-2}x_{n-1}x_nx_1$ , $y_{n-1} = x_{n-1}x_nx_1x_2$ , $y_n = x_nx_1x_2x_3$ ). All $y_k$ are $1$ or $-1$ . Then, by the conditions of the problem, we get $y_1 + ... + y_n = 0$ . Therefore $n = 2k$ and moreover exactly $k$ of the numbers $y_1, ..., y_n$ are equal to $1$ and the remaining $k$ are equal to $-1$ . But then $y_1 \cdot ... \cdot y_n = (-1)^k$ . On the other hand, notice that $y_1 \cdot ... \cdot y_n = x_1^4 \cdot x_2^4 \cdot ... \cdot x_n^4$ , from where we get that $y_1 \cdot ... \cdot y_n = 1$ , hence $k = 2t$ , i.e. $n = 4t$ .

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.