Maths Olympiad Prep

Library / /3 of 32

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 ABA \subseteq B and
xBx=xBx2. \prod_{x \in B} x = \sum_{x \in B} x^2.

Solution

For any finite set SS of positive integers, let
D(S)=xSxxSx2. 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=maxAm = \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)kk(m+k)2D(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 AkA'_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{xAkx1}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
maxAk<xAkx2=xAkxD(Ak)<xAkx. \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, xAkx1>maxAk\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)=xAk+1xxAk+1x2=xAkx(xAkx1)xAkx2(xAkx1)2=xAkxxAkx21=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,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.