Test of Mathematics Solution Subjective 188 - The Numbered Chessboard

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 188 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Problem

Consider the squares of an $ 8 X 8 $ chessboard filled with the numbers 1 to 64 as in the figure below. If we choose 8 squares with the property that there is exactly one from each row and exactly one from each column, and add up the numbers in the chosen squares, show that the sum always adds up to 260.

Untitled


Solution

The problem asks us to choose numbers selectively such that they are from unique rows and columns. We write the numbers in the table in such a manner that helps us in our calculations. This is how it will be done:

Let the number in the $ i^{th} $ row and $ j^{th}$ column be $ x$. If we carefully observe the table we find an intuitive way of representing $ x$ as follows:

$ x = 8*(i-1) + j $ if $ x$ is the element in the $ i^{th} $ row and $ j^{th}$ column. Now all that is left to do is sum up all such numbers such that no two $ j^{t} $ or $ i^{th}$ value is same. There for the total sum is: $ (8*(i_1-1)+ j_1) + (8*(i_2-1) + j_2) + . . . + (8*(i_8-1) + j_8) $

that means Sum (S) = $ (8*(i_1 - 1 + i_2 - 1 + . . . + i_8 - 1)) + (j_1 + j_2 + . . . + j_8) $

$ => S = 8*(i_1 + i_2 + i_3 + ... + i_8 - 8) +  (j_1 + j_2 + . . . + j_8)$

We know that as all the $ i$ and $ j$ values are different and range from 1 to 8 we can ascertain that

the sum of the $ i$ values $ = $ sum of $ j$ values = $ 1+2+3+...+8 = \frac{8*(8+1)}{2}$

Therefore S = $ 8*(\frac{8*(8+1)}{2} - 8) + \frac{8*(8+1)}{2} $ = $ 8*(36-8) +36 = 260 $

Hence the sum of all the values taken from unique rows and columns is 260.

Hence Proved.


Chatuspathi:

Test of Mathematics Solution Subjective 181 - Diagonal Moves

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 181 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

Suppose that one moves along the points (m, n ) in the plane where m and n are integers in such a way that each move is a diagonal step, that is, consists of one unit to the right or left followed by one unit either up or down.

(a) Which point (p, q) can be reached from the origin.

(b) What is the minimum number of moves needed to reach such a point (p, q)?


Discussion

For each horizontal movement (right or left) there is one vertical movement (up or down). Suppose there are R right moves, L left moves. Also there be U upward move and D downward move. Since number of horizontal movement equals number of vertical movements hence we have

R+L = U+D = k (say)

The final coordinate reached is (R - L , U - D) (as each right move counts as +1 and left move counts as -1, and similarly for vertical movements),

L = k -R

D = k -U

Hence the final coordinate is (2R - k, 2U - k)

Therefore both the coordinates are of same parity (that is either both are even or both are odd).

So we have shown that the final point that can be reached has both x and y coordinate of the same parity. Now we show the converse. That is all the points whose x and y coordinates are of same parity can be reached.

Say P be a point whose both coordinates are even. Without loss of generality we may say P = (2m, 2n) where $ 2m \ge 2n $ and both coordinates are positive.

1. 2(m-n) moves of the form Right-Up followed by Left-down is performed to reach the point (2(m-n) , 0)

2. Next 2n moves of the form Right-Up is performed to reach the point (2m, 2n)

So in total 2(m-n) + 2n = 2m moves are performed to reach the point (2m, 2n)

Similarly to reach a point whose both coordinates are odd, say (2j+1, 2l + 1),  we first reach the point (2j, 2l) and then move one more unit diagonally upward.

This same algorithm will work for all the quadrants.

Also if (p, q) is the final coordinate with p > q, we have taken p steps to reach the point. It is not possible to reach the point in less than p steps, because we must cover at least p boxes in at least one direction and in one step exactly one box can be covered.

Therefore we have found the answer:

(1) All the points (p, q) can be reached where $ p \equiv q \text{mod} 2 $

(2) If $ p \ge q$ , minimum number of steps required is p. If $ q \ge p $, the minimum number of steps required is q.

Test of Mathematics Solution Subjective 58 - Balls of Different Color

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 58 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

In a certain game, 30 balls of k, different colours are kept inside a sealed box .You are told only the value of k,but not the number of balls of each colour . Based on this, you have to guess whether it is possible to split the balls into 10 groups of each, such that in each group the three balls are of different colours.Your answer is to be a simple YES or NO.You win or loss a point according as your guess correct or not.For what values of k, you can say NO and be sure of winning?For what values of k, you can say YES and be sure of winning?Justify your solution.


Solution:

(i) No & sure of winning :- 1,2.

Justification: If colours are there the 3 balls cannot be of different colours & if $ {{k} \ge {3}} $ then there exists a possibility of splitting into two groups of 3 each in each group 3 balls are of different colours.

For k = 3 take 10 ball of each colour & the splitting is possible.

(ii) Yes & sure of winning 21,...,30


Justification:

By we can say that number of ball of a certain colour is at most two.So we can keep them in different boxes.For $ {{k} \le {20}} $ is not possible .

For example take (k-1) balls of different colours & (30-k+1) ball of different colour. Now by (30-k+1) ball of same colour are placed in two groups.So at least one group contain more than one ball of same colours.

Test of Mathematics Solution Subjective 60 - Equivalence Class

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 60 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

Consider the set S of all integers between and including 1000 and 99999. Call two integers x and y in S to be in the same equivalence class if the digits appearing in x and y are the same. For example, if x = 1010, y = 1000 and z = 1201, then x and y are in the same equivalence class, but y and z are not. Find the number of distinct equivalence classes that can be formed out of S.

Solution

Any set of distinct digits with maximum order 5 is a equivalence class that can be formed out of S except {0}.
Number of such sets is
= $ { {10} \choose {1}} $ + $ { {10} \choose {2}} $ + $ {{10} \choose {3}} $ + $ { {10}\choose{4}} $ + $ {{10}\choose{5}} $ -1
= 10 + 45 + 120 + 210 + 252 -1
= 636

Test of Mathematics Solution Subjective 59 - Number of squares

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 59 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

Consider the set of point S = { (x,y) : x,y are non-negative integers $ {\le {n}} $ }.
Find the number of squares that can be formed with vertices belonging to S and sides parallel to the axes.

Solution

S = {(x,y) : x,y are non-negative integers $ {\le {n}} $ }
We calculate number of squares by calculating number of |x| squares ,& number of squares number of $ {{n}* {n}} $ squares.
Now number of |x| squares = number of choosing one pair of lines with difference 1 parallel to x axis & integer distance x number of choosing one pair of lines to y axis with distance 1 & integer distance from y axis = $ {{n}*{n}} $ = $ {n^2} $
Similarly number of $ {{k}*{k}} $ squares
= $ {(n-k+1)^2} $
So total number of squares
= $ {\sum_{k=1}^{n}}{{k}^{2}} $ = $ {\frac{n(n+1)(2n+1)}{6}} $

Test of Mathematics Solution Subjective 55 - Partition of a set of functions

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 55 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

For a finite set A, let |A| denote the number of elements in set A.

(a) Let F be the set of all functions f:{1, 2, ... , n} --> {1, 2, ... , k}  $ (n \ge 3, k \ge 2 ) $ satisfying $ f(i) \ne f(i+1) $ for every i, $ 1\le i \le n-1 $. Show that |F| = $ k(k-1)^{(n-1)}$.

Solution

The function f may take the element 1 in domain to one of the k numbers in codomain (k choices for 1). Since f(2) cannot equal f(1), we have (k-1) choices for 2 to go. Similarly f(3) cannot equal f(2) (but it can equal f(1)) so there are k-1 choices for 3 and so on. In total the number of functions possible equals $ k \times (k-1) \times (k-1) ... (n-1) \times = k (k-1)^{(n-1)} $.

(b) Let c(n,k) denote the number of functions in F such that $ f(n) \ne f(1) , n \ge 4$. Then show that $ c(n,k) = k(k-1)^{(n-1)} - c(n-1, k) $

Solution: We consider the following partition of the set of functions F:
(1) functions in which $ f(n) \ne f(1)$
(2) functions in which f(n) = f(1)
Note the above partition is well defined as they are mutually exclusive and exhaustive. Functions of type (1) are given by c(n, k) and functions of type two is given by c(n-1, k) because if f(n) = f(1), f(n-1) cannot equal f(1) as F contains functions for which $ f(i) \ne f(i+1) $
As functions of type 1 and type 2
makes up all the functions in F we have $ c(n,k) + c(n-1, k) = k(k-1)^{(n-1)} $.

(c) Using part (b) or otherwise prove $ c(n, k) = (k-1)^{(n-1)} + (-1)^n (k-1) $

Solution: We use induction on part (b). Suppose $ c(n, k) = (k-1)^{(n-1)} + (-1)^n (k-1) $. Then $ c(n+1, k) = k (k-1)^{(n)} - c(n, k) = k (k-1)^{(n)} - (k-1)^{(n-1)} + (-1)^n (k-1) $

Test of Mathematics Solution Subjective 50 -Dictionary Ranking

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 50 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

All the permutation of the letters \(a,b,c,d,e\) are written down and arranged in alphabetical order as in dictionary. Thus the arrangement \(abcde\) is in first position and \(abced\) is in second position. What is the position of the word \(debac\)?


Solution:


According to the arrangement in a dictionary, number of words:

i) starting with \(a\) = 4!

ii) starting with \(b\) = 4!

iii) starting with \(c\) = 4!

iv) starting with \(da\) = 3!

v) starting with \(db\) = 3!

vi) starting with \(dc\) = 3!

vii) starting with \(dea\) = 2!

viii) starting with \(deba\) = 1!

The last case gives us the word itself. So the position of the word will be = \(3*4! + 3*3! + 2! +1\) = \(93\)

\(debac\) is in the \(93^{rd}\) position.

Test of Mathematics Solution Subjective 49 - Arrangement of Similar Items

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 49 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem:

\(x\) red balls, \(y\) black balls,\(z\) white balls are to be arranged in a row. Suppose that any two balls of the same color are indistinguishable. Given \(x+y+z=30\) prove that number of possible arrangements is maximum when \(x=y=z=10\).

Solution:

Given a total of \(n\) objects out of which \(r\) are of the same type, total number of arrangements possible is given by \(\frac{n!}{r!}\). Therefore in this case the total number of arrangements is \(\frac{30!}{x!y!z!}\).

Now we have to maximise \(\frac{30!}{x!y!z!}\).

Thus we need to minimise \({x!y!z!}\). As the question claims that all have to be equal to \(10\), let us consider that they are not all equal to \(10\). So the cases that arise are:

Case 1: \(x>10\) , \(y=10\), \(z<10\)

OR

Case 2: \(x>10\), \(y>10\), \(z<10\)

OR

Case 3: \(x>10\), \(y<10\), \(z<10\)

These cases are considered without any loss of generality as any other possible case will just be another permutation of the given cases.

So as the question claims the ideal condition is \(x!y!z!=(10!)^3\).

Now considering Case 1, as \(x+y+z=30\), \(x!y!z!=(10+a)!(10)!(10-a)!\) = \((10!)^3\frac{(10+1)(10+2)\cdots(10+a)}{(10-1)(10-2)\cdots(10-a)}> (10!)^3\). So this is not a possible option as we have to minimise \(x!y!z!\).

Now taking Case 2, \(x!y!z!=(10+a)!(10+b)!(10-a-b)!\) = \((10!)^3\frac{[(10+1)(10+2)\cdots(10+a)][(10+1)(10+2)\cdots(10+b)]}{(10-1)(10-2)\cdots(10-a-b)}> (10!)^3\). So again not a possibility.

Similarly it can be shown for Case 3 also, thus proving that any other value of \(x,y\) and \(z\) does not minimise \(x!y!z!\).

Hence \(x=y=z=10\) is the solution that maximises the number of possible arrangements.

 

Test of Mathematics Solution Subjective 48 - The Gifts Distribution

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 48 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

Find the different number of ways \(5\) different gifts can be presented to \(3\) children so that each child receives at least one gift.

Solution:

There are two possible ways in which the gifts can be distributed.

Case 1: They are distributed as \(2,2,1\).

So first we choose the children who get \(2\) gifts each in \(^3C_2\) ways. Then we choose the gifts in \(\frac{5!}{2!.2!}\) ways.

Thus total number of ways = \(3.\frac{5!}{2!2!}= 90\) ways.

Case 2: They are distributed as \(3,1,1\).

So first we choose the child who gets \(3\) gifts  in \(^3C_1\) ways. Then we choose the gifts in \(\frac{5!}{3!}\) ways.

Thus total number of ways = \(3.\frac{5!}{3!}= 60\) ways.

Therefore total number of ways to distribute the gifts = \(90+60\) = \(150\) ways.

 

Test of Mathematics Solution Subjective 46 - Number of Onto Functions

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 46 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.


Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

A function \(f\) from set \(A\) into set \(B\) is a rule which assigns each element \(x\) in \(A\), a unique (one and only one) element (denoted by \(f(x)\) in \(B\). A function of set from \(A\) into \(B\) is called an onto function, if for each element \(y\) in \(B\) there is some element \(x\) in \(A\), such that \(f(x)=y\). Now suppose that \(A =\) {\(1,2,\cdots,n\)} and \(B=\){\(1,2,3\)}. Determine the total number of onto functions of \(A\) into \(B\).

Sequential Hints


(How to use this discussion: Do not read the entire solution at one go. First, read more on the Key Idea, then give the problem a try. Next, look into Step 1 and give it another try and so on.)

Key Idea

This is the generic use case of Inclusion-Exclusion Principle. Read on this from Wikipedia

Step 1

1 may map to 1, 2, or 3 (3 choices). For each of these three choices, may map to 1, 2, or 3 (again three choices. Hence 3 choices again. How many functions are possible in total? Can you delete the functions which are not onto from the total number of functions?

Try the problem with this hint before looking into step 2. Remember, no one learnt mathematics by looking at solutions.

The total number of functions is \( 3^n \) since there are 3 output choices for each of the n input choices. Now let us count the functions which are not onto.

How many functions are there such that \( 1 \in B \) has no preimage? (that is nothing is going to 1). There are \( 2^n \) such functions as each of the n elements of A has 2 choices. Similarly, count the cases where nothing goes to 2 (\(2^n \) more cases) and nothing goes to 3 (\( 2^n \) more cases).

Delete these 'not onto' cases ( \( 3 \times 2^n \)) from total number of cases ( \( 3^n \) ).

But we have double deleted the case where nothing goes to 1 'and' nothing goes to 2. This is the case where everything goes to 3. Only one such function is there: f(x) = 3.

Similarly, we have double deleted the case where nothing goes to 2 'and' nothing goes to 3. This is the case where everything goes to 1. Only one such function is there: f(x) = 1.

Similarly, we have double deleted the case where nothing goes to 1 'and' nothing goes to 3.

This is the case where everything goes to 2. Only one such function is there: f(x) = 2. Since we do not want to double delete something, we add back these three cases.

Thus the final answer is: \( 3^n - 3 \times 2^n + 3 \)