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
31.05.2024 07:44
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
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$
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
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.
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 ?
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$$
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.
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.
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.
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.
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
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
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.