Maximising largest integer on a list given mean, median and mode
A list of $10$ positive integers has a mean of $11$, a median of $10$ and a unique mode of $7$. What is the largest possible value of an integer in the list?
In an ascending (albeit not strictly ascending) list of ten positive integers ($n_1$ to $n_{10}$), the last will be the highest, and you want to make the earlier ones as small as possible. The given conditions force $\sum_{i=1}^{10}n_i = 110$ and $n_5 + n_6 = 20$. In addition, at least two values have to be $7$.
With a bit of trial and error I deduced the optimal list is probably $1, 2, 7, 7, 9, 11, 12, 13, 14, 34$ with the answer being $34$. But I'm dissatisfied with this as I can't be sure it's the best solution and I'm wondering if there's a more systematic way of approaching the problem (short of an exhaustive search).
Thank you.
$\endgroup$ 22 Answers
$\begingroup$The condition $n_5 + n_6 = 20$ implies that $n_5 \le 10 \le n_6$, from which we deduce that the value $7$ occurs at least twice and at most five times, all of which must precede $n_6$.
From this, we consider two cases: first, when $n_5 = 7$, and second, when $n_5 > 7$. The case $n_5 < 7$ is impossible since we require $n_6 \ge 10$.
Case 1: $(n_5 = 7)$This implies $n_6 = 13$, hence $13 \le n_7 \le n_8 \le n_9 \le n_{10}$. Since the goal is to maximize $n_{10}$ for a fixed total $T = 110$, we must minimize the other values of $n_i$; i.e., $n_{i+1} \in \{n_i, n_i + 1\}$ for each $i = 6, 7, 8$. Consequently $n_9$ is at least $13$ and at most $16$.
On the other end, we must also have at least $n_4 = 7$, and $1 \le n_1 \le n_2 \le n_3 \le 7$. If we have $n_3 < 7$, then all other $n_i$ are unique and this forces the choice$$(1, 2, 3, 7, 7, 13, 14, 15, 16, 32).$$If we have $n_3 = 7$, this is only slightly better since the minimal choice becomes$$(1, 1, 7, 7, 7, 13, 13, 14, 14, 33).$$Increasing the frequency of $7$ saved $1$ from the low end and $4$ on the high end but cost $4$ by changing $n_3 = 3$ to $n_3 = 7$. It is obvious that allowing $n_2 = 7$ or $n_1 = 7$ will be inferior to the above, since at most $2$ more units can be saved from the high end but at a minimum cost of $6$ on the low. Therefore the maximum $n_{10}$ attained in this case is $33$.
Case 2: $(n_5 > 7)$We must have at least two of $n_1, n_2, n_3, n_4$ equal to $7$, and $n_5 \in \{8, 9, 10\}$. If exactly two of the $n_i$ equal $7$, then $n_5 \ne 10$, and the minimum is attained for the choices $(1, 2, 7, 7, n_5, 20 - n_5, 21 - n_5, 22 - n_5, 23 - n_5, 7 + 3n_5)$; thus the choice $n_5 = 9$ gives $n_{10} = 34$, with the sequence $$(1, 2, 7, 7, 9, 11, 12, 13, 14, 34).$$
If more than two of the $n_i$ equal $7$, then we may choose $n_5 = 10$, and we have for example $$(1, 7, 7, 7, 10, 10, 11, 11, 12, 34)$$ for three repetitions, and $$(7, 7, 7, 7, 10, 10, 10, 11, 11, 30)$$ for four repetitions, which is inferior.
Therefore, the maximum is $n_{10} = 34$, attained for exactly those two sequences described above.
$\endgroup$ 2 $\begingroup$We wish to minimize the sum of the other $9$ numbers $a_1\leq \dots \leq a_9$ with the condition $a_5+a_6 = 20$ and the condition that $7$ appears more times than the others, the sum we got is $76$, lets prove less is not possible.
If $a_5$ is $7$ then $a_6$ is $13$ and so $a_6+a_7+a_8+ a_9 \geq 4\times 13 = 52$, so the sum of $a_1+a_2+\dots+a_5$ would have to be less than $24$. If $a_3,a_4,a_5= 7$ the minimum sum of $a_1+\dots + a_5$ is $1+1+7+7+7 = 23$ but since we can't have all of $a_6,\dots,a_{9} = 13$ this becomes impossible. Hence we must have $a_3\neq 7$ and the minimum is greedily $1+2+3+7+7+13+14+15+16 = 78$.
Hence $a_5> 7$. It can now be seen that if we select how many $7$'s we want then the solution can be formed greedily by taking the smallest numbers possible and setting $a_4 = 7$.
If there are two $7$'s the solution is $1,2,7,7,9,10,11,12,13=76$
If there are three $7$'s the solution is $1,7,7,7,10,10,11,11,12 = 76$
If there are four $7$'s the solution is $7,7,7,7,10,10,10,11,11 = 80$
$\endgroup$ 5
