Assume the $n$ sets $A_1, A_2..., A_n$ are a partition of the set $A=\{1,2,...,29\}$, and the sum of any elements in $A_i$ , $(i=1,2,...,n)$ is not equal to $30$. Find the smallest possible value of $n$.
Problem
Source: China Northern MO 2011 p4 CNMO
Tags: combinatorics
11.05.2024 16:08
$\textbf{Part 1: }$ Does not exist a partition with the requested condition for $n\le2$. $\textbf{1.a: }$ For $n=1$: obvious. $\textbf{1.b: }$ For $n=2$: Consider the set $B=\{1,2,...,7,8\}$. $1+2+...+7+8=36$. Consider a partition of $A$ in $2$ sets $A_1,A_2$. Denote $B_1=A_1\cap B;\;B_2=A_2\cap B$. Then occurs at least one of the properties: a) $B_1$ or $B_2$ contains a subset with the sum of the elements equal to $30$; b) $B_1$ and $B_2$ contain non-empty subsets $C=\{c_1,c_2,...,c_k\}\subset B_1,\;D=\{d_1,d_2,...,d_m\}\subset B_2$ such that $c_1+c_2+...+c_k=d_1+d_2+...+d_m=s\le\dfrac{1+2+...+7+8}{2}=18$. In this case, if $x=30-s\in B_1\subset A_1$, then $c_1+c_2+...+c_k+x=30$, respectively if $x\in B_2\subset A_2$, then $d_1+d_2+...+d_m+x=30$. $\textbf{Proof:}$ Assume $1\in B_1$. $\textbf{Case 1): }|B_1|=1\Longleftrightarrow B_1=\{1\}$. Results $\{4,5,6,7,8\}\subset B_2\subset A_2$ and $4+5+6+7+8=30$ (occurs the property a). $\textbf{Case 2): }|B_1|=2$. Case 2.1: $B_1=\{1,a\},\;2\le a\le 7$. Results: $1\in B_1,\;a\in B_1,\;a+1\in B_2$ and $1+a\; (\textit{as sum of elements from }B_1)=a+1\; (\textit{as element from }B_2)$ (occurs the property b). Case 2.2: $B_1=\{1,8\}$. Results: $\{2,7\}\in B_2$ and $1+8=2+7$ (occurs the property b). $\textbf{Case 3): }|B_1|\ge3$. Case 3.1: If exists $a\in\{2,3,4,5,6,7\}$ such that $a\in B_1,\;a+1\in B_2$, then $\{1,a\}\subset B_1\subset A_1;\;\{a+1\}\subset B_2\subset A_2$ and $1+a=a+1$ (occurs the property b). Case 3.2: If exists $a\in\{4,5,6,7\}$ such that $\{a,a+1,...,7,8\}\subset B_1$ and $\{2,a-1\}\subset B_2$, then $\{1,a\}\subset B_1\subset A_1,\;\{2,a-1\}\subset B_2\subset A_2$ and $1+a=2+(a-1)$ (occurs the property b). Case 3.3: If $B_1=\{1,3,4,5,6,7,8\},\;B_2=\{2\}$, then $\{4,5,6,7,8\}\subset B_1\subset A_1$ and $4+5+6+7+8=30$ (occurs the property a). $\textbf{Part 2: }$ Exists a partition with the requested condition for $n=3$. We will construct a partition of $A$ in $3$ sets $A_1,A_2,A_3$. $m=7$ is the greatest natural number with the property $\sum_{k=1}^mk<30$. Indeed, $\sum_{k=1}^7k=28<30$ and $\sum_{k=1}^8k=36>30$. We choose $A_1=\{1,2,3,4,5,6,7\}$. Results: the sum of the elements of any subset of $A_1$ is smaller than $30$. The smallest $4$ numbers from $A_2\cup A_3$ are $8,9,10,11$ and $8+9+10+11=38>30$. The possible subsets of $A_2\cup A_3$ with the sum of the elements equal to $30$ are: $\bullet\quad$ the triplets $\{8,9,13\},\,\{8,10,12\},\,\{9,10,11\}$; $\bullet\quad$ the pairs $\{8,22\},\,\{9,21\},\,\{10,20\},\,\{11,19\},\,\{12,18\},\,\{13,17\},\,\{14,16\}$. We choose $A_2$ and $A_3$ such that none of these sets contains one of the triplets/pairs presented above. Results a possible partition of $A$: $A_1=\{1,2,3,4,5,6,7\}$; $A_2=\{8,9,10,14,15,17,18,19,23,24,25,26,27,28,29\}$; $A_3=\{11,12,13,16,20,21,22\}$. $\textbf{Conclusion: }$ From the $\textbf{Part 1}$ and the $\textbf{Part 2}$ results: the smallest possible value of $n$ is $n_{min}=3$.