Here is the question: Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ball and the urn we selected will need to be empty. Moreover, we can select what urns the balls go into. We have some extra urns if needed (I have not used them though). Our reward is the number of balls from the urn we select for redistribution.

My goal is to find the algorithm (in loose terms, no need for pseudo-code just the idea) which allows to have the highest average reward as the number of itterations goes to infinity. This will imply that if I have at first reward $a_1 , \cdots , a_l$ and then $b$ for infinity, the average will be $b$ as the itterations go to infinity.

So far my best result is an average reward of $r$ for $k=\frac{r(r+1)}{2}$. So this implies that the function of the average reward for $k$ balls is $\frac{-1 + \sqrt{1+8k}}{2}$. Is this the bets possible result?

My reasoning is that for say $k=66$ after a finite number of iterations, I will have $0$ balls in all the urns, except for the last 11, where I have consecutively this distribution: $(0, \cdots , 0 ,11,10,9,8,7,6,5,4,3,2,1)$ So then I can select the urn with $11$ balls and distribute them along all the ones in front and the first urn, we can then always have a reward of $11$. I am not convinced this is the best method though, any insight would help!

Is this problem commonly known? (I posted this on mathstackexchange, but I was told this is a better place for this question)

  • $\begingroup$ Although your post mentions "algorithm", this is a question more suitable to Mathematics. You are not really interested in an algorithm, you are interested in the best strategy in this game. $\endgroup$ May 1 '19 at 19:44
  • $\begingroup$ @YuvalFilmus What is the difference between an algorithm and a strategy to solve a problem? $\endgroup$ May 1 '19 at 19:48
  • $\begingroup$ It's the same thing. Using the word algorithm suggests that there is no general solution to the problem (and so we need the algorithm to find a solution for a given instance), whereas in your case it might well exist. Moreover, an input to your algorithm consists of just an integer. While there are some algorithms like that (for example, primality testing and factoring), typically the input is more substantial. In your case, "algorithm" would suggest an arbitrary starting point, rather than just $k$ bins with one ball each. $\endgroup$ May 1 '19 at 19:50
  • $\begingroup$ @YuvalFilmus So it seems this question would fit in both forums. In my post, I explained part of the algorithm in so far as it justified my bound for returns. So I am interested in what strategy for an input $k$ of my problem would yield the largest number based on the constraints I imposed in particular what would be one that beats my result. Some algorithms have small rewards over some periods of time with occasional large rewards, my algorithm provides a constant reward for all iterations after a finite time which leads me to think it is not an optimal solution to the problem. $\endgroup$ May 1 '19 at 19:59
  • $\begingroup$ I checked your conjecture empirically and it holds for small $r$. More generally, the answer is A004201 (or A061885) divided by $\lceil r \rceil$: for $k=1,2,\ldots$, it is $1, 3/2, 2, 7/3, 8/3, 3, 13/4, 7/2, 15/4, 4, \dots$. Multiplied by $1,2,2,3,3,3,4,4,4,4$, we get $1,3,4,7,8,9,13,14,15, 16$. $\endgroup$ May 1 '19 at 20:52