A sleeping rabbit lies in the interior of a convex $2024$-gon. A hunter picks three vertices of the polygon and he lays a trap which covers the interior and the boundary of the triangular region determined by them. Determine the minimum number of times he needs to do this to guarantee that the rabbit will be trapped. Proposed by Anant Mudgal and Rohan Goyal
Problem
Source: India IMOTC 2024 Day 1 Problem 1
Tags: combinatorics, india, combinatorial geometry
Rijul saini
31.05.2024 07:44
Let the $2024$-gon be $A_0A_1\cdots A_{2023}$. We claim that the answer is $2022$ which is achieved by picking the triangles $\triangle A_0A_iA_{i+1}$ for $i=1,2, \ldots, 2022$.
For any $0 \le i \le 2023$, we claim that the entirety of $\angle A_iA_{i+1}A_{i+2}$ is covered by triangles with one of their vertices at $A_{i+1}$. To prove this, consider one point in the intersection of the triangle $A_iA_{i+1}A_{i+2}$ with each of $A_{i+1}A_jA_{j+1}$ for all $j\ne {i,i-1}$. Observe that if the entire angle is not covered then at least one of these points is not in any triangle.
Thus, the sum of all angles covered by the triangles is at least $(2022)\cdot180^{\circ}$, but each triangle covers only $180^\circ$. Thus, we need at least $2022$ triangles.
A set of triangles that cover the entire polygon $\mathcal{P}$ is called a trapulation. For a trapulation $\mathcal{T}$, let $S\subset \{A_1,A_2,\dots ,A_n\}$ be a minimal subset of vertices such that $\mathcal{T}$ contains a triangulation of $\mathcal{P}-\mathcal{P}_S$, where $\mathcal{P}_S$ is the polygon with $S$ as vertices. Let $\mathcal{T}_S\subset \mathcal{T}$ be the set of triangles that have non-empty intersection with $\mathcal{P}_S$. For an edge $e$ of $\mathcal{P}_S$, we say that $e$ is uncovered if no triangle of $T_S$ contains $e$ (as a side).
Let $t$ be the minimum number of triangles in a trapulation and suppose $t<n-2$. Let $\mathcal{T}$ be a trapulation with $t$ triangles such that $\mathcal{T}$ has minimum number of uncovered edges. Note that $|T_S|<|S|-2$ and $|S|\geqslant 4$.
Claim : Every edge of $\mathcal{P}_S$ is covered.
Proof: Suppose an edge $e=A_iA_j$ ($i<j$) is uncovered. Consider a point $P$ in the triangle formed by lines $A_iA_j, A_iA_{j+1}$ and $A_{i-1}A_{i+1}$. Note that $P\in \mathcal{P}_S$. So, there must be a triangle $T\in \mathcal{T}_S$ containing $P$. As $P$ lies on $A_i$ side of the line $A_{i-1}A_{i+1}$, $A_i$ is a vertex of $T$. Let $A_k$ and $A_\ell$ be the other two vertices. If both, $k,\ell\in \{i+1,\dots, j\}$ or both $k,\ell\in \{j+1,j+2,\dots,n,1,\dots, i-1\}$, then $A_l$ and $P$ are on different sides of the line $A_iA_k$ which is not possible. So, w.l.o.g. let $k\in \{i+1,\dots, j\}$ and $\ell\in \{j+1,j+2,\dots,n,1,\dots, i-1\}$. Now, if $k=j$ then $T$ contains $e$. Otherwise, we can replace $T$ with the triangle $A_iA_jA_\ell$ and get another trapulation $\mathcal{T}'$ which preserves the covered edges and covers an additional uncovered edge. This contradicts the minimality of number of edges uncovered.
Now, if no triangle of $\mathcal{T}_S$ contains at least two edges of $\mathcal{P}_S$, then $|\mathcal{T}_S|\geqslant |S|$ which is a contradiction. So, there is a triangle $T$ that contains two edges, whose common end is say $A_i$. In this case, $S'=S-A_i$ contradicts the minimality of $S$.
anantmudgal09
31.05.2024 09:20
Official wording: everythingpi3141592 wrote: A sleeping rabbit lies in the interior of a convex $2024$-gon. A hunter picks three vertices of the polygon and he lays a trap which covers the interior and the boundary of the triangular region determined by them. Determine the minimum number of times he needs to do this to guarantee that the rabbit will be trapped. Proposed by Anant Mudgal and Rohan Goyal It would seem the only rabbits that got trapped were the people caught off-guard by this problem
surpidism.
31.05.2024 09:54
I used induction, is this correct? (Edit: fakesolve) Replace $2024$ with $n \in \mathbb{N}$. We claim the minimum is $n-2$ and we use induction on $n$ to prove it. Base case: It is trivial for $n= 3$ Inductive hypothesis: Assume for convex polygon with $n = k$ sides, the minimum number of traps required is $k-2$. Inductive step: For convex polygon with $k+1$ sides, let $A_1$, $A_2$, ... , $A_k$, $A_{k+1}$ be the vertices. Now consider $A_1$, $A_2$, $A_3$; join $A_1$ and $A_3$ to form a convex polygon $A_1 A_3 A_4 ... A_{k+1} A_1$. Note that this has $k$ sides, so by inductive hypothesis, minimum number of traps required for this region is $k-2$. Now for $A_1 A_2 A_3$, this is just base case. Hence, minimum for $k+1$-gon is $k - 2 + 1 = (k+1) -2$ , as required. $\square$
AshAuktober
31.05.2024 10:40
surpidism. wrote: I used induction, is this correct? Replace $2024$ with $n \in \mathbb{N}$. We claim the minimum is $n-2$ and we use induction on $n$ to prove it. Base case: It is trivial for $n= 3$ Inductive hypothesis: Assume for convex polygon with $n = k$ sides, the minimum number of traps required is $k-2$. Inductive step: For convex polygon with $k+1$ sides, let $A_1$, $A_2$, ... , $A_k$, $A_{k+1}$ be the vertices. Now consider $A_1$, $A_2$, $A_3$; join $A_1$ and $A_3$ to form a convex polygon $A_1 A_3 A_4 ... A_{k+1} A_1$. Note that this has $k$ sides, so by inductive hypothesis, minimum number of traps required for this region is $k-2$. Now for $A_1 A_2 A_3$, this is just base case. Hence, minimum for $k+1$-gon is $k - 2 + 1 = (k+1) -2$ , as required. $\square$ You are now the rabbit
idkk
31.05.2024 22:05
Can someone just take the effort to pricesly define "trap" and "trapped" for me ;-; . Is the sleeping rabit gonna wake up and move lot of things arent making sense.
Asynchrone
31.05.2024 23:56
Let me rephrase it : You have a $2024$-gon, initially its interior is colored white, i put a random point in the interior of the polygon, it doesn't move. A trap is defined as choosing three vertices of the polygon (If you chose a vertice before, you can choose it again, no problem), then drawing the triangle formed by them, and coloring the inside of that triangle. How many triangles do you need to guarantee that the point will be in a colored area ?
sami1618
01.06.2024 01:15
Answer: $2022$: Construction: Simply consider any triangulation of the polygon. Bound: Let $T$ be the number of triangles. Notice that at each vertex we need the angle to be completely covered by triangles. Summing over all angles we get $$180^{\circ}\cdot T\geq 2022\cdot {180^{\circ}}\Rightarrow T\geq 2022$$
matematica007
03.06.2024 22:48
Answer: 2022 Let A be the number of triangles. Each angle of the polygon must be completely covered by these A triangles. So $180^{\circ}\cdot A\geq 2022\cdot {180^{\circ}}\Rightarrow A\geq 2022$. To show that there is a construction for $A=2022$ we consider a triangulation of the polygon. So the answer is 2022.
mofumofu
21.07.2024 04:35
everythingpi3141592 wrote: A sleeping rabbit lies in the interior of a convex $2024$-gon. A hunter picks three vertices of the polygon and he lays a trap which covers the interior and the boundary of the triangular region determined by them. Determine the minimum number of times he needs to do this to guarantee that the rabbit will be trapped. Proposed by Anant Mudgal and Rohan Goyal Answer: 1 The hunter can see the rabbit, so 1 triangle is enough. 0 triangular traps is not enough to catch the rabbit, so the minimum is 1.
Eka01
28.08.2024 20:24
Wow I'd heard this was easy but didn't know this was that easy. Since the triangles must cover every angle of the polygon, summing over angles we get that if $T$ is the number of triangles, then $T \geq 2022$ and for $T=2022$ the triangulation of the polygon works.
L13832
28.08.2024 20:27
Eka01 wrote: Wow I'd heard this was easy but didn't know this was that easy. Since the triangles must cover every angle of the polygon, summing over angles we get that if $T$ is the number of triangles, then $T \geq 2022$ and for $T=2022$ the triangulation of the polygon works. this is head-solve problem, literally did it in a car.
quantam13
06.10.2024 13:53
My solution: Answer is 2022 For construction, take any triangulation of the polygon For bound, consider angle sum over all the triangles and notice that it must be greater than the sum of the angles at the polygon. This solves the problem Cute problem that was
Siddharthmaybe
13.10.2024 19:46
Intuitive approach For a convex polygon of n sides , we know that it can be split into n-2 triangles Also total degree measures is 2022 x 180 Now a triangle can cover at max 180 degrees, So the answer should atleast be 2022, we now claim that this is the answer. A 2024 polygon is just composed of 2022 triangles (by joining the vertices Ai,Ai+1,Ai+2) and then the construction is trivial, Props to creating such a problem that even someone from class 8th has a fair chance of solving this
sansgankrsngupta
06.11.2024 14:48
OG! The answer is 1 because the hunter can see the sleeping rabbit and the sleeping rabbit wouldn't wake up due to the hunter's special skills of placing the trap quitely hence done. EDIT: WHILE IN LITERAL AND TECHNIACAL SENSE IT IS CORRECT BUT OFC DURING THE CONTEST ASSUME THAT THE RABBIT IS INVISIBLE, SO you get 2022.