In the city of Flensburg there is a single, infinitely long, street with housesnumbered $2, 3, \ldots$. The police in Flensburg is trying to catch a thief who every night moves from the house where she is currently hiding to one of its neighbouring houses. To taunt the local law enforcement the thief reveals every morning the highest prime divisor of the number of the house she has moved to. Every Sunday afternoon the police searches a single house, and they catch the thief if they search the house she is currently occupying. Does the police have a strategy to catch the thief in finite time?
Problem
Source: Baltic Way 2023/8
Tags: combinatorics
pi_quadrat_sechstel
12.11.2023 21:46
a_507_bc wrote: In the city of Flensburg there is a single, infinitely long, street with housesnumbered $2, 3, \ldots$. The police in Flensburg is trying to catch a thief who every night moves from the house where she is currently hiding to one of its neighbouring houses. To taunt the local law enforcement the thief reveals every morning the highest prime divisor of the number of the house she has moved to. Every Sunday afternoon the police searches a single house, and they catch the thief if they search the house she is currently occupying. Does the police have a strategy to catch the thief in finite time? If on two consecutive days the prime highest prime divisors are $(2,3)$ or $(3,2)$ the thief was in two consecutive houses with numbers $2^n$ and $2^k3^m$ with difference $\pm1$. So $2^k3^m$ must be odd and $k=0$. We claim that all pairs $(2^n,3^m)$ with $n,m\geq1$ and difference $\pm1$ are $(2,3),(4,3),(8,9)$.
If $2^n+1=3^m$ we have $3\mid 2^n+1$ and thus $n\equiv1\pmod{2}$. For $n=1$ we get the soloution $(2^n,3^m)=(2,3)$. For $n>1$ we get $4\mid 3^m-1$ and thus $2\mid m$. So the positive integers $y:=2^{\frac{n-1}{2}},x=3^{\frac{m}{2}}$ satisfy $x^2-2y^2=1$. But all solutions for this Pell-equation in positive integers are given by $(x_1,y_1)=(3,2),(x_{n+1},y_{n+1})=(3x_n+4y_n,2x_n+3y_n)$. By induction we get that $3\mid y_n$ for even $n$ and $y_n\equiv2\pmod{4}$ for odd $n$. So only $y_1=2$ is a power of $2$. This leads to the solution $(2^n,3^m)=(8,9)$.
If $2^n-1=3^m$ we have $n>1$. Thus $4\mid 3^m+1$ and $m$ is odd. We have $3\mid 2^n-1$ implying that $n$ is even. So the positive integers $x:=2^{\frac{n}{2}},y=3^{\frac{m-1}{2}}$ satisfy $x^2-3y^2=1$. But all solutions for this Pell-equation in positive integers are given by $(x_1,y_1)=(2,1),(x_{n+1},y_{n+1})=(2x_n+3y_n,x_n+2y_n)$. By induction we get that $2\nmid x_n$ for even $n$ and $x_n\equiv2\pmod{4}$ for odd $n$. So only $x_1=2$ is a power of $2$. This leads to the solution $(2^n,3^m)=(4,3)$.
If the thief ever leaves $2,3,4,8,9$ the police exactly knows where she is. Even if she returns to $2,3,4,8,9$ the police knows where she is on days where she is in a house with an odd number. So they can strike on one of two consecutive sundays. If she never leaves $2,3,4,8,9$ the police can strike $3,3,9,9$ on four consecutive sundays. Thus we can assume that the two consecutive highest prime divisors $(2,3)$ or $(3,2)$ never occour. If numbers $(n,n\pm 2)$ have the same highest prime divisor, it must be $2$ since no number $>2$ can divide both $n,n\pm2$. So the pair $(n,n\pm2)$ is $(2,4)$ or $(4,2)$. But since the police never gets two consecutive highest prime divisors $(2,3)$ or $(3,2)$ revealed no two numbers $(n,n\pm 2)$ in the path of the thief have the same prime highest prime divisor. So the police can distinguish between the following two possibilities: 1. The thief is in the same house as two days earlier. 2. The thief move on the last two night in the same direction. Now the police keeps track of the set $S$ of all possible pairs $(a_1,a_2)$ of the housenumbers the thief was in the first two days. The path the thief follows is fully determined by the first two houses and the revealed highest prime divisors. Whenever the police gets new information the police can remove elements from $S$. After the second reveal for every $a_1$ there is at most one possible path starting at $a_1$. The police can use the following strategy: They search the house the thief would be in the path starting at a minimal $a_1$. This way the minimal $a_1$ increases every week and the police will catch the thief in a finite amount of time.