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

Hint: Consider \(\displaystyle s(I)-s(J)\) for all pairs \(\displaystyle I,J\subset \{1,2,\ldots,n\}\) with \(\displaystyle s(I)=2019\).

  Solution