A hilly island has $2023$ lookouts. It is known that each of them is in line of sight with at least $42$ of the other lookouts. For any two distinct lookouts $X$ and $Y$ there is a positive integer $n$ and lookouts $A_1,A_2,\dots,A_{n+1}$ such that $A_1=X$ and $A_{n+1}=Y$ and $A_1$ is in line of sight with $A_2$, $A_2$ with $A_3$, $\dots$ and $A_n$ with $A_{n+1}$. The smallest such number $n$ is called the viewing distance of $X$ and $Y$. Determine the largest possible viewing distance that can exist between two lookouts under these conditions.
Problem
Source: Bundeswettbewerb Mathematik 2023, Round 2 - Problem 2
Tags: combinatorics proposed, combinatorics, graph theory
11.09.2023 14:41
I think, the correct condition is $A_{n+1}=Y$ instead $A_2=Y$. Let be $M$ the maximum possible value of the viewing distance between two lookouts and $A_1, A_2,...,A_M, A_{M+1}$ a sequence of lookouts with the property $A_1$ is in line of sight with $A_2$, $A_2$ with $A_3$, $\dots$ and $A_M$ with $A_{M+1}$. We construct a partition of the set $L$ of 2023 lookouts into "levels", as follow: $\bullet\; L_1=\{A_1\}$; $\bullet\;$ for $k\in\{1,2,...,M\},\; L_{k+1}=\{A_p\in L|\exists A_q\in L_k \text{ such that } A_p \text{ is in line of sight with } A_q\text{ and }A_p\notin L_1\cup L_2\cup...\cup L_k\}$. $\bullet\; A_k\in L_k,\;\forall k\in\{1,2,...,M+1\}$. Results: $\textbf{P1: }L_i\cap L_j=\phi,\;\forall i,j\in\{1,2,...,M+1\},\;i\ne j$. $\textbf{P2: }|L_1|+|L_2|+...+|L_M|+|L_{M+1}|=2023$. $\textbf{P3: }$ if $A_p\in L_i$ is in line of sight with $A_q\in L_j$, then $|i-j|\in\{0,1\}$. Proof: WLOG, we can consider $i\le j$. For $i=j$ we obtain $|i-j|=0$. For $i<j:\;A_p\in L_i$ is in line of sight with $A_q\in L_j\Longrightarrow A_q\in L_{i+1}\Longrightarrow j=i+1$. $\textbf{P4: }|L_1|+|L_2|\ge43;\;|L_M|+|L_{M+1}|\ge43$. Proof: a) $|L_1|=1$; using $P3$, all lookouts in line of sight with $A_1$ belong to $L_2$. $A_1$ is in line of sight with at least $42$ of the other lookouts $\Longrightarrow |L_2|\ge42\Longrightarrow |L_1|+|L_2|\ge43$. b) let be $A_t\in L_{M+1}$; using $P3$, all lookouts in line of sight with $A_t$ belong to $L_M\cup L_{M+1}\Longrightarrow |L_M|+(|L_{M+1}|-1)\ge42\Longrightarrow |L_M|+|L_{M+1}|\ge43$. $\textbf{P5: }|L_k|+|L_{k+1}|+|L_{k+2}|\ge43,\;\forall k\in\{3,4,5,...,M-3\}$. Proof: let be $A_t\in L_{k+1}$; using $P3$, all lookouts in line of sight with $A_t$ belong to $L_{k}\cup L_{k+1}\cup L_{k+2}\Longrightarrow |L_k|+(|L_{k+1}|-1)+|L_{k+2}|\ge42\Longrightarrow |L_k|+|L_{k+1}|+|L_{k+2}|\ge43$. $\textbf{P6: }M\le 140$. Proof: $2023=47\cdot43+2$. Using $P4$ and $P5$, results: $M+1\le2\cdot2+45\cdot3+2=141\Longrightarrow M\le140$, where $2\cdot2$ comes from the pairs $(L_1,L_2)$, respectively $(L_M,L_{M+1})$, each with $43$ lookouts; $45\cdot3$ comes from the triplets $(L_3,L_4,L_5),\;(L_6,L_7,L_8),...,(L_{135},L_{136},L_{137})$, each with $43$ lookouts; with the remaining $2$ lookouts we can form $2$ sets $L_{138},L_{139}$, each with $1$ lookout. $\textbf{P7: }$ exists a configuration with $M=140$ for which the requested conditions are satisfied. Proof: consider $(|L_1|,|L_2|,|L_3|,|L_4|,|L_5|,...,|L_{135}|,|L_{136}|,|L_{137}|,|L_{138}|,|L_{139}|,|L_{140}|,|L_{141}|)=$ $=(1,42,\;\textsl{ 45 times }(1,1,41),\;1,1,42,1)$, with the properties: $\bullet\;\forall L_k$ with $|L_k|>1$, each $A_m\in L_k$ is in line of sight with all other lookouts from $L_k$; $\bullet\;\forall L_k$ with $|L_k|>1$, each $A_m\in L_k$ is in line of sight with the lookout from $L_{k+1}$. It's easy to verify that for this configuration each lookout is in line of sight with $42$ or $43$ of the other lookouts. $\textbf{Final answer:}$ Using $P6$ and $P7$, results: the largest possible viewing distance that can exist between two lookouts under the requested conditions is $M=140$.
13.09.2023 15:03
Answer is here: [url] https://www.sciencedirect.com/science/article/pii/009589568990066X?ref=pdf_download&fr=RR-2&rr=7f15e1919aca90e0[/url]