Problem:
Find a four digit number which is a perfect square, knowing that the first two digit number exceeds by $1$ the last two digit number.
Solution:
Let $x$ be the first two digit number and let $y^2$ be the four digit number. Then, $31 < y < 100$ and
$$100(x+1)+x=y^2 \iff 101x=(y-10)(y+10).$$ So, $101$ divides one between $y-10$ and $y+10$. But $y-10<101$, so $101|(y+10)$. Since $41<y+10<110$, $y+10=101$, which gives $y=91$. Therefore, $y^2=8281$.
Friday, December 21, 2012
Thursday, December 20, 2012
KöMaL (Metresis) 1894, Problem 10
Problem:
Find all integers such that their fifth power minus three times their square is equal to $216$.
Solution:
Suppose that $n$ is an integer such that $n^5-3n^2=216=2^3\cdot3^3$. Then $$n^2(n^3-3)=216.$$ From this equality we get $n>1$. Let $d=\gcd(n^2,n^3-3)$. Then $d=1,3$. If $d=1$, then both $n^2$ and $(n^3-3)$ are perfect cubes, impossible since $$(n-1)^3 < n^3-3 < n^3.$$ If $d=3$, then $3^2|n^2$, so $n^2=9a, n^3-3=3b$ and $\gcd(a,b)=1$. Therefore, $ab=8$ and $b+1=3^{3k-1}$ for some $k \in \mathbb{N}$, which gives $a=1,b=8$, i.e. $n=3$.
Note. It was faster to note that $n^2$ and $(n^3-3)$ have different parity, so one of the two is odd. If $n^2$ is odd, $n^2=9$ which yields $n=3$, if $(n^3-3)$ is odd, then $n^3-3=1,3,9,27$, i.e. no solution.
Find all integers such that their fifth power minus three times their square is equal to $216$.
Solution:
Suppose that $n$ is an integer such that $n^5-3n^2=216=2^3\cdot3^3$. Then $$n^2(n^3-3)=216.$$ From this equality we get $n>1$. Let $d=\gcd(n^2,n^3-3)$. Then $d=1,3$. If $d=1$, then both $n^2$ and $(n^3-3)$ are perfect cubes, impossible since $$(n-1)^3 < n^3-3 < n^3.$$ If $d=3$, then $3^2|n^2$, so $n^2=9a, n^3-3=3b$ and $\gcd(a,b)=1$. Therefore, $ab=8$ and $b+1=3^{3k-1}$ for some $k \in \mathbb{N}$, which gives $a=1,b=8$, i.e. $n=3$.
Note. It was faster to note that $n^2$ and $(n^3-3)$ have different parity, so one of the two is odd. If $n^2$ is odd, $n^2=9$ which yields $n=3$, if $(n^3-3)$ is odd, then $n^3-3=1,3,9,27$, i.e. no solution.
Tuesday, November 27, 2012
Mathematical Reflections 2012, Issue 5 - Problem U243
Problem:
Let $f:(a,b) \longrightarrow \mathbb{R}$ be a differentiable function such that $f'(a)=f'(b)=0$ and with the
property that there is a real valued function $g$ for which $g(f'(x))=f(x)$ for all $x$ in $\mathbb{R}$.
Prove that $f$ is constant.
Solution:
Since $f$ is differentiable in $(a,b)$ and $f'(a)=f'(b)=0$, $f$ is continuous in $[a,b]$. By Weierstrass's Theorem there exist maximum $M$ and minimum $m$ in $[a,b]$. If these are both attained at $a$ and $b$, $f$ is constant. If one of these is not attained at $a$ or $b$, then there exists $c \in (a,b)$ such that $f(c)=M$ or $f(c)=m$. Since $f$ is differentiable $f'(c)=0$, so $g(0)=f(c)=f(a)=f(b)$, which means that $f$ is constant in $(a,b)$.
Let $f:(a,b) \longrightarrow \mathbb{R}$ be a differentiable function such that $f'(a)=f'(b)=0$ and with the
property that there is a real valued function $g$ for which $g(f'(x))=f(x)$ for all $x$ in $\mathbb{R}$.
Prove that $f$ is constant.
Proposed by Mihai Piticari and Sorin Radulescu.
Solution:
Since $f$ is differentiable in $(a,b)$ and $f'(a)=f'(b)=0$, $f$ is continuous in $[a,b]$. By Weierstrass's Theorem there exist maximum $M$ and minimum $m$ in $[a,b]$. If these are both attained at $a$ and $b$, $f$ is constant. If one of these is not attained at $a$ or $b$, then there exists $c \in (a,b)$ such that $f(c)=M$ or $f(c)=m$. Since $f$ is differentiable $f'(c)=0$, so $g(0)=f(c)=f(a)=f(b)$, which means that $f$ is constant in $(a,b)$.
Mathematical Reflections 2012, Issue 5 - Problem U241
Problem:
Let $a>b$ be positive real numbers. Prove that $$c_n=\dfrac{\sqrt[n+1]{a^{n+1}-b^{n+1}}}{\sqrt[n]{a^n-b^n}}$$
is a decreasing sequence and find its limit.
Solution:
Let $c_n=\dfrac{\sqrt[n+1]{1-x^{n+1}}}{\sqrt[n]{1-x^n}}$, where $x=b/a < 1$. We first prove that $c_n > 1$. Let $b_n=c^{n(n+1)}_n$. Then $$b_n(x)=\dfrac{(1-x^{n+1})^n}{(1-x^n)^{n+1}}$$ and $$b'_n(x)=\dfrac{n(n+1)x^{n-1}(1-x^{n+1})^{n-1}(1-x^n)^n(1-x)}{(1-x^n)^{2(n+1)}}.$$ So, $b'_n(x) > 0$ for all $x \in (0,1)$, so $b_n(x)$ is increasing in $(0,1)$ and $b_n(x) > b_n(0)=1$, i.e. $c^{n(n+1)}_n > 1$, which yields $c_n > 1$. Now, we prove that $c_n$ is a decreasing sequence. We have $$\dfrac{b_{n-1}}{b_n}=\left(\dfrac{(1-x^n)^2}{(1-x^{n-1})(1-x^{n+1})}\right)^n > 1,$$ so $c_{n-1}^{(n-1)n}>c_n^{n(n+1)}=c_n^{(n-1)n}c_n^{2n}>c_n^{(n-1)n}$, i.e. $c_{n-1}>c_n$. Moreover,
$$\lim_{n \to \infty} \log c_n=\lim_{n \to \infty} \left[\dfrac{1}{n+1}\log (1-x^{n+1})-\dfrac{1}{n}\log(1-x^n)\right]=0,$$ so $$\lim_{n \to \infty} c_n= \lim_{n \to \infty} e^{\log c_n}=1.$$
Let $a>b$ be positive real numbers. Prove that $$c_n=\dfrac{\sqrt[n+1]{a^{n+1}-b^{n+1}}}{\sqrt[n]{a^n-b^n}}$$
is a decreasing sequence and find its limit.
Proposed by Ivan Borsenco.
Solution:
Let $c_n=\dfrac{\sqrt[n+1]{1-x^{n+1}}}{\sqrt[n]{1-x^n}}$, where $x=b/a < 1$. We first prove that $c_n > 1$. Let $b_n=c^{n(n+1)}_n$. Then $$b_n(x)=\dfrac{(1-x^{n+1})^n}{(1-x^n)^{n+1}}$$ and $$b'_n(x)=\dfrac{n(n+1)x^{n-1}(1-x^{n+1})^{n-1}(1-x^n)^n(1-x)}{(1-x^n)^{2(n+1)}}.$$ So, $b'_n(x) > 0$ for all $x \in (0,1)$, so $b_n(x)$ is increasing in $(0,1)$ and $b_n(x) > b_n(0)=1$, i.e. $c^{n(n+1)}_n > 1$, which yields $c_n > 1$. Now, we prove that $c_n$ is a decreasing sequence. We have $$\dfrac{b_{n-1}}{b_n}=\left(\dfrac{(1-x^n)^2}{(1-x^{n-1})(1-x^{n+1})}\right)^n > 1,$$ so $c_{n-1}^{(n-1)n}>c_n^{n(n+1)}=c_n^{(n-1)n}c_n^{2n}>c_n^{(n-1)n}$, i.e. $c_{n-1}>c_n$. Moreover,
$$\lim_{n \to \infty} \log c_n=\lim_{n \to \infty} \left[\dfrac{1}{n+1}\log (1-x^{n+1})-\dfrac{1}{n}\log(1-x^n)\right]=0,$$ so $$\lim_{n \to \infty} c_n= \lim_{n \to \infty} e^{\log c_n}=1.$$
Mathematical Reflections 2012, Issue 5 - Problem S243
Problem:
A group of boys and girls went to a dance party. It is known that for every pair of boys, there are exactly two girls who danced with both of them; and for every pair of girls there are exactly two boys who danced with both of them. Prove that the numbers of girls and boys are equal.
Solution:
Let $m$ be the number of boys and $n$ be the number of girls. There are $\displaystyle{m \choose 2}$ possibile pairs of boys and $\displaystyle{n \choose 2}$ possible pairs of girls. Suppose that $\displaystyle{m \choose 2} > \displaystyle{n \choose 2}$. Then, there are two distinct pairs of boys which dance with a pair of girls, but this means that there are at least three boys which dance with two girls, contradiction. With the same reasoning we can prove that it can't be $\displaystyle{m \choose 2} < \displaystyle{n \choose 2}$, so $\displaystyle{m \choose 2} = \displaystyle{n \choose 2}$, i.e. $m=n$.
A group of boys and girls went to a dance party. It is known that for every pair of boys, there are exactly two girls who danced with both of them; and for every pair of girls there are exactly two boys who danced with both of them. Prove that the numbers of girls and boys are equal.
Proposed by Iurie Boreico.
Solution:
Let $m$ be the number of boys and $n$ be the number of girls. There are $\displaystyle{m \choose 2}$ possibile pairs of boys and $\displaystyle{n \choose 2}$ possible pairs of girls. Suppose that $\displaystyle{m \choose 2} > \displaystyle{n \choose 2}$. Then, there are two distinct pairs of boys which dance with a pair of girls, but this means that there are at least three boys which dance with two girls, contradiction. With the same reasoning we can prove that it can't be $\displaystyle{m \choose 2} < \displaystyle{n \choose 2}$, so $\displaystyle{m \choose 2} = \displaystyle{n \choose 2}$, i.e. $m=n$.
Mathematical Reflections 2012, Issue 5 - Problem S241
Problem:
Let $p$ and $q$ be odd primes such that $\dfrac{p^3-q^3}{3} \geq 2pq+3.$ Prove that
$$\dfrac{p^3-q^3}{4} \geq 3pq+16.$$
Solution:
Clearly, $p>q$, so $p-2 \geq q$. It must be $p-2 \neq q$, otherwise we would have $$p^3-q^3=p^3-(p-2)^3=6p^2-12p+8=6pq+8,$$ which contradicts the given inequality. So $p-4 \geq q$ and $$p^3-q^3 \geq p^3-(p-4)^3=12p^2-48p+64=12p(p-4)+64 \geq 12pq+64,$$ which gives the conclusion.
Let $p$ and $q$ be odd primes such that $\dfrac{p^3-q^3}{3} \geq 2pq+3.$ Prove that
$$\dfrac{p^3-q^3}{4} \geq 3pq+16.$$
Proposed by Titu Andreescu.
Solution:
Clearly, $p>q$, so $p-2 \geq q$. It must be $p-2 \neq q$, otherwise we would have $$p^3-q^3=p^3-(p-2)^3=6p^2-12p+8=6pq+8,$$ which contradicts the given inequality. So $p-4 \geq q$ and $$p^3-q^3 \geq p^3-(p-4)^3=12p^2-48p+64=12p(p-4)+64 \geq 12pq+64,$$ which gives the conclusion.
Mathematical Reflections 2012, Issue 5 - Problem J245
Problem:
Find all triples $(x,y,z)$ of positive real numbers satisfying simultaneously the inequalities $x+y+z-2xyz \leq 1$ and $$xy+yz+zx+\dfrac{1}{xyz} \leq 4.$$
Solution:
Using HM-AM Inequality, from the first inequality we have
$$\dfrac{9xyz}{xy+yz+zx} \leq x+y+z \leq 1+2xyz,$$ which gives $\dfrac{9xyz}{2xyz+1} \leq xy+yz+zx$. From the second inequality, we have $$\dfrac{9xyz}{2xyz+1}+\dfrac{1}{xyz} \leq 4.$$ Putting $t=xyz>0$ and clearing the denominators, we obtain $$9t^2+2t+1 \leq 4t(2t+1),$$ i.e. $(t-1)^2 \leq 0$, which gives $t=1$. So, the first inequality is $x+y+z \leq 3xyz$, but by AM-GM Inequality $3xyz \leq x+y+z$, which implies $x+y+z=3xyz$. The equality holds if and only if $x=y=z=1$, so the only triple which satisfies the two inequalities is $(1,1,1)$.
Find all triples $(x,y,z)$ of positive real numbers satisfying simultaneously the inequalities $x+y+z-2xyz \leq 1$ and $$xy+yz+zx+\dfrac{1}{xyz} \leq 4.$$
Proposed by Titu Andreescu.
Solution:
Using HM-AM Inequality, from the first inequality we have
$$\dfrac{9xyz}{xy+yz+zx} \leq x+y+z \leq 1+2xyz,$$ which gives $\dfrac{9xyz}{2xyz+1} \leq xy+yz+zx$. From the second inequality, we have $$\dfrac{9xyz}{2xyz+1}+\dfrac{1}{xyz} \leq 4.$$ Putting $t=xyz>0$ and clearing the denominators, we obtain $$9t^2+2t+1 \leq 4t(2t+1),$$ i.e. $(t-1)^2 \leq 0$, which gives $t=1$. So, the first inequality is $x+y+z \leq 3xyz$, but by AM-GM Inequality $3xyz \leq x+y+z$, which implies $x+y+z=3xyz$. The equality holds if and only if $x=y=z=1$, so the only triple which satisfies the two inequalities is $(1,1,1)$.
Mathematical Reflections 2012, Issue 5 - Problem J244
Problem:
Let $a$ and $b$ positive real numbers. Prove that
$$1 \leq \dfrac{\sqrt[n]{a^n+b^n}}{\sqrt[n+1]{a^{n+1}+b^{n+1}}} \leq \sqrt[n(n+1)]{2}.$$
Let $a$ and $b$ positive real numbers. Prove that
$$1 \leq \dfrac{\sqrt[n]{a^n+b^n}}{\sqrt[n+1]{a^{n+1}+b^{n+1}}} \leq \sqrt[n(n+1)]{2}.$$
Proposed by Ivan Borsenco.
Solution:
Since we can collect $a$ or $b$ in the given expression, it is sufficient to prove that
$$1 \leq \dfrac{\sqrt[n]{1+x^n}}{\sqrt[n+1]{1+x^{n+1}}} \leq \sqrt[n(n+1)]{2} \qquad \forall x \in \mathbb{R}^+,$$ or equivalently
$$1 \leq \dfrac{(1+x^n)^{n+1}}{(1+x^{n+1})^n} \leq 2, \qquad \forall x \in \mathbb{R}^+.$$ Put $f(x)=\dfrac{(1+x^n)^{n+1}}{(1+x^{n+1})^n}$. Then, $$f'(x)=\dfrac{n(n+1)x^{n-1}(1+x)^n(1+x^{n+1})^{n-1}(1-x)}{[(1+x^{n+1})^n]^2},$$ and $f'(x) > 0$ if and only if $x<1$, i.e. $f(1)$ is a maximum. Moreover, $f(0)=1$ and $\lim_{x \to +\infty} f(x)=1^+$, so $f(0) \leq f(x) \leq f(1)$ for all positive real numbers $x$, which gives $1 \leq f(x) \leq 2$ for all positive real numbers $x$.
$$1 \leq \dfrac{\sqrt[n]{1+x^n}}{\sqrt[n+1]{1+x^{n+1}}} \leq \sqrt[n(n+1)]{2} \qquad \forall x \in \mathbb{R}^+,$$ or equivalently
$$1 \leq \dfrac{(1+x^n)^{n+1}}{(1+x^{n+1})^n} \leq 2, \qquad \forall x \in \mathbb{R}^+.$$ Put $f(x)=\dfrac{(1+x^n)^{n+1}}{(1+x^{n+1})^n}$. Then, $$f'(x)=\dfrac{n(n+1)x^{n-1}(1+x)^n(1+x^{n+1})^{n-1}(1-x)}{[(1+x^{n+1})^n]^2},$$ and $f'(x) > 0$ if and only if $x<1$, i.e. $f(1)$ is a maximum. Moreover, $f(0)=1$ and $\lim_{x \to +\infty} f(x)=1^+$, so $f(0) \leq f(x) \leq f(1)$ for all positive real numbers $x$, which gives $1 \leq f(x) \leq 2$ for all positive real numbers $x$.
Mathematical Reflections 2012, Issue 5 - Problem J243
Problem:
Let $a,b,c$ be real numbers such that $$\left(-\dfrac{a}{2}+\dfrac{b}{3}+\dfrac{c}{6}\right)^3+\left(\dfrac{a}{3}+\dfrac{b}{6}-\dfrac{c}{2}\right)^3+\left(\dfrac{a}{6}-\dfrac{b}{2}+\dfrac{c}{3}\right)^3=\dfrac{1}{8}.$$ Prove that $$(a-3b+2c)(2a+b-3c)(-3a+2b+c)=9.$$
Solution:
From the given equality, we have $$(-3a+2b+c)^3+(2a+b-3c)^3+(a-3b+2c)^3=27.$$
Let $x=-3a+2b+c, y=2a+b-3c, z=a-3b+2c$. Since $x+y+z=0$, using the well known identity
$$x^3+y^3+z^3-3xyz=(x+y+z)(x^2+y^2+z^2-xy-yz-zx),$$ we get $x^3+y^3+z^3=3xyz$, i.e.
$$3(-3a+2b+c)(2a+b-3c)(a-3b+2c)=27,$$ which gives $(-3a+2b+c)(2a+b-3c)(a-3b+2c)=9$.
Let $a,b,c$ be real numbers such that $$\left(-\dfrac{a}{2}+\dfrac{b}{3}+\dfrac{c}{6}\right)^3+\left(\dfrac{a}{3}+\dfrac{b}{6}-\dfrac{c}{2}\right)^3+\left(\dfrac{a}{6}-\dfrac{b}{2}+\dfrac{c}{3}\right)^3=\dfrac{1}{8}.$$ Prove that $$(a-3b+2c)(2a+b-3c)(-3a+2b+c)=9.$$
Proposed by Titu Andreescu.
Solution:
From the given equality, we have $$(-3a+2b+c)^3+(2a+b-3c)^3+(a-3b+2c)^3=27.$$
Let $x=-3a+2b+c, y=2a+b-3c, z=a-3b+2c$. Since $x+y+z=0$, using the well known identity
$$x^3+y^3+z^3-3xyz=(x+y+z)(x^2+y^2+z^2-xy-yz-zx),$$ we get $x^3+y^3+z^3=3xyz$, i.e.
$$3(-3a+2b+c)(2a+b-3c)(a-3b+2c)=27,$$ which gives $(-3a+2b+c)(2a+b-3c)(a-3b+2c)=9$.
Mathematical Reflections 2012, Issue 5 - Problem J242
Problem:
Let $ABC$ be a triangle and let $D,E,F$ be the feet of the altitudes from $A,B,C$ to the
sides $BC,CA,AB$, respectively. Let $X,Y,Z$ be the midpoints of segments $EF,FD,DE$ and let $x,y,z$ be the perpendiculars from $X,Y,Z$ to $BC,CA$, and $AB$, respectively. Prove that the lines $x,y,z$ are concurrent.
Let $ABC$ be a triangle and let $D,E,F$ be the feet of the altitudes from $A,B,C$ to the
sides $BC,CA,AB$, respectively. Let $X,Y,Z$ be the midpoints of segments $EF,FD,DE$ and let $x,y,z$ be the perpendiculars from $X,Y,Z$ to $BC,CA$, and $AB$, respectively. Prove that the lines $x,y,z$ are concurrent.
Proposed by Cosmin Pohoata.
Solution:
Obviously, the lines $x,y,z$ are parallel to the altitudes $AD,BE,CF$ respectively. Since the orthocenter of the triangle $ABC$ is the incenter of the orthic triangle $DEF$, the lines $AD,BE,CF$ are bisectrices of the angle $D,E,F$ of the triangle $DEF$ respectively. Moreover, since $X,Y,Z$ are midpoints of the segments $EF,FD,DE$, then $XY,YZ,ZX$ are parallel to $DE,EF,FD$. The angle between the line $XY$ and the line $x$ and the angle $ADE$ are equal (alternate interior angles) and so are the angle between the line $XZ$ and the line $x$ and the angle $ADF$ (alternate exterior angles), so the line $x$ is the bisectrix of the angle $X$ of the triangle $XYZ$. Likewise, the lines $y$ and $z$ are bisectrices of the angles $Y,Z$ respectively. So the lines $x,y,z$ are concurrent since their point of intersection is the incenter of the triangle $XYZ$.
Mathematical Reflections 2012, Issue 5 - Problem J241
Problem:
Determine all positive integers that can be represented as $$\dfrac{ab+bc+ca}{a+b+c+\min (a,b,c)}$$ for some positive integers $a,b,c$.
Determine all positive integers that can be represented as $$\dfrac{ab+bc+ca}{a+b+c+\min (a,b,c)}$$ for some positive integers $a,b,c$.
Proposed by Titu Andreescu.
Solution:
We claim that every positive integer $n$ can be represented in this form. Suppose $a \geq b \geq c$. Let $c=1, b=n$. Then
$$\dfrac{ab+bc+ca}{a+b+c+\min (a,b,c)}=\dfrac{a(n+1)+n}{a+n+2}=n+1-\dfrac{n^2+2n+2}{a+n+2},$$ so it suffices to choose $a=n^2+n$.
$$\dfrac{ab+bc+ca}{a+b+c+\min (a,b,c)}=\dfrac{a(n+1)+n}{a+n+2}=n+1-\dfrac{n^2+2n+2}{a+n+2},$$ so it suffices to choose $a=n^2+n$.
Monday, November 5, 2012
Mathematical Reflections 2012, Issue 4 - Problem O235
Problem:
Solve in integers the equation $$xy-7\sqrt{x^2+y^2}=1.$$
Solution:
Clearly, $xy \geq 1$. By symmetry, we reduce to $x,y > 0$. Rewriting the equation in the form $(xy-1)^2=49(x^2+y^2)$, we put $xy=7t+1, t \geq 0$, so that $x^2+y^2=t^2$. Then $$(x+y)^2=x^2+y^2+2xy=t^2+2(7t+1)=(t+7)^2-47,$$ which gives $$(t+7-x-y)(t+7+x+y)=47.$$
So, we must solve the systems
$$\left\{\begin{array}{rcl} t+7-x-y & = & 1 \\ t+7+x+y & = & 47 \end{array} \right. \qquad \left\{\begin{array}{rcl} t+7-x-y & = & -47 \\ t+7+x+y & = & -1 \end{array} \right.$$
Solving the first, we get $t=17$ and $x+y=23$, solving the second we get $t=-31<0$, i.e. no solution. So we have $x+y=23, xy=120$, which gives $x=15,y=8$ and $x=8, y=15$. In conclusion, the solutions are $$(15,8),(8,15),(-15,-8),(-8,-15).$$
Solve in integers the equation $$xy-7\sqrt{x^2+y^2}=1.$$
Proposed by Titu Andreescu.
Solution:
Clearly, $xy \geq 1$. By symmetry, we reduce to $x,y > 0$. Rewriting the equation in the form $(xy-1)^2=49(x^2+y^2)$, we put $xy=7t+1, t \geq 0$, so that $x^2+y^2=t^2$. Then $$(x+y)^2=x^2+y^2+2xy=t^2+2(7t+1)=(t+7)^2-47,$$ which gives $$(t+7-x-y)(t+7+x+y)=47.$$
So, we must solve the systems
$$\left\{\begin{array}{rcl} t+7-x-y & = & 1 \\ t+7+x+y & = & 47 \end{array} \right. \qquad \left\{\begin{array}{rcl} t+7-x-y & = & -47 \\ t+7+x+y & = & -1 \end{array} \right.$$
Solving the first, we get $t=17$ and $x+y=23$, solving the second we get $t=-31<0$, i.e. no solution. So we have $x+y=23, xy=120$, which gives $x=15,y=8$ and $x=8, y=15$. In conclusion, the solutions are $$(15,8),(8,15),(-15,-8),(-8,-15).$$
Mathematical Reflections 2012, Issue 4 - Problem U237
Problem:
Let $\mathcal{H}$ be a hyperbola with foci $A$ and $B$ and center $O$. Let $P$ be an arbitrary point
on $\mathcal{H}$ and let the tangent of $\mathcal{H}$ through $P$ cut its asymptotes at $M$ and $N$. Prove that $PA + PB = OM + ON$.
Let $\mathcal{H}$ be a hyperbola with foci $A$ and $B$ and center $O$. Let $P$ be an arbitrary point
on $\mathcal{H}$ and let the tangent of $\mathcal{H}$ through $P$ cut its asymptotes at $M$ and $N$. Prove that $PA + PB = OM + ON$.
Proposed by Luis Gonzalez.
Solution:
Let $\mathcal{H}: \dfrac{x^2}{a^2}-\dfrac{y^2}{b^2}=1$, so that $O=(0,0)$. By symmetry, suppose that $P$ is on the first quadrant. Then $P=\left(k,\dfrac{b}{a}\sqrt{k^2-a^2}\right)$, where $k \geq a$ is an arbitrary real number. The equation of the tangent of $\mathcal{H}$ at $P$ is $\dfrac{kx}{a^2}-\dfrac{\dfrac{b}{a}\sqrt{k^2-a^2}y}{b^2}=1$, so intersecting this line with the asymptotes $y=\pm \dfrac{b}{a}x$ we get the points $$M=\left(k+\sqrt{k^2-a^2},\dfrac{b}{a}(k+\sqrt{k^2-a^2})\right), \qquad N=\left(k-\sqrt{k^2-a^2},-\dfrac{b}{a}(k-\sqrt{k^2-a^2})\right).$$ Then
$$OM+ON=\dfrac{2k}{a}\sqrt{a^2+b^2}=2ke,$$ where $e=\sqrt{a^2+b^2}/a$ is the eccentricity of the hyperbola. Since the foci have coordinates $A=(-c,0), B=(c,0)$ where $c=\sqrt{a^2+b^2}$, we have
$$\begin{array}{lcl}PA+PB & = &\sqrt{(k+c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}+\sqrt{(k-c)^2+\dfrac{b^2}{a^2}(k^2-a^2)} \\ & = & \dfrac{4kc}{\sqrt{(k+c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}-\sqrt{(k-c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}}\\ &=&\dfrac{2kc}{a}\\&=&2ke \end{array}$$
and the statement follows.
$$OM+ON=\dfrac{2k}{a}\sqrt{a^2+b^2}=2ke,$$ where $e=\sqrt{a^2+b^2}/a$ is the eccentricity of the hyperbola. Since the foci have coordinates $A=(-c,0), B=(c,0)$ where $c=\sqrt{a^2+b^2}$, we have
$$\begin{array}{lcl}PA+PB & = &\sqrt{(k+c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}+\sqrt{(k-c)^2+\dfrac{b^2}{a^2}(k^2-a^2)} \\ & = & \dfrac{4kc}{\sqrt{(k+c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}-\sqrt{(k-c)^2+\dfrac{b^2}{a^2}(k^2-a^2)}}\\ &=&\dfrac{2kc}{a}\\&=&2ke \end{array}$$
and the statement follows.
Mathematical Reflections 2012, Issue 4 - Problem U236
Problem:
Let $f(X)$ be an irreducible polynomial in $\mathbb{Z}[X]$. Prove that $f(XY)$ is irreducible in $\mathbb{Z}[X,Y]$.
Let $f(X)$ be an irreducible polynomial in $\mathbb{Z}[X]$. Prove that $f(XY)$ is irreducible in $\mathbb{Z}[X,Y]$.
Proposed by Mircea Becheanu.
Solution:
If $f(X)$ is a constant polynomial, the statement is trivial. So, assume that $\deg f(X) > 0$. Since $f(X)$ is irreducible, then must be primitive. Assume that $f(XY)$ is reducible in $\mathbb{Z}[X,Y]$. Then, there are two non constant polynomials $g(X,Y), h(X,Y) \in \mathbb{Z}[X,Y]=\mathbb{Z}[X][Y]$ such that $f(XY)=g(X,Y)h(X,Y)$. It cannot be $f(XY)=g(X)h(Y)$, otherwise $f(0)=g(0)h(Y)$, so $h(Y)$ must be constant. Then both $g(X,Y)$ and $h(X,Y)$ must contain both $X$ and $Y$. But $$f(X)=g(X,1)h(X,1)=\overline{g}(X)\overline{h}(X), \qquad \overline{g}(X), \overline{h}(X) \in \mathbb{Z}[X]$$ is the product of two non constant polynomials, i.e. $f(X)$ is reducible, contradiction.
Mathematical Reflections 2012, Issue 4 - Problem S235
Problem:
Solve the equation $$\dfrac{8}{\{x\}}=\dfrac{9}{x}+\dfrac{10}{[x]},$$ where $[x]$ and $\{x\}$ denote the greatest integer less or equal than $x$ and the fractional part of $x$, respectively.
Solve the equation $$\dfrac{8}{\{x\}}=\dfrac{9}{x}+\dfrac{10}{[x]},$$ where $[x]$ and $\{x\}$ denote the greatest integer less or equal than $x$ and the fractional part of $x$, respectively.
Proposed by Titu Andreescu.
Solution:
Clearly $x \notin \mathbb{Z}, x \not \in (0,1)$ and from $\dfrac{8}{\{x\}} > 0$, we gather $x > 1$. Since $0 < \{x\} < 1$ and $0 < [x] \leq x$, we have $$8 < \dfrac{8}{\{x\}} \leq \dfrac{19}{[x]},$$ so $[x]=1,2$. Clearing the denominators and using the fact that $\{x\}=x-[x]$ we obtain the equation $$10x^2-9x[x]-9[x]^2=0.$$
(i) If $[x]=1$, we get $10x^2-9x-9=0$, which gives $x=\dfrac{3}{2},-\dfrac{3}{5}$, i.e. $x=\dfrac{3}{2}$.
(i) If $[x]=1$, we get $10x^2-9x-9=0$, which gives $x=\dfrac{3}{2},-\dfrac{3}{5}$, i.e. $x=\dfrac{3}{2}$.
(ii) If $[x]=2$, we get $10x^2-18x-36=0$, which gives $x=3,-\dfrac{6}{5}$, i.e. no solution.
So, $x=\dfrac{3}{2}$ is the only solution to the given equation.
So, $x=\dfrac{3}{2}$ is the only solution to the given equation.
Mathematical Reflections 2012, Issue 4 - Problem J239
Problem:
Let $a$ and $b$ be real numbers so that $2a^2 + 3ab + 2b^2 \leq 7$. Prove that $$\max\{2a+b,2b+a\} \leq 4.$$
$$7 \geq 2a^2 + 3ab + 2b^2 > b^2+2b+8,$$ which gives $(b+1)^2 < 0$, contradiction.
Let $a$ and $b$ be real numbers so that $2a^2 + 3ab + 2b^2 \leq 7$. Prove that $$\max\{2a+b,2b+a\} \leq 4.$$
Proposed by Titu Andreescu.
Solution:
Suppose
that $a \geq b$, so that $\max\{2a+b,2b+a\}=2a+b$. We argue by
contradiction. Suppose that for some real numbers $a,b$ we have
$2a+b>4$, i.e. $a>\dfrac{4-b}{2}$. Then$$7 \geq 2a^2 + 3ab + 2b^2 > b^2+2b+8,$$ which gives $(b+1)^2 < 0$, contradiction.
Mathematical Reflections 2012, Issue 4 - Problem J237
Problem:
Prove that the diameter of the incircle of a triangle $ABC$ is equal to $\dfrac{AB-BC+CA}{\sqrt{3}}$ if and only if $\angle BAC = 60^{\circ}$.
Solution:
Let $r$ be the radius of the incircle of $\triangle ABC$ and let $\alpha=\angle BAC$. Clearly $0^{\circ} < \alpha < 180^{\circ}$ and $$2r=\dfrac{2AB\cdot CA \sin \alpha}{AB+BC+CA}.$$ Then $$2r=\dfrac{AB-BC+CA}{\sqrt{3}} \iff AB^2+CA^2+2AB\cdot CA - BC^2=2\sqrt{3}AB \cdot CA \sin \alpha.$$ Since $BC^2=AB^2+CA^2-2AB\cdot CA \cos \alpha$, we obtain $$2r=\dfrac{AB-BC+CA}{\sqrt{3}} \iff 1 + \cos \alpha = \sqrt{3} \sin \alpha,$$ i.e. if and only if $\sin (\alpha-30^{\circ})=\dfrac{1}{2},$ which gives $\alpha=60^{\circ}$.
Prove that the diameter of the incircle of a triangle $ABC$ is equal to $\dfrac{AB-BC+CA}{\sqrt{3}}$ if and only if $\angle BAC = 60^{\circ}$.
Proposed by Titu Andreescu.
Solution:
Let $r$ be the radius of the incircle of $\triangle ABC$ and let $\alpha=\angle BAC$. Clearly $0^{\circ} < \alpha < 180^{\circ}$ and $$2r=\dfrac{2AB\cdot CA \sin \alpha}{AB+BC+CA}.$$ Then $$2r=\dfrac{AB-BC+CA}{\sqrt{3}} \iff AB^2+CA^2+2AB\cdot CA - BC^2=2\sqrt{3}AB \cdot CA \sin \alpha.$$ Since $BC^2=AB^2+CA^2-2AB\cdot CA \cos \alpha$, we obtain $$2r=\dfrac{AB-BC+CA}{\sqrt{3}} \iff 1 + \cos \alpha = \sqrt{3} \sin \alpha,$$ i.e. if and only if $\sin (\alpha-30^{\circ})=\dfrac{1}{2},$ which gives $\alpha=60^{\circ}$.
Mathematical Reflections 2012, Issue 4 - Problem J235
Problem:
In the equality $\sqrt{ABCDEF}=DEF$, different letters represent different digits. Find the six-digit number $ABCDEF$.
Solution:
From the given equality, it must be $ABCDEF^2-DEF \equiv 0 \pmod {1000}$, and since $ABCDEF \equiv DEF \pmod{1000}$, we have $DEF^2-DEF=DEF(DEF-1) \equiv 0 \pmod{1000}$. Since $DEF$ and $DEF-1$ are coprime and $1000=2^3\cdot5^3$, one between this two numbers must be odd and divisibile by $5^3$ and the other must be divisible by $2^3$. Since $DEF$ and $DEF-1$ are three digit numbers, $DEF \in \{125,375,625,875\}$ or $DEF-1 \in \{125,375,625,875\}$. In the first case, $DEF-1$ is divisible by $8$ if and only if $DEF=625$, in the second case $DEF$ is divisible by $8$ if and only if $DEF-1=375$. So, $DEF=625,376$, but
$$625^2=390625 \qquad 376^2=141376,$$ i.e. the only number which satisfies the required conditions is $625$.
In the equality $\sqrt{ABCDEF}=DEF$, different letters represent different digits. Find the six-digit number $ABCDEF$.
Proposed by Titu Andreescu.
Solution:
From the given equality, it must be $ABCDEF^2-DEF \equiv 0 \pmod {1000}$, and since $ABCDEF \equiv DEF \pmod{1000}$, we have $DEF^2-DEF=DEF(DEF-1) \equiv 0 \pmod{1000}$. Since $DEF$ and $DEF-1$ are coprime and $1000=2^3\cdot5^3$, one between this two numbers must be odd and divisibile by $5^3$ and the other must be divisible by $2^3$. Since $DEF$ and $DEF-1$ are three digit numbers, $DEF \in \{125,375,625,875\}$ or $DEF-1 \in \{125,375,625,875\}$. In the first case, $DEF-1$ is divisible by $8$ if and only if $DEF=625$, in the second case $DEF$ is divisible by $8$ if and only if $DEF-1=375$. So, $DEF=625,376$, but
$$625^2=390625 \qquad 376^2=141376,$$ i.e. the only number which satisfies the required conditions is $625$.
Sunday, October 14, 2012
KöMaL (Metresis) 1894, Problem 8
Problem:
If $2 \cos \vartheta = u+\dfrac{1}{u}$, prove that $2 \cos n \vartheta = u^n+\dfrac{1}{u^n}$ for every positive integer $n$.
Solution 1:
We prove the statement by induction on $n \geq 2$. If $n=2$ we have $$2 \cos 2\vartheta =4 \cos^2 \vartheta - 2=\left(u+\dfrac{1}{u} \right)^2 - 2=u^2+\dfrac{1}{u^2}.$$ Assume that the statement is true for every $2 \leq k \leq n$. Then, $$\begin{eqnarray*} 2 \cos (n+1)\vartheta &= &2[2\cos n \vartheta \cos \vartheta - \cos (n-1)\vartheta]\\ &= & 2\left[\left(u^n+\dfrac{1}{u^n}\right)\dfrac{1}{2}\left(u+\dfrac{1}{u}\right)-\dfrac{1}{2}\left(u^{n-1}+\dfrac{1}{u^{n-1}}\right)\right] \\ & = & u^{n+1}+\dfrac{1}{u^{n+1}}, \end{eqnarray*}$$ and the statement follows.
Solution 2:
From the given equality, we obtain $u^2-(2\cos \vartheta) u + 1=0$, and solving this equation in $u$ we get $u=\cos \vartheta \pm i \sin \vartheta=e^{\pm i \vartheta}$. Then, for every positive integer $n$
$$2 \cos n \vartheta = e^{\pm in\vartheta}+e^{\mp in \vartheta}=u^n+u^{-n}=u^n+\dfrac{1}{u^n}$$ as we wanted to prove.
If $2 \cos \vartheta = u+\dfrac{1}{u}$, prove that $2 \cos n \vartheta = u^n+\dfrac{1}{u^n}$ for every positive integer $n$.
Solution 1:
We prove the statement by induction on $n \geq 2$. If $n=2$ we have $$2 \cos 2\vartheta =4 \cos^2 \vartheta - 2=\left(u+\dfrac{1}{u} \right)^2 - 2=u^2+\dfrac{1}{u^2}.$$ Assume that the statement is true for every $2 \leq k \leq n$. Then, $$\begin{eqnarray*} 2 \cos (n+1)\vartheta &= &2[2\cos n \vartheta \cos \vartheta - \cos (n-1)\vartheta]\\ &= & 2\left[\left(u^n+\dfrac{1}{u^n}\right)\dfrac{1}{2}\left(u+\dfrac{1}{u}\right)-\dfrac{1}{2}\left(u^{n-1}+\dfrac{1}{u^{n-1}}\right)\right] \\ & = & u^{n+1}+\dfrac{1}{u^{n+1}}, \end{eqnarray*}$$ and the statement follows.
Solution 2:
From the given equality, we obtain $u^2-(2\cos \vartheta) u + 1=0$, and solving this equation in $u$ we get $u=\cos \vartheta \pm i \sin \vartheta=e^{\pm i \vartheta}$. Then, for every positive integer $n$
$$2 \cos n \vartheta = e^{\pm in\vartheta}+e^{\mp in \vartheta}=u^n+u^{-n}=u^n+\dfrac{1}{u^n}$$ as we wanted to prove.
KöMaL (Metresis) 1894, Problem 2
Problem:
Find all positive integers $N$ divisible only by $2$ and by $3$ such that $N^2$ has three times the number of divisors of $N$.
Solution:
Let $N=2^a 3^b$, where $a,b \in \mathbb{N}^*$. Then $N^2 = 2^{2a}3^{2b}$. So, it must be $$3(a+1)(b+1)=(2a+1)(2b+1) \iff ab-a-b-2=0 \iff (a-1)(b-1)=3.$$ Since $a-1 \geq 0$ and $b-1 \geq 0$, we obtain $$\left\{ \begin{array}{rcl} a-1 & = & 1 \\ b-1 & = & 3 \end{array} \right. \qquad \textrm{or} \qquad \left\{ \begin{array}{rcl} a-1 & = & 3 \\ b-1 & = & 1 \end{array} \right.$$ i.e. $a=2, b=4$ or $a=4, b=2$. Then all the positive integers required are $N_1=2^2 3^4=324$ and $N_2=2^4 3^2=144$.
Find all positive integers $N$ divisible only by $2$ and by $3$ such that $N^2$ has three times the number of divisors of $N$.
Solution:
Let $N=2^a 3^b$, where $a,b \in \mathbb{N}^*$. Then $N^2 = 2^{2a}3^{2b}$. So, it must be $$3(a+1)(b+1)=(2a+1)(2b+1) \iff ab-a-b-2=0 \iff (a-1)(b-1)=3.$$ Since $a-1 \geq 0$ and $b-1 \geq 0$, we obtain $$\left\{ \begin{array}{rcl} a-1 & = & 1 \\ b-1 & = & 3 \end{array} \right. \qquad \textrm{or} \qquad \left\{ \begin{array}{rcl} a-1 & = & 3 \\ b-1 & = & 1 \end{array} \right.$$ i.e. $a=2, b=4$ or $a=4, b=2$. Then all the positive integers required are $N_1=2^2 3^4=324$ and $N_2=2^4 3^2=144$.
KöMaL (Metresis) 1894, Problem 1
Problem:
Find all the two digit numbers $\overline{ab}$ such that $\overline{ababab}+1$ is a perfect cube.
Solution:
Let $x=\overline{ab}$ be the two digit number. Then, $101010x+1=n^3$, for some positive integer $n$. Clearly, $10^6 \leq n^3 < 10^7$, i.e. $100 \leq n \leq 215$. Moreover,
$$101010x=n^3-1.$$ Since $101010=30\cdot3367$, it's easy to see that $n^3-1 \equiv 0 \pmod{30}$ if and only if $n \equiv 1 \pmod{30}$, i.e. $n-1$ is divisible by $30$. So $n \in \{121,151,181,211\}$ and an easy check shows that only $n=211$ works. In this case, $x=93$.
Find all the two digit numbers $\overline{ab}$ such that $\overline{ababab}+1$ is a perfect cube.
Solution:
Let $x=\overline{ab}$ be the two digit number. Then, $101010x+1=n^3$, for some positive integer $n$. Clearly, $10^6 \leq n^3 < 10^7$, i.e. $100 \leq n \leq 215$. Moreover,
$$101010x=n^3-1.$$ Since $101010=30\cdot3367$, it's easy to see that $n^3-1 \equiv 0 \pmod{30}$ if and only if $n \equiv 1 \pmod{30}$, i.e. $n-1$ is divisible by $30$. So $n \in \{121,151,181,211\}$ and an easy check shows that only $n=211$ works. In this case, $x=93$.
Tuesday, June 12, 2012
Mathematical Reflections 2012, Issue 2 - Problem S224
Problem:
Let $a,b,c$ real numbers greater than $2$ such that $$\dfrac{7-2a}{3a-6}+\dfrac{7-2b}{3b-6}+\dfrac{7-2c}{3c-6}=\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}.$$ Prove that
$\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c} \leq 1.$
Solution:
Since $$\dfrac{7-2a}{3a-6}+\dfrac{7-2b}{3b-6}+\dfrac{7-2c}{3c-6}=-\dfrac{2}{3}+\dfrac{1}{a-2}-\dfrac{2}{3}+\dfrac{1}{b-2}-\dfrac{2}{3}+\dfrac{1}{c-2},$$ the given condition can be rewritten as $$\dfrac{1}{a(a-2)}+\dfrac{1}{b(b-2)}+\dfrac{1}{c(c-2)}=1.$$
Suppose without loss of generality that $a \leq b \leq c$. If $$\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c} > 1$$ then $\dfrac{1}{a-2}+\dfrac{1}{b-2}+\dfrac{1}{c-2} > 3$ and by Chebychev's Inequality,
$$3 < \left(\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}\right)\left(\dfrac{1}{a-2}+\dfrac{1}{b-2}+\dfrac{1}{c-2}\right) \leq 3,$$ contradiction.
Let $a,b,c$ real numbers greater than $2$ such that $$\dfrac{7-2a}{3a-6}+\dfrac{7-2b}{3b-6}+\dfrac{7-2c}{3c-6}=\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}.$$ Prove that
$\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c} \leq 1.$
Proposed by Titu Andreescu.
Solution:
Since $$\dfrac{7-2a}{3a-6}+\dfrac{7-2b}{3b-6}+\dfrac{7-2c}{3c-6}=-\dfrac{2}{3}+\dfrac{1}{a-2}-\dfrac{2}{3}+\dfrac{1}{b-2}-\dfrac{2}{3}+\dfrac{1}{c-2},$$ the given condition can be rewritten as $$\dfrac{1}{a(a-2)}+\dfrac{1}{b(b-2)}+\dfrac{1}{c(c-2)}=1.$$
Suppose without loss of generality that $a \leq b \leq c$. If $$\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c} > 1$$ then $\dfrac{1}{a-2}+\dfrac{1}{b-2}+\dfrac{1}{c-2} > 3$ and by Chebychev's Inequality,
$$3 < \left(\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}\right)\left(\dfrac{1}{a-2}+\dfrac{1}{b-2}+\dfrac{1}{c-2}\right) \leq 3,$$ contradiction.
Mathematical Reflections 2012, Issue 2 - Problem J227
Problem:
For a positive integer $N$ let $r(N)$ be the number obtained by reversing the digits of $N$.
Find all $3$-digit numbers $N$ such that $r^2(N)-N^2$ is the cube of a positive integer.
Solution:
Let $N=100a+10b+c$ and $r(N)=100c+10b+c$ with $0 \leq a,b,c \leq 9$, $ac \neq 0$. Then
$$r^2(N)-N^2=(100c+10b+a)^2-(100a+10b+c)^2=99(c-a)[101(c+a)+20b].$$
Since $r^2(N)-N^2 > 0$, it must be $c > a$. If $r^2(N)-N^2$ is a cube, as $c-a \leq 8$, then $101(c+a)+20b \equiv 0 \pmod{121}$, i.e. $b-(a+c) \equiv 0 \pmod{121}$. Since $-17 \leq b-(a+c) \leq 6$, then $b=a+c$. So,
$$r^2(N)-N^2=11^3\cdot3^2(c-a)(c+a).$$
If $c-a=3$ then $c+a=2a+3$ and $5 \leq 2a+3 \leq 19$ must be an odd cube, contradiction. Likewise, $c-a=6$ yields $c+a=2(a+3)$, so that $a+3=2k^3$ where $k$ is a positive integer, contradiction. So, $c+a=3,6,9$.
(i) If $c+a=3$, then $a=1, c=2$ and it's easy to see that $r^2(N)-N^2=11^3\cdot3^3 = 33^3$.
(ii) If $c+a=6$, then $c-a=2(3-a)$ and $r^2(N)-N^2=11^3\cdot3^3\cdot2^2(3-a)$, so $a=1$ and $c=5$.
(iii) If $c+a=9$, then $c-a=9-2a$ and $r^2(N)-N^2=11^3\cdot3^4 (9-2a)$, but $9-2a=9k^3$ has no positive integer solution.
In conclusion, all the $3$-digit numbers which satisfy the required conditions are $132$ and $165$.
For a positive integer $N$ let $r(N)$ be the number obtained by reversing the digits of $N$.
Find all $3$-digit numbers $N$ such that $r^2(N)-N^2$ is the cube of a positive integer.
Proposed by Titu Andreescu.
Solution:
Let $N=100a+10b+c$ and $r(N)=100c+10b+c$ with $0 \leq a,b,c \leq 9$, $ac \neq 0$. Then
$$r^2(N)-N^2=(100c+10b+a)^2-(100a+10b+c)^2=99(c-a)[101(c+a)+20b].$$
Since $r^2(N)-N^2 > 0$, it must be $c > a$. If $r^2(N)-N^2$ is a cube, as $c-a \leq 8$, then $101(c+a)+20b \equiv 0 \pmod{121}$, i.e. $b-(a+c) \equiv 0 \pmod{121}$. Since $-17 \leq b-(a+c) \leq 6$, then $b=a+c$. So,
$$r^2(N)-N^2=11^3\cdot3^2(c-a)(c+a).$$
If $c-a=3$ then $c+a=2a+3$ and $5 \leq 2a+3 \leq 19$ must be an odd cube, contradiction. Likewise, $c-a=6$ yields $c+a=2(a+3)$, so that $a+3=2k^3$ where $k$ is a positive integer, contradiction. So, $c+a=3,6,9$.
(i) If $c+a=3$, then $a=1, c=2$ and it's easy to see that $r^2(N)-N^2=11^3\cdot3^3 = 33^3$.
(ii) If $c+a=6$, then $c-a=2(3-a)$ and $r^2(N)-N^2=11^3\cdot3^3\cdot2^2(3-a)$, so $a=1$ and $c=5$.
(iii) If $c+a=9$, then $c-a=9-2a$ and $r^2(N)-N^2=11^3\cdot3^4 (9-2a)$, but $9-2a=9k^3$ has no positive integer solution.
In conclusion, all the $3$-digit numbers which satisfy the required conditions are $132$ and $165$.
Mathematical Reflections 2012, Issue 2 - Problem J225
Problem:
Let $a, b, c$ be nonnegative real numbers such that $a+b+c=1$. Prove that $$ab(a^2+b^2)+bc(b^2+c^2)+ca(c^2+a^2)+abc \leq \dfrac{1}{8}.$$
Let $a, b, c$ be nonnegative real numbers such that $a+b+c=1$. Prove that $$ab(a^2+b^2)+bc(b^2+c^2)+ca(c^2+a^2)+abc \leq \dfrac{1}{8}.$$
Proposed by Titu Andreescu.
Solution:
Using the fact that $abc=abc(a+b+c)$ and factorizing we have
$$ab(a^2+b^2)+bc(b^2+c^2)+ca(c^2+a^2)+abc=(a^2+b^2+c^2)(ab+bc+ca).$$
By AM-GM Inequality, $$a^2+b^2+c^2+2(ab+bc+ca)=1 \geq 2\sqrt{2(a^2+b^2+c^2)(ab+bc+ca)},$$
then $$(a^2+b^2+c^2)(ab+bc+ca) \leq \dfrac{1}{8}.$$
$$ab(a^2+b^2)+bc(b^2+c^2)+ca(c^2+a^2)+abc=(a^2+b^2+c^2)(ab+bc+ca).$$
By AM-GM Inequality, $$a^2+b^2+c^2+2(ab+bc+ca)=1 \geq 2\sqrt{2(a^2+b^2+c^2)(ab+bc+ca)},$$
then $$(a^2+b^2+c^2)(ab+bc+ca) \leq \dfrac{1}{8}.$$
Mathematical Reflections 2012, Issue 2 - Problem J223
Problem:
Let $a$ and $b$ be real numbers such that $\sin^3 a - \dfrac{4}{3} \cos^3 a \leq b-\dfrac{1}{4}$. Prove that
$$\dfrac{3}{4}\sin a - \cos a \leq b+\dfrac{1}{6}.$$
Solution:
We argue by contradiction. Suppose that $b+\dfrac{1}{6} < \dfrac{3}{4}\sin a - \cos a$. Then, summing up the two inequalities and rearranging, we have $$\dfrac{5}{12} < \dfrac{1}{4} \sin 3a + \dfrac{1}{3} \cos 3a.$$
But $$\dfrac{1}{4} \sin 3a + \dfrac{1}{3} \cos 3a = \dfrac{5}{12} \left(\dfrac{4}{5}\cos 3a + \dfrac{3}{5} \sin 3a\right) = \dfrac{5}{12} \cos \left(3a-\arctan \dfrac{3}{4}\right) \leq \dfrac{5}{12},$$ a contradiction.
Let $a$ and $b$ be real numbers such that $\sin^3 a - \dfrac{4}{3} \cos^3 a \leq b-\dfrac{1}{4}$. Prove that
$$\dfrac{3}{4}\sin a - \cos a \leq b+\dfrac{1}{6}.$$
Proposed by Titu Andreescu.
Solution:
We argue by contradiction. Suppose that $b+\dfrac{1}{6} < \dfrac{3}{4}\sin a - \cos a$. Then, summing up the two inequalities and rearranging, we have $$\dfrac{5}{12} < \dfrac{1}{4} \sin 3a + \dfrac{1}{3} \cos 3a.$$
But $$\dfrac{1}{4} \sin 3a + \dfrac{1}{3} \cos 3a = \dfrac{5}{12} \left(\dfrac{4}{5}\cos 3a + \dfrac{3}{5} \sin 3a\right) = \dfrac{5}{12} \cos \left(3a-\arctan \dfrac{3}{4}\right) \leq \dfrac{5}{12},$$ a contradiction.
Tuesday, April 3, 2012
Mathematical Reflections 2012, Issue 1 - Problem U217
Problem:
Define an increasing sequence $(a_k)_{k \in \mathbb{Z}^+}$ to be attractive if $\sum_{k=1}^\infty \dfrac{1}{a_k}$ diverges and $\sum_{k=1}^\infty \dfrac{1}{a^2_k}$ converges. Prove that there is an attractive sequence $a_k$ such that $a_k\sqrt{k}$ is also an attractive sequence.
Proposed by Ivan Borsenco.
Define an increasing sequence $(a_k)_{k \in \mathbb{Z}^+}$ to be attractive if $\sum_{k=1}^\infty \dfrac{1}{a_k}$ diverges and $\sum_{k=1}^\infty \dfrac{1}{a^2_k}$ converges. Prove that there is an attractive sequence $a_k$ such that $a_k\sqrt{k}$ is also an attractive sequence.
Proposed by Ivan Borsenco.
Solution:
We claim that $a_k = \sqrt{k} \log (k+1)$ do the trick. Indeed, $a_k = \sqrt{k} \log (k+1)$ is obviously increasing for all $k \geq 1$. Moreover, since $\dfrac{1}{k} \leq \dfrac{1}{\sqrt{k}\log (k+1)}$ for all $k \geq 1$ and $\displaystyle \int_1^\infty \dfrac{1}{x\log^2 (x+1)} \ dx$ converges we obtain that
$$\lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{\sqrt{k}\log (k+1)} = \infty, \qquad \lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k \log^2 (k+1)} = M < \infty$$
as a consequence of the Comparison Test and the Integral Test.
Finally, $a_k\sqrt{k}=k \log (k+1)$ is also attractive. As a matter of fact, $k \log (k+1)$ is increasing for all $k \geq 1$, $\displaystyle \int_1^\infty \dfrac{1}{x\log (x+1)} \ dx$ diverges and $\dfrac{1}{k^2 \log^2 (k+1)} \leq \dfrac{1}{k^2}$ for all $k \geq 2$, therefore
$$\lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k\log (k+1)} = \infty, \qquad \lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k^2 \log^2 (k+1)} = N < \infty.$$
$$\lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{\sqrt{k}\log (k+1)} = \infty, \qquad \lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k \log^2 (k+1)} = M < \infty$$
as a consequence of the Comparison Test and the Integral Test.
Finally, $a_k\sqrt{k}=k \log (k+1)$ is also attractive. As a matter of fact, $k \log (k+1)$ is increasing for all $k \geq 1$, $\displaystyle \int_1^\infty \dfrac{1}{x\log (x+1)} \ dx$ diverges and $\dfrac{1}{k^2 \log^2 (k+1)} \leq \dfrac{1}{k^2}$ for all $k \geq 2$, therefore
$$\lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k\log (k+1)} = \infty, \qquad \lim_{n \to \infty} \sum_{k=1}^n \dfrac{1}{k^2 \log^2 (k+1)} = N < \infty.$$
Mathematical Reflections 2012, Issue 1 - Problem J221
Problem:
Solve in integers the system of equations
Therefore, $(3,0,-3)$ is the only integer solution to the given system.
Solve in integers the system of equations
$\begin{array}{lll} xy-\dfrac{z}{3} = xyz+1 \\ yz-\dfrac{x}{3} = xyz - 1 \\ zx-\dfrac{y}{3} = xyz-9. \end{array}$
Proposed by Titu Andreescu.
Solution:
It's easy to see that $x,y,z$ must be divisible by $3$. Summing up all the equations and factorizing, we obtain $$(x-1)(y-1)(z-1)(xy+yz+zx+1)=8.$$ Then $x-1=\pm1,\pm 2, \pm 4, \pm 8$, i.e. $x=0,2,-1,3,-3,5,-7,9$ and for what we said, we reduce to $x \in \{-3,0,3,9\}$. Now, consider the second equation of the system $$yz-\dfrac{x}{3} = xyz - 1.$$ We have four cases.
(i) If $x=-3$, then $2yz=-1$, so no integer solution.
(ii) If $x=0$, then $yz=-1$, but the first equation gives $z=-3$, so no integer solution.
(ii) If $x=0$, then $yz=-1$, but the first equation gives $z=-3$, so no integer solution.
(iii) If $x=3$, then $yz=0$. If $y=0$ we get $z=-3$ from the first equation of the system and these values satisfy also the third equation, i.e. $(3,0,-3)$ is a solution. If $z=0$, the first equation gives $3y=1$, i.e. no integer solution.
(iv) If $x=9$, then $4yz=-1$, so no integer solution.
Therefore, $(3,0,-3)$ is the only integer solution to the given system.
Mathematical Reflections 2012, Issue 1 - Problem J220
Problem:
Find the least prime $p$ for which $p=a^2_k+kb^2_k, k=1,\ldots,5$, for some $(a_k,b_k)$ in $\mathbb{Z} \times \mathbb{Z}$.
Find the least prime $p$ for which $p=a^2_k+kb^2_k, k=1,\ldots,5$, for some $(a_k,b_k)$ in $\mathbb{Z} \times \mathbb{Z}$.
Proposed by Cosmin Pohoata.
Solution:
We have $p \equiv a^2_k \pmod{k}$ for $k=2,\ldots,5$, so $$\begin{array}{lll} p \equiv 1 \pmod{2} \\ p \equiv 1 \pmod{3} \\ p \equiv 1 \pmod{4} \\ p \equiv 1,4 \pmod{5}. \end{array}$$ Then $p=1+60n$ or $p=49+60n$ where $n \in \mathbb{N}$. Clearly $p \neq 1,49$. Moreover, $p \neq 61,109,121,169,181,229$ since $121,169$ are not primes and the equation
$$a^2_2+2b^2_2 \equiv 5 \pmod{8}$$ has no solution. We conclude that $p=241$ is the least prime which satisfies the given conditions, since
$$241=15^2+4^2=13^2+2\cdot6^2=7^2+3\cdot8^2=15^2+4\cdot2^2=14^2+5\cdot3^2.$$
$$a^2_2+2b^2_2 \equiv 5 \pmod{8}$$ has no solution. We conclude that $p=241$ is the least prime which satisfies the given conditions, since
$$241=15^2+4^2=13^2+2\cdot6^2=7^2+3\cdot8^2=15^2+4\cdot2^2=14^2+5\cdot3^2.$$
Mathematical Reflections 2012, Issue 1 - Problem J219
Problem:
Trying to solve a problem, Jimmy used the following "`formula"': $\log_{ab} x = \log_a x \log_b x$,
where $a, b, x$ are positive real numbers different from $1$. Prove that this is correct only
if $x$ is a solution to the equation $\log_a x + \log_b x = 1$.
Trying to solve a problem, Jimmy used the following "`formula"': $\log_{ab} x = \log_a x \log_b x$,
where $a, b, x$ are positive real numbers different from $1$. Prove that this is correct only
if $x$ is a solution to the equation $\log_a x + \log_b x = 1$.
Proposed by Titu Andreescu.
Solution:
We have $\log_{ab} x = \dfrac{\log_a x}{1+\log_a b}$. So $$\log_{ab} x = \log_a x \log_b x \iff \dfrac{1}{1+\log_a b}=\log_b x \iff 1=\log_b x + \log_a b \log_b x.$$ Since $\log_b x = \dfrac{\log_a x}{\log_a b}$, we are done.
Mathematical Reflections 2012, Issue 1 - Problem J217
Problem:
If $a, b, c$ are integers such that $a^2 + 2bc = 1$ and $b^2 + 2ca = 2012$, find all possible values
of $c^2 + 2ab$.
If $a, b, c$ are integers such that $a^2 + 2bc = 1$ and $b^2 + 2ca = 2012$, find all possible values
of $c^2 + 2ab$.
Proposed by Titu Andreescu.
Solution:
Subtracting the two given equations, we have $(b-a)(b+a-2c)=2011$, so we get $$\left\{ \begin{array}{lll} b & = & a \pm 1 \\ 2c & = & b+a \mp 2011 \end{array} \right. \qquad \left\{ \begin{array}{lll} b & = & a \pm 2011 \\ 2c & = & b+a \mp 1. \end{array} \right.$$
Substituting these values into the equation $a^2+2bc=1$, we obtain the four equations
(i) $3a^2-2008a-2011=0$
(ii) $3a^2+2008a-2011=0$
(iii) $3a^2+6032a+2010\cdot2011-1=0$
(iv) $3a^2-6032a+2010\cdot2011-1=0$.
Equation (i) gives $(a+1)(3a-2011)=0$, so $a=-1, b=0, c=-1006$.
Equation (ii) gives $(a-1)(3a+2011)=0$, so $a=1, b=0, c=1006$.
Equations (iii) and (iv) have no solution since their discriminant is negative.
In conclusion, $c^2+2ab=1006^2=1012036$.
Substituting these values into the equation $a^2+2bc=1$, we obtain the four equations
(i) $3a^2-2008a-2011=0$
(ii) $3a^2+2008a-2011=0$
(iii) $3a^2+6032a+2010\cdot2011-1=0$
(iv) $3a^2-6032a+2010\cdot2011-1=0$.
Equation (i) gives $(a+1)(3a-2011)=0$, so $a=-1, b=0, c=-1006$.
Equation (ii) gives $(a-1)(3a+2011)=0$, so $a=1, b=0, c=1006$.
Equations (iii) and (iv) have no solution since their discriminant is negative.
In conclusion, $c^2+2ab=1006^2=1012036$.
Tuesday, February 21, 2012
Mathematical Reflections 2011, Issue 6 - Problem O213
Problem:
Let $n$ be a positive integer and let $z$ be a complex number such that $z^{2^n-1}-1=0$. Evaluate
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right).$$
Let $n$ be a positive integer and let $z$ be a complex number such that $z^{2^n-1}-1=0$. Evaluate
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right).$$
Proposed by Titu Andreescu.
Solution:
It's clear that if $z=1$, then $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Assume that $z \neq 1$. We have $$z^{2^n-1}-1=(z-1)(z^{2^n-2}+z^{2^n-3}+\ldots+z+1)=0,$$ so $z^{2^n-2}+z^{2^n-3}+\ldots+z+1=0$. Then,
$$\begin{array}{lll} \displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right) & = & \displaystyle \prod_{k=0}^{n-1}\left(z^{2^{k+1}}-z^{2^k}+1\right) \\ & = & \displaystyle \prod_{k=0}^{n-1} \dfrac{z^{3\cdot2^k}+1}{z^{2^k}+1}.\end{array}$$ Clearly, $$\displaystyle \prod_{k=0}^{n-1} (z^{2^k}+1) = \sum_{k=0}^{2^n-1} z^k = z^{2^n-1} + \sum_{k=0}^{2^n-2} z^k = 1.$$ Let $n$ be odd. Since $\gcd(2^n-1,3)=1$, then $z^{3i} \neq z^{3j} \quad \forall i \not \equiv j \pmod{2^n-1}$. So, $$\displaystyle \prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3 (2^n-1)} + \sum_{k=0}^{2^n-2} z^{3k} = 1 + \sum_{k=0}^{2^n-2} z^k = 1,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Now, let $n$ be even. Then $$z^{2^n-1}-1=(z^3-1)(z^{2^n-4}+z^{2^n-7}+\ldots+z^3+1)=0.$$ If $z$ is a third root of unity, then $z^3=1$ and
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = 2^n,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=2^n$. If $z$ is not a third root of unity, since $z^{2^n-(3k+1)}=z^{3(2^n-1-k)}$, then
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3k(2^n-1)} + \sum_{k=1}^{2^n-1} z^{3(2^n-1-k)} = 1 + 3 \sum_{k=1}^{\frac{2^n-1}{3}} z^{2^n-(3k+1)} = 1.$$
In summary,
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=\left\{ \begin{array}{lll} 2^n & \textrm{if } n \textrm{ is even and } z = e^{\frac{2i\pi}{3}},e^{\frac{4i\pi}{3}} \\ 1 & \textrm{otherwise.} \end{array} \right.$$
$$\begin{array}{lll} \displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right) & = & \displaystyle \prod_{k=0}^{n-1}\left(z^{2^{k+1}}-z^{2^k}+1\right) \\ & = & \displaystyle \prod_{k=0}^{n-1} \dfrac{z^{3\cdot2^k}+1}{z^{2^k}+1}.\end{array}$$ Clearly, $$\displaystyle \prod_{k=0}^{n-1} (z^{2^k}+1) = \sum_{k=0}^{2^n-1} z^k = z^{2^n-1} + \sum_{k=0}^{2^n-2} z^k = 1.$$ Let $n$ be odd. Since $\gcd(2^n-1,3)=1$, then $z^{3i} \neq z^{3j} \quad \forall i \not \equiv j \pmod{2^n-1}$. So, $$\displaystyle \prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3 (2^n-1)} + \sum_{k=0}^{2^n-2} z^{3k} = 1 + \sum_{k=0}^{2^n-2} z^k = 1,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Now, let $n$ be even. Then $$z^{2^n-1}-1=(z^3-1)(z^{2^n-4}+z^{2^n-7}+\ldots+z^3+1)=0.$$ If $z$ is a third root of unity, then $z^3=1$ and
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = 2^n,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=2^n$. If $z$ is not a third root of unity, since $z^{2^n-(3k+1)}=z^{3(2^n-1-k)}$, then
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3k(2^n-1)} + \sum_{k=1}^{2^n-1} z^{3(2^n-1-k)} = 1 + 3 \sum_{k=1}^{\frac{2^n-1}{3}} z^{2^n-(3k+1)} = 1.$$
In summary,
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=\left\{ \begin{array}{lll} 2^n & \textrm{if } n \textrm{ is even and } z = e^{\frac{2i\pi}{3}},e^{\frac{4i\pi}{3}} \\ 1 & \textrm{otherwise.} \end{array} \right.$$
Mathematical Reflections 2011, Issue 6 - Problem O212
Problem:
Let $f_0(i)=1$ for all $i \in \mathbb{N}$ and let $f_k(n)=\displaystyle \sum_{i=1}^n f_{k-1}(i)$ for $k \geq 1$. Prove that
$$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j)=F_n,$$ where $F_n$ is the $n$-th Fibonacci number.
Solution:
First we show that if $n,k \geq 1$, then
\begin{equation}\label{identity1}
\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}. \qquad (1)
\end{equation}
By Pascal's Identity,
$$\begin{array}{lll} \displaystyle \sum_{i=k}^{n} {i \choose k} & = & \displaystyle {k \choose k+1} + \sum_{i=k}^{n} {i \choose k}\\
& = & \displaystyle {k+1 \choose k+1} + \sum_{i=k+1}^{n} {i \choose k} \\ & = & \displaystyle {k+2 \choose k+1} + \sum_{i=k+2}^{n} {i \choose k} \\ & = & \displaystyle \vdots \\ & = & \displaystyle {n+1 \choose k+1}. \end{array}$$
Now, we prove by induction on $k \geq 1$ that $f_k(n)=\displaystyle {n+k-1 \choose k}$ for any $n \in \mathbb{N}$.
For $k=1$ we have $f_1(n)=\displaystyle \sum_{i=1}^n f_{0}(i)=n$, so the equality holds. Suppose that the equality is true for $k$. Then
$$f_{k+1}(n)=\sum_{i=1}^n f_{k}(i)=\sum_{i=1}^n {i+k-1 \choose k} = {n+k \choose k+1}$$ by (1). Now, it is clear that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j) = \sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j}.$$ So, we only have to prove that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j}=F_n,$$ where $F_n$ is the $n$-th Fibonacci number. This can be done by induction on $n$. For $n=1$ and $n=2$ is obvious. Suppose that the equality holds for every $m$ such that $1 \leq m \leq n$. Since $\lfloor \frac{n-1}{2} \rfloor + 1 = \lfloor \frac{n+1}{2} \rfloor$, we have
$$\begin{array}{lll} F_{n-1}+F_{n} & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} {n-j-2 \choose j} + \sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j} \\ & = & \displaystyle {n-1 \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2} \rfloor}\left[{n-j-1 \choose j-1} + {n-j-1 \choose j}\right] \\ & = & \displaystyle
{n \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2} \rfloor} {n-j \choose j} \\ & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n+1}{2} \rfloor} {n-j \choose j} = F_{n+1}, \end{array}$$ as we wanted to prove.
Let $f_0(i)=1$ for all $i \in \mathbb{N}$ and let $f_k(n)=\displaystyle \sum_{i=1}^n f_{k-1}(i)$ for $k \geq 1$. Prove that
$$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j)=F_n,$$ where $F_n$ is the $n$-th Fibonacci number.
Proposed by Ivan Borsenco.
Solution:
First we show that if $n,k \geq 1$, then
\begin{equation}\label{identity1}
\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}. \qquad (1)
\end{equation}
By Pascal's Identity,
$$\begin{array}{lll} \displaystyle \sum_{i=k}^{n} {i \choose k} & = & \displaystyle {k \choose k+1} + \sum_{i=k}^{n} {i \choose k}\\
& = & \displaystyle {k+1 \choose k+1} + \sum_{i=k+1}^{n} {i \choose k} \\ & = & \displaystyle {k+2 \choose k+1} + \sum_{i=k+2}^{n} {i \choose k} \\ & = & \displaystyle \vdots \\ & = & \displaystyle {n+1 \choose k+1}. \end{array}$$
Now, we prove by induction on $k \geq 1$ that $f_k(n)=\displaystyle {n+k-1 \choose k}$ for any $n \in \mathbb{N}$.
For $k=1$ we have $f_1(n)=\displaystyle \sum_{i=1}^n f_{0}(i)=n$, so the equality holds. Suppose that the equality is true for $k$. Then
$$f_{k+1}(n)=\sum_{i=1}^n f_{k}(i)=\sum_{i=1}^n {i+k-1 \choose k} = {n+k \choose k+1}$$ by (1). Now, it is clear that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j) = \sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j}.$$ So, we only have to prove that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j}=F_n,$$ where $F_n$ is the $n$-th Fibonacci number. This can be done by induction on $n$. For $n=1$ and $n=2$ is obvious. Suppose that the equality holds for every $m$ such that $1 \leq m \leq n$. Since $\lfloor \frac{n-1}{2} \rfloor + 1 = \lfloor \frac{n+1}{2} \rfloor$, we have
$$\begin{array}{lll} F_{n-1}+F_{n} & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} {n-j-2 \choose j} + \sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} {n-j-1 \choose j} \\ & = & \displaystyle {n-1 \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2} \rfloor}\left[{n-j-1 \choose j-1} + {n-j-1 \choose j}\right] \\ & = & \displaystyle
{n \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2} \rfloor} {n-j \choose j} \\ & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n+1}{2} \rfloor} {n-j \choose j} = F_{n+1}, \end{array}$$ as we wanted to prove.
Mathematical Reflections 2011, Issue 6 - Problem O211
Problem:
Prove that for any positive integer $n$ the number $(2^n+4^n)^2+4(6^n+9^n+12^n)$ has at least $9$ positive divisors.
Solution:
Rewriting,
$$(2^n+4^n)^2+4\cdot3^n(2^n+4^n)+4\cdot9^n = (2^n+4^n+2\cdot3^n)^2 = 2^2(2^{n-1}+2^{2n-1}+3^n)^2.$$ Since $4$ has three positive divisors and $2^{n-1}+2^{2n-1}+3^n \neq 2^k, k \in \mathbb{N}$ for every positive integer $n$, then $2^{n-1}+2^{2n-1}+3^n$ has one prime divisor $p > 2$. So, there are at least $3 \cdot 3 = 9$ positive divisors for the given number, namely $$\{1,2,4,p,2p,4p,p^2,2p^2,4p^2\}.$$
Prove that for any positive integer $n$ the number $(2^n+4^n)^2+4(6^n+9^n+12^n)$ has at least $9$ positive divisors.
Proposed by Titu Andreescu.
Solution:
Rewriting,
$$(2^n+4^n)^2+4\cdot3^n(2^n+4^n)+4\cdot9^n = (2^n+4^n+2\cdot3^n)^2 = 2^2(2^{n-1}+2^{2n-1}+3^n)^2.$$ Since $4$ has three positive divisors and $2^{n-1}+2^{2n-1}+3^n \neq 2^k, k \in \mathbb{N}$ for every positive integer $n$, then $2^{n-1}+2^{2n-1}+3^n$ has one prime divisor $p > 2$. So, there are at least $3 \cdot 3 = 9$ positive divisors for the given number, namely $$\{1,2,4,p,2p,4p,p^2,2p^2,4p^2\}.$$
Mathematical Reflections 2011, Issue 6 - Problem U212
Problem:
Let $G$ be a finite abelian group such that $G$ contains a subgroup $K \neq \{e\}$ with the
property that $K \subset H$ for each subgroup $H$ of $G$ such that $H \neq \{e\}$. Prove that $G$ is a
cyclic group.
Let $G$ be a finite abelian group such that $G$ contains a subgroup $K \neq \{e\}$ with the
property that $K \subset H$ for each subgroup $H$ of $G$ such that $H \neq \{e\}$. Prove that $G$ is a
cyclic group.
Proposed by Daniel Lopez Aguayo.
Solution:
We use the following
Lemma.
A finite abelian group is not cyclic if and only if it contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ for some prime $p$.
A finite abelian group is not cyclic if and only if it contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ for some prime $p$.
Proof.
Let $G$ be a finite abelian group. If $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ (which is not cyclic) then $G$ can't be cyclic since every subgroup of a cyclic group is cyclic. Conversely, if $G$ is a finite abelian group which is not cyclic then (by Fundamental Theorem of Finitely Generated Abelian Groups) $G$ contains a subgroup isomorphic to $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$, because if all the components in the direct product correspond to distinct primes, then $G$ would be cyclic. So, the subgroup $(p^{a-1}) \times (p^{b-1})$ of $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$ is isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$.
Let $G$ be a finite abelian group. If $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ (which is not cyclic) then $G$ can't be cyclic since every subgroup of a cyclic group is cyclic. Conversely, if $G$ is a finite abelian group which is not cyclic then (by Fundamental Theorem of Finitely Generated Abelian Groups) $G$ contains a subgroup isomorphic to $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$, because if all the components in the direct product correspond to distinct primes, then $G$ would be cyclic. So, the subgroup $(p^{a-1}) \times (p^{b-1})$ of $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$ is isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$.
Now, suppose that $G$ is not a cyclic group. Then $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ and this subgroup, by Cauchy's Theorem, contains a subgroup $H$ which is isomorphic to $\mathbb{Z}_p$. If $K \neq \{e\}$ is a proper subgroup of $H$, then, by Lagrange's Theorem, $|K|$ divides $|H|$, i.e. $|K|$ divides $p$. So $K=\{e\}$ or $K=H$, contradiction.
Mathematical Reflections 2011, Issue 6 - Problem U211
Problem:
On the set $M=\mathbb{R}-\{3\}$ the following binary law is defined:
$$x \ast y = 3(xy-3x-3y)+m,$$ where $m \in \mathbb{R}$. Find all possible values of $m$ such that $(M, \ast)$ is a group.
On the set $M=\mathbb{R}-\{3\}$ the following binary law is defined:
$$x \ast y = 3(xy-3x-3y)+m,$$ where $m \in \mathbb{R}$. Find all possible values of $m$ such that $(M, \ast)$ is a group.
Proposed by Bogdan Enescu.
Solution:
First we observe that $x \ast y = 3(x-3)(y-3)+m-27$.
We want that $\ast$ satisfies the group axioms.
(i) Closure: For every $x,y \in M$, $x \ast y \in M$. It must be $3(x-3)(y-3)+m-27 \neq 3$, i.e. $3(x-3)(y-3)+m \neq 30$ and this is clearly satisfied for $m=30$.
(ii) Associativity: For every $x,y,z \in M, (x \ast y) \ast z = x \ast (y \ast z)$. It must be
$$\begin{array}{lll} [3(x-3)(y-3)+m-27] \ast z = 3[(3(x-3)(y-3)+m-27)-3][z-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3(27x+27y+(m-3)z)-8m \end{array}$$
and
$$\begin{array}{lll} x \ast [3(y-3)(z-3)+m-27] = 3(x-3)[3(y-3)(z-3)+m-27-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3((m-3)x+27y+27z)-8m, \end{array}$$
so the associativity holds if and only if $m=30$.
(iii) Identity element: There exists $e \in M$ such that for every $x \in M$, $x \ast e = e \ast x = x$. It must be
$$3(x-3)(e-3)+3=x \iff 3e(x-3)=10(x-3) \iff e=\dfrac{10}{3}.$$
(iv) Inverse element: For each $x \in M$, there exists $y \in M$ such that $x \ast y = y \ast x = e$. It must be
$$3(x-3)(y-3)+3=\dfrac{10}{3} \iff (x-3)(y-3)=\dfrac{1}{9} \iff y=\dfrac{1}{9(x-3)}+3.$$
So $(M,\ast)$ is a group if and only if $m=30$.
We want that $\ast$ satisfies the group axioms.
(i) Closure: For every $x,y \in M$, $x \ast y \in M$. It must be $3(x-3)(y-3)+m-27 \neq 3$, i.e. $3(x-3)(y-3)+m \neq 30$ and this is clearly satisfied for $m=30$.
(ii) Associativity: For every $x,y,z \in M, (x \ast y) \ast z = x \ast (y \ast z)$. It must be
$$\begin{array}{lll} [3(x-3)(y-3)+m-27] \ast z = 3[(3(x-3)(y-3)+m-27)-3][z-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3(27x+27y+(m-3)z)-8m \end{array}$$
and
$$\begin{array}{lll} x \ast [3(y-3)(z-3)+m-27] = 3(x-3)[3(y-3)(z-3)+m-27-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3((m-3)x+27y+27z)-8m, \end{array}$$
so the associativity holds if and only if $m=30$.
(iii) Identity element: There exists $e \in M$ such that for every $x \in M$, $x \ast e = e \ast x = x$. It must be
$$3(x-3)(e-3)+3=x \iff 3e(x-3)=10(x-3) \iff e=\dfrac{10}{3}.$$
(iv) Inverse element: For each $x \in M$, there exists $y \in M$ such that $x \ast y = y \ast x = e$. It must be
$$3(x-3)(y-3)+3=\dfrac{10}{3} \iff (x-3)(y-3)=\dfrac{1}{9} \iff y=\dfrac{1}{9(x-3)}+3.$$
So $(M,\ast)$ is a group if and only if $m=30$.
Mathematical Reflections 2011, Issue 6 - Problem S213
Problem:
Let $a,b,c$ be positive real numbers such that $a^2 \geq b^2+bc+c^2$. Prove that
$$a > \min(b,c) + \dfrac{|b^2-c^2|}{a}.$$
Solution:
Without loss of generality, suppose that $\min(b,c)=c$. If $a \geq b+c$, then
$$a^2-ac \geq ab > (b+c)(b-c)=b^2-c^2.$$ If $a<b+c$, then
$$a^2-ac > a^2-(b+c)c \geq b^2 > b^2-c^2.$$ So, for any $a,b,c$ satisfying the required conditions, we have $a > \min(b,c) + \dfrac{|b^2-c^2|}{a}$.
Let $a,b,c$ be positive real numbers such that $a^2 \geq b^2+bc+c^2$. Prove that
$$a > \min(b,c) + \dfrac{|b^2-c^2|}{a}.$$
Proposed by Titu Andreescu.
Solution:
Without loss of generality, suppose that $\min(b,c)=c$. If $a \geq b+c$, then
$$a^2-ac \geq ab > (b+c)(b-c)=b^2-c^2.$$ If $a<b+c$, then
$$a^2-ac > a^2-(b+c)c \geq b^2 > b^2-c^2.$$ So, for any $a,b,c$ satisfying the required conditions, we have $a > \min(b,c) + \dfrac{|b^2-c^2|}{a}$.
Mathematical Reflections 2011, Issue 6 - Problem J215
Problem:
Prove that for any prime $p>3$, $\dfrac{p^6-7}{3}+2p^2$ can be written as sum of two perfect cubes.
Prove that for any prime $p>3$, $\dfrac{p^6-7}{3}+2p^2$ can be written as sum of two perfect cubes.
Proposed by Titu Andreescu.
Solution:
We have
$$\begin{array}{lll} \dfrac{p^6-7}{3}+2p^2 & = & \dfrac{p^6+6p^2-7}{3}\\ & = & \dfrac{9p^6+54p^2-63}{27}\\
& = & \dfrac{(p^6-12p^4+48p^2-64)+(8p^6+12p^4+6p^2+1)}{27} \\ & = & \left(\dfrac{p^2-4}{3}\right)^3 + \left(\dfrac{2p^2+1}{3}\right)^3\end{array}$$ and it is clear that the two summands on the right hand side are integers, since if $p > 3$, $p^2 \equiv 1 \pmod 3$.
$$\begin{array}{lll} \dfrac{p^6-7}{3}+2p^2 & = & \dfrac{p^6+6p^2-7}{3}\\ & = & \dfrac{9p^6+54p^2-63}{27}\\
& = & \dfrac{(p^6-12p^4+48p^2-64)+(8p^6+12p^4+6p^2+1)}{27} \\ & = & \left(\dfrac{p^2-4}{3}\right)^3 + \left(\dfrac{2p^2+1}{3}\right)^3\end{array}$$ and it is clear that the two summands on the right hand side are integers, since if $p > 3$, $p^2 \equiv 1 \pmod 3$.
Mathematical Reflections 2011, Issue 6 - Problem J214
Problem:
Let $a,b,c,d,e \in [1,2]$. Prove that
$$ab+bc+cd+de+ea \geq a^2+b^2+c^2+d^2-e^2.$$
Let $a,b,c,d,e \in [1,2]$. Prove that
$$ab+bc+cd+de+ea \geq a^2+b^2+c^2+d^2-e^2.$$
Proposed by Ion Dobrota and Adrian Zahariuc.
Solution:
It is equivalent to prove that given $a,b,c,d,e \in [1,2]$, the following inequality holds
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq 4e^2.$$
Clearly,
$$(a-b)^2 \leq 1, \qquad (b-c)^2 \leq 1, \qquad (c-d)^2 \leq 1, \qquad (d-e)^2 \leq 1, \qquad (e-a)^2 \leq 1,$$
so
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq |a-b|+|b-c|+|c-d|+|d-e|+|e-a|.$$
The right hand side is maximum if and only if there is only one term which cancels out when removing the absolute values. Without loss of generality, we can suppose that $b$ cancels out, so
$$|a-b|+|b-c|+|c-d|+|d-e|+|e-a| \leq 2(a+d)-2(c+e) \leq 4 \leq 4e^2,$$
and the desired conclusion follows. From the made observations, we have four cases for the equality:
(i) If $a$ cancels out, then $(b-a)+(b-c)+(d-c)+(d-1)+(a-1)=2(b+d)-2c-2=4 \iff 4 \leq b+d \iff b=d=2, c=1$, and $a=1,2$.
(ii) If $b$ cancels out, then $(a-b)+(b-c)+(d-c)+(d-1)+(a-1)=2(a+d)-2c-2=4 \iff 4 \leq a+d \iff a=d=2, c=1$, and $b=1,2$.
(iii) If $c$ cancels out, then $(a-b)+(c-b)+(d-c)+(d-1)+(a-1)=2(a+d)-2b-2=4 \iff 4 \leq a+d \iff a=d=2, b=1$, and $c=1,2$.
(iv) If $d$ cancels out, then $(a-b)+(c-b)+(c-d)+(d-1)+(a-1)=2(a+c)-2b-2=4 \iff 4 \leq a+c \iff a=c=2, b=1$, and $d=1,2$.
In conclusion, the equality can be obtained if $e=1$ and occurs if and only if $$(a,b,c,d,e) \in \{(1,2,1,2,1),(2,2,1,2,1),(2,1,1,2,1),(2,1,2,2,1),(2,1,2,1,1)\}.$$
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq 4e^2.$$
Clearly,
$$(a-b)^2 \leq 1, \qquad (b-c)^2 \leq 1, \qquad (c-d)^2 \leq 1, \qquad (d-e)^2 \leq 1, \qquad (e-a)^2 \leq 1,$$
so
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq |a-b|+|b-c|+|c-d|+|d-e|+|e-a|.$$
The right hand side is maximum if and only if there is only one term which cancels out when removing the absolute values. Without loss of generality, we can suppose that $b$ cancels out, so
$$|a-b|+|b-c|+|c-d|+|d-e|+|e-a| \leq 2(a+d)-2(c+e) \leq 4 \leq 4e^2,$$
and the desired conclusion follows. From the made observations, we have four cases for the equality:
(i) If $a$ cancels out, then $(b-a)+(b-c)+(d-c)+(d-1)+(a-1)=2(b+d)-2c-2=4 \iff 4 \leq b+d \iff b=d=2, c=1$, and $a=1,2$.
(ii) If $b$ cancels out, then $(a-b)+(b-c)+(d-c)+(d-1)+(a-1)=2(a+d)-2c-2=4 \iff 4 \leq a+d \iff a=d=2, c=1$, and $b=1,2$.
(iii) If $c$ cancels out, then $(a-b)+(c-b)+(d-c)+(d-1)+(a-1)=2(a+d)-2b-2=4 \iff 4 \leq a+d \iff a=d=2, b=1$, and $c=1,2$.
(iv) If $d$ cancels out, then $(a-b)+(c-b)+(c-d)+(d-1)+(a-1)=2(a+c)-2b-2=4 \iff 4 \leq a+c \iff a=c=2, b=1$, and $d=1,2$.
In conclusion, the equality can be obtained if $e=1$ and occurs if and only if $$(a,b,c,d,e) \in \{(1,2,1,2,1),(2,2,1,2,1),(2,1,1,2,1),(2,1,2,2,1),(2,1,2,1,1)\}.$$
Mathematical Reflections 2011, Issue 6 - Problem J213
Problem:
For any positive integer $n$, let $S(n)$ denote the sum of digits in its decimal representation.
Prove that the set of all positive integers $n$ such that $n$ is not divisible by $10$ and $S(n) >
S(n^2 + 2012)$ is infinite.
For any positive integer $n$, let $S(n)$ denote the sum of digits in its decimal representation.
Prove that the set of all positive integers $n$ such that $n$ is not divisible by $10$ and $S(n) >
S(n^2 + 2012)$ is infinite.
Proposed by Preudtanan Sriwongleang.
Solution:
With the notation introduced, let $A = \{ n \in \mathbb{N} : n \neq 10k \textrm{ and } S(n) > S(n^2+2012), k \in \mathbb{N}\}$. We prove that $A \supset \{5\cdot10^{m}-1, m \in \mathbb{N}\setminus\{0\}\} = \{49,499,\ldots,4\underbrace{9\ldots9}_{m},\ldots\}$, so that $A$ must be infinite. Clearly, $49,499 \in A$, since
$$49 \neq 10k, k \in \mathbb{N}, \qquad S(49)=13 > 12=S(4413)$$ and
$$499 \neq 10k, k \in \mathbb{N}, \qquad S(499)=22 > 12=S(251013).$$
Let $m > 2$. Then $5\cdot10^m-1 \neq 10k, k \in \mathbb{N}$ and $$(5\cdot 10^m - 1)^2+2012=25\cdot10^{2m}-10^{m+1}+2013=24\underbrace{9\ldots9}_{m-1}\underbrace{0\ldots0}_{m+1} + 2013,$$
from which $$S((5\cdot10^m-1)^2+2012)=2+4+9(m-1)+2+1+3=9m+3.$$
Therefore, $S(5\cdot10^m-1)=9m+4 > 9m+3=S((5\cdot10^m-1)^2+2012)$, i.e. $$5\cdot10^m-1 \in A \qquad \forall m \in \mathbb{N}\setminus\{0\},$$ which gives the desired conclusion.
$$49 \neq 10k, k \in \mathbb{N}, \qquad S(49)=13 > 12=S(4413)$$ and
$$499 \neq 10k, k \in \mathbb{N}, \qquad S(499)=22 > 12=S(251013).$$
Let $m > 2$. Then $5\cdot10^m-1 \neq 10k, k \in \mathbb{N}$ and $$(5\cdot 10^m - 1)^2+2012=25\cdot10^{2m}-10^{m+1}+2013=24\underbrace{9\ldots9}_{m-1}\underbrace{0\ldots0}_{m+1} + 2013,$$
from which $$S((5\cdot10^m-1)^2+2012)=2+4+9(m-1)+2+1+3=9m+3.$$
Therefore, $S(5\cdot10^m-1)=9m+4 > 9m+3=S((5\cdot10^m-1)^2+2012)$, i.e. $$5\cdot10^m-1 \in A \qquad \forall m \in \mathbb{N}\setminus\{0\},$$ which gives the desired conclusion.
Mathematical Reflections 2011, Issue 6 - Problem J212
Problem:
Solve in real numbers the system of equations
$$\begin{array}{lll} (x-2y)(x-4z)=6 \\ (y-2z)(y-4x)=10 \\ (z-2x)(z-4y)=-16. \end{array}$$
Solve in real numbers the system of equations
$$\begin{array}{lll} (x-2y)(x-4z)=6 \\ (y-2z)(y-4x)=10 \\ (z-2x)(z-4y)=-16. \end{array}$$
Proposed by Titu Andreescu.
Solution:
Rewriting the equations, we have
$$\begin{array}{lll} x^2-2xy+8yz-4zx=6 \\ y^2-4xy-2yz+8zx=10 \\ z^2+8xy-4yz-2zx=-16. \end{array}$$
and summing up the equations we obtain $(x+y+z)^2=0$, i.e. $x+y+z=0$. Putting $z=-x-y$, and substituting into the first two equations, we have
$$\begin{array}{lll} 5x^2-6xy-8y^2=6 \\ 3y^2-10xy-8x^2=10,\end{array}$$ so $5(5x^2-6xy-8y^2)-3(3y^2-10xy-8x^2)=49(x^2-y^2)=0$, which gives $y=\pm x$. If $y=x$, the first equation yields $-9x^2=6$, so no real solutions. If $y=-x$, the first equations yields $3x^2=6$, so $x=\pm \sqrt{2}$ and $y=\mp \sqrt{2}$. Therefore, the real solutions are $(\sqrt{2},-\sqrt{2},0)$ and $(-\sqrt{2},\sqrt{2},0)$.
$$\begin{array}{lll} x^2-2xy+8yz-4zx=6 \\ y^2-4xy-2yz+8zx=10 \\ z^2+8xy-4yz-2zx=-16. \end{array}$$
and summing up the equations we obtain $(x+y+z)^2=0$, i.e. $x+y+z=0$. Putting $z=-x-y$, and substituting into the first two equations, we have
$$\begin{array}{lll} 5x^2-6xy-8y^2=6 \\ 3y^2-10xy-8x^2=10,\end{array}$$ so $5(5x^2-6xy-8y^2)-3(3y^2-10xy-8x^2)=49(x^2-y^2)=0$, which gives $y=\pm x$. If $y=x$, the first equation yields $-9x^2=6$, so no real solutions. If $y=-x$, the first equations yields $3x^2=6$, so $x=\pm \sqrt{2}$ and $y=\mp \sqrt{2}$. Therefore, the real solutions are $(\sqrt{2},-\sqrt{2},0)$ and $(-\sqrt{2},\sqrt{2},0)$.
Subscribe to:
Posts (Atom)