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.

Short Answer

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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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.

Step by Step Solution

Step 1: Given Information

Step 2: Definition

Step 3: Proof

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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.

Step by Step Solution

Step 1: Given Information

Step 2: Definition

Step 3: Proof

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths