16
$\begingroup$

At time T=0, a cell is placed at the origin. Every second, you can control the cell to divide once (one cell splits into two). After division, you can move the daughter cells one unit distance up, down, left, or right. Since each coordinate point can hold at most one cell, at least one daughter cell must move during each division, and they can't both move in the same direction. If all the up, down, left, and right positions of a cell are occupied, that cell cannot divide at that time.

For example, at T=1, you can have the original cell divide into two, moving to coordinates (0,1) and (1,0) respectively; then at T=2, you can have these two cells divide into four, moving to positions (0,2), (-1,1), (1,1), and (1,-1), and so on.

Given unlimited amount of time, your goal is to achieve the largest possible R, such that there are no cells within the circle of radius R centered at the origin. What is the maximum value of R?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I assume the cells are taken to be point-like (i.e., zero width)? $\endgroup$ Commented Jul 25 at 10:11
  • 6
    $\begingroup$ Does every cell have to divide (if it can) or is it optional at each time step? $\endgroup$ Commented Jul 25 at 14:43
  • 6
    $\begingroup$ Do I have to divide all the cells at every step? Or can I choose which cells to divide? $\endgroup$ Commented Jul 25 at 14:58
  • $\begingroup$ Yes, you can choose which cells to divide. $\endgroup$ Commented Jul 26 at 1:29
  • 2
    $\begingroup$ Previously: Amoebas escaping the prison $\endgroup$ Commented Jul 26 at 22:39

1 Answer 1

Reset to default
6
$\begingroup$

EDIT: Turns out the result below only gives an upper bound (although quite a decent one), and it's not actually possible to reach with actual moves given in the question. Leaving the answer up anyways, since the approach might be useful for others. Thanks to @TimSeifert for pointing this out in the comments.

If you place the initial cell at the origin, and then for every coordinate point (x, y) you calculate their Manhattan distance d = |x| + |y| from the origin and assign a multiplier of $ \frac{1}{2^d} $ to each point, like so

                   1/8
               1/8 1/4 1/8
           1/8 1/4 1/2 1/4 1/8
       1/8 1/4 1/2  1  1/2 1/4 1/8
           1/8 1/4 1/2 1/4 1/8
               1/8 1/4 1/8
                   1/8

then, at every move, the total amount of cell on the grid will stay the same, or increase if you move suboptimally.

This property turns out to be very useful, because if we now add up all the multipliers along the x axis we get 1/2^n + ... 1/4 + 1/2 + 1 + 1/2 + 1/4 ... + 1/2^n which approaches 3 when n approaches infinity, and similarly adding up all the horizontal lines (y = integer constant), we get the same result multiplied by 3, for a sum of

9

units of multiplier over the entire x/y plane.

The original cell starting at the origin will always take (at least) one unit of it, so we're left with a possible maximum of

8 units of empty circle.

That turns out to be a surprisingly small circle. Sorting all the coordinate points by their (cartesian) distance c = $\sqrt{x^2+y^2}$ from the origin, and tallying up their multipliers, we get

 distance c | number of points | sum of multipliers | cumulative sum
 0          | 1                | 1                  | 1
 1          | 4                | 2                  | 3
 sqrt(2)    | 4                | 1                  | 4
 2          | 4                | 1                  | 5
 sqrt(5)    | 8                | 1                  | 6
 2*sqrt(2)  | 4                | .25                | 6.25
 3          | 4                | .5                 | 6.75
 sqrt(10)   | 8                | .5                 | 7.25
 sqrt(13)   | 8                | .25                | 7.5
 4          | 4                | .25                | 7.75
 sqrt(17)   | 8                | .25                | 8.00

This means that with optimal play, all the points at distance 4 or less can be empty, and there will unavoidably be cells at distance

$\mathbf{\sqrt{17}}$, because we can only make arbitrarily many (not infinitely many) moves,

which is thus the radius of the maximal empty circle.

(Disclaimer: all of this of course hinges on the unlikely assumption that I made no mistakes while manually adding all that up :-] )

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ I thought about this approach as well, and I believe that this upper bound, while nontrivial, is still pretty far from the truth. One immediate issue is that you can never have more than two cells on the coordinate axes without having made some non-optimal moves (wrt to this weight system), which already complicated things a bit. When playing around with it, I wasn't even able to clear the full sqrt(10)-circle and going to sqrt(13) seemed definitely hopeless. But I also didn't see any useful improvement to the upper bound, so maybe there might be a way? $\endgroup$ Commented Jul 25 at 18:08
  • $\begingroup$ Also, minor point: The points on the sqrt(17)-circle only contribute a a weight of 1/4, so the total weight up to that point would be exactly 8. But this does not change your bound, since we have only finitely many steps to play with :) $\endgroup$ Commented Jul 25 at 18:09
  • 1
    $\begingroup$ The problem with the axes is definitely something I didn't consider! $\endgroup$ Commented Jul 25 at 18:13
  • 1
    $\begingroup$ For what it's worth, it's fairly straightforward to get all points up to (and including) distance $R=\sqrt{10}$ emptied out. It seems unlikely that $R=4$ can be reached, but $R=\sqrt{13}$ feels within reach. $\endgroup$ Commented Jul 26 at 19:28
  • 1
    $\begingroup$ @Servaes: Could you post your $R = \sqrt 10$ solution? That one went unanswered on the other question (linked in comment on the question). Like Tim, I have tried it quite a bit, without success (though I am SO CLOSE). $\endgroup$ Commented Jul 30 at 15:53

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.