International Mathematics Competition
for University Students
2019

IMC2019: Day 2, Problem 8

Problem 8. Let \(\displaystyle x_1,\ldots,x_n\) be real numbers. For any set \(\displaystyle I\subset \{1,2,\ldots,n\}\) let \(\displaystyle s(I)=\sum\limits_{i\in I} x_i\). Assume that the function \(\displaystyle I\mapsto s(I)\) takes on at least \(\displaystyle 1.8^n\) values where \(\displaystyle I\) runs over all \(\displaystyle 2^n\) subsets of \(\displaystyle \{1,2,\ldots,n\}\). Prove that the number of sets \(\displaystyle I\subset \{1,2,\ldots,n\}\) for which \(\displaystyle s(I)=2019\) does not exceed \(\displaystyle 1.7^n\).

Proposed by Fedor Part and Fedor Petrov, St. Petersburg State University

Solution. Choose disctint sets \(\displaystyle I_1,\ldots,I_A\subset \{1,2,\ldots,n\}\) where \(\displaystyle {A\geq 1.8^n}\), and let \(\displaystyle J_1,\ldots,J_B\subset \{1,2,\ldots,n\}\) be all sets so that \(\displaystyle S(J_i)=2019\); for the sake of contradiction, assume that \(\displaystyle {B\geq 1.7^n}\).

Every set \(\displaystyle I\subset \{1,2,\ldots,n\}\) can be identified with a \(\displaystyle 0-1\) vector of length \(\displaystyle n\): the \(\displaystyle k\)th coordinate in the vector is \(\displaystyle 1\) if \(\displaystyle k\in I\). Then \(\displaystyle s(I)=\langle I,X\rangle\), where \(\displaystyle X=(x_1,\ldots,x_n)\) and \(\displaystyle \langle \cdot,\cdot\rangle\) stands for the usual scalar product.

For all ordered pairs \(\displaystyle (a,b)\in \{1,\ldots,A\}\times \{1,\ldots,B\}\) consider the vector \(\displaystyle I_a-J_b \in \{-1,0,1\}^n\). By the pigeonhole principle, since \(\displaystyle AB\ge(1.8\cdot1.7)^n>3^n\), there are two pairs \(\displaystyle (a,b)\) and \(\displaystyle (c,d)\) such that \(\displaystyle I_a-J_b=I_c-J_d\). Multiplying this by \(\displaystyle X\) we get \(\displaystyle s(I_a)-2019=s(I_c)-2019\); that implies \(\displaystyle a=c\). But then \(\displaystyle J_b=J_d\), that is, \(\displaystyle b=d\), and our pairs coincide. Contradiction.