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

Let $n$ be a positive integer Define \[f(x) = min \{|x-1|,|x-2|,\dots,|x-n|\} \] $$$$ Then evaluate \[ \int_{0}^{n+1} f(x) dx \] $$$$ When \(0 < x < 1+ \frac{1}{2} \), $|x-1|=min \{|x-1|,|x-2|,\dots,|x-n|\}$. Now $|x-1|= 1-x$ for \( 0 < x < 1\) and $|x-1|= x-1 $ for $1 < x < 1+ \frac{1}{2}$ $$$$ So, \(\int_{0}^{1+\frac{1}{2}} f(x) dx = \int_{0}^{1} (1-x) dx + \int_{1}^{1+ \frac{1}{2}} (x-1) dx = \frac{1}{2}+ \frac{1}{2} \times \frac{1}{4} \dots (A)\) $$$$ When \(n+ \frac{1}{2} < x < n+1 \), $|x-n|=min \{|x-1|,|x-2|,\dots,|x-n|\}$. Now $|x-n|= x-n$ for \( n+ \frac{1}{2} < x < n+1 \)$$$$ So, \(\int_{n+\frac{1}{2}}^{n+1} f(x) dx = \int_{n+\frac{1}{2}}^{n+1} (x-n) dx = \frac{1}{2}- \frac{1}{2} \times \frac{1}{4} \dots (B)\) $$$$ Consider the diagram given below where $1 < k \leq n$,. When \( x \in \big(k-\frac{1}{2},k+\frac{1}{2} \big) \), $|x-k|$ is minimum among $|x-i|$ where $i=1,2,3,\dots,k-1,k+1,\dots,n$ $$$$ $$$$ So, \( \int_{k-\frac{1}{2}}^{k+\frac{1}{2}} f(x) dx = \int_{k-\frac{1}{2}}^{k+\frac{1}{2}} |x-k| dx = \int_{k-\frac{1}{2}}^{k} (k-x) dx + \int_{k}^{k+\frac{1}{2}} (x-k) dx = \frac{1}{4}\) for $k=2,3,4\dots,n$.$$$$ Summing for $k=2,3,4\dots,n$ we get \[\int_{1+\frac{1}{2}}^{n+\frac{1}{2}} f(x) dx = \frac{(n-1)}{4} \dots (C)\] $$$$ Adding equations $A,C$ and $B$ we get \[ \int_{0}^{n+1} f(x) dx = \int_{0}^{1+\frac{1}{2}} f(x) dx+ \int_{1+\frac{1}{2}}^{n+\frac{1}{2}} f(x) dx+\int_{n+\frac{1}{2}}^{n+1} f(x) dx = \frac{1}{2}+ \frac{1}{2} \times \frac{1}{4}+ \frac{(n-1)}{4}+ \frac{1}{2}- \frac{1}{2} \times \frac{1}{4} \] $$$$ \[= \frac{(n-1)}{4}+1 = \frac{n+3}{4} \]

Indian Statistical Institute B.Math & B.Stat : Square of a real is non-negative

Show that the following system of inequalities has exactly one solution $a-b^2 \geq \frac{1}{4},$ $b-c^2 \geq \frac{1}{4},$ $c-d^2 \geq \frac{1}{4}$ and $d-a^2 \geq \frac{1}{4}.$ $$$$ Adding up all the inequalities we get \( a-b^2 + b-c^2 + c-d^2 + d-a^2 \geq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} +\frac{1}{4} \) $$$$ \( \implies a-a^2 - \frac{1}{4} + b-b^2- \frac{1}{4} + c-c^2 - \frac{1}{4} + d-d^2 - \frac{1}{4} \geq 0 \) $$$$ \( \implies -\big(a- \frac{1}{2} \big)^2 -\big(b- \frac{1}{2} \big)^2 - \big(c- \frac{1}{2} \big)^2 - \big(d- \frac{1}{2} \big)^2 \geq 0 \) $$$$ which is possible only when R.H.S is zero i.e., \( a=b=c=d= \frac{1}{2} \), since the R.H.S is always non-positive.

Indian Statistical Institute B.Math & B.Stat : Limits at Infinity

Let \( a_1 > a_2 > \dots > a_r \) be positive real numbers. Compute \(\lim_{n \to \infty} \big( a_1^n+a_2^n+\dots+a_r^n \big)^{\frac{1}{n}}\). $$$$ Since \( a_1 > a_2 > \dots > a_r \) and each of them is positive we have \(a_1^n>a_2^n>\dots>a_r^n \) $$$$ \( \implies a_1^n+a_2^n+\dots+a_r^n < a_1^n+a_1^n+\dots+a_1^n = ra_1^n \) $$$$ Letting \( n \to \infty \) we have, \(\lim_{n \to \infty} \big( a_1^n+a_2^n+\dots+a_r^n \big)^{\frac{1}{n}} < \lim_{n \to \infty}(ra_1^n)^{\frac{1}{n}} \) \( = a_1\lim_{n \to \infty}r^{\frac{1}{n}}= a_1 \) Note $r>0$ $$$$ Now, \( \big( a_1^n+a_2^n+\dots+a_r^n \big)^{\frac{1}{n}} = \bigg( a_1^n \big(1+\frac{a_2^n}{a_1^n}+\dots+\frac{a_r}{a_1}\big) \bigg)^{\frac{1}{n}} = a_1\bigg( 1+\frac{a_2^n}{a_1^n}+\dots+\frac{a_r}{a_1}\big) \bigg)^{\frac{1}{n}} > a_1 \) Since \(\bigg( 1+\frac{a_2^n}{a_1^n}+\dots+\frac{a_r}{a_1} \bigg)^{\frac{1}{n}} > 1\) $$$$ Letting \( n \to \infty \) we have, \(\lim_{n \to \infty} \big( a_1^n+a_2^n+\dots+a_r^n \big)^{\frac{1}{n}} > \lim_{n \to \infty}a_1 =a_1 \) $$$$ Thus by $Sandwhich-theorem$ \(\lim_{n \to \infty} \big( a_1^n+a_2^n+\dots+a_r^n \big)^{\frac{1}{n}} = a_1\)

Inequality

$Problem$ #3 $$ $$ Find all real numbers $x$ for which \(\sqrt{3-x}-\sqrt{x+1} > \frac{1}{2}\) $$ $$ Let $f(x)$ \(=\sqrt{3-x}-\sqrt{x+1}\). First note that $f(x)$ is defined for \( -1 \leq x \leq 3 \) $$ $$ \( f'(x) = \frac{-1}{2\sqrt{3-x}} - \frac{1}{2\sqrt{x+1}} = - \big(\frac{1}{2\sqrt{3-x}} + \frac{1}{2\sqrt{x+1}}\big) < 0 \Rightarrow f(x)\) is strictly decreasing $$ $$ Now \( f(-1) = 2 > \frac{1}{2}\) and \( f(3) = -2 < \frac{1}{2}\) Since $f(x)$ is continuous, $\exists$ at least one x $\in$ ${(-1,3)}$ suct that $f(x) = \frac{1}{2}$ $$ $$ \( f(x) = \frac{1}{2} \Rightarrow \sqrt{3-x}-\sqrt{x+1} = \frac{1}{2} \Rightarrow 64x^2-128x+33 = 0 \Rightarrow x = 1 \pm \frac{\sqrt{31}}{8} \)$$ $$ but \(x = 1 + \frac{\sqrt{31}}{8}\) does not satisfy \(\sqrt{3-x}-\sqrt{x+1} = \frac{1}{2}\) Check yourself! So the only solution is \(x = 1 - \frac{\sqrt{31}}{8}\) $$ $$ Since $f(x)$ is strictly decreasing, the given inequality is true for \( x \in {[-1,1 - \frac{\sqrt{31}}{8}\big)}\) $$ $$

Matrices & Determinants

$Problem$ #1 $$ $$ If $A$ and $B$ are different matrices satisfying \( A^3 = B^3 \) and \(A^2B = B^2A\), find \(det(A^2+B^2)\) $$ $$ Since $A$ and $B$ are different matrices \( A-B \neq O \), Now \((A^2+B^2)(A-B) = A^3-A^2B+B^2A-B^3\) $$ $$ =$O$ since \(A^3 = B^3\) and \(A^2B = B^2A\) $$ $$ This shows that \((A^2+B^2)\) has a zero divisor, so it is not invertible hence \(det(A^2+B^2) = 0\)

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

Let $k$ be any odd integer greater that 1. Then show that \( 1^k+2^k+3^k+\dots \dots+2006^k \) is divisible by 2013021. $$$$ We will prove the general case. Let \(S= 1^k+2^k+3^k+\dots \dots+n^k\) where $n \geq 2$ and \(n\in \mathbb{N}\). $$$$ \(2S = 1^k+2^k+3^k+\dots \dots+n^k + 1^k+2^k+3^k+\dots \dots+n^k = (1^k+n^k)+(2^k+(n-1)^k)+\dots \dots+(n^k+1^k)\) $$$$ Using the result, $n^k+m^k$ is always divisible by $n+m$ if $k$ is odd we see that $2S$ is divisible by $(n+1)$ $$$$ Again \(2S = 1^k+2^k+3^k+\dots \dots+n^k + 1^k+2^k+3^k+\dots \dots+n^k\) $$$$ \( = (1^k+(n-1)^k)+(2^k+(n-2)^k)+\dots \dots+((n-1)^k+1^k)+2n^k\) $$$$ Using the same result and noting that $2n^k$ is divisible by $n$ we see that $2S$ is divisible by $n$. Now both $n$ an $n+1$ divides $2S$ and $g.c.d(n.n+1)=1$ we see that $n(n+1)$ divides $2S$ this implies $\frac{n(n+1)}{2}$ divides $S$. ( $n(n+1)$ is always even) $$$$ In the given problem $n=2006$, thus \( 1^k+2^k+3^k+\dots \dots+2006^k \) is divisible by $\frac{2006(2006+1)}{2}=2013021$

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.