Number of Triangles in an N-sided Polygon by white vertices only

0
5 min read

Maths is considered as one of the most important skills for a computer science student. It helps you to understand and analyze the problem to come up with an optimal solution.

In this article, one can learn one of the important topic of mathematics, i.e., combinatorics using a sample problem.

Problem Statement

You are given a polygon of N sides with vertices numbered from 1, 2, …, N. Now, exactly 2 vertices of the polygons are coloured black and remaining are coloured white. You are required to find the number of triangles denoted by A such that:

  1. The triangle is formed by joining only the white-coloured vertices of the polygon.
  2. The triangle shares at least one side with the polygon.

Approach

This problem can be solved in O(1) if you have a strong foundation of mathematics. For this law of combinatorics are required.

We can divide our problem in three parts as follows:-

  1. Polygon in which black vertices are adjacent to each other.
  2. Polygon in which there is a white vertex between black vertices.
  3. All other cases

Case 1: – Polygon in which black vertices are adjacent to each other

polygon with black vertices adjacent to each other

Here in the above image vertex 1 and vertex 2 are black and all other vertices are white.

Now, in this question, it is mentioned that the triangle should share at least one side with the polygon.

By the law of combinators,
No. of triangles formed = no. of ways to choose one side * no. of ways to choose another vertex – no. of triangles counted more than once.
Here, as triangles should have only white vertices side formed by vertex 1 or vertex 2 can’t be chosen.
No. of ways to choose one side= n-3C1 (as sides formed by (1,2),(1,6) and (2,3) can’t be chosen.

Let us assume that the side formed by vertex pairs (3,4) is chosen.

No. of ways to choose another vertex = n-4C1 (as vertices 1,2,3 and 4 can’t be chosen). We have 4 fewer choices when choosing another vertex.

Now, some triangles have been counted twice. For eg: -△ 345 is counted twice. Therefore, triangles formed by two sides common should be removed.

Generally, n triangles with two sides common can be formed with an n-sided polygon. But as black vertices can’t be included, we have 4 fewer pairs of two consecutive sides. (Pairs ((5,6),(6,1)), ((6,1),(1,2)), ((1,2),(2,3)), ((2,3),(3,4)) ) can’t be chosen). Therefore, n-4 triangles are counted twice.

No. of triangles formed: - n-3C1×n-4C1 - (n-4)
= (n-3) × (n-4) -(n-4)
= n2 - 7n + 12 -n +4 = n2-8n+16
= (n-4)2

No. of triangles formed in hexagon = (6-4)×(6-4) = 2×2=4
triangles formed in hexagon with black vertices adjacent to each other
Triangles formed are:- △356, △346, △345 & △456.

Case 2: – Polygon in which white vertex is between black vertices

polygon with a vertex between black vertices adjacent

Here, all vertices are white except vertex 1 and vertex 3.

By the law of combinators,
No. of triangles formed = no. of ways to choose one side * no. of ways to choose another vertex – no. of triangles counted more than once.
Here, as triangles should have only white vertices side formed by vertex 1 or vertex 2 can’t be chosen.
No. of ways to choose one side= n-4C1 (as sides formed by (1,2),(1,6),(2,3) and (3,4) can’t be chosen.

Similar to previous case, there are n-4C1 ways to choose another vertex.

No. of triangles counted twice = No. of triangles formed by two consecutive sides.
Here, We have 5 less consecutive pairs as black vertices are excluded. (Pairs ((5,6),(6,1)), ((6,1),(1,2)), ((1,2),(2,3)), ((2,3),(3,4)) & ((3,4),(4,5)) ) can’t be chosen).

No. of triangles formed: - n-4C1×n-4C1 - (n-5)
= (n-4) × (n-4) -(n-5)
= n2 - 8n + 16 -n +5
= n2-9n+21

No. of triangles formed in hexagon = 6×6 – 9×6 +21 = 36 – 54 + 21 = 3
triangles formed in hexagon with more than one white vertex between black vertices
Triangles formed are:- △245, △256 & △456.

Case 3: – Polygon in which there are more than two or more vertices between black vertices

no of triangle in a polygon
Hexagon with two white vertices between black vertices

Here all vertices are white except 1 vertex 1 and vertex 4.

Similar to previous case, the no. of ways to choose a side and another vertex are same, i.e, n-4C1

There are no consecutive pairs in the above hexagon. By visualizing some more polygons with more sides we can deduce that there are 6 fewer pairs.

No. of triangles formed: - n-4C1×n-4C1 - (n-6)
= (n-4) × (n-4) -(n-6)
= n2 - 8n + 16 -n +6
= n2-9n+22

No. of triangles formed in hexagon = 6×6 – 9×6 +22 = 36 – 54 + 22 = 4
triangles formed in hexagon with white vertex between black vertices
Triangles formed are:- △235, △236, △256 & △356.

Code in Python

for _ in range(int(input())):
    n,b1,b2=map(int,input().split())
    if abs(b1-b2)==1 or abs(b1-b2)==n-1:
        print((n-4)**2)
    elif abs(b1-b2)==2 or abs(b1-b2)==n-2:
        print(n*n-9*n+21)
    else:
        print(n*n-9*n+22)

If you found any error, feel free to post in the comments section.

Reference Link:- https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/number-of-triangles-6ac88eb2/description/

Choose your Reaction!
Leave a Comment