Skip to main content
added 337 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Claim. The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

TheProof. The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ always moves at speed faster than $1$.

A few trivial factsAssume $C$ has radius $1$ and clarificationspick a number $r$ once and for all, with $1/2<r<1$.

At any time there are neededexactly two circles $C_1$, $C_2$ of radius $r$, tangent to describe the$C$ and contaning $T$. The strategy of the the thief is to always run at speed $1$, alternating between these two ways:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

$-$ either move right on $C_1$ towards $A$ (dragging $C_2$ and $B$ along)

Finally$-$ or move left on $C_2$ towards $B$ (dragging $C_1$ and $A$ along).

circle

No matter how $T$ zigzags left and right, the strategy:symmetry between $C_1$ and $C_2$ with respect to $T$ guarantees that the path followed by $T$ has the same total length $\overset{\frown}{TA}=\overset{\frown}{TB}$. Therefore $T$ will land on $C$ in finite time.

As for the shadow $S$, $r>1/2$ implies that it always moves at speed $>1$, i.e. the (infinitesimal) arc length inequality $\delta_1<\delta_2$ always holds (see figure). This is a tedious but elementary trigonometric inequality, better left to the reader.

Before detailing how the thief's zigzags are decided, we need to notice that any policeman to the right of $A$, or to the left of $B$, by strictly more than $\overset{\frown}{SA}$, is inactive, in other words he can never catch $T$, even if $T$ runs towards him all the way to $C$.

Finally, enumerate all the policemen $P_1, P_2, \dots$.$P_1, P_2, P_3 \dots$

Take the first active policeman on the list, say $P$$P_{i_1}$. If $P$$P_{i_1}$ is to the left of $S$ (or on $S$) $T$ will movechooses to therun right towards $A$ at speed $1$. (Similarly if $P$ iswere to the right, $T$ will move would choose to run left towards $B$.) SinceBecause $S$ moves at speed $>1$ at some point $P$ will fall and remain$P_{i_1}$ permanently falls behind $S$ by some amount $\epsilon$$\epsilon_1$ (it doesn't matter how small). ButHowever $P$$P_{i_1}$ may still be within the active range, so $T$ continues to movekeeps running towards $A$ until $\overset{\frown}{SA}<\epsilon/3$$\overset{\frown}{SA}<\epsilon_1/3$. That makesSince $P$ inactive: he is$\overset{\frown}{SB}=\overset{\frown}{SA}$, now even$P_{i_1}$ is behind $B$ by strictly more than $\epsilon/3$$\epsilon_1/3$. This renders $P_{i_1}$ permanently inactive!

Similarly we, take the next active policeman $Q$$P_{i_2}$ on the list and again. Again $T$ movesruns in the direction away from him, until $Q$$P_{i_2}$ is inactive too. There are onlyat most countably many active policemen and one by one they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.$\quad \blacksquare$

This proof should easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ moves at speed faster than $1$.

A few trivial facts and clarifications are needed to describe the strategy:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

Finally the strategy: enumerate the policemen $P_1, P_2, \dots$. Take the first active policeman, say $P$. If $P$ is to the left of $S$ (or on $S$) $T$ will move to the right towards $A$ at speed $1$. (Similarly if $P$ is to the right, $T$ will move left towards $B$.) Since $S$ moves at speed $>1$ at some point $P$ will fall and remain behind $S$ by $\epsilon$ (it doesn't matter how small). But $P$ may still be active so $T$ continues to move towards $A$ until $\overset{\frown}{SA}<\epsilon/3$. That makes $P$ inactive: he is now even behind $B$ by more than $\epsilon/3$!

Similarly we take the next active policeman $Q$ on the list and again $T$ moves in the direction away from him, until $Q$ is inactive too. There are only countably many policemen and they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.

This proof easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

Claim. The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

Proof. The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ always moves at speed faster than $1$.

Assume $C$ has radius $1$ and pick a number $r$ once and for all, with $1/2<r<1$.

At any time there are exactly two circles $C_1$, $C_2$ of radius $r$, tangent to $C$ and contaning $T$. The strategy of the the thief is to always run at speed $1$, alternating between these two ways:

$-$ either move right on $C_1$ towards $A$ (dragging $C_2$ and $B$ along)

$-$ or move left on $C_2$ towards $B$ (dragging $C_1$ and $A$ along).

circle

No matter how $T$ zigzags left and right, the symmetry between $C_1$ and $C_2$ with respect to $T$ guarantees that the path followed by $T$ has the same total length $\overset{\frown}{TA}=\overset{\frown}{TB}$. Therefore $T$ will land on $C$ in finite time.

As for the shadow $S$, $r>1/2$ implies that it always moves at speed $>1$, i.e. the (infinitesimal) arc length inequality $\delta_1<\delta_2$ always holds (see figure). This is a tedious but elementary trigonometric inequality, better left to the reader.

Before detailing how the thief's zigzags are decided, we need to notice that any policeman to the right of $A$, or to the left of $B$, by strictly more than $\overset{\frown}{SA}$, is inactive, in other words he can never catch $T$, even if $T$ runs towards him all the way to $C$.

Finally, enumerate all the policemen $P_1, P_2, P_3 \dots$

Take the first active policeman on the list, say $P_{i_1}$. If $P_{i_1}$ is to the left of $S$ (or on $S$) $T$ chooses to run right towards $A$ at speed $1$. (Similarly if $P$ were to the right, $T$ would choose to run left towards $B$.) Because $S$ moves at speed $>1$ at some point $P_{i_1}$ permanently falls behind $S$ by some amount $\epsilon_1$ (it doesn't matter how small). However $P_{i_1}$ may still be within the active range, so $T$ keeps running towards $A$ until $\overset{\frown}{SA}<\epsilon_1/3$. Since $\overset{\frown}{SB}=\overset{\frown}{SA}$, now $P_{i_1}$ is behind $B$ by strictly more than $\epsilon_1/3$. This renders $P_{i_1}$ permanently inactive!

Similarly, take the next active policeman $P_{i_2}$ on the list. Again $T$ runs in the direction away from him, until $P_{i_2}$ is inactive too. There at most countably many active policemen and one by one they all become inactive, guaranteeing that $T$ lands on a police-free point of $C$.$\quad \blacksquare$

This proof should easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

added 5 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ moves at speed faster than $1$.

A few trivial facts and clarifications are needed to describe the strategy:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

Finally the strategy: enumerate the policemen $P_1, P_2, \dots$. Take the first active policeman, say $P$. If $P$ is to the left of $S$ (or on $S$) $T$ will move to the right towards $A$ at speed $1$. (Similarly if $P$ is to the right, $T$ will move left towards $B$.) Since $S$ moves at speed $>1$ at some point $P$ will fall and remain behind $S$ by $\epsilon$ (it doesn't matter how small). But $P$ may still be active so $T$ continues to move towards $A$ until $\overset{\frown}{SA}<\epsilon/3$. That makes $P$ inactive: he is now even behind $B$ by more than $\epsilon/3$!

NextSimilarly we take the next active policeman $Q$ on the list and again $T$ moves in the direction away from him, until $Q$ is inactive too. There are only countably many policemen and they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.

This proof easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ moves at speed faster than $1$.

A few trivial facts and clarifications are needed to describe the strategy:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

Finally the strategy: enumerate the policemen $P_1, P_2, \dots$. Take the first active policeman, say $P$. If $P$ is to the left of $S$ (or on $S$) $T$ will move to the right towards $A$ at speed $1$. (Similarly if $P$ is to the right, $T$ will move left towards $B$.) Since $S$ moves at speed $>1$ at some point $P$ will fall and remain behind $S$ by $\epsilon$ (it doesn't matter how small). But $P$ may still be active so $T$ continues to move towards $A$ until $\overset{\frown}{SA}<\epsilon/3$. That makes $P$ inactive: he is now even behind $B$ by more than $\epsilon/3$!

Next we take the next active policeman $Q$ on the list and again $T$ moves in the direction away from him, until $Q$ is inactive too. There are only countably many policemen and they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.

This proof easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ moves at speed faster than $1$.

A few trivial facts and clarifications are needed to describe the strategy:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

Finally the strategy: enumerate the policemen $P_1, P_2, \dots$. Take the first active policeman, say $P$. If $P$ is to the left of $S$ (or on $S$) $T$ will move to the right towards $A$ at speed $1$. (Similarly if $P$ is to the right, $T$ will move left towards $B$.) Since $S$ moves at speed $>1$ at some point $P$ will fall and remain behind $S$ by $\epsilon$ (it doesn't matter how small). But $P$ may still be active so $T$ continues to move towards $A$ until $\overset{\frown}{SA}<\epsilon/3$. That makes $P$ inactive: he is now even behind $B$ by more than $\epsilon/3$!

Similarly we take the next active policeman $Q$ on the list and again $T$ moves in the direction away from him, until $Q$ is inactive too. There are only countably many policemen and they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.

This proof easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ moves at speed faster than $1$.

A few trivial facts and clarifications are needed to describe the strategy:

  • Assume $C$ has radius $1$, then pick a number $r$ once and for all, with $1/2<r<1$. It's obvious that wherever $T$ may be, there are exactly two circles of radius $r$, tangent to $C$ and contaning $T$: circles

  • As $T$ moves along one or the other of the two circles towards the landing points ($A$ or $B$), the second circle is not static but dragged along with $T$, so that $T$ is always the intersection point.

  • No matter how often $T$ zigzags (sometimes moving towards $A$, sometimes towards $B$) the path followed by $T$ has the same length, since $A$ and $B$ always have equal distances $\overset{\frown}{TA}=\overset{\frown}{TB}$ from $T$. At the end $T$ may land anywhere between $A$ and $B$, but in finite time, independent of the turns.

  • The fact that $r>1/2$ guarantees that $S$ moves at speed $>1$, that is $\overset{\frown}{SA}>\overset{\frown}{TA}$. This is a tedious but easy trigonometric inequality, better left to the reader.

  • Any policeman to the right of $A$, or to the left of $B$, by more than $\overset{\frown}{SA}$, is inactive, he will never catch $T$.

Finally the strategy: enumerate the policemen $P_1, P_2, \dots$. Take the first active policeman, say $P$. If $P$ is to the left of $S$ (or on $S$) $T$ will move to the right towards $A$ at speed $1$. (Similarly if $P$ is to the right, $T$ will move left towards $B$.) Since $S$ moves at speed $>1$ at some point $P$ will fall and remain behind $S$ by $\epsilon$ (it doesn't matter how small). But $P$ may still be active so $T$ continues to move towards $A$ until $\overset{\frown}{SA}<\epsilon/3$. That makes $P$ inactive: he is now even behind $B$ by more than $\epsilon/3$!

Next we take the next active policeman $Q$ on the list and again $T$ moves in the direction away from him, until $Q$ is inactive too. There are only countably many policemen and they will all eventually become inactive, guaranteeing that $T$ lands on a police-free point of $C$.

This proof easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.