Let $m \ge 2$ be an integer. Find the smallest integer $n>m$ such that for any partition of the set $\{m,m+1,\cdots,n\}$ into two subsets, at least one subset contains three numbers $a, b, c$ such that $c=a^{b}$.
Problem
Source:
Tags:
21.04.2009 17:01
The answer is $ m^{m^{m+2}}$. Consider the set $ S=\{m,m+1,\ldots,m^{m^{m+2}}\}$. Assume that there is a partition of $ S$ into two subsets $ A$ and $ B$ such that no subset contains three number $ a,b,c$ for which $ c=a^b$. Without loss of generality, assume $ m\in A$, thus $ m^m\in B$, $ (m^m)^{m^m}=m^{m^{m+1}}\in A$, $ \left(m^{m^{m+1}}\right)^m=m^{m^{m+2}}\in B$. Note that $ \left(m^m\right)^{m^{m+1}}=m^{m^{m+2}}$ so $ m^{m+1}\in A$. But then $ m,m^{m+1},m^{m^{m+1}}\in A$, contradiction. Now consider the set $ \{m,m+1,\ldots,m^{m^{m+2}}\}$ which is partitioned into $ A=\{m,m+1,\ldots,m^m-1\}\cup\{m^{m^{m+1}},\ldots,m^{m^{m+2}}-1\}$ and $ B=\{m^m,\ldots,m^{m^{m+1}}-1\}$. We have $ m^m>m^m-1$, $ \left(m^m-1\right)^{m^m-1}<\left(m^m\right)^{m^m}=m^{m^{m+1}}$, $ \left(m^{m^{m+1}}\right)^{m^{m^{m+1}}}>m^{m^{m+2}}-1$, so there cannot be $ a,b\in A$ for which $ a^b\in A$. Also for all $ c,d\in B$, $ c^d\ge\left(m^m\right)^{m^m}>m^{m^{m+1}}-1$, so $ c^d\not\in B$. Our proof is now complete.