[PYTHON] import numpy as np from scipy.optimize import minimize, LinearConstraint

def solve_for_n(n): # Objective: maximize sum x_i * x_{i+2} # equivalent to minimizing -sum def objective(x): val = 0 for i in range(n): val += x[i] * x[(i+2) % n] return -val

# Constraints: x_i + x_{i+1} + x_{i+2} <= 1
# We can express this as a matrix A such that A x <= 1
A = np.zeros((n, n))
for i in range(n):
    A[i, i] = 1
    A[i, (i+1)%n] = 1
    A[i, (i+2)%n] = 1

# LinearConstraint requires lb <= A.dot(x) <= ub
# Here lb = -inf, ub = 1
constraint = LinearConstraint(A, -np.inf, 1)

# Bounds x >= 0
bounds = [(0, None) for _ in range(n)]

# Initial guess: uniform distribution satisfying constraints
x0 = np.ones(n) / 3.0

# Run optimization multiple times with random starts to avoid local optima
best_res = None
best_val = np.inf

# Try a few starting points
for _ in range(10):
    if _ == 0:
        start_x = x0
    else:
        start_x = np.random.rand(n)
        # Normalize to satisfy constraints roughly
        start_x = start_x / (3 * np.max(start_x)) 
        
    res = minimize(objective, start_x, method='SLSQP', constraints=[constraint], bounds=bounds, tol=1e-9)
    if res.fun < best_val:
        best_val = res.fun
        best_res = res
        
return -best_val

for n in range(3, 16): val = solve_for_n(n) print(f"n={n}, M_n approx {val:.6f}") [/PYTHON] [PYTHON] import numpy as np from scipy.optimize import minimize, LinearConstraint from fractions import Fraction

def solve_for_n(n): def objective(x): val = 0 for i in range(n): val += x[i] * x[(i+2) % n] return -val

A = np.zeros((n, n))
for i in range(n):
    A[i, i] = 1
    A[i, (i+1)%n] = 1
    A[i, (i+2)%n] = 1

constraint = LinearConstraint(A, -np.inf, 1)
bounds = [(0, None) for _ in range(n)]

best_val = np.inf

# Strategies for initial guesses
# 1. Uniform
# 2. Periodic patterns
# 3. Random

guess_list = []
guess_list.append(np.ones(n)/3.0)

# Pattern 1, 0, 0...
pat = np.array([1, 0, 0] * (n//3 + 1))[:n]
pat = pat / 2.0 # Normalize roughly? No, max sum is 1.
guess_list.append(pat)

# Pattern 1, 0, 1, 0...
pat = np.array([1, 0] * (n//2 + 1))[:n]
pat = pat / 2.0
guess_list.append(pat)

for _ in range(5):
    guess_list.append(np.random.rand(n))

for start_x in guess_list:
    # Ensure start_x is feasible-ish
    # Scale so max sum of 3 is 1
    sums = np.array([start_x[i] + start_x[(i+1)%n] + start_x[(i+2)%n] for i in range(n)])
    if np.max(sums) > 1e-6:
        start_x = start_x / np.max(sums)
    
    res = minimize(objective, start_x, method='SLSQP', constraints=[constraint], bounds=bounds, tol=1e-9)
    if res.fun < best_val:
        best_val = res.fun
        
return -best_val

results = {} for n in range(3, 13): val = solve_for_n(n) results[n] = val print(f"n={n}, M_n approx {val:.6f}") [/PYTHON] [PYTHON]

This block is just to confirm the previous code execution or re-run if needed.

Since I cannot see the output of the previous block until I finish this thought,

I will assume the previous block runs successfully.

I will add code here to try to rationalize the results.

Re-running the solve and rationalizing

import numpy as np from scipy.optimize import minimize, LinearConstraint from fractions import Fraction

def solve_and_rationalize(): results = {}

def solve_n(n):
    def objective(x):
        # Using negative for minimization
        # We want to maximize sum x_i x_{i+2}
        return -np.sum(x * np.roll(x, -2))

    A = np.zeros((n, n))
    for i in range(n):
        A[i, i] = 1
        A[i, (i+1)%n] = 1
        A[i, (i+2)%n] = 1
    
    constraint = LinearConstraint(A, -np.inf, 1)
    bounds = [(0, None) for _ in range(n)]
    
    best_val = np.inf
    
    # Try multiple starts
    starts = []
    starts.append(np.ones(n)/3.0)
    # Periodic 1,0,0
    p1 = np.array([1,0,0]*(n//3+1))[:n]; starts.append(p1/np.max([p1[i]+p1[(i+1)%n]+p1[(i+2)%n] for i in range(n)]))
    # Periodic 1,1,0
    p2 = np.array([1,1,0]*(n//3+1))[:n]; starts.append(p2/np.max([p2[i]+p2[(i+1)%n]+p2[(i+2)%n] for i in range(n)]))
    # Periodic 1,0
    p3 = np.array([1,0]*(n//2+1))[:n]; starts.append(p3/np.max([p3[i]+p3[(i+1)%n]+p3[(i+2)%n] for i in range(n)]))
    
    for _ in range(5):
        r = np.random.rand(n)
        # normalize
        sums = np.array([r[i] + r[(i+1)%n] + r[(i+2)%n] for i in range(n)])
        starts.append(r / np.max(sums))
        
    for x0 in starts:
        res = minimize(objective, x0, method='SLSQP', constraints=[constraint], bounds=bounds, tol=1e-9)
        if res.fun < best_val:
            best_val = res.fun
    return -best_val

for n in range(3, 13):
    val = solve_n(n)
    # Try to find rational approximation
    frac = Fraction(val).limit_denominator(1000)
    print(f"n={n}: {val:.6f} ~ {frac}")

solve_and_rationalize() [/PYTHON] ** 5/9 n=6: 0.750000 -> 3/4 n=7: 0.833333 -> 5/6 n=8: 1.000000 -> 1 n=9: 1.111111 -> 10/9 n=10: 1.250000 -> 5/4 n=11: 1.363636 -> 15/11 n=12: 1.500000 -> 3/2 n=13: 1.615385 -> 21/13 n=14: 1.750000 -> 7/4

[THOUGHT]
Let's analyze the sequence of values $M_n$:
$n=3: 1/3 = 3/9$
$n=4: 1/2 = 2/4$
$n=5: 5/9$
$n=6: 3/4 = 9/12$
$n=7: 5/6 = 10/12$? No. $5/6$.
$n=8: 1$
$n=9: 10/9$
$n=10: 5/4 = 15/12$? $1.25$.
$n=11: 15/11$
$n=12: 3/2 = 1.5$
$n=13: 21/13$
$n=14: 7/4 = 1.75$

Let's look at $M_n$ values again.
3: 1/3
4: 1/2
5: 5/9
6: 3/4
7: 5/6
8: 1
9: 10/9
10: 5/4
11: 15/11
12: 3/2
13: 21/13
14: 7/4

Let's try to find a formula.
Maybe separate by parity of $n$.
Odd $n$:
3: 1/3 = 3/9
5: 5/9
7: 5/6 = 15/18? No.
9: 10/9
11: 15/11
13: 21/13

Let's look at $M_n$ for odd $n$.
$n=3 \to 1/3 \approx 0.333$
$n=5 \to 5/9 \approx 0.555$
$n=7 \to 5/6 \approx 0.833$
$n=9 \to 10/9 \approx 1.111$
$n=11 \to 15/11 \approx 1.3636$
$n=13 \to 21/13 \approx 1.615$

Let's look at the numerators and denominators.
3: 1/3
5: 5/9
7: 5/6 = 25/30?
9: 10/9
11: 15/11
13: 21/13

Notice $n=9, 11, 13$.
$M_9 = 10/9$.
$M_{11} = 15/11$.
$M_{13} = 21/13$.
Differences in numerators:
$10, 15, 21$.
$15-10 = 5$.
$21-15 = 6$.
Next might be 7? $21+7 = 28$. So $M_{15} = 28/15$?
Let's check $n=3, 5, 7$.
$M_3 = 1/3 = 3/9$? No, $1/3$.
$M_5 = 5/9$.
$M_7 = 5/6 = 15/18$? No.
Let's rewrite them with denominator $n$ or something related.
$n=3: 1/3 = 1/3$.
$n=5: 5/9$.
$n=7: 5/6 = 35/42$?
$n=9: 10/9$.
$n=11: 15/11$.
$n=13: 21/13$.

Let's look at $M_n \times n$.
$3 \times 1/3 = 1$.
$5 \times 5/9 = 25/9 \approx 2.77$.
$7 \times 5/6 = 35/6 = 5.83$.
$9 \times 10/9 = 10$.
$11 \times 15/11 = 15$.
$13 \times 21/13 = 21$.
Sequence of integers $1, ?, ?, 10, 15, 21$.
$10, 15, 21$ are triangular numbers?
$T_4 = 10$.
$T_5 = 15$.
$T_6 = 21$.
So for $n=9$, value is $T_4$.
$n=11$, value is $T_5$.
$n=13$, value is $T_6$.
Formula for these: $n=2k+1$.
$n=9 \implies k=4$. $T_k = k(k+1)/2 = 4 \times 5 / 2 = 10$. Correct.
$n=11 \implies k=5$. $T_5 = 15$. Correct.
$n=13 \implies k=6$. $T_6 = 21$. Correct.
Does it work for smaller odd $n$?
$n=7 \implies k=3$. $T_3 = 6$. $M_7 = 6/7$?
Observed $M_7 = 5/6$.
$6/7 \approx 0.857$. $5/6 \approx 0.833$.
So $M_7$ is NOT $6/7$.
$n=5 \implies k=2$. $T_2 = 3$. $M_5 = 3/5$?
Observed $M_5 = 5/9 \approx 0.555$. $3/5 = 0.6$.
$n=3 \implies k=1$. $T_1 = 1$. $M_3 = 1/3$. Correct.

So for $n \ge 9$ odd, it seems $M_n = \frac{k(k+1)}{2 n}$ where $n=2k+1$.
Wait, $M_n = \frac{T_k}{n}$.
Let's check $n=15$. $k=7$. $T_7 = 28$. $M_{15} = 28/15$?
I should verify this with code.

Now Even $n$:
$n=4: 1/2$.
$n=6: 3/4$.
$n=8: 1$.
$n=10: 5/4$.
$n=12: 3/2 = 6/4$.
$n=14: 7/4$.
Sequence: $1/2, 3/4, 4/4, 5/4, 6/4, 7/4$.
This is very regular.
$M_n = \frac{n}{8}$?
$4/8 = 1/2$. Correct.
$6/8 = 3/4$. Correct.
$8/8 = 1$. Correct.
$10/8 = 5/4$. Correct.
$12/8 = 3/2$. Correct.
$14/8 = 7/4$. Correct.
So for even $n$, $M_n = n/8$.

Let's verify $n=16$ with code. $M_{16}$ should be $16/8 = 2$.
And $n=15$ (odd). $k=7$. $M_{15} = 28/15$.
Let's check $n=7$ again. $M_7 = 5/6$.
Formula $T_k/n$ for $n=7$ ($k=3$) gives $6/7$.
$5/6 < 6/7$.
Why is $n=7$ different?
Maybe the pattern starts later?
Or maybe my formula for odd $n$ is slightly off.
Let's check $n=5$. $M_5 = 5/9$. Formula $3/5$.
$5/9 \approx 0.555$. $3/5 = 0.6$.
So for $n=5, 7$, the value is lower than $T_k/n$.
For $n=3$, $1/3 = 1/3$. Matches.

Let's re-evaluate the odd case.
$n=3$: $1/3$.
$n=5$: $5/9$.
$n=7$: $5/6$.
$n=9$: $10/9$.
$n=11$: $15/11$.
$n=13$: $21/13$.

Let's look at $M_n$ for $n=2026$.
$n=2026$ is EVEN.
If the even formula $M_n = n/8$ holds, then $M_{2026} = 2026/8 = 1013/4$.
This is a rational number.
$p=1013, q=4$.
$p+q = 1017$.

I must be very sure about the even case.
The pattern $1/2, 3/4, 1, 5/4, 3/2, 7/4$ is very strong.
It corresponds to $n=4, 6, 8, 10, 12, 14$.
Let's check $n=16$ and $n=18$ to be sure.
Also check $n=20$.
If it holds, I am confident.

What if $n$ is not divisible by something?
$n=4, 8, 12, 16$ are $0 \pmod 4$.
$n=6, 10, 14, 18$ are $2 \pmod 4$.
The formula $n/8$ works for both $0 \pmod 4$ and $2 \pmod 4$ in the observed range.
So it likely works for all even $n \ge 4$.

Let's write a script to verify $n=16, 18, 20$ and also check $n=15, 17$ for the odd pattern just in case.

[/THOUGHT]
[PYTHON]
import numpy as np
from scipy.optimize import minimize, LinearConstraint
from fractions import Fraction

def solve_n(n):
    def objective(x):
        return -np.sum(x * np.roll(x, -2))

    A = np.zeros((n, n))
    for i in range(n):
        A[i, i] = 1
        A[i, (i+1)%n] = 1
        A[i, (i+2)%n] = 1
    
    constraint = LinearConstraint(A, -np.inf, 1)
    bounds = [(0, None) for _ in range(n)]
    
    best_val = np.inf
    
    starts = []
    starts.append(np.ones(n)/3.0)
    
    # Even pattern guess: n/8
    # How to construct x for n/8?
    # For n=4, x=[1/2, 0, 1/2, 0] -> S=1/2 = 4/8.
    # For n=6, x=[1/2, 0, 1/2, 0, 1/2, 0] -> S=3/4 = 6/8.
    # It seems x_i = 1/2 for odd i, 0 for even i works?
    # Let's check constraints for x=[1/2, 0, 1/2, 0...]
    # Sums: 1/2+0+1/2 = 1. 0+1/2+0 = 1/2.
    # All sums <= 1.
    # Value: sum x_i x_{i+2}.
    # Indices i and i+2 are both odd or both even.
    # If i is odd, x_i=1/2, x_{i+2}=1/2. Product 1/4.
    # If i is even, x_i=0. Product 0.
    # There are n terms. n/2 are odd indices.
    # So sum is (n/2) * (1/4) = n/8.
    # This construction is always valid for EVEN n.
    # So M_n >= n/8 for even n.
    
    # Add this specific start
    if n % 2 == 0:
        p = np.zeros(n)
        p[::2] = 0.5
        starts.append(p)
    
    # Random starts
    for _ in range(5):
        r = np.random.rand(n)
        sums = np.array([r[i] + r[(i+1)%n] + r[(i+2)%n] for i in range(n)])
        starts.append(r / np.max(sums))
        
    for x0 in starts:
        res = minimize(objective, x0, method='SLSQP', constraints=[constraint], bounds=bounds, tol=1e-9)
        if res.fun < best_val:
            best_val = res.fun
            
    return -best_val

print("Checking higher n:")
for n in [15, 16, 17, 18, 20]:
    val = solve_n(n)
    frac = Fraction(val).limit_denominator(1000)
    print(f"n={n}: {val:.6f} -> {frac}")
[/PYTHON]
** -> 36/17
n=18: 2.250000 -> 9/4
n=20: 2.500000 -> 5/2

[THOUGHT] Results: $n=15$: $28/15$. $n=16$: $2 = 16/8$. $n=17$: $36/17$. $n=18$: $2.25 = 9/4 = 18/8$. $n=20$: $2.5 = 5/2 = 20/8$.

The pattern for even $n$ is confirmed to be $M_n = n/8$. $M_{16} = 16/8 = 2$. $M_{18} = 18/8 = 2.25$. $M_{20} = 20/8 = 2.5$.

So for $n=2026$: $M_{2026} = \frac{2026}{8} = \frac{1013}{4}$. $p = 1013$. $q = 4$. $p$ and $q$ are coprime? 1013 is not divisible by 2. So yes. $p+q = 1013 + 4 = 1017$.

Just to be absolutely sure, is there any exception? The sequence for even $n$ so far: 4: 1/2 6: 3/4 8: 1 10: 5/4 12: 3/2 14: 7/4 16: 2 18: 9/4 20: 5/2 All fit $n/8$. The construction $x = (1/2, 0, 1/2, 0, \dots)$ works for all even $n$. Is it maximal? For small $n$, the optimizer didn't find anything better. The problem states $M_n$ is a rational number. The function $n/8$ is rational.

Let's briefly check the odd case pattern just for curiosity/confirmation of robustness. $n=15$: $28/15$. $T_7 = 28$. $n=2(7)+1$. Matches $T_k/n$. $n=17$: $36/17$. $n=2(8)+1$. $T_8 = 36$. Matches $T_k/n$. So for odd $n \ge 9$, $M_n = \frac{(n-1)(n+1)}{8n} = \frac{n^2-1}{8n}$? $T_k = \frac{k(k+1)}{2}$. $k = (n-1)/2$. $T_k = \frac{\frac{n-1}{2} \frac{n+1}{2}}{2} = \frac{n^2-1}{8}$. So $M_n = \frac{n^2-1}{8n} = \frac{n}{8} - \frac{1}{8n}$. This is slightly less than $n/8$. For even $n$, we achieve $n/8$. Since $n/8$ is achievable for even $n$, and for odd $n$ it's slightly less (due to parity constraints likely), it makes perfect sense that for even $n$ the answer is exactly $n/8$.

Wait, let's check $n=3, 5, 7$ with the formula $\frac{n^2-1}{8n}$. $n=3$: $(9-1)/24 = 8/24 = 1/3$. Matches. $n=5$: $(25-1)/40 = 24/40 = 3/5$. But observed $M_5 = 5/9 \approx 0.555$. $3/5 = 0.6$. So for $n=5$, the formula fails. $n=7$: $(49-1)/56 = 48/56 = 6/7 \approx 0.857$. Observed $M_7 = 5/6 \approx 0.833$. So for $n=5, 7$, the value is lower. Why? For $n=9$: $(81-1)/72 = 80/72 = 10/9$. Matches. So the formula $\frac{n^2-1}{8n}$ works for $n=3$ and $n \ge 9$ (odd). It fails for $n=5, 7$. This is a known phenomenon in such problems (small $n$ anomalies). However, for even $n$, the pattern $n/8$ has held from $n=4$ to $n=20$ without exception. The construction is simple and robust. I am confident in $M_{2026} = 2026/8$.

Let's double check if there's any constraint I missed. $x_i \ge 0$. $x_i + x_{i+1} + x_{i+2} \le 1$. $S = \sum x_i x_{i+2}$. The construction $1/2, 0, 1/2, 0 \dots$ gives $S = n/8$. Suppose we could do better. Let $x_i = 1/2 + \epsilon_i$. This would violate constraints or require negative values if we just shift. The upper bound proof: Sum over $i$ of $(x_i + x_{i+1} + x_{i+2})^2$? No. Consider $\sum (x_i + x_{i+1} + x_{i+2}) = 3 \sum x_i \le n$. So $\sum x_i \le n/3$. This doesn't help much with quadratic.

Let's try to prove $S \le n/8$. $S = \sum x_i x_{i+2}$. Consider $(x_i + x_{i+1} + x_{i+2})^2 \le 1$. Sum over $i$: $\sum (x_i^2 + x_{i+1}^2 + x_{i+2}^2 + 2 x_i x_{i+1} + 2 x_{i+1} x_{i+2} + 2 x_i x_{i+2}) \le n$. $3 \sum x_i^2 + 2 \sum x_i x_{i+1} + 2 \sum x_i x_{i+1} + 2 S \le n$. $3 \sum x_i^2 + 4 \sum x_i x_{i+1} + 2 S \le n$. We want to bound $S$. We know $x_i x_{i+1} \ge 0$ and $x_i^2 \ge 0$. This gives $2 S \le n \implies S \le n/2$. Too loose.

Try another expansion. Maybe sum of $(x_i + x_{i+1} + x_{i+2}) x_{i+1}$? No. What if we sum $(x_i + x_{i+1} + x_{i+2}) x_{i+2}$? $\sum x_i x_{i+2} + \sum x_{i+1} x_{i+2} + \sum x_{i+2}^2 \le \sum x_{i+2}$. $S + \sum x_i x_{i+1} + \sum x_i^2 \le \sum x_i$. This also doesn't immediately give $n/8$.

However, given the numerical evidence and the clean construction, $n/8$ is almost certainly correct for even $n$. The problem asks for $p+q$. $M_{2026} = 1013/4$. $p=1013, q=4$. $p+q = 1017$.

One detail: "On a circle are placed nonnegative real numbers". "indices taken modulo n". "maximal possible value of S". "M_n is a rational number". Everything aligns.

Let's do a quick check on $n=5$ anomaly just to be satisfied. Why is $M_5 = 5/9$? $5/9 \approx 0.555$. Formula $(n^2-1)/8n = 24/40 = 0.6$. Why can't we reach $0.6$? For $n=5$, to get $0.6$, we would need $x \approx 1/2, 0, 1/2, 0, 1/2$ pattern? $1/2, 0, 1/2, 0, 1/2$. Sums: $1/2+0+1/2 = 1$. $0+1/2+0 = 1/2$. $1/2+0+1/2 = 1$. $0+1/2+1/2 = 1$. $1/2+1/2+1/2 = 1.5 > 1$. FAIL. So the "wrap around" kills the $n/8$ pattern for odd $n$. For $n=3$, $1/3$ is optimal. Formula $(9-1)/24 = 1/3$. For $n=5$, we can't fit the pattern. For $n=9$, the cycle is long enough to adjust? Actually, for odd $n$, the optimal solution is likely uniform $x_i = \alpha$ or close to it? If $x_i = 1/3$, $S = n/9$. For $n=5$, $5/9$. This matches $M_5$. For $n=7$, $7/9 \approx 0.77$. But $M_7 = 5/6 \approx 0.83$. So for $n=7$, uniform is not optimal. For $n=9$, $9/9 = 1$. But $M_9 = 10/9$. So uniform is only optimal for $n=3, 5$. For $n \ge 7$ (odd), we can do better than uniform. For $n \ge 9$ (odd), we can approach the even bound $n/8$ closely. The formula $(n^2-1)/8n$ is exactly the value for $n=9, 11, 13, 15, 17$. So the pattern is: Even $n$: $n/8$. Odd $n \ge 9$: $(n^2-1)/(8n)$. Odd $n=3, 5$: $n/9$. Odd $n=7$: $5/6$. (Note: $(7^2-1)/56 = 48/56 = 6/7 \approx 0.857$. $5/6 \approx 0.833$. $5/6 < 6/7$. So $n=7$ is also an anomaly).

But for even $n$, there is no wrap around conflict for the $1/2, 0$ pattern. The bipartite nature of the indices (odd/even) fits perfectly with the step 2 in the objective and the step 1 in constraints. $x_i + x_{i+1} + x_{i+2}$. If we set even positions to 0, then $x_{2k} = 0$. Constraint becomes: $x_{2k-1} + 0 + x_{2k+1} \le 1$. $0 + x_{2k+1} + 0 \le 1 \implies x_{2k+1} \le 1$. $x_{2k+1} + 0 + x_{2k+3} \le 1$. So we need $x_{odd} + x_{next\_odd} \le 1$. We want to maximize $\sum x_{odd} x_{next\_odd}$. Let $y_k = x_{2k-1}$. Maximize $\sum y_k y_{k+1}$ subject to $y_k + y_{k+1} \le 1$. This is a classic problem. Maximize $\sum y_k y_{k+1}$ subject to $y_k + y_{k+1} \le 1$. For a chain of length $m$ (here $m=n/2$ and it's a cycle). Set $y_k = 1/2$. Then $y_k + y_{k+1} = 1$. Sum is $m \times (1/4) = m/4$. With $m = n/2$, sum is $n/8$. Can we do better? Maximize $\sum y_i y_{i+1}$ subject to $y_i + y_{i+1} \le 1$. Let $y_i = 1/2 + \delta_i$. $1 \ge y_i + y_{i+1} = 1 + \delta_i + \delta_{i+1} \implies \delta_i + \delta_{i+1} \le 0$. Sum over cycle: $2 \sum \delta_i \le 0 \implies \sum \delta_i \le 0$. Objective: $\sum (1/2 + \delta_i)(1/2 + \delta_{i+1}) = \sum (1/4 + 1/2(\delta_i + \delta_{i+1}) + \delta_i \delta_{i+1})$. $= m/4 + 1/2 \sum (\delta_i + \delta_{i+1}) + \sum \delta_i \delta_{i+1}$. $= m/4 + \sum \delta_i + \sum \delta_i \delta_{i+1}$. We know $\delta_i + \delta_{i+1} \le 0$. If we take $\delta_i = 0$, we get $m/4$. Can we get positive $\sum \delta_i + \sum \delta_i \delta_{i+1}$? If we alternate $\delta, -\delta, \delta, -\delta$. Then $\delta_i + \delta_{i+1} = 0$. Sum $\delta_i = 0$. Term $\sum \delta_i \delta_{i+1} = \sum (-\delta^2) < 0$. So alternating perturbations decrease the sum. What if not alternating? It seems $y_i = 1/2$ is the global maximum for the cyclic problem $\sum y_i y_{i+1}$ subject to $y_i + y_{i+1} \le 1$. Thus, for even $n$, the reduction to the odd/even subproblem proves $n/8$ is optimal, provided setting one set to 0 is optimal. Why set one set to 0? $S = \sum x_i x_{i+2}$. Terms are $x_1 x_3, x_2 x_4, x_3 x_5, \dots$. This splits into two sums: $S_{odd} = x_1 x_3 + x_3 x_5 + \dots$ and $S_{even} = x_2 x_4 + x_4 x_6 + \dots$. Constraints link them: $x_1+x_2+x_3 \le 1$. If we set $x_{even} = 0$, we remove the linkage between $x_{odd}$ terms in the constraints (except the distance is now effectively 1 in the reduced indices). Specifically, $x_1 + x_2 + x_3 \le 1 \implies x_1 + x_3 \le 1$ (if $x_2=0$). This allows $x_1, x_3$ to be larger (up to sum 1). If $x_2 > 0$, then $x_1 + x_3$ must be smaller. It seems intuitive that concentrating mass on one parity is better. Suppose $n=4$. $S = x_1 x_3 + x_2 x_4 + x_3 x_1 + x_4 x_2 = 2(x_1 x_3 + x_2 x_4)$. Constraints: $x_1+x_2+x_3 \le 1$, etc. If $x_1=x_3=1/2, x_2=x_4=0$, $S = 2(1/4) = 1/2$. If $x_i = 1/3$, $S = 4/9 \approx 0.44$. If $x_1=x_2=x_3=x_4=1/4$. $S = 2(1/16+1/16) = 1/4$. So $n/8$ seems robust.

Final check on the question: "Determine the integer p+q". $M_{2026} = 1013/4$. $p=1013, q=4$. $p+q = 1017$.

One more check: $n=2026$. $2026 = 2 \times 1013$. 1013 is prime. Is there any weirdness for $n = 2 \times p$? $n=6 = 2 \times 3$. $M_6 = 3/4 = 6/8$. OK. $n=10 = 2 \times 5$. $M_{10} = 5/4 = 10/8$. OK. $n=14 = 2 \times 7$. $M_{14} = 7/4 = 14/8$. OK. $n=22 = 2 \times 11$. (Not checked, but pattern is strong). The pattern holds for $n=2 \times \text{odd}$. So $n=2026$ should follow the pattern.

I am confident.

[/THOUGHT] [THOUGHT] The maximum value $M_n$ for even $n$ appears to be $n/8$. For $n=2026$, $M_{2026} = \frac{2026}{8} = \frac{1013}{4}$. $p=1013, q=4$. $p, q$ are coprime. $p+q = 1013 + 4 = 1017$. [/THOUGHT]

\boxed{1017}

The maximum value $M_n$ for the given problem exhibits a clear pattern for even $n$. Based on the computational results:

• For $n=4$, $M_4 = 0.5 = 1/2 = 4/8$.
• For $n=6$, $M_6 = 0.75 = 3/4 = 6/8$.
• For $n=8$, $M_8 = 1.0 = 1 = 8/8$.
• For $n=10$, $M_{10} = 1.25 = 5/4 = 10/8$.
• For $n=12$, $M_{12} = 1.5 = 3/2 = 12/8$.
• For $n=16$, $M_{16} = 2.0 = 2 = 16/8$.
• For $n=18$, $M_{18} = 2.25 = 9/4 = 18/8$.
• For $n=20$, $M_{20} = 2.5 = 5/2 = 20/8$.

The pattern for even $n$ is $M_n = \frac{n}{8}$. For $n=2026$, which is even: [ M_{2026} = \frac{2026}{8} = \frac{1013}{4}. ] The fraction $\frac{1013}{4}$ is in lowest terms because 1013 is not divisible by 2 (it is odd). Thus, $p = 1013$ and $q = 4$. The value $p+q = 1013 + 4 = 1017$.

\boxed{1017}