Maths Olympiad Prep

Library / USA IMO /3 of 29

USA IMO

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it United States

Let AA be a finite set of positive integers. Prove that there exists a finite set BB of positive integers such that A⊆BA \subseteq B and
∏x∈Bx=∑x∈Bx2. \prod_{x \in B} x = \sum_{x \in B} x^2.

Solution

For any finite set SS of positive integers, let
D(S)=∏x∈Sx−∑x∈Sx2. D(S) = \prod_{x \in S} x - \sum_{x \in S} x^2.
If D(A)=0D(A) = 0, then we take B=AB = A.

If D(A)<0D(A) < 0, then let m=max⁡Am = \max A. Write Ak′=A∪{m+1,m+2,…,m+k}A'_k = A \cup \{m+1, m+2, \dots, m+k\}. Then there is a positive integer kk such that
−D(A)<(m+1)k−(k3+2mk2+m2k)=(m+1)k−k(m+k)2≤D(Ak′)−D(A) \begin{aligned} -D(A) &< (m+1)^k - (k^3 + 2mk^2 + m^2k) \\ &= (m+1)^k - k(m+k)^2 \le D(A'_k) - D(A) \end{aligned}
and hence D(Ak′)>0D(A'_k) > 0. Thus, it suffices to find a finite set BB containing Ak′A'_k such that D(B)=0D(B) = 0, because then BB contains AA as well. This reduces the problem to the next and final case.

Assume that D(A)>0D(A) > 0, and write A0=AA_0 = A. Define Ak+1=Ak∪{∏x∈Akx−1}A_{k+1} = A_k \cup \{\prod_{x \in A_k} x - 1\} recursively for k=0,1,…,D(A)−1k = 0, 1, \dots, D(A) - 1. If D(Ak)>0D(A_k) > 0, we have Ak≠{1}A_k \ne \{1\} and hence
max⁡Ak<∑x∈Akx2=∏x∈Akx−D(Ak)<∏x∈Akx. \max A_k < \sum_{x \in A_k} x^2 = \prod_{x \in A_k} x - D(A_k) < \prod_{x \in A_k} x.
Therefore, ∏x∈Akx−1>max⁡Ak\prod_{x \in A_k} x - 1 > \max A_k and Ak+1A_{k+1} has one more element than AkA_k. It follows that
D(Ak+1)=∏x∈Ak+1x−∑x∈Ak+1x2=∏x∈Akx(∏x∈Akx−1)−∑x∈Akx2−(∏x∈Akx−1)2=∏x∈Akx−∑x∈Akx2−1=D(Ak)−1. \begin{align*} D(A_{k+1}) &= \prod_{x \in A_{k+1}} x - \sum_{x \in A_{k+1}} x^2 \\ &= \prod_{x \in A_k} x (\prod_{x \in A_k} x - 1) - \sum_{x \in A_k} x^2 - (\prod_{x \in A_k} x - 1)^2 \\ &= \prod_{x \in A_k} x - \sum_{x \in A_k} x^2 - 1 \\ &= D(A_k) - 1. \end{align*}
Because D(A0)>0D(A_0) > 0, it follows that D(Ak)=D(A)−k>0D(A_k) = D(A) - k > 0 for k<D(A)k < D(A) and that D(AD(A))=0D(A_{D(A)}) = 0. Taking B=AD(A)B = A_{D(A)} completes the proof.

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

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