There are $2023$ guinea pigs placed in a circle, from which everyone except one of them, call it $M$, has a mirror that points towards one of the $2022$ other guinea pigs. $M$ has a lantern that will shoot a light beam towards one of the guinea pigs with a mirror and will reflect to the guinea pig that the mirror is pointing and will keep reflecting with every mirror it reaches. IsaĆas will re-direct some of the mirrors to point to some other of the $2023$ guinea pigs. In the worst case scenario, what is the least number of mirrors that need to be re-directed, such that the light beam hits $M$ no matter the starting point of the light beam?
Problem
Source: 2023 Mathematics Regional Olympiad of Mexico West P6
Tags: combinatorics, combinatorial geometry, reflection, geometry
21.10.2024 22:36
The answer is $1011$. Number the guinea pigs from $0$ to $2022$ such that $0$ in the lantern. If the mirror $1$ is pointing to mirror $2$, mirror $2$ is pointing to mirror $1$... mirror $2n+1$ pointing $2n+2$ and $2n+2$ pointing $2m+1$ we have $1011$ couplet of mirror that point each other so we need to change at list one pointing from every couplet so we need at least $1011$ chainging. Now we prove that $1011$ are always enought. Consider the function $f$ that given a mirror give it's pointed. And we say $a$ is descendant of $b$ if applying $f$ a finite (also $0$) number of times to $b$ we obtain $a$. And say that $a \approx b$ if and only if $a$ and $b$ have a common descendant. We divide the mirrors in groups such that $a$ and $b$ are in the same grup if and only if $a \approx b$. There are at most $1011$ groups because every group conteins at least $2$ elements. Now from every group $S$ we chose an element $x$ such that $x$ is descendant of every element of $S$ and direct the mirror $x$ to $0$
28.10.2024 08:02
OG! We claim the answer is 1011. Proof that this is necessary: Lablel the pigs from 1,2...2023. WLOG, let $M$ be labelled 2023. Consider that pig labelled $2n-1$ points towards $2n$ and vice-versa of $n \leq 1011$. Then, In these 1011 pairs of $(2n-1,2n)$ for $1 \leq \leq 1011$. Atleast 1 member of a pair has to be redirected else if a pair is not redirected then, if $M$ points the lantern towards a member in that pair, the light beam would be reflected to and fro between the mirrors forever. Hence at least 1011 pigs' mirros need to be redirected. Proof that this is sufficient: Call a set of pigs $loop$ if the light is reflected by a pig's mirror in that set, then it eventually comes back to the pig by hitting all and only pigs in the same set exactly once. The definiton implies that the number of pigs in a loop $\geq 2$. Of course any 2 $loops$ must be disjoint, if they are not then consider 2 distinct $loops$ $S_1$ and $S_2$ they share a member $n$. Now, if a beam of light strikes $n$ then it must reach back to $n$ after touching only and all elements of the set $S_1- n$. it must also reach back to $n$ after touching only and all elements of the set $S_2- n$. This means $S_1-n = S_2-n$ or $S_1=S_2$ a contradiction!. Let there be $x$ loops among the 2023 pigs. If there are more than 1011 loops or for that matter say 1012 loops, then since each loop has at least 2 pigs, so we have at least 2x1012 =2024 pigs. A contradiction. So there are at maximum 1011 loops. Now $M$ will redirect exactly pig from each loop that does not contain $M$ towards itself. So it redirects at most 1011 pigs. Now this is sufficient as if there were to be not sufficient then there must exist a $loop$ without $M$. But we had already redirected such loop towards $M$, so we are done.