Track / Stage 4 / 148 of 340 #1048 of 2604

Problem 1048

AMC 12 late, AIME early

Combinatorics Difficulty 4.7 Prove it Bulgarian Mathematical Competitions · Bulgaria

Is there a set $A \supset \{1,2, \ldots, 2004\}$ of positive integers such that the product of its elements is equal to the sum of their squares?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
There exists. Let us take $a_{0}=1$ , $a_{i}=2004!a_{0} a_{1} \ldots a_{i-1}-1$ , $i \geq 1$ and $A_{i}=\{2,3, \ldots, 2004, a_{0}, a_{1}, \ldots, a_{i}\}$ , $i \geq 0$ . Then
$\begin{gathered} \left(\prod_{a \in A_{i-1}} a-\sum_{a \in A_{i-1}} a^{2}\right)-\left(\prod_{a \in A_{i}} a-\sum_{a \in A_{i}} a^{2}\right)-1 \\ \quad=a_{i}^{2}-1-\left(a_{i}-1\right) \prod_{a \in A_{i-1}} a \\ \quad=\left(a_{i}-1\right)\left(a_{i}+1-2004!a_{0} a_{1} \ldots a_{i-1}\right)=0 \end{gathered}$
Hence
$\prod_{a \in A_{n}} a=\sum_{a \in A_{n}} a^{2} \text{ for } n=\prod_{a \in A_{0}} a-\sum_{a \in A_{0}} a^{2}$

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