The mower's challenge

Question

Weeds have taken over the paths (two squares). If mowed, they don't grow back, but unmowed weeds spread at speed $1$ along the road. What's the minimum speed of the mower to get rid of all the weeds? Roads are connected at each intersection and the mower must move on roads.

---

I've edited the problem to reduce the number of squares from 9 to 2. But the dynamics of the optimal solution still seems eluding. The puzzle was initially asked here.

Answer 1

The problem seems nice and difficult to me.

First of all, let’s see if I understood correctly your game.

At the beginning, weeds are everywhere along the roads. You pick a point in the green grid and start mowing weeds moving in one direction. Instantly, as you clear the road, weeds from behind you starts spreading along the road at speed 1. When you arrive at a crossroad, you must select just one possible way, but if spreading weeds arrive at a crossroad, they spread in all directions.

Assuming that all this is right, let’s see…

It seems clear that a large enough speed would do the job. A trivial case is the one where you reduced all weeds to within one “step” of the grid, with no crossroads involved. Then you can make it if the speed is more than $\frac L\ell$, where $L$ is the length of the weeds segment and $\ell$ is the distance between the weeds segment endpoint and the closest crossroad. But this is only a trivial sufficient condition, of course. Assuming that at the crossroad four paths intersect, you can still make it with $\ell$ very small if you can chop the three new branches arising one at a time. This easily leads to the (very lazy…) bound $v>7$, so the zero-order step is: if you confined weeds to a single step of the grid, you can do it if your speed is 7 or more.

I’ll try to come back later to think about more interesting cases.

Update: in the new version with only 2 squares, a better lazy bound can be given for the zero-step, that is $v>5$.

Answer 2

Expanding my comment on the threeway intersections, we get an auxiliary result:

Lemma 1. If $v>5$, then starting from a threeway intersection where the branches have $0$, $a$ and $b$ units of weed, and enough free space outside that, the mower can clear the intersection in time $2(a+b) \, / \, (v-5)$.

(By "enough space" we mean that any other weed segments will not touch these branches during the operation.)

Proof. Keep doing round-trips to the three branches and back alternatively, always choosing the longest branch. Let us first consider the first round-trip and assume without loss of generality that it is $b$.

• The outgoing leg takes time $t=b/(v-1)$ because the mower starts $b$ units behind the tip, and his relative speed is $v-1$ as the tip is growing. During this time, the other two branches grow $t$ units each.
• The incoming leg also takes time $t$. During this time the mower completely cleans this branch (including any weed that was growing back to the branch from the intersection). The other branches grow another $t$ units each.

Overall in one round-trip, in $2t$ time the net weed decrease is $b - 4t = t(v-5)$, so weed is cleared at rate $(v-5)/2$. It is easy to see that the same average rate holds for each round trip. Having started with $(a+b)$ units of weed, it is all cleared in time $2(a+b) \, / \, (v-5)$.

---

If $v$ is large — let's take $v=100$ for concreteness — this suggests the following strategy. Let $L,R$ be the left and right intersections.

• Start from $L$. Make three round-trips to $R$: first along the north route ($3$ units and back), then along the middle route ($1$ unit and back), and then along the south route ($3$ units and back). In total this takes time $0.14$.
• Now $L$ has weed lengths north=$0.08$, middle=$0.06$ and south=$0$.
• And $R$ has weed lengths north=$0.11$, middle=$0.07$ and south=$0.03$.
• By Lemma 1, we can clear around $L$ in time $2\cdot 0.14 / 95 < 0.003$. During this time the weed around $R$ grows less than $0.01$ in each direction.
• Move east to $R$ in time $0.01$. During this time the weed grows another $0.01$ units.
• Now $R$ has weed lengths north $< 0.13$ and south $< 0.05$. (Nothing on the middle branch because we cleared it on the way.)
• By Lemma 1, we can clear around $R$ in less than $2 \cdot 0.18 / 95 < 0.004$ time.

Clearly $v=100$ suffices. It should now be relatively straightforward to find the minimum $v$ that suffices with this strategy. Of course this says nothing about possible other strategies.