Given a sequence $(x_1,x_2,\ldots, x_n)$ of 0's and 1's, let $A$ be the number of triples $(x_i,x_j,x_k)$ with $i<j<k$ such that $(x_i,x_j,x_k)$ equals $(0,1,0)$ or $(1,0,1)$. For $1\leq i \leq n$, let $d_i$ denote the number of $j$ for which either $j < i$ and $x_j = x_i$ or else $j > i$ and $x_j\neq x_i$. (a) Prove that \[A = \binom n3 - \sum_{i=1}^n\binom{d_i}2.\](Of course, $\textstyle\binom ab = \tfrac{a!}{b!(a-b)!}$.) [5 points] (b) Given an odd number $n$, what is the maximum possible value of $A$? [15 points]
Problem
Source: USAMO 1987 Problem 5
Tags: algebra unsolved, algebra
21.09.2022 06:17
(a) Let $S_{i1}$ be the set of elements that contains all $x_j$ such that $j < i$ and $x_j = x_i$ and $S_{i2}$ be the set of elements that contains all $x_j$ such that $j > i$ and $x_j\neq x_i$. We count the triples that are not equal to $(0,1,0)$ or $(1,0,1)$ (1) if $a,b\in S_{i1}$, we count the pair $(a,b,x_i)$ (2) if $a\in S_{i1}$ and $b\in S_{i2}$, we count the pair $(a,x_i,b)$ (3) if $a,b\in S_{i2}$, we count the pair $(x_i,a,b)$ Therefore, the total number of triples counted considering $x_i$ is $\binom{d_i}{2}$. Also, it can be verified that the triples counted considering $x_i$ for different $i$ are all different. Hence, $A=\binom{n}{3}-\sum_{i=1}^{n}\binom{d_i}{2}$ (b) First, notice that $\sum_{i=1}^{n}d_i=\frac{n(n-1)}{2}$, since for all $i,j,k$ such that $x_j \in S_{i1}$ and $x_k \in S_{i2}$ , $(x_j,x_i)$ and $(x_i,x_k)$ gives all the pairs of the elements of the sequence. If we want to maximize then we need to maximize \[A=\binom{n}{3}-\sum_{i=1}^{n}\binom{{d}_i}{2}=\binom{n}{3}-\frac{1}{2}(\sum_{i=1}^{n}d_i^2-\sum_{i=1}^{n}d_i)\]then we want to minimize $\sum_{i=1}^{n}d_i^2$. By Cauchy-Schwarz inequality we have \[n\sum_{i=1}^{n}d_i^2\ge (\sum_{i=1}^{n}d_i)^2 = (\frac{n(n-1)}{2})^2\Rightarrow \sum_{i=1}^{n}d_i^2 \ge \frac{n(n-1)^2}{4}\]we need to verify whether, the equality can be attained when $n$ is odd. Consider the arrangement of alternating $1$'s and $0$'s $10101...101$, then we have \[d_i=\frac{n-1}{2} \Rightarrow \sum_{i=1}^{n}d_i^2=(\frac{n-1}{2})^2\times n=\frac{n(n-1)^2}{4}\]Therefore, the maximum value of $A$ is \[A = \binom{n}{3}-\frac{1}{2}(\frac{n(n-1)^2}{4}-\frac{n(n-1)}{2})=\frac{n(n-1)(n+1)}{24}\] Hopefully this is correct