Competition problem — Number theory

Library / /153 of 264

Number theory Difficulty 5.9 AIME, harder Prove it Romania

Let $A = \{1, 3, 3^2, 3^3, \dots, 3^{2014}\}$ . We obtain a partition of $A$ if $A$ is written as a disjoint union of nonempty subsets.

a) Prove that there is no partition of $A$ such that the product of elements in each subset is a square.

b) Prove that there exists a partition of $A$ such that the sum of elements in each subset is a square.

Solution

a) Assume that such a partition exists. Then the product of all elements of $A$ must be a square as well. But this equals $3^{1+2+3+\dots+2014} = 3^{2015 \cdot 1007}$ , obviously not a square.

b) Observe that $3^{2n} + 3^{2n+1} = (3^n \cdot 2)^2$ , hence a possible partition is
$A = \{1,3\} \cup \{3^2, 3^3\} \cup \dots \cup \{3^{2012}, 3^{2013}\} \cup \{3^{2014}\}.$

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.