Problem

Source: Poland - Second Round P2

Tags: combinatorics, computer science



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.