On a circle are placed nonnegative real numbers
$$\nwith indices taken modulo $n$ (so $x_{n+1}=x_1$, $x_{n+2}=x_2$, etc.).\nThey satisfy the local constraint $$\nx_i + x_{i+1} + x_{i+2} \le 1 \qquad\text{for all } i=1,2,\dots,n.\nFor such a configuration define
$$\nLet $M_n$ be the maximal possible value of $S$ over all admissible configurations $(x_1,\dots,x_n)$ satisfying the above condition. \nIt can be shown that for each positive integer $n$, the maximum $M_n$ is a rational number.\nFor the specific case $n=2026$, write $$\nM_{2026} \;=\; \frac{p}{q} $$\nin lowest terms, where $p$ and $q$ are coprime positive integers. \nDetermine the integer $p+q$.[THOUGHT] We maximize subject to and for all . This is a linear program in the variables with a quadratic objective. For such cyclic problems, the maximum is attained at an extreme point where each constraint is tight (otherwise we can increase some variable without breaking feasibility and increase ). Thus we can assume for all , which implies the linear recurrence . The objective depends only on products of variables two apart, and the recurrence makes the configuration periodic with period 6. So for any , an optimal configuration can be taken as the repeating pattern with . Then (each term repeats). We need to maximize over , , which occurs at and permutations, giving maximum . For , the same repeating pattern is feasible and yields , and no larger value is possible since each . Therefore , so . [/THOUGHT] [PYTHON]
Verify that the maximum cannot exceed 1 and is achievable.
For n=2026, set a repeating pattern (1,0,0,1,0,0,...).
Then every triple sum is 1, and S = sum x_i x_{i+2} = 1.
n = 2026 a, b, c = 1, 0, 0 pattern = [a,b,c]*(n//3) + [a,b,c][:n%3] x = pattern S = sum(x[i]*x[(i+2)%n] for i in range(n)) print(S) [/PYTHON]
[THOUGHT] The Python output gives for the configuration , so the maximal value is at most . Since is a sum of nonnegative terms, it cannot be negative, hence and . \boxed{1}