If the set $S = \{1,2,3,…,16\}$ is partitioned into $n$ subsets, there must be a subset in which elements $a, b, c$ (can be the same) exist, satisfying $a+ b=c$. Find the maximum value of $n$.
Problem
Source: China Northern MO 2015 grade 10 p4 CNMO
Tags: number theory, combinatorics
08.05.2024 06:19
The answer is $max(n) = 3.$ We first see that $n \leq 3$. For this consider the partition:$$A_1 = \{1, 5, 9, 13\}$$$$A_2 = \{2, 6, 10, 14\}$$$$A_3 = \{3, 7, 11, 12\}$$$$A_4 = \{4, 8, 15, 16\}.$$We now show that n=3 is achievable. Consider the complete graph $K_{17}$ of order 17 with the vertices labelled $1, 2, 3,\cdots 17.$ We assign three colors $c_1, c_2, c_3$ to the sets $A_1, A_2, A_3$ respectively and color the edge $ij$ of $K_17$ by $c_k$ if $|j - i| \in A_k.$ $\textcolor{red}{Claim} :-$ There is a monochromatic triangle. $\textcolor{blue}{Proof} :-$ Consider the vertex $A_1.$ The other 16 vertices are connected to it. Since $16 = 3*5 +1,$ at least $5+1=6$ of these edges must have the same color by the pigeonhole principle. WLOG, let this color be $c_1$ and these vertices be $2, 3, 4, 5, 6, 7.$ If some edge connecting two of these vertices is of color $c_1,$ we are done. Otherwise only two colors are used to color the edges of this subgraph $K_6.$ Since $5 = 2*2 +1,$ again by the pigeonhole principle, at least $2+1=3$ edges connecting 3 vertices to $A_2$ must have the same color, which WLOG be $c_2.$ If one edge among them has color $c_2,$ there is a monochromatic triangle. Otherwise those three vertices will from a monochromatic triangle. Hence there is a monochromatic triangle. Let it's vertices be $i, j ,k \text{with} i < j < k.$ So $j-i, k-j, k-i \in A_k$ for some k. Since $(k-j) + (j-i) = k-i,$ A_k has three elements $a, b, c$ with $a+b=c,$ as desired.