calendarBack
Quant

/

Modern Maths

/

Permutations & Combinations
ALL MODULES

CAT 2025 Lesson : Permutations & Combinations - Selection in Geometry

bookmarked

7. Combinations in Geometry

7.1 Intersection of circles of different radii

Number of ways in which 22 circles can be selected from nn circles == nC2=n(n−1)2^{n}C_{2} = \dfrac{n(n - 1)}{2}

As any 22 circles can form a maximum of 22 intersection points,

Maximum Intersection points =n(n−1)2×2=n(n−1)= \dfrac{n(n - 1)}{2} \times 2 = \bm{n(n - 1)}

7.2 Intersection of non-concurrent lines

When 33 or more lines intersect each other at the same common point, they are called concurrent lines.

If there are n\bm{n} non-concurrent lines, any 22 such lines will form 11 intersection point. Number of intersection points is the number of ways in which 22 lines can be selected, i.e. nC2\bm{^{n}C_{2}}.

7.3 Lines drawn through non-collinear points

Non-collinear points are those where not more that 22 of them can lie on a straight line. In other words, three or more points do not lie on one line.

Through any 22 points, 11 line can be drawn. Therefore, to find number of lines formed by a pair of points, we need to find the number of pairs that can be chosen from n\bm{n} non-collinear points, i.e. nC2^{n}C_{2}.

7.3.1 Lines drawn through collinear & non-collinear points

Note that the collinear cases need to be removed. So, number of straight lines that can be drawn where there are nn points of which rr are collinear is nC2−^{n}C_{2} - rC2+1^{r}C_{2} + 1. Note that 11 is added back as this is to consider the 11 line that can be drawn through the collinear points.

Example 56

A to J are 1010 points on a plane. A, B, C and D are collinear. E, F and G are another set of collinear points. If no other set of 33 or more points are collinear, then how many different lines can be drawn through these points?

Solution

For a line to be formed, two distinct points are required. So, the total number of lines which can be formed with the 1010 points are 10C2=45^{10}C_{2} = 45 lines.

But since A, B, C and D are collinear, we can construct only one line with it. So, the 4C2^{4}C_{2} lines formed with it has to be eliminated and only 11 line should be added. Likewise, 3C2^{3}C_{2} lines has to be eliminated and only 11 line should be added for E, F and G, as they are also collinear.

Therefore, total number of lines == 10C2−^{10}C_{2} - 4C2+1−^{4}C_{2} + 1 - 3C2+1=^{3}C_{2} + 1 = 45−6+1−3+1=3845 - 6 + 1 - 3 + 1 = 38

Answer: 3838


Example 57

What is the maximum number points of intersection that can be formed by 6 non-overlapping lines and 5 circles of different radii on a plane?

Solution

2 non-overlapping lines can intersect at a maximum of 1 point. 2 circles of different radii can intersect at a maximum of 2 points. 1 circle and 1 line can intersect at a maximum of 2 points.

Selecting No. of Ways Max Intersection Points Total Points
22 lines 6C2^{6}C_{2} 11 15×1=1515 \times 1 = 15
22 circles 5C2^{5}C_{2} 22 10×2=2010 \times 2 = 20
11 line & 11 circle 6C1×^{6}C_{1} \times 5C1^{5}C_{1} 22 30×2=6030 \times 2 = 60
Total 9595


Answer: 9595


7.4 Triangles drawn through non-collinear points

As the points are non-collinear, with every 33 points, 11 triangle can be drawn. Therefore, number of triangles that can be drawn is the number of ways in which 33 points can be selected from n\bm{n} non-collinear points, which is nC3\bm{^{n}C_{3}}.

7.4.1 Triangles drawn through collinear & non-collinear points

If 33 points lie on a straight line, we cannot draw a triangle using them. Let out of a total of n\bm{n} points, r\bm{r} points be lying on a straight line, and none of the other points being collinear.

Total number of triangles, assuming all nn points are collinear == nC3^{n}C_{3}

However, the above calculation includes triangles formed using the rr collinear points, which is rC3\bm{^{r}C_{3}}. This needs to be subtracted.

Therefore, number of triangles that can be drawn from n\bm{n} given points, where r\bm{r} points lie on the straight line and none of the other points are collinear == nC3−rC3\bm{^{n}C_{3} - ^{r}C_{3}}

Example 58

There are 1515 points on a plane. Of this, 66 of them belong to one set of collinear points and 44 of them are another set of collinear points. The rest of the points are non-collinear. What is the maximum number of triangles that can be formed using these points as the vertices?

Solution

If all 99 points were non-collinear, then number of triangles that can be drawn == 15C3=455^{15}C_{3} = \bm{455}

Triangles that cannot be formed are those within the respective sets of collinear points.

Triangles that cannot be formed == 6C3+^{6}C_{3} + 4C3=24^{4}C_{3} = \bm{24}

Number of triangles that can be formed =455−24=431= 455 - 24 = \bm{431}

Answer: 431431


7.5 Diagonals of a Polygon

This can be explained in 22 ways.

Logical Approach: From a vertex of a polygon, diagonals can be drawn to all the other vertices other than itself and its 22 adjacent vertices. Therefore, in an nn-sided polygon, from a point we can draw n−3\bm{n - 3} diagonals. There are nn such vertices we should be able to draw n(n−3)n(n - 3) diagonals. However, diagonals are double counted here (for instance a diagonal from A to C which is also from C to A is counted twice). We can remove this by dividing by 22.

Number of diagonals of an nn-sided polygon =n(n−3)2= \bm{\dfrac{n(n - 3)}{2}}

Combinations Approach: Between any 22 points in a polygon, lines can be drawn. Number of ways in which we can select 22 points is nC2=n(n−1)2^{n}C_{2} = \dfrac{n(n - 1)}{2}

However, lines connecting adjacent vertices are sides of the polygon and not diagonals. There are nn such sides which need to be removed.

Number of diagonals of an nn-sided polygon == nC2−n=n(n−1)2−n=^{n}C_{2} - n = \dfrac{n(n - 1)}{2} - n = n(n−3)2\bm{\dfrac{n(n - 3)}{2}}

7.6 Parallelograms formed by parallel lines

Where m\bm{m} parallel lines intersect another set of n\bm{n} parallel lines, parallelograms can be formed. We can form a parallelogram with any 22 of the mm parallel lines and any 22 of the nn parallel lines.

mC2^{m}C_{2} and nC2^{n}C_{2} is the number of ways to select 22 lines from mm and nn parallel lines respectively.

Number of parallelograms that can be formed == mC2×\bm{^{m}C_{2}} \times nC2\bm{^{n}C_{2}}

7.7 Rectangles and Squares

From a larger rectangle with mm rows and nn columns,
Number of rectangles that can be formed =(1+2+...+m)= (1 + 2 + ... + m) (1+2+...+n)=(1 + 2 + ... + n) = m(m+1)2×n(n+1)2\dfrac{m (m + 1)}{2} \times \dfrac{n (n + 1)}{2}

Number of squares that can be formed =mn+(m−1)(n−1)+(m−2)(n−2)+...= \bm{mn + (m - 1) (n - 1) + (m - 2) (n - 2) + ...}

If we have a square instead of a rectangle, then the number of rows and columns will be the same. We can simply replace mm with nn in the above formulae.

From a larger square with nn rows and nn columns,

Number of rectangles that can be formed =(n(n+1)2)2= \bm{\left( \dfrac{n(n + 1)}{2} \right)^{2}}

Number of squares that can be formed =n2+(n−1)2+...+1== n^{2} + (n - 1)^{2} + ... + 1 = n(n+1)(2n+1)6\bm{\dfrac{n (n + 1) (2n + 1)}{6}}

Example 59

How many squares are there in a chessboard which has 88 rows and 88 columns?

Solution

With equal number of rows and columns, we have a large square.

Number of squares that can be formed from a large square =n(n+1)(2n+1)6= \dfrac{n(n + 1) (2n + 1)}{6}

=8(8+1)(16+1)6=12×17=204= \dfrac{8 (8 + 1) (16 + 1)}{6} = 12 \times 17 = 204

Answer: 204204


Loading...Loading Video....