Let $C$ be a circle, $A_1 , A_2,\ldots ,A_n$ be distinct points inside $C$ and $B_1 , B_2 ,\ldots ,B_n$ be distinct points on $C$ such that no two of the segments $A_1B_1 , A_2 B_2 ,\ldots ,A_n B_n$ intersect. A grasshopper can jump from $A_r$ to $A_s$ if the line segment $A_r A_s$ does not intersect any line segment $A_t B_t (t \neq r, s)$. Prove that after a certain number of jumps, the grasshopper can jump from any $A_u$ to any $A_v$ .
Problem
Source:
Tags: combinatorics unsolved, combinatorics
Carolstar9
04.01.2012 13:43
See problem 368, in solutions of http://www.math.ust.hk/excalibur/v16_n1.pdf
mlm95
04.01.2012 14:18
this is my way i cant write it completely because of my time and my bad english skills first show that we can go from any $A_{i}$ to at least another $A_{j}$ then consider $A_{i}$ and $A_{j}$ such that we can go from $A_{i}$ to $A_{j}$ and show that for another point $A_{t}$ we can arrive to at least one of $A_{i}$ or $A_{j}$
mathophile593
04.01.2012 23:03
Here is a conceptual proof. Add walls along the segments $A_iB_i$ and around the circumference of the circle. The remaining room is connected, so we can connect any pair of points $A_i$ and $A_j$ with a string that never passes through a wall. Now tighten the string. The string will be straight except where it touches a wall, and it may only touch a wall at the points $A_1, A_2, \hdots, A_n$. This is the grasshopper's desired path.
themathematicalmantra
09.12.2020 13:25
Induction works on this we can prove the base case and then move to prove for n+1. We can then consider that let the nearest line to A1 be Aq so we can check on them and see that if AtBt is the only line intersecting then AtAq or AtA1 works and then by induction hypothesis it follows. If in case more than 1 line falls or instersects it by the condition that no 2 AtBt interesct choose th one which is nearest to A1 or th respective Ai and then AiAt works .