Minimize sum of guesses to win lottery

Question

Ten boxes are given with $a_1,a_2,a_3,a_4,a_5 ......a_{10}$ number of balls in them respectively .These boxes are randomly ordered but $a_1,a_2 .....a_{10}$ is told.We can arbitrary select a box and guess number of balls in it.If our guess is greater or equal to number of balls in it then we win that box.We are told if our guess is right or wrong , if our guess is wrong then we can change our guess and make another for same box(in this case our previous guess for this box will not be considered ).

Rules - 1.Only final guess for a chosen box will be considered for sum.

2.We can make guess for given box as many times we want and we can select any box any number of time (but only final guess for given box will be considered) till we have not won it.

3.Our guess for given box must be greater than previous guess for same box if we want to guess again for that box.

We can select boxes and guess as many times we want.

We need to select four boxes.

If our sum of guesses is least possible but guarenteed to win four boxes , then we win the lottery.After winning lottery we return boxes for next candidates .

How to choose the boxes to win the lottery ? How to solve this problem in general where $n$ is total number of boxes , $a_1,a_2,....a_n$ and we need to select $k$ boxes to win the lottery in minimum number of guesses possible.

Hint 1 -

suppose two boxes , one with 200,10 balls is given .We need to select 1 box in minimum sum of guesses to win lottery .Answer is 20 .

Hint 2 -

The explanation of above is - first i randomly select any box and i guess if it has 10 balls.Now if the box i selected was really having 10 boxes i win the lottery.But if i did not win then now i know that the box was having 200 balls.Hence i select the other box and again guess 10.Now i win the lottery.sum of guesses (for guaranteed success) = 20.Also it is minimum.

Hint 3 -

Suppose i have two boxes with 99, 101 balls and i need to win one box for winning the lottery.Minimum guess required is 101.First we choose a box and guess 99.If the box was really having 99 balls we win the lottery , else now we know that the box was having 101 balls.Hence for same box we change our guess and we say 101.Answer is 101.

Answer 1

First, assume (without loss of generality) that $a_1\geqslant a_2\geqslant a_3 \dots \geqslant a_n$ (otherwise we can just reindex the sequence).
Now, notice that the set (actually multiset) of guesses $G_m=\{a_m \times m, a_{m+1}, a_{m+2}, \dots, a_{m+k-1}\}$ (here, $a_m \times m$ means $a_m$ repeated $m$ times) is sufficient to win $k$ boxes ($m$ can be any integer from $1$ to $n-k+1$). The algorithm using $G_m$ as the set of guesses is as follows:
1. Pick any box and guess the lowest available value $g$ from $G_m$ (on initial step, it will be $a_{m+k-1}$.
2. If we had won the box, proceed to the next one and remove $g$ from $G_m$. Otherwise, try the next available guess from $G_m$ on the same box (don't remove $g$ from $G_m$ in this case!).
3. If we reached the maximum available value (namely $a_m$) and still not won the box, just discard it and proceed to the next one.
4. After using all $m+k-1$ available guesses, we must win at least $k$ boxes, since there are only $m-1$ boxes whose value is greater then $a_m$ (namely $a_1,a_2,\dots,a_{m-1}$), and only these ones can be discarded, so the other $(m+k-1)-(m-1)=k$ ones should be won.
Now, the only remaining step is to pick an $m$ which gives the lowest possible sum of all guesses: $S = \min\limits_{m}{\sum\limits_{g\in G_m}{g}}$.

Example:

Let $n=10$ and $k=4$ (as stated in the question). Let the values $a_1$ to $a_{10}$ be $1,2,5,10,21,22,23,100,101,102$. The maximum value of $m$ is $10-4+1=7$. So, let's consider the following sets (the sums are shown in parentheses):
$G_1=\{102,101,100,23\} (326)$
$G_2=\{101,101,100,23,22\} (347)$
$G_3=\{100,100,100,23,22,21\} (366)$
$G_4=\{23,23,23,23,22,21,10\} (145)$
$G_5=\{22,22,22,22,22,21,10,5\} (146)$
$G_6=\{21,21,21,21,21,21,10,5,2\} (143)$
$G_7=\{10,10,10,10,10,10,10,5,2,1\} (78)$
So, $G_7$ is the most optimal variant, and the solution is try 1,2,5 and 10 on each box (and if it becomes clear that it's greater than 10, don't guess this box anymore).

Code snippet for the algorithm (Python 3.6+):

 a = [1, 2, 5, 10, 21, 22, 23, 100, 101, 102]
 n = len(a)
 k = 4
 min_sum = None
 a.sort()
 a.reverse()
 for m in range(n - k + 1):
     # m + 1 here due to zero-based indexing
     g = [a[m]] * (m + 1) + a[m+1:m+k]
     print(f"G_{m+1}={g} ({sum(g)})")
     if min_sum is None or sum(g) < min_sum:
         min_sum = sum(g)
 print(f"Min sum is {min_sum}")
 

Answer 2

Lets say we just have $n$ boxes: $a_1,a_2,a_3,a_4,a_5 ......a_n$
I suppose we know values of each $a_x$ but we don't know "which is which" even when we guess any number in it.
First take lowest value, lets say we have values $v_1,v_2,v_3,v_4,v_5 ......v_n$ and lowest value for this moment is $v_{x1}$, second lowest is $v_{x2}$ and so on.
We were also given random $k$ boxes.
But since we don't know which values we choose, there is low probability to win - because for example, there is given $v_{x1}=10$ and $v_{x2}=21$, but in our $k$ boxes is only $v_{x2}$. So our correct strategy must be to ask for 21 and not for 10.
Example:

We are given numbers 10,21,22,23,100,101,102. $k=3$
We blindly choose 21,22,23. Best "SUM" (for guaranteed success) is 23.
We blindly choose 10,100,101. Best "SUM" is 30.
We blindly choose 10,21,22. Best "SUM" is 22.
We blindly choose 21,22,100. Best "SUM" is 44.

I had to read whole text 5 times before I could understand it. If I have wrong approach please clarify rules.