2
$\begingroup$

The game is a function of an integer $n\geq 1$ and a number $t\in(0,n)$.

An adversary picks $n$ numbers in $[0,1]$ whose total sum is $t$. You divide the numbers into two subsets and the adversary picks one of them. Your score is the sum of numbers in the remaining subset.

What is the largest sum $s(n,t)$ that you can guarantee?

  • $s(1,t) = 0$ - one subset will always be empty.
  • $s(2,t) = \max(0, t-1)$ - each subset will contain one number. The adversary will try to make them as unbalanced as possible, and the worst he can do is make the larger number equal 1 so you get the smaller one which is $t-1$.
  • $s(3,t) = \min(t/3, \max(t-1,0))$ - the optimal division for you is apparently to put the two smallest numbers in one subset and the largest number in the other subset, so the adversary will try to make these subsets as unbalanced as possible. One way to do it is to make all numbers equal, in which case your score is $t/3$; another way is to make the largest number 1, in which case your score is $t-1$. The adversary will pick the worst of these two options.

For $n\geq 4$, the game becomes much more complex to analyze, since there are many different possible partitions. Do you see any pattern? Any way to make it simpler?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.