• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

### Select your language

Suggested languages for you:

Americas

Europe

Q45E

Expert-verified
Found in: Page 735

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

### Answers without the blur.

Just sign up for free and you're in.

# 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

See the step by step solution

## Step 1: Given Information

• 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.

## Step 2: Definition

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.

## Step 3: Proof

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.

### Want to see more solutions like these?

Sign up for free to discover our expert answers

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.