Home » Blog » Problems on Grids, Paths, and Chessboards for CAT Exam

Problems on Grids, Paths, and Chessboards for CAT Exam

Tuesday, November 3rd, 2020

---

Permutation and Combination Concepts:

Problems based on grids/chessboards are frequently asked among various exams. They appear to be really difficult when encountered for the first time but once we get hands on, they become really simple. The key lies in understanding the basic concepts involved. Although direct questions are rare, there could be questions which test the same concept in a hidden manner.

Number of squares in m*m figures

In a simple 2*2 figure, it is easy to see that there are 5 squares in total – 4 small ones and 1 large.

Again, if you try it in a 3*3 square,

You can see that there are 14 squares in total.

If you want to find all the 2*2 squares, start from the top left corner and you get (m-1) squares. Also, this can be done for (m-1) rows and total becomes (m-1) * (m-1) squares of 2*2 dimension. In a similar manner, it can be done for 3*3, 4*4 and so on till a square of dimensions m*m is reached that is the outer square. Hence the total number of squares becomes:

m² + (m-1)² + (m-2)² + … + 3² + 2² + 1² = ^{m(m+1) (2m+1)}/₆

 

Number of squares in m*n figures

Let us take an example of 2 rows and 3 columns. The number of unit squares is simply = 2 x 3 = 6.

There are squares of dimension 2*2 which are 2 in number. This gives a total of 8 squares.

mn + (m-1)(n-1) + (m-2)(n-2) + … (m-n+1)(1) where m>n

This can be simplified to:

Number of squares in an m*n squares (m>n) =

Number of rectangles in a Grid

Consider 2 sets of parallel lines (consisting of m+1 and n+1 lines) perpendicular to each other and intersect at all the points. For a rectangle, 2 horizontal and 2 vertical lines are needed.

Number of ways to choose from (m+1) and (n+1) line is ^m+1C₂ * ⁿ⁺¹C₂

In an m*m grid, the number of rectangles will also be given by the sum of cubes of the first m natural numbers which will be m²(m+1)²/4

The simple grids can be solved using the permutations, whereas some of them might be confusing.

Simple grids:

A person has to move from point A to point B taking the shortest route, the number of which is to be calculated. The shortest route signifies the person has to move top and right, which implies moving left or down is not allowed. Total nine steps are needed including 5 right and 4 up, so we need to rearrange the letters RRRRRUUUU in all possible ways, which is ^9!/_5!4!

Hence for any m*n grid, the number of ways to diagonally from one end to the another

is given by ^(m+n)!/_m!n!

 Now let us consider a case

There is a path C which shortens the route.

It should necessarily be a part of the shortest route. So, we need to reach C and go at the other end and proceed to B.

Now we have to reach A to D, D to E and E to B.

A to D is normal 2*2 grid, D to E is a single one and E to B is 2*1 grid.

So number of shortest routes = 4!/(2!2!) * 1 * 3!/(2!1!) = 18 ways

Problems
Given is a road map of a city in form of chess board (as shown in figure B where a portion in between is darkened to depict that in between roads are under construction). Find the number of different paths that a person can take to reach from A to X first then from Y to B under the condition that a person cannot take in between roads which are under construction?

 Solution:

Let us calculate the number of ways at which a person can go from A to X
In going from A to X a person will take 3 horizontal steps (HHH where H denotes horizontal steps) and 3 vertical ones (VVV where V denotes vertical step) i.e. he moved in manner VVVHHH

The no. of ways of arranging the word with 3 V and 3 H are 6!/(3! x 3!) = 20 ways
Now, in between roads are under construction so he cannot take in between roads which are under construction.

This leaves only 2 ways to go from X to Y i.e. from X ->P->Y or X ->Q->Y
In going from Y to B a person will take 2 horizontal steps (HH where H denotes horizontal steps)

and 2 verticals (VV where V denotes vertical step) i.e. he moved in manner VVHH.

We know the number of ways of arranging the word with 2 V and 2 H are 4!/(2!x2!) = 6 ways

Thus, the total number of ways in going from A to B = 20 × 2 × 6 = 240.

Two squares are chosen at random from small squares drawn on a chess board. Find the number of ways in which 2 squares can be chosen such that they have exactly one corner in common?

 Solution:

Two squares selected can have a corner common if they are selected from two consecutive rows or columns.

The number of ways to select two consecutive rows (or columns) are 7.
So for each pair of rows/columns, the count of pairs of squares having exactly one common corner =2× 7=14 ways
Total number of selections = 14× 7 =98

Find the number of ways in which a white and a black square on a chess board be chosen so that two squares do not belong to same row or column?

 Solution:
In a standard chess board, we have 32 white squares and 32 black squares.

Thus, a white square can be chosen in 32 ways and once a particular white square is chosen, we cannot pick any other square from that particular row or column (i.e. in that row or column we will have 4 black and 4 white squares). This leaves us with 32 – 8 = 24 squares.

So, the number of ways in which a white and a black square on a chess board be chosen so that two squares do not belong to same row or column are 32 ×24 =768.

 

In the given Grid (A Chessboard designed in such a way that middle square of outer chess board of 8×8 contains 1 smaller grid of dimension 4×4), Find the number of squares of all possible dimensions?

 Solution: 

The number of squares in the outer 8×8 chess board = 8²+7²+6²+5²+4²+3²+2²+1²=204

The number of squares in the inner 4 x 4 grid = 4²+3²+2²+1²=30

Since one square is common, required number of squares =204+30 -1 =233.

 

In how many ways can you place 2 rooks on 8*8 chessboard such that they are not in attacking positions?

Solution:

Number of ways of selecting 1^st rook= ⁶⁴C₁

Number of ways of selecting 2nd rook (it should not be in the same row or column) =7*7/2

Therefore, total number of ways= 64*7*7/2= 32*49=1568.

 

 

In how many ways is it possible to choose a white square and a black square on a chess board so that the squares must not lie in the same row or column? 

 Solution:

There are 32 ways by which a white square can be chosen.

If we remove the row and the column which contains the chosen white square, we will be left with 7 Rows & 7 Columns a total of 49 squares (24 black and 25 white). We would have removed 15 squares (7 white and 8 black)

Required ways = 32*24 = 768

 

If two squares are chosen on a 8*8 chessboard, what is the probability that they have one side in common?

 Solution:

Total number of ways of picking 2 squares= ⁶⁴C₂=2016

To get the favourable cases, we will consider 3 cases.

 

Case 1: The corner squares.

There are 4 corner squares. For each corner square, we can select the other square in 2 ways.

Therefore, for this cases, favourable cases= 4*2=8

 

Case 2: The squares on the edges.

There are 24 squares on the edges. For each such square, we can select the other square in 3 ways.

Therefore, for this cases, favourable cases= 24*3=72

 

Case 3: The inner squares.

There are 36 inner squares. For each such square, we can select the other square in 4 ways.

Therefore, for this case, favourable cases= 36*4=144

On adding these three cases we get 8+72+144=224

However, one catch over here is we have counted every case twice.

So total favourable cases= 224/2=112

The probability= 112/2016

 

If two squares are chosen on a 8*8 chessboard, what is the probability that they have one vertex in common?

 Solution:

Number of ways of picking 2 squares= ⁶⁴C₂= 2016

To get the favourable cases, we will consider 3 cases.

 

Case 1: The corner squares.

There are 4 corner squares. For each corner square, we can select the other square in 1 way.

Therefore, for this cases, favourable cases= 4*1=4

 

Case 2: The squares on the edges.

There are 24 squares on the edges. For each such square, we can select the other square in 2 ways.

Therefore, for this cases, favourable cases= 24*2=48

 

Case 3: The inner squares

There are 36 inner squares. For each such square, we can select the other square in 4 ways.

Therefore, for this cases, favourable cases= 36*4=144

 

On adding these three cases we get 4+48+144=196

One catch over here is we have counted every case twice.

So total favourable cases= 196/2=98

The probability= 98/2016.

Other posts related to Quantitative Aptitude – Modern Maths

Set Theory- Maximum and Minimum Values
How to solve questions based on At least n in Set Theory for CAT Exam?
Permutation and Combination – Fundamental Principle of Counting
How to find Rank of a Word in Dictionary (With or Without Repetition)
Basic Probability Concepts for CAT Preparation
Sequence and Series Problems and Concepts for CAT Exam Preparation
Permutation and Combination – Distribution of Objects

CAT Questions related to Quantitative Aptitude – Modern Maths

All questions from CAT Exam Quantitative Aptitude – Modern Maths
Quantitative Aptitude – Modern Maths – Progressions – Q1: If a1 = 1/(2*5), a2 = 1/(5*8), a3 = 1/(8*11),……, then a1 + a2 +……..+ a100 is
Quantitative Aptitude – Modern Maths – Progressions – Q2: An infinite geometric progression a1, a2, a3,… has the property that an = 3(a(n+ l) + a(n+2) +….) for every n ≥ 1. If the sum a1 + a2 + a3 +……. = 32, then a5 is
Quantitative Aptitude – Modern Maths – Progressions – Q3: Let a1, a2, a3, a4, a5 be a sequence of five consecutive odd numbers. Consider a new sequence of five consecutive even numbers ending with 2a3.
Quantitative Aptitude – Modern Maths – Progressions – Q4: Let a1, a2,……..a3n be an arithmetic progression with a1 = 3 and a2 = 7. If a1 + a2 + ….+a3n = 1830, then what is the smallest positive integer m such that m (a1 + a2 + …. + an ) > 1830?
Quantitative Aptitude – Modern Maths – Progressions – Q5: If the square of the 7th term of an arithmetic progression with positive common difference equals the product of the 3rd and 17th terms, then the ratio of the first term to the common difference is
Quantitative Aptitude – Modern Maths – P&C – Q1: How many four digit numbers, which are divisible by 6, can be formed using the digits 0, 2, 3, 4, 6, such that no digit is used more than once and 0 does not occur in the left-most position?
Quantitative Aptitude – Modern Maths – P&C – Q2: In how many ways can 8 identical pens be distributed among Amal, Bimal, and Kamal so that Amal gets at least 1 pen, Bimal gets at least 2 pens, and Kamal gets at least 3 pens?
Quantitative Aptitude – Modern Maths – P&C – Q3: In how many ways can 7 identical erasers be distributed among 4 kids in such a way that each kid gets at least one eraser but nobody gets more than 3 erasers?
Quantitative Aptitude – Modern Maths – P&C – Q4: Let AB, CD, EF, GH, and JK be five diameters of a circle with center at O. In how many ways can three points be chosen out of A, B, C, D, E, F, G, H, J, K, and O so as to form a triangle?

Quantitative Aptitude – Modern Maths – Set Theory – Q.1 If among 200 students, 105 like pizza and 134 like burger, then the number of students who like only burger can possibly be?
Quantitative Aptitude – Modern Maths – Progressions – Q.2 Let x, y, z be three positive real numbers in a geometric progression such that x < y < z. If 5x, 16y, and 12z are in an arithmetic progression then the common ratio of the geometric progression is? Quantitative Aptitude – Modern Maths – Set Theory – Q.3 Each of 74 students in a class studies at least one of the three subjects H, E and P. Ten students study all three subjects, while twenty study H and E, but not P. Every student who studies P also studies H or E or both. If the number of students studying H equals that studying E, then the number of students studying H is?
Quantitative Aptitude – Modern Maths – P&C – Q.4 How many numbers with two or more digits can be formed with the digits 1,2,3,4,5,6,7,8,9, so that in every such number, each digit is used at most once and the digits appear in the ascending order?
Quantitative Aptitude – Modern Maths – P&C – Q.5 In a tournament, there are 43 junior level and 51 senior level participants. Each pair of juniors play one match. Each pair of seniors play one match. There is no junior versus senior match. The number of girl versus girl matches in junior level is 153, while the number of boy versus boy matches in senior level is 276. The number of matches a boy plays against a girl is?
Quantitative Aptitude – Modern Maths – Progressions – Q.6 The arithmetic mean of x, y and z is 80, and that of x, y, z, u and v is 75, where u=(x+y)/2 and v=(y+z)/2. If x ≥ z, then the minimum possible value of x is?
Quantitative Aptitude – Modern Maths – Set Theory – Q.7 For two sets A and B, let AΔB denote the set of elements which belong to A or B but not both. If P = {1,2,3,4}, Q = {2,3,5,6,}, R = {1,3,7,8,9}, S = {2,4,9,10}, then the number of elements in (PΔQ)Δ(RΔS) is?
Quantitative Aptitude – Modern Maths – Set Theory – Q.8 If A = {6^2n -35n -1: n = 1,2,3,…} and B = {35(n-1) : n = 1,2,3,…} then which of the following is true?
Quantitative Aptitude – Modern Maths – Sequence and Series – Q.9 Let t1, t2,… be real numbers such that t1+t2+…+tn = 2n2+9n+13, for every positive integer n ≥ 2. If tk=103, then k equals?
Quantitative Aptitude – Modern Maths – Progressions – Q.10 Let a1, a2, … , a52 be positive integers such that a1 < a2 < … < a52. Suppose, their arithmetic mean is one less than the arithmetic mean of a2, a3, …, a52. If a52 = 100, then the largest possible value of a1 is?

---