5
$\begingroup$

A spiderweb is a square with $100 \times 100$ nodes. $100$ flies caught into the web stacked at $100$ different nodes. A spider which was originally at the corner of the web crawls from a node to an adjacent node counting moves and eating flies on its way. Can the spider eat all flies in no more than $2100$ moves? or $2000$ moves?

Thanks in advance.

$\endgroup$
  • 3
    $\begingroup$ Well, if all flies are on 100 nodes side by side, (one column f.e.) it can eat them in 100 moves. But i don't think that is what you meant. Please edit your question to remove ambiguity. $\endgroup$ – SAJW Oct 15 '16 at 5:10
  • 1
    $\begingroup$ I think the question is fairly unambiguous. (And interesting, although at present I have no idea how to solve it.) $\endgroup$ – copper.hat Oct 15 '16 at 5:25
  • 2
    $\begingroup$ Is the spiderweb a rectangular grid? 100 x100 nodes each connected with a line up, down, left, and right (except for boundary nodes) $\endgroup$ – Thanassis Oct 15 '16 at 6:17
  • 1
    $\begingroup$ @copper.hat the question is "Can the spider eat all flies in no more than 2100 moves? or 2000 moves?" and that can be answered with YES, in 100 moves. You see the ambiguity now? Because he probably means "what is the maximum number of (perfect) moves" $\endgroup$ – SAJW Oct 15 '16 at 6:36
  • $\begingroup$ Are you asking if the spider can always eat all the flies in 2100 moves regardless of placement? And can the spider move diagonally? $\endgroup$ – Morgan Rodgers Oct 16 '16 at 11:33
4
$\begingroup$

As has been pointed out, your question is very unclear. In my answer I shall assume that you start at the corner $O$ of an $n \times n$ square grid of nodes and you can only move along edges between (orthogonally) adjacent nodes. Then the maximum number of moves you need to reach any given set of $n$ target nodes in the grid is at least $(r^3+2s-r)$ and at most $(2ns-s-1)$, where $r = \lfloor\sqrt{n}\rfloor$ and $s = \lceil\sqrt{n}\,\rceil$. Note that both bounds are $Θ(n \sqrt{n})$ as $n \to \infty$.

Firstly, if the target nodes include an $r \times r$ subarray of nodes with spacing of $r$ nodes between each row or column, positioned as far from $O$ as possible (*), then you need at least $r$ moves to get from one node in the subarray to another, and at least $2s$ moves to get to the first node in the subarray, and hence you need a total of at least $(r^2-1)r+2s = r^3+2s-r$ moves.

Secondly, we can always divide the grid into $s$ rectangular subgrids in a vertical stack (each having width $n$ and height at most $s$). We can move through the subgrids one at a time, from the closest to the furthest from $O$, and in each subgrid we visit the target nodes in that subgrid in order of their horizontal position, starting and ending at nodes on the left/right boundaries, alternating between going from left to right and going from right to left each time we go to the next subgrid. We can complete each subgrid using at most $(n-1)$ horizontal moves and $k(s-1)$ vertical moves, where $k$ is the number of target nodes in the subgrid. We can traverse between subgrids using at most $(n-1)$ vertical moves. Therefore we need at most $(s+1)(n-1)+n(s-1) = 2ns-s-1$ moves.

(*) In case it is not clear enough, we are considering the case when the target nodes include $r^2$ nodes placed in a square configuration where adjacent target nodes are $r$ moves away. Of course we want to place this configuration as far from $O$ as possible. One can get a slightly better lower bound by adding in the $(n-r^2)$ leftover nodes somewhere, but I am too busy to work out the details, and they don't matter much.

$\endgroup$
  • $\begingroup$ I can't follow your arguments. You are talking about a subarray but in the problem there is no array mentioned. So of what array is your subarray a subarray? Array isn't a mathematical term. I think you are talking about an $r\times r$- matrix $\left((x_{i,j},y_{i,j})\right)_{i=1,\ldots n,j=1, \ldots n}$ of grid points with a special property that have stacked flies . What property? $\endgroup$ – miracle173 Oct 17 '16 at 7:48
  • $\begingroup$ @miracle173: I said "if". See thefreedictionary.com/array for "array"; "mathematical" is not a mathematical term either. What you call "special property" was already specified as "with spacing of $r$ nodes between each row or column, positioned as far from $O$ as possible". All we need to show a lower bound is to construct a configuration of target nodes that takes some number of moves at least. Any set of target nodes that contains the described array will take $r^3+2s-r$ moves at least. $\endgroup$ – user21820 Oct 17 '16 at 7:53
  • $\begingroup$ Of course "mathematical" is not a mathematical term but it is a term of the meta language. But it seems that array is a synonym for matrix. I think you are talking about $\left\{(s+i\cdot r,s+j\cdot r)\mid i=0,\ldots n-1,j=0, \ldots n-1\right\}$. $\endgroup$ – miracle173 Oct 17 '16 at 8:39
  • $\begingroup$ @miracle173: The indices cannot range all the way from $0$ to $(n-1)$. Remember that you can only guarantee to fit $r$ rows and $r$ columns, so $i,j < r$. Otherwise yes that's the set of nodes, if your original grid was in the Cartesian plane and with coordinates in the range $[0..n-1]$. $\endgroup$ – user21820 Oct 17 '16 at 8:44
  • 1
    $\begingroup$ @miracle173: Yep. By the way, if your "meta-language" is the one used in mathematical logic, then no "mathematical" is not a term there either. And if your "meta-language" is so broad as to be able to refer to anything in any mathematical activity, then every English word is up for grabs too. After all, nearly every word in your comments are English words, not mathematical terms, such as "it" and "is" and "a". My point was that we shouldn't arbitrarily impoverish our language unless aiming for formalized proofs. Feel free to continue at chat.stackexchange.com/rooms/44058/logic. =) $\endgroup$ – user21820 Oct 17 '16 at 8:50
3
$\begingroup$

Not a proof, but I decided to test out the problem with Mathematica to get an idea of what a typical case might be. Here's my main code:

n=100;
Flies = Union[{{0, 0}}, Table[{RandomInteger[n-1]+1, RandomInteger[n-1]+1}, {i, 1, n}]]
Hunt = First[FindShortestTour[Flies, DistanceFunction -> ManhattanDistance]]

After running it inside a loop $2000$ times, I have the following results

Average Tour Length = 1044.62
Max Tour Length     = 1182

(The minimum Tour Length would be $100$ moves.)


Edit:

The tour lengths found aren't truly optimal unless using Method -> "IntegerLinearProgramming" as an argument for FindShortestTour. However, this is much slower. The optimal tours are roughly $100$ moves better.


Examples of longer paths

Example 1: Evenly spaced.

Set of flies:

{{0, 0}, {50, 50}, {0, 11}, {0, 22}, {0, 33}, {0, 44}, {0, 55}, {0, 66}, {0, 77}, {0, 88}, {0, 99}, {11, 0}, {11, 11}, {11, 22}, {11, 33}, {11, 44}, {11, 55}, {11, 66}, {11, 77}, {11, 88}, {11, 99}, {22, 0}, {22, 11}, {22, 22}, {22, 33}, {22, 44}, {22, 55}, {22, 66}, {22, 77}, {22, 88}, {22, 99}, {33, 0}, {33, 11}, {33, 22}, {33, 33}, {33, 44}, {33, 55}, {33, 66}, {33, 77}, {33, 88}, {33, 99}, {44, 0}, {44, 11}, {44, 22}, {44, 33}, {44, 44}, {44, 55}, {44, 66}, {44, 77}, {44, 88}, {44, 99}, {55, 0}, {55, 11}, {55, 22}, {55, 33}, {55, 44}, {55, 55}, {55, 66}, {55, 77}, {55, 88}, {55, 99}, {66, 0}, {66, 11}, {66, 22}, {66, 33}, {66, 44}, {66, 55}, {66, 66}, {66, 77}, {66, 88}, {66, 99}, {77, 0}, {77, 11}, {77, 22}, {77, 33}, {77, 44}, {77, 55}, {77, 66}, {77, 77}, {77, 88}, {77, 99}, {88, 0}, {88, 11}, {88, 22}, {88, 33}, {88, 44}, {88, 55}, {88, 66}, {88, 77}, {88, 88}, {88, 99}, {99, 0}, {99, 11}, {99, 22}, {99, 33}, {99, 44}, {99, 55}, {99, 66}, {99, 77}, {99, 88}, {99, 99}}

Optimal Tour Length: $1110$

Optimal Tour:

Graph 1

Example 2: Randomly generated then refined.

Set of flies:

{{0, 0}, {1, 48}, {3, 68}, {4, 39}, {5, 96}, {77, 70}, {6, 51}, {23, 89}, {89, 36}, {8, 64}, {10, 17}, {10, 48}, {22, 100}, {68, 31}, {59, 80}, {15, 42}, {25, 16}, {16, 54}, {19, 12}, {30, 92}, {21, 48}, {22, 63}, {22, 69}, {22, 79}, {24, 55}, {25, 84}, {26, 73}, {25, 42}, {75, 52}, {12, 72}, {30, 44}, {30, 82}, {76, 14}, {32, 10}, {32, 25}, {32, 59}, {35, 76}, {36, 38}, {67, 84}, {37, 56}, {37, 99}, {38, 12}, {39, 4}, {39, 87}, {40, 26}, {42, 69}, {43, 44}, {44, 31}, {44, 80}, {45, 98}, {46, 13}, {66, 0}, {47, 53}, {38, 31}, {49, 25}, {49, 67}, {51, 94}, {53, 57}, {56, 22}, {58, 51}, {54, 34}, {60, 42}, {61, 65}, {62, 8}, {64, 18}, {65, 58}, {67, 5}, {67, 70}, {69, 21}, {69, 56}, {1, 30}, {72, 7}, {15, 28}, {72, 63}, {74, 23}, {49, 34}, {75, 41}, {69, 48}, {76, 75}, {59, 92}, {80, 32}, {80, 56}, {80, 82}, {81, 44}, {84, 39}, {85, 2}, {82, 22}, {25, 93}, {88, 80}, {90, 47}, {91, 70}, {23, 37}, {93, 98}, {53, 0}, {97, 0}, {98, 41}, {98, 62}, {50, 74}, {99, 84}, {100, 31}, {28, 98}}

Optimal Tour Length: $1252$

Optimal Tour:

Graph 2

(Note: This tour has an estimated length of $1360$ using the default (non-optimal) method used in the first part.)

$\endgroup$
  • $\begingroup$ mmh, i'm not that strong in statistics anymore, but is there a way to be x% certain that your max tour is the highest possible one given enough times? Also: Is 100 moves equally likely as max length? $\endgroup$ – SAJW Oct 15 '16 at 6:49
  • 1
    $\begingroup$ @saturatedexpo Not in general. There could be pathological examples that a random guessing never approaches. (Just like my random sampling never found any lengths less than about $930$ when we know the minimum is $100$.) $\endgroup$ – Alexis Olson Oct 15 '16 at 6:52
  • $\begingroup$ just as a question, did you allow diagonal moves? or are those generally not allowed in such problems (grits) $\endgroup$ – SAJW Oct 15 '16 at 7:15
  • $\begingroup$ @saturatedexpo No. I assumed the spider stayed on a square lattice grid. $\endgroup$ – Alexis Olson Oct 15 '16 at 7:17
  • $\begingroup$ I like the simulation, but I do note that this code finds a complete circuit, when we should properly start at $(0,0)$ and end at the point the last fly is eaten. Very comparable, but will always read at least 1 unit too high. $\endgroup$ – erfink Oct 15 '16 at 8:09
1
$\begingroup$

Utilizing @Alexis Olson's mathematica code, I came up with the following distribution for path lengths (shown in red) and plotted it against the normal distribution (shown in blue, using the mean & standard deviation of the path lengths). Seems to agree remarkably well (tested on 5000 paths).

enter image description here

$\endgroup$
1
$\begingroup$

I had a different solution from the answer by user21820 for the asymptotic upper bound for an $n\times n$ grid. I'll just briefly sketch it here:

Take the left-most remaining $\approx\sqrt{n}$ points (which we will call a block), and traverse them from top to bottom, going left/right where necessary. Repeat, but switch vertical direction alternately. Total vertical movement is $\text{number of repeats}\times (n-1)$ and total horizontal movement is $\le\sum_{\text{block}}{\text{width of block}\times(\text{number of points in block}+1)}$. Maximum is $\approx 2n\sqrt{n}$.

Edit: This solution is slightly worse than the other one, and hence cannot answer the question about 2000 moves.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.