Saturday, May 30, 2015

Inequality

Mathematics Olympiad ~ Vinod Singh, Kolkata $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

Mathematics Olympiad ~ Vinod Sing, Kolkata $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

Indian Statistical Institute : 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

Indian Statistical Institute : 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

Indian Statistical Institute : 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.

Friday, May 29, 2015

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

Indian Statistical Institute B.Math & B.Stat 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

Indian Statistical Institute B.Math & B.Stat 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

Indian Statistical Institute B.Math & B.Stat 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

Indian Statistical Institute B.Math & B.Stat 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 \)

Thursday, May 28, 2015

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

Indian Statistical Institute B.Math & B.Stat 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.

Wednesday, May 27, 2015

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

Indian Statistical Institute B.Math & B.Stat 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

Indian Statistical Institute B.Math & B.Stat 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\] $$$$

Monday, May 25, 2015

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.
google.com, pub-6701104685381436, DIRECT, f08c47fec0942fa0