$A_1, A_2,\dots A_k$ are different subsets of the set $\{1,2,\dots ,2016\}$. If $A_i\cap A_j$ forms an arithmetic sequence for all $1\le i <j\le k$, what is the maximum value of $k$?
Problem
Source: Turkey TST 2016 P7
Tags: arithmetic sequence, combinatorics
12.04.2016 04:53
anyone please??
20.04.2016 07:38
Look at taiwan 2000, 5th problem
22.10.2018 21:49
We claim that the answer is $\sum_{k=0}^3 \binom{2016}{k}$. First, check that, if $|A_k|=1$, for some $k$, then for any $j$, $|A_j\cap A_k|\leq 1$ is trivially an arithmetic sequence. Similarly, if $|A_k|=2$, then no matter which $\ell$ we take, $|A_\ell \cap A_k|\leq 2$, which always is an arithmetic sequence. Furthermore, by considering all $3-$element subsets, in addition to singletons and pairs, we obtain that $k\geq \sum_{k=0}^3 \binom{2016}{k}$. Let's now prove the converse. For this, we shall prove that, among $A_1,A_2,\dots,A_k$, we can have at most $\binom{2016}{3}$ sets with number of elements at least $3$. In order to prove this fact, take any $A=\{a_1,a_2,\dots,a_n\}$ (with $a_1<\cdots<a_n$), and construct a function $f(A)=(a_1,a_2,b)$ where $b$ is the smallest number in $A$ that breaks the condition of being an arithmetic sequence. In case no such $b$ exists, that is, entries of $A$ form an arithmetic progression, take $b=a_n$. Now, note that, we can have at most $\binom{2016}{3}$ such triples. Therefore, if the number of sets with cardinality at least $3$ (among $k$), is greater than or equal to $\binom{2016}{3}+1$, then there are two sets $A,A'$ for which, $f(A)=f(A')$. Furthermore, $\{a_1,a_2,b\}\subset A\cap A'$. If $A$ is not an arithmetic sequence, then by definition $A'$ is not either, hence, neither their intersection. If $A$ is an arithmetic progression, and also $A'$, we must have that $a_1,a_2$ are members of this progression, and also $a_n$, hence, entire $A$ must belong to the progression, namely, $A\subset A'$ must hold. However, if $A'$ is not an arithmetic progression, then $b$ should have been distinct from $a_n$, hence it is an arithmetic progression. But in this case, since $A'\neq A$, we must have $A'\supsetneq A$, hence $f(A')$ should have been $(a_1,a_2,a_{n'})$ where $a_{n'}$ is the last element of $A'$, a contradiction.