StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q45E

Expert-verifiedFound in: Page 735

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Question: Show that \(g\left( n \right) \ge \frac{n}{3}\). (Hint: Consider the polygon with \(3k\) vertices that resembles a comb with \(k\) prongs, such as the polygon with \(15\) sides shown here.**

Thus,\(g(n) \ge \left( {n/3} \right)\)

Hence proved

- To prove that \(g(n) \ge \left( {n/3} \right)\)
- Consider the polygon with \(3k\) vertices that resembles a comb with \(k\) prongs, such as the polygon with \(15\) sides shown here.

**In a two-dimensional plane, a polygon is a closed figure made up of line segments (not curves). Polygon is made up of two words: poly, which means many, and gon, which means sides. To construct a closed figure, at least three line segments must be connected end to end. Thus, a triangle is a polygon with at least three sides, commonly known as a three-gon.**

There are \(3k\) vertices in the figure indicated in the suggestion i.e. generalized to have \(k\) prongs for each \(k \ge 1\). Consider the range of points from which a guard can view the first prong's tip, the range of points from which a guard can see the second prong's tip, and so on. This is a set of disconnected triangles that is together with their interiors.

As a result, each of the k prongs needs its own protection, requiring at least \(k\) guards. This shows that

\(g(3) \ge k = \left( {3k/3} \right)\).

To deal with \(n\) values that aren't multiples of three.

Let \(n = 3k + i,\)where \(i = 1\)or\(2.\)

then obviously

\(g(n) \ge g(3k) \ge k\left( {3k/3} \right)\).

So, we get

\(g(n) \ge \left( {n/3} \right)\)

Hence the result.

94% of StudySmarter users get better grades.

Sign up for free