Let $n$ be a positive integer. Jadzia has to write all integers from $1$ to $2n-1$ on a board, and she writes each integer in blue or red color. We say that pair of numbers $i,j\in \{1,2,3,...,2n-1\}$, where $i\leqslant j$, is $\textit{good}$ if and only if number of blue numbers among $i,i+1,...,j$ is odd. Determine, in terms of $n$, maximal number of good pairs.
Problem
Source: Poland - Second Round P2
Tags: combinatorics, computer science
09.02.2020 05:41
Nice problem.
11.02.2020 15:18
pggp wrote: Let $n$ be a positive integer. Jadzia has to write all integers from $1$ to $2n-1$ on a board, and she writes each integer in blue or red color. We say that pair of numbers $i,j\in \{1,2,3,...,2n-1\}$, where $i\geqslant j$, is $\textit{good}$ if and only if number of blue numbers among $i,i+1,...,i+j$ is odd. Determine, in terms of $n$, maximal number of good pairs. Should be $i \leqslant j$ instead of $i \geqslant j$ and $i,i+1,...,j$ instead of $i,i+1,...,i+j$.
11.02.2020 19:13
With the modification in #3, the answer should be $\boxed{n^2}.$ This is easy to construct by simply letting $n$ be blue and nothing else. Let's construct a graph on the vertices $1, 2, \cdots, 2n$, where we connect $1 \le a < b \le 2n$ if and only if $(b-1, a)$ is a good pair. Observe that this graph is triangle-free, and hence has at most $n^2$ edges by Turan. Hence, $n^2$ is optimal, and so our answer is $\boxed{n^2}.$ $\square$
12.02.2020 22:27
Another solution (using prefix sums). For $i=0,1,2,...,2n-1$, define $a_i$ as following: $$ a_i = \left\{\begin{array}{l}\mbox{$0$, if $i$ is red or $i=0$}\\\mbox{$1$, if $i$ is blue}\end{array}\right.$$Now, for $i=0,1,2,...,2n-1$, define $b_i$: $$b_i = \left\{\begin{array}{l}\mbox{$0$, if $\sum_{j=0}^{i} a_i \equiv 0 \pmod{2}$}\\ \mbox{$1$ otherwise} \end{array}\right. $$Note that $(i,j)$ is good $\Leftrightarrow b_{i-1} \neq b_{j}$. Let $k$ be the number of $i \in \left\{ 0,1,2,...,2n-1 \right\}$ such that $b_i = 1$. Then there are exactly $2n-k$ indices $i$ that $b_i = 0$. Hence, the number of good pairs is $\leqslant k(2n-k) = n^2 - (n-k)^2 \leqslant n^2$. Note that the number of good pairs is equal to $n^2$ when $n$ of the numbers are blue. Hence, $n^2$ is the answer.