Sign in
Please select an account to continue using cracku.in
↓ →
Join Our JEE Preparation Group
Prep with like-minded aspirants; Get access to free daily tests and study material.
Let $$\mathcal{P}$$ be a convex polygon with $$50$$ vertices. A set $$\mathcal{F}$$ of diagonals of $$\mathcal{P}$$ is said to be minimally friendly if any diagonal $$d\in\mathcal{F}$$ intersects at most one other diagonal in $$\mathcal{F}$$ at a point interior to $$\mathcal{P}$$. Find the largest possible number of elements in a minimally friendly set $$\mathcal{F}$$.
Correct Answer: 71
Label the vertices of the convex $$50$$-gon $$\mathcal P$$, in counter-clockwise order, as $$1,2,\ldots ,50$$.
Pick the vertex $$1$$ and draw every diagonal emanating from it: $$\,(1,3),(1,4),\ldots ,(1,49)\,.$$ There are
$$50-3=47$$
such diagonals, and none of them intersect one another because they have the common endpoint $$1$$. They divide the polygon into
$$48$$
fan-shaped triangles $$T_1=[1,2,3],\;T_2=[1,3,4],\ldots ,T_{48}=[1,49,50].$$
Every diagonal that is not incident with the vertex $$1$$ must have its two endpoints on the boundary of two different fan triangles; call them the endpoint triangles of the diagonal. Such a diagonal necessarily crosses exactly one of the star diagonals, namely, the one that separates its two endpoint triangles.
No triangle can serve as an endpoint triangle for two different diagonals that are not incident with $$1$$. Indeed, if two diagonals shared the same endpoint triangle, then, inside that triangle, they would emanate from the same side and would have to cross each other before reaching their opposite endpoints, creating an additional interior intersection for at least one of them. That would violate the “at most one intersection per diagonal’’ condition.
Consequently, each diagonal that is not incident with $$1$$ occupies two exclusive endpoint triangles, and the $$48$$ triangles can supply at most
$$\left\lfloor\dfrac{48}{2}\right\rfloor=24$$
such diagonals. Call these the partner diagonals; each of them crosses exactly one star diagonal and is disjoint from every other diagonal in the set.
Hence the size $$|\mathcal F|$$ of any minimally friendly set satisfies
$$|\mathcal F| \le 47 \;+\;24 \;=\;71.$$
To see that $$71$$ can actually be attained, pair the triangles symmetrically:
$$T_1\!-\!T_{25},\;T_2\!-\!T_{26},\;\ldots ,\;T_{24}\!-\!T_{48}.$$
For each pair $$T_i,\;T_{i+24}$$ (indices mod $$48$$) draw the diagonal joining their outer vertices. Explicitly, for $$i=1,\dots ,24$$ join $$\bigl(i+1\bigr)\text{ with }\bigl(i+25\bigr).$$ These $$24$$ partner diagonals are mutually non-intersecting and every one of them crosses exactly the star diagonal $$(1,i+25).$$ Together with the original $$47$$ star diagonals we obtain
$$47+24=71$$
diagonals, and each diagonal intersects at most one other member of the family. Thus $$71$$ is both an upper bound and is achievable.
Therefore, the largest possible size of a minimally friendly set $$\mathcal F$$ in a convex $$50$$-gon is
71.
Predict your JEE Main percentile, rank & performance in seconds
Educational materials for JEE preparation