Optimizing the number of robots to be used for a certain task

142 Views Asked by At

We have $N$ buttons numbered $1$,$2$ .. $N$. Our aim is to press each of the buttons at least once in the minimum time possible. For that purpose we choose $m$ robots. These robots can press one of the buttons in each second. But when two or more robots try to press the same button at the same time, that button won't be pressed (the robots will know that the button couldn't be pressed). Under the restriction that all the robots should be coded identically (i.e. they should execute the same instructions), what value of $m$ will you choose and how will you code them?

For example, if we choose $m=1$ and instruct the robot to press the $i$th button in the $i$th second, it will take a total of $N$ seconds before all the buttons are pressed. If we choose $m=2$ and instruct the robots to press button $1$ or $2$ uniformly at random until they have successfully pressed one of those(if one of them is successful in pressing one, then the other is automatically successful in pressing the other), and then sequentially press every other button (for example, if the robot succeeded in pressing button $1$, then it will try(successfully) to press the buttons numbered $3$, $5$,.. in the next seconds), then it will take an average time of $2+\frac{N-2}{2}$ seconds before each button is pressed.

1

There are 1 best solutions below

4
On

For small $N$, the details of the optimal algorithm seem likely to be complicated; they're probably best determined by dynamic programming. However, for large $N$, the following algorithm covers all buttons in $3$ seconds asymptotically almost surely.

Take a very large number of robots, i.e. $m\gg N$, and let them press any of the buttons with probability $p=1/m$ each, and no button with probability $1-Np=1-N/m$. (This last probability is non-negative since $m\gg N$.) The probability that a particular button is pressed exactly once, and thus the expected fraction of buttons that get pressed exactly once, is

$$ mp(1-p)^{m-1}=m\cdot\frac1m\left(1-\frac1m\right)^{m-1}=\left(1-\frac1m\right)^{m-1}\to_{m\to\infty}\frac1{\mathrm e}\;. $$

For large $N$, the distribution is sharply peaked around this expected value, so the fraction of buttons successfully pressed is almost certain to be greater than $1/3$. Now let the robots that successfully pressed a button press further buttons according to some predefined scheme. (For instance, let the robots plan their actions by virtually acting in succession in the order of the numbers of the buttons they pressed in the first second, and let each robot press the button with the lowest number that hasn't been pressed either in a previous second or in a previous planning step.)