Find the smallest integer $n > 3$ such that, for each partition of $\{3, 4,..., n\}$ in two sets, at least one of these sets contains three (not necessarily distinct) numbers $ a, b, c$ for which $ab = c$. (Alberto Alfarano)
Problem
Source: Oliforum Contest V 2017 p5 https://artofproblemsolving.com/community/c2487525_oliforum_contes
Tags: partition, number theory, Sets
30.09.2021 15:28
We say: a set $X$ of natural numbers has the property $\textbf{P}$ if for each partition of $X$ in two sets, at least one of these sets contains three (not necessarily distinct) numbers $ a, b, c$ for which $ab = c$. For $a=b$, the condition $ab=c$ becomes $a^2=c$. $\textbf{Property P1: }$ the set $T=\{3^1,3^2,3^3,3^4\}$ doesn't have the property $\textbf{P}$. Just consider $T=\{3^1,3^4\}\cup\{3^2,3^3\}$. $\textbf{Property P2: }$ the set $U=\{3^1,3^2,3^3,3^4,3^5\}$ has the property $\textbf{P}$. $U=V\cup W;V\cap W=\phi$. Assume the set $U$ doesn't have the property $\textbf{P}$. WLOG, we can consider $3^1\in V$. $3^1\in V\Longrightarrow 3^2\in W\Longrightarrow 3^4\in V\Longrightarrow \{3^1,3^4\}\subset V\Longrightarrow 3^5\in W\Longrightarrow \{3^2,3^5\}\subset W$. If $3^3\in V\Longrightarrow V=\{3^1,3^3,3^4\}$ and $3^1\cdot3^3=3^4$, contradiction. If $3^3\in W\Longrightarrow W=\{3^2,3^3,3^5\}$ and $3^2\cdot3^3=3^5$, contradiction. Results: our assumption is false, hence the set $U$ has the property $\textbf{P}$. $\textbf{Consequence: }$ $U=\{3^1,3^2,3^3,3^4,3^5\}=\{3,9,27,81,243\}$ has the property $\textbf{P}\Longrightarrow $ $\Longrightarrow \{3,4,5,\dots,242,243\}$ has the property $\textbf{P}$. $\textbf{Property P3: }$ The set $S=\{3,4,5,\dots,241,242\}$ doesn't have the property $\textbf{P}$. We construct the sets $A,B$ such that $S=A\cup B;\;A\cap B=\phi$ and none of these sets contains three (not necessarily distinct) numbers $ a, b, c$ for which $ab = c$. $3\in A\Longrightarrow 9\in B\Longrightarrow 81\in A$. We consider: $A_1=\{3,4,5,6,7,8\}\subset A;\;B_1=\{9,10,11,\dots,79,80\}\subset B$. $A_2=\{ab|a,b\in B_1;\;ab\le242\}=\{81,90,99,100,108,\dots, 240,242\}$. $A=A_1\cup A_2;\;B=S\setminus A$. The set $A$ doesn't have the property $\textbf{P}$: Case 1: $a,b\in A_1\Longrightarrow 9\le ab\le 64\Longrightarrow ab\in B_1\Longrightarrow ab\notin A$. Case 2: $a\in A_1;b\in A_2\Longrightarrow ab\ge 3\cdot81>242\Longrightarrow ab\notin A$. Case 3: $a,b\in A_2\Longrightarrow ab\ge 81^2>242\Longrightarrow ab\notin A$. The set $B$ doesn't have the property $\textbf{P}$: Case 1: $a,b\in B_1$ and $ab\le242\Longrightarrow ab\in A_2\Longrightarrow ab\notin B$. Case 2: $a,b\in B_1$ and $ab>242\Longrightarrow ab\notin B$. Case 3: $a,b\in B\setminus B_1\Longrightarrow ab\ge 82^2>242\Longrightarrow ab\notin B$. Case 4: $a\in B_1;b\in B\setminus B_1\Longrightarrow ab\ge 9\cdot82>242\Longrightarrow ab\notin B$. $\textbf{Final conclusion:}$ $n=243$ is the smallest integer such that, for each partition of $\{3, 4,..., n\}$ in two sets, at least one of these sets contains three (not necessarily distinct) numbers $ a, b, c$ for which $ab = c$.