Indian Statistical Institute B.Math & B.Stat : Combinatorics

In how many ways one can choose three distinct numbers from the set \( \{1,2,3,\dots \dots,19,20\}\) such that their product is divisible by 4? $$$$ We partition the set \( \{1,2,3,\dots \dots,19,20\}\) into three disjoint sets \(S_1=\{4,8,12,16,20\},S_2=\{2,6,10,14,18\},S_3=\{1,3,5,7,9,11,13,15,17,19\}\) $$$$ Three selected (distinct) numbers will not be divisible by $4$ $iff$ all the $three$ numbers are selected form $S_3$ or $two$ of them are selected from $S_3$ and $one$ of them from $S_1$. Numbers of such numbers are \( \binom{10}{3}+\binom{5}{2} \times \binom{5}{1} = 345 \) $$$$ So numbers of selection such that their product is divisible by $4$ is \(\binom{20}{3}-345= 795 \)

Indian Statistical Institute B.Math & B.Stat : Number Theory

Find the digit at the unit place of \[\big(1!-2!+3!-\dots \dots +25!\big )^{\big(1!-2!+3!-\dots \dots +25!\big )}\] First note that \( k! \equiv 0 (mod\ 10) \) for all $k \geq 5 , k \in \mathbb{N}$ $$$$ So, \( 5!-6!+7!-\dots \dots +25! \equiv 0 (mod\ 10) \) and \( 1!-2!+3!-4! = -19 \equiv 1 (mod\ 10)\) (Using the property of $congruences$). $$$$ Using the above two congruences \( \big(1!-2!+3!-\dots \dots +25!\big ) \equiv 1 (mod\ 10) \) $$$$ So, \[\big(1!-2!+3!-\dots \dots +25!\big )^{\big(1!-2!+3!-\dots \dots +25!\big )} \equiv 1^{\big(1!-2!+3!-\dots \dots +25!\big )} \equiv 1 (mod 10) \] giving $1$ as the last digit. $$$$ Let \(a \equiv a' (mod\ m) \) and \(b \equiv b' (mod\ m)\), then important properties of $congruences$ include the following, where $\implies$ means "implies": $$$$ 1. Reflexivity: $a\equiv a (mod- m)$. $$$$ 2. Symmetry: \(a\equiv b (mod\ m) \implies b\equiv a (mod\ m)\).$$$$ 3. Transitivity: \(a\equiv b (mod\ m)\) and \(b \equiv c (mod\ m)\implies a\equiv c (mod\ m)\). $$$$ 4. \(a+b \equiv a'+b' (mod\ m)\)$$$$ 5. \(a-b\equiv a'-b' (mod\ m)\). $$$$ 6. \(ab\equiv a'b' (mod\ m)\). $$$$ 7. \(a\equiv b (mod\ m)\implies ka \equiv kb (mod\ m)\). $$$$ 8. \(a\equiv b (mod\ m)\implies a^n\equiv b^n (mod\ m)\). $$$$ 9. \(ak\equiv bk (mod\ m)\implies\) \(a\equiv b \big(mod\ \frac{m}{(k,m)}\big),\) where $(k,m)$ is the greatest common divisor. $$$$ 11. If $a \equiv b (mod\ m)$, then $P(a) \equiv P(b) (mod\ m)$, for $P(x)$ a polynomial with integer coefficients.

Indian Statistical Institute B.Math & B.Stat : Number Theory

Find the sum of all even positive divisors of $1000$. $$$$ \( 1000 = 2^3 \times 5^3 \). Now any even divisor of $1000$ must contain a factor of the form $2^j$ where $j \in \{1,2,3\}$. We note that $2$ and $5$ are the only prime factors of $1000$ , so a even factor must be of the form $2^j\times 5^i$ where $j \in \{1,2,3\}$ and $i \in \{0,1,2,3\}$. $$$$ So the required sum is \( \sum_{j=0}^{3} \sum_{i=1}^{3} 2^i \times 5^j =\sum_{j=0}^{3} 14 \times 5^j = 14 \times \frac{5^4-1}{5-1} = 2184\)

Indian Statistical Institute B.Math & B.Stat : Integration

Let $\alpha$ and $\beta$ be two positive real numbers. For any integer $n>0$, define \( a_n = \int_{\beta}^{n} \frac{\alpha}{u(u^\alpha+2+u^{-\alpha})}du\). Then find \( \lim_{n \to \infty} a_n \). $$$$ Multiplying $u^{\alpha-1}$ to the numerator and denominator of the integrand, we have \( a_n = \int_{\beta}^{n} \frac{\alpha u^{\alpha-1}}{u\times u^{\alpha-1}(u^\alpha+2+u^{-\alpha})}du\) $$$$ Substituting $u^{\alpha}=t$ we get the transformed integral as \(a_n = \int_{\beta^\alpha}^{n^\alpha}\frac{dt}{(t+1)^2}dt = \frac{n^\alpha-\beta^\alpha}{(1+\beta^\alpha)(1+n^\alpha)}\) $$$$ Therefore,\( \lim_{n \to \infty} a_n = \lim_{n \to \infty} \frac{n^\alpha-\beta^\alpha}{(1+\beta^\alpha)(1+n^\alpha)}= \lim_{n \to \infty} \frac{1-\big({\frac{\beta}{n}}\big)^\alpha}{(1+\beta^\alpha)(1+\frac{1}{n})}=\frac{1}{1+\beta^\alpha}\)

Indian Statistical Institute B.Math & B.Stat : Number Theory

Let $S$ be the set of all integers $k$, \( 1 \leq k \leq n\), such that $g.c.d(k,n)=1$. What is the arithmetic mean of the integers in $S$?. $$$$ First note that \( |S| = \phi(n) \). Now let $k \in S$ then there exists intergers $u,v$ such that $ku+nv=1\dots (A)$. $$$$ The integer \( n-k \in \{1,2,\dots,n-1\} \) because $k$ can never be equals $n$, for $g.c.d(n,n)=n$ and $k \in S$. We will now show that $g.c.d(n-k,n)=1.$ Adding $-nu$ to both sides of $(A)$ we get \( -nu+ku+nv=-nu+1 \implies -u(n-k)+(v+u)n = 1 \implies g.c.d(n-k,n)=1 \) $$$$ So, for \( k \in \{1,2,\dots,n-1\}\) if \( k \in S \implies n-k \in S \) Thus $S$ can be written in the form, \( S=\{k_1,k_2,k,.....,k_r,n-k_r,......,n-k_2,n-k_1\} \) where $|S| = \phi(n)$ $$$$ Clearly the sum of the elements of $S$ is \( (k_1+n-k_1)+(k_2+n-k_2)+\dots+(k_r+n-k_r) = \frac{n\phi(n)}{2} \) ( Pairing reduces the terms to half the original ($\phi(n)))$. $$$$ arithmetic mean \[ =\frac{\frac{n\phi(n)}{2}}{\phi(n)} = \frac{n}{2} \]

Indian Statistical Institute B.Math & B.Stat : Inequality

If \(a,b,c \in (0,1) \) satisfy $a+b+c=2$, prove that \( \frac{abc}{(1-a)(1-b)(1-c)} \geq 8. \) $$$$ Let \( p = 1-a, q = 1-b, r = 1-c \). $p+q+r= 3-(a+b+c)=1$.Clearly $p,q,r$ are positive. Substituting in the given inequality, it transforms to $$$$ \( \frac{(1-p)(1-q)(1-r)}{pqr} \geq 8 \iff {(1-p)(1-q)(1-r)} \geq 8{pqr} \) $$$$ \( \iff 1-(p+q+r)+qr+rp+pq-pqr \geq 8{pqr} \iff qr+rp+pq-pqr \geq 8{pqr} \) $$$$ \( \iff qr+rp+pq \geq 9{pqr} \iff \frac{1}{p}+\frac{1}{q}+\frac{1}{r} \geq 9 \) $$$$ Thus proving the above inequality reduces to proving \(\frac{1}{p}+\frac{1}{q}+\frac{1}{r} \geq 9\) subjected to $p+q+r=1$ $$$$ Since $p,q,r$ are positive, apllying $A.M \geq H.M$ we have \( \frac{p+q+r}{3} \geq \frac{3}{\frac{1}{p}+\frac{1}{q}+\frac{1}{r}}\) $$$$ Noting $p+q+r=1$, we have \(\frac{1}{p}+\frac{1}{q}+\frac{1}{r} \geq 9 \)

Indian Statistical Institute B.Math & B.Stat : Combinatorics

A point $P$ with coordinates $(x,y)$ is said to be good if both $x$ and $y$ are positive integers. Find the number of good points on the curve $xy=27027.$ $$$$ First note that, \( 27027 = 3^3 \times 13 \times 11 \times 7 \). Now for any good point on the curve $xy=27027$, $x$ must be of the form \(3^p \times 13^q \times 11^r \times 7^s \) and $y$ must be of the form \(3^{p'} \times 13^{q'} \times 11^{r'} \times 7^{s'}. \) Where $p+p'=3,q+q'=1,r+r'=1$ and $s+s'=1$ $$$$ Now considers the coordinates \( (3^3 \times ?, 3^0 \times ?),(3^2 \times ?, 3^1 \times ?),(3^1 \times ?, 3^2 \times ?),(3^0 \times ?, 3^3 \times ?)\) where in the place of $?$ in the $x-$ coordinate we can have any combinations of the products \( 13^q \times 11^r \times 7^s \) and in the place of $?$ in the $y-$ coordinate we can have any combinations of the products \( 13^{q'} \times 11^{r'} \times 7^{s'} \) such that $q+q'=1,r+r'=1$ and $s+s'=1.$ $$$$ Note that for the equation $q+q'=1$ the possible non-negative solutions are \( (1,0), (0,1) \). Similarly for the other two equations $r+r'=1$ and $s+s'=1$. $$$$ Counting the combinations for $?$ is the $x-$coordinate for the coordinate \((3^3 \times ?, 3^0 \times ?)\) we can have $$$$ CASE I : All the three numbers $13,11,7$ appears which can be done in \( \binom {3}{3} \) ways. $?$ in the $y-$ coordinate the must contain $13^0,11^0,7^0$. $$$$ CASE II : Any two of the three numbers $13,11,7$ appears which can be done in \( \binom {3}{2} \) ways. $?$ in the $y-$ coordinate the must contain $13$ or $11$ or $7$. $$$$ CASE III : Any one of the three numbers $13,11,7$ appears which can be done in \( \binom {3}{1} \) ways. $?$ in the $y-$ coordinate the must contain $13,11$ or $11,7$ or $7,13$. $$$$ CASE IV : None of the three numbers $13,11,7$ appears which can be done in \( \binom {3}{0} \) ways. $?$ in the $y-$ coordinate the must contain $13,11,7$. $$$$ Giving a total of \( \binom {3}{3}+ \binom {3}{2}+ \binom {3}{1}+ \binom {3}{0}=8\) possibilities. $$$$ Similarly we have $8$ possibilities for each of the coordinates of the form \((3^2 \times ?, 3^1 \times ?),(3^1 \times ?, 3^2 \times ?),(3^0 \times ?, 3^3 \times ?)\), giving in total $4\times8=32$ good coordinates $$$$ Another problem of same flavor form $Indian- Statistical- Institute$ $$$$ What is the number of ordered triplets $(a, b, c)$, where $a, b, c$ are positive integers (not necessarily distinct), such that $abc = 1000$? $$$$ First note that, \( 1000 = 2^3 \times 5^3 \). Any ordered triplet with the given condition must be of the form \( (2^l\times5^m,2^p\times5^q,2^r\times5^s)\) where $l+p+r=3$ and $m+q+s=3$. $$$$ Number of non-negative solutions of the above equations is \( \binom {3+3-1}{2} = 10\) in both cases. $$$$ Now consider one ordered triplet \( (2^1\times5^m,2^0\times5^q,2^2\times5^s)\) ( 10 such triplet are possible, varying powers of 2 subjected to $l+p+r=3$ ), for this triplet now we can vary $m,q,s$ subjected to $m+q+s=3$ in 10 ways.Thus in total $10\times10=100$ ordered triplets are possible. $$$$ Another good problem with a kick of $Derangement!!$ $$$$ There are $8$ balls numbered $1,2,\dots,8$ and $8$ boxes numbered $1,2,\dots,8$. Find the number of ways one can put these balls in the boxes so that each box gets one ball and exactly $4$ balls go in their corresponding numbered boxes. $$$$ $4$ balls can be selected in \(\binom{8}{4}\) ways and for each for such selection, say \(\{Ball_2,Ball_5,Ball_3,Ball_7\}\) the balls can go in their corresponding boxes in exactly one way (why?). Now the remaining $4$ balls \(\{Ball_3,Ball_4,Ball_1,Ball_8\}\) has to be put in the boxes in such a way none of the balls goes to the box of same number. Since, exactly $4$ balls go in their corresponding numbered boxes. $$$$ Which is nothing but $D_4$, so total number of ways is \(\binom{8}{4} \times D_4\) $$$$ where \( D_4 = 4!\big( 1 - \frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\big) = 9 \) $$$$ In general $D_n$ is Derangement of $n$ objects.

Indian Statistical Institute B.Math & B.Stat : Combinatorics

Using only the digits $2$, $3$ and $9$, how many six digit numbers can be formed which are divisible by $6$? $$$$ First note that a number is divisible by $6$, $iff$ it is divisible by $2$ and by $3.$ ($2$ and $3$ being co-prime)$$$$ The above argument clearly shows that the number $222222$ is divisible by $6$. Use divisibility test of $2$ and $3$. First note that a number will be divisible by $2$, $iff$ the digit at the unit place is $2.$ Now observe that, if the number which is divisible by $2$ has to be divisible by $3$, the sum of the digits must be divisible by $3.$ So the 5 places of the number (except the digit at the unit place, which is $2$) is a combination of the digits $2$, $3$ and $9$ such that the sum including the digit at the unit place is divided by $3$.$$$$ Now observe that among the $5$ places to be filled, exactly $two$ places can be the digit $2$. (Convince yourself why?! thin if not...) And the remaining $three$ places can be filled by either $3$ or $9$. Thus giving \( \binom {5} {2} \times 2\times2\times2 \) possibilities with desired condition. $$$$ therefore, total number of numbers \(= \binom {5} {2} \times 2\times2\times2+1 = 80+1=81 \)

Indian Statistical Institute B.Math & B.Stat : Integration

Evaluate: \[\int_\frac{1}{2014}^{2014} \frac{tan^{-1}x}{x} dx\] $$$$ Let \( I=\int_\frac{1}{2014}^{2014} \frac{tan^{-1}x}{x} dx\), Put $x=\frac{1}{t}$ \( \implies I = -\int_{2014}^\frac{1}{2014} \frac{tan^{-1}\frac{1}{t}}{t} dt =\int_\frac{1}{2014}^{2014} \frac{tan^{-1}\frac{1}{t}}{t} dt = \int_\frac{1}{2014}^{2014} \frac{tan^{-1}\frac{1}{x}}{x} dx \) $$$$ \(\mathbb{Therefore,}\) $$$$ \[2I=\int_\frac{1}{2014}^{2014} \frac{tan^{-1}x}{x} dx+\int_\frac{1}{2014}^{2014} \frac{tan^{-1}\frac{1}{x}}{x} dx\] $$$$ \[=\int_\frac{1}{2014}^{2014} \frac{tan^{-1}x+tan^{-1}\frac{1}{x}}{x} dx \] $$$$ \[=\int_\frac{1}{2014}^{2014} \frac{\frac{\pi}{2}}{x} dx \] $$$$ \[=\frac{\pi}{2}\int_\frac{1}{2014}^{2014} \frac{dx}{x} \] $$$$ \[=\frac{\pi}{2}[\log x]_{\frac{1}{2014}}^{2104} \] $$$$ \[=\frac{\pi}{2}\big[\log 2014-\log \frac{1}{2014}\big]\] $$$$ \[=\frac{\pi}{2}\log 2014^2\] $$$$ \[=\pi\log 2014\] $$$$

Indian Statistical Institute B.Math & B.Stat : Continuity

Let \( P: \mathbb{R} \rightarrow \mathbb{R}\) be a continuous function such that $P(x)=x$ has no real solution. Prove that $P(P(x))=x$ has no real solution. $$$$ If possible let, $P(P(x))=x$ has a real solution for $x=x_0$. Then $P(P(x_0))=x_0\dots(1)$ $$$$ Now let, $P(x_0)=y_0$ \( \implies P(y_0)=x_0\) using $(1)$ $$$$ Note that $x_0 \neq y_0$, otherwise we will have a solution to the equation $P(x)=x$! A contradiction to the hypothesis. Without loss of generality assume that \(x_0 < y_0\) $$$$ Construct a function \( Q:[x_0,y_0]\rightarrow \mathbb{R}\) where \(Q(x)=P(x)-x\),since $P$ is given to be continuous on $\mathbb{R}$, $Q$ is continuous on \([x_0,y_0].\) $$$$ Observe that, \( Q(x_0)=P(x_0)-x_0=y_0-x_0 > 0\) and \( Q(y_0)=P(y_0)-y_0=x_0-y_0 < 0\) $$$$ \(\implies Q(x_0)Q(y_0) < 0 \implies \) there exists a point $c\in$ \([x_0,y_0]\) such that $Q(c)=0$ using $ Intermediate-Value-Theorem$ $$$$ \(\implies P(c)-c=0 \implies P(c)=c\) for a real value, which contradicts the hypothesis, thus the assumption $P(P(x))=x$ has a real solution is not tenable.

Combinatorics :Indian Statistical Institute B.Math & B.Stat

How many $three-digits$ numbers of distinct digits can be formed by using the digits $1,2,3,4,5,9$ such that the sum of digits is at least 12? $$$$ First note that since the digits must be distinct there must be no repetition and further note that the maximum sum of such three digits is $9+5+4=18.$ $$$$ We will find all such possible by considering their sum of the digits. $$$$ Case I: Sum of the digits is 12. In this case the selection of digits can be \(\{1,2,9\},\{3,4,5\}\) $$$$ So, a total of $3!+3!=12$ $three-digits$ numbers possible. $$$$ Case II: Sum of the digits is 13. In this case the selection of digits can be \(\{1,3,9\}\) $$$$ So, a total of $3!=6$ $three-digits$ numbers possible. $$$$ Case III: Sum of the digits is 14. In this case the selection of digits can be \(\{1,4,9\},\{2,3,9\}\) $$$$ So, a total of $3!+3!=12$ $three-digits$ numbers possible. $$$$ case IV: Sum of the digits is 15. In this case the selection of digits can be \(\{1,5,9\},\{2,4,9\}\) $$$$ So, a total of $3!+3!=12$ $three-digits$ numbers possible. $$$$ Case V: Sum of the digits is 16. In this case the selection of digits can be \(\{2,5,9\},\{2,5,9\}\) $$$$ So, a total of $3!+3!=12$ $three-digits$ numbers possible. $$$$ Case VI: Sum of the digits is 17. In this case the selection of digits can be \(\{3,5,9\}\) $$$$ So, a total of $3!=6$ $three-digits$ numbers possible. $$$$ Case VII: Sum of the digits is 18. In this case the selection of digits can be \(\{4,5,9\}\) $$$$ So, a total of $3!=6$ $three-digits$ numbers possible. $$$$ Adding all the cases we have $12+6+12+12+12+6+6=66$, $three-digits$ numbers of distinct digits can be formed.

Complex Numbers :Indian Statistical Institute B.Math & B.Stat

Let \(\omega\) be the complex cube root of unity. Find the cardinality of the set $S$ where \(S = \{(1+\omega+\omega^2+\dots+\omega^n)^m | m,n = 1,2,3,......\}\) $$$$ $n$ must be of the form \( 3k, 3k+1\) or \(3k+2\) where \(k \in N\) $$$$ when $n$ is multiple of $3$,\(1+\omega+\omega^2+\dots+\omega^n = 0\) whence \((1+\omega+\omega^2+\dots+\omega^n)^m = 0\) \(\forall\) \(n,m \in N\) $$$$ when $n$ is of the form $3k+1$,\(1+\omega+\omega^2+\dots+\omega^n = 1\) whence \((1+\omega+\omega^2+\dots+\omega^n)^m = 1^m=1\) \(\forall\) \(n,m \in N\) $$$$ when $n$ is of the form $3k+2$,\(1+\omega+\omega^2+\dots+\omega^n = 1+\omega(**)\) whence \((1+\omega+\omega^2+\dots+\omega^n)^m = (1+\omega)^m =(-\omega)^{2m}\) \(\forall\) \(n,m \in N\) $$$$ In this case the possible values are possible values of \((-\omega)^{2m}\) which are \(-1,1,\omega,-\omega,\omega^2,-\omega^2\), note m varies over the set of Natural numbers $$$$ Combining the three cases we see that \( S = \{0,-1,1,\omega,-\omega,\omega^2,-\omega^2\} \), therefore $|S|=7$. \((**)\) To understand these first observe that $\omega^n=1,\omega,\omega^2$ for any natural number $n$. So when $n$ is of the for $3k+2$ we can couple the three consecutive recurring terms $1,\omega,\omega^2$ to get the sum as $0$. After that we are left with two more terms $1$ and $\omega$, since the series \(1+\omega+\omega^2+\omega^3+\omega^4+\omega^5\dots+\omega^n\) has repeated terms after every 3 terms (similar to the first three terms). Similarly for the othere cases the same argument follows. This concludes the result .

Common terms of two A.P Series : Indian Statistical Institute B.Math & B.Stat

Consider the two arithmetic progressions \( 3,7,11,\dots,407\) and \(2,9,16,\dots,709\). Find the number of common terms of these two progressions. $$$$ Let $a_n$ and $a_m$ be the last terms of the progressions respectively \( \Rightarrow 407 = 3+(n-1)4\) and \( 709 = 2+(m-1)7 \) $$$$ Solving we get, \( n,m = 102\). To find the common terms, assume that the $n^{th}$ term of the first progression is equal to the $m^{th}$ term of the second progression. $$$$ \(\Rightarrow 3+(n-1)4=2+(m-1)7 \Rightarrow 3+4n-4-2+7=7m \Rightarrow 4(n+1)=7m,\) where \( n,m \in \{1,2,3,\dots,102\}\) $$$$ R.H.S is a multiple of 7, while L.H.S is 4(n+1). Since $g.c.d(4,7)=1$ L.H.S will be multiple of $7$, $iff$ $n+1$ is a multiple of $7$. $$$$ \( \Rightarrow n = 6,13,20,\dots \) Again since $n$ is bounded by $102$. The largest possible value of $n$ is $97$. $$$$ So, \( n \in \{6,13,20,\dots\,97}\) Which has $14$ terms. Thus the number of common terms of the progression is $14$