Given 2017 lines separated into three sets such that lines within the same set are parallel to each other. What is the maximum number of triangles that can be formed with vertices on these lines?

#
Solution

Let $a \geq b \geq c$ be the number of lines in the three sets. Then $a+b+c=2017$ and the number of triangles that can be formed is $a \cdot b \cdot c$, since lines in the same set do not intersect. Thus, we want to maximize the product. If $a>c+1$, we can decrease one line from the set with $a$ and increase one line in the set with $c$, maintaining the total number of lines, but increasing the product:

$$
\begin{aligned}
a \cdot b \cdot c & <b \cdot(a \cdot c+a-c-1) \\
& =b \cdot(a-1) \cdot(c+1)
\end{aligned}
$$

Therefore, for the product to be maximized, $a=c$ or $a=c+1$. If we have $a=c$, we will also have $b=c$ and $3 c=a+b+c=2017$. Since 2017 is not a multiple of 3, this does not occur. Thus, $a=c+1$ and $b=c+1$ or $b=c$. Therefore, $a+b+c$ is either $3 c+1$ or $3 c+2$. The remainder of 2017 divided by 3 is $1$, and this allows us to conclude that $a+b+c=3 c+1$. Therefore, $c=672$ and $a \cdot b \cdot c=673 \cdot 672^{2}$.