Library / /639 of 740

, 2015

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Call a set of positive integers good if there is a partition of it into two sets $S$ and $T$ , such that there do not exist three elements $a, b, c \in S$ such that $a^{b}=c$ and such that there do not exist three elements $a, b, c \in T$ such that $a^{b}=c$ ( $a$ and $b$ need not be distinct). Find the smallest positive integer $n$ such that the set $\{2,3,4, \ldots, n\}$ is not good.

Solution

Solution:

First, we claim that the set $\{2,4,8,256,65536\}$ is not good. Assume the contrary and say $2 \in S$ . Then since $2^{2}=4$ , we have $4 \in T$ . And since $4^{4}=256$ , we have $256 \in S$ . Then since $256^{2}=65536$ , we have $65536 \in T$ . Now, note that we cannot place $8$ in either $S$ or $T$ , contradiction.

Hence $n \leq 65536$ . And the partition $S=\{2,3\} \cup \{256,257, \ldots, 65535\}$ and $T=\{4,5, \ldots, 255\}$ shows that $n \geq 65536$ . Therefore $n=65536$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.