Problem

Source: 2010 Indonesia TST stage 2 test 4 p4

Tags: inequalities, algebra



Given a positive integer $n$ and $I = \{1, 2,..., k\}$ with $k$ is a positive integer. Given positive integers $a_1, a_2, ..., a_k$ such that for all $i \in I$: $1 \le a_i \le n$ and $$\sum_{i=1}^k a_i \ge 2(n!).$$Show that there exists $J \subseteq I$ such that $$n! + 1 \ge \sum_{j \in J}a_j >\sqrt {n! + (n - 1)n}$$