MHB Find the maximal number of subsets, k.

[lfdahl]

Let $A_1, A_2, … , A_k$ be distinct subsets of $\left \{ 1,2,...,2018 \right \}$,

such that for each $1 \leq i < j \leq k$ the intersection $A_i \cap A_j$ forms an arithmetic progression.

Find the maximal value of $k$.

 

[lfdahl]

Here´s the suggested solution:

Spoiler

The answer is: $\binom{2018}{0}+\binom{2018}{1}+\binom{2018}{2}+\binom{2018}{3}.$
It can be readily seen, that the collection of all subsets having at most $3$ elements satisfies the conditions.

In order to complete the solution, we show, that the number of subsets having at least $3$ elements is not greater than $\binom{2018}{3}$.
Consider any subset $A = \left \{a_1,a_2,…,a_n \right \}$ having at least $3$ elements and let $a_1<a_2<…<a_n$. We assign a label $L(A) = (a_1, a_2,c)$ to each such subset, where

if $A$ is an arithmetic progression then $c = a_n.$

if not then $c$ is the first element breaking arithmetic progression $(a_1,a_2,…)$.

For example if $A = \left \{3,6,9,12,19,29 \right \}$ then $L(A) = \left \{ 3,6,19 \right \}.$

Now note, that different $3$ or more element sets have different labels, and therefore there are at most $\binom{2018}{3}$. Done.