Showing posts with label Mathematical Reflections. Show all posts
Showing posts with label Mathematical Reflections. Show all posts

Friday, February 16, 2018

Mathematical Reflections 2017, Issue 6 - Problem U429

Problem:
Let $n \geq 2$ and let $A$ be a $n \times n$ matrix with positive real entries. Do there exist a $n \times n$ matrix $X$ with $(n-1)^2$ zero entries and a diagonal matrix $D$ such that $AX=D$?

Proposed by Alessandro Ventullo, Milan, Italy


Solution:
Assume that there exist a $n \times n$ matrix $X$ with $(n-1)^2$ zero entries and a diagonal matrix $D$ such that $AX=D$.
Observe that $$\det(A)\det(X)=\det(D) \neq 0,$$ so in partcular $\det X \neq 0$.
Now, $X$ has $n^2-(n-1)^2=2n-1$ nonzero entries. Since $X$ has $n$ columns, then $X$ has at least one column with at most one nonzero entry. But $\det X \neq 0$, so $X$ has at least one column with exactly one nonzero entry, say the $k$-th column. Denote by $a_{ij}$, $x_{ij}$ and $d_{ij}$ the elements of $A$, $X$ and $D$, respectively. Then, $x_{hk} \neq 0$ for some $h$ and $x_{ik}=0$ for all $i \neq h$. Hence, for $m \neq k$ we have
$$0=d_{mk}=\sum_{i=1}^n a_{mi}x_{ik}=a_{mh}x_{hk},$$ contradiction. The conclusion follows.

Mathematical Reflections 2017, Issue 6 - Problem U427

Problem:
Let $f:\mathbb{R}^2 \to \mathbb{R}$ be a function defined by $f(x,y)=\mathbf{1}_{(0,1/y)}(x)\cdot\mathbf{1}_{(0,1)}(y)\cdot y$, where $\mathbf{1}$ is the characteristic function. Evaluate
$$\int_{\mathbb{R}^2} f(x,y) \ dx \ dy.$$

Proposed by Alessandro Ventullo, Milan, Italy


Solution:
Since $f$ is clearly non-negative, by Tonelli's Theorem we can evaluate the double integral as iterated integrals, i.e.
$$\int_{\mathbb{R}^2} f(x,y) \ dx \ dy=\int_{\mathbb{R}} \left(\int_{\mathbb{R}} f(x,y) \ dy\right) \ dx.$$
Observe that
$$\renewcommand{\arraystretch}{2}\begin{array}{lll} \displaystyle \int_{\mathbb{R}} f(x,y) \ dy&=& \displaystyle \int_{\mathbb{R}} \mathbf{1}_{(0,1/y)}(x)\cdot\mathbf{1}_{(0,1)}(y)\cdot y \ dy\\&=& \displaystyle \int_{\mathbb{R}} \mathbf{1}_{(0,1/x)}(y)\cdot\mathbf{1}_{(0,1)}(y)\cdot y \ dy\\&=& \displaystyle \int_{\mathbb{R}} \mathbf{1}_{(0,\min(1,1/x))}(y)\cdot y \ dy. \end{array}$$
Since $$\mathbf{1}_{(0,\min(1,1/x))}(y)=\begin{cases} \mathbf{1}_{(0,1)}(y) & \textrm{if } 0 < x \leq 1 \\ \mathbf{1}_{(0,1/x)}(y) & \textrm{if } x > 1, \end{cases}$$
it follows that $$\int_{\mathbb{R}} \mathbf{1}_{(0,\min(1,1/x))}(y)\cdot y \ dy = \begin{cases} 1/2 & \textrm{if } 0 < x \leq 1 \\ 1/(2x^2) & \textrm{if } x > 1. \end{cases}.$$
So, $$\int_{\mathbb{R}^2} f(x,y) \ dx \ dy=\int_0^1 \dfrac{1}{2} \ dx+\int_{1}^{\infty} \dfrac{1}{2x^2} \ dx=1.$$

Mathematical Reflections 2017, Issue 5 - Problem O422

Problem:
Let $P(x)$ be a polynomial with integer coefficients having an integer root $k$ and $P(0) \neq 0$. Prove that if $p$ and $q$ are distinct odd primes such that $P(p)=p<2q-1$ and $P(q)=q<2p-1$, then $p$ and $q$ are twin primes.

Proposed by Alessandro Ventullo, Milan, Italy


Solution:
Assume that $k \in \mathbb{Z}$ is a root of the polynomial with integer coefficients $P$. So, $P(k)=0$, which gives $P(x)=(x-k)Q(x)$ for some polynomial with integer coefficients $Q(x)$. Hence,
$$p=P(p)=(p-k)Q(p), \qquad q=P(q)=(q-k)Q(q).$$ It follows that $(p-k) \mid p$ and $(q-k) \mid q$, so $p-k \in \{\pm 1, -p\}$ and $q-k \in \{\pm 1, -q\}$. Since $p$ and $q$ are distinct primes, then $p-k \neq q-k$ and we have seven cases.

(i) $p-k=-1$ and $q-k=1$. It follows that $q-p=2$, i.e. $q=p+2$, so $p$ and $q$ are twin primes.

(ii) $p-k=-1$ and $q-k=-q$. It follows that $p=2q-1$, contradiction.

(iii) $p-k=1$ and $q-k=-1$. It follows that $p-q=2$, i.e. $p=q+2$, so $p$ and $q$ are twin primes.

(iv) $p-k=1$ and $q-k=-q$. It follows that $p=2q+1$, contradiction.

(v) $p-k=-p$ and $q-k=-1$. It follows that $q=2p-1$, contradiction.

(vi) $p-k=-p$ and $q-k=1$. It follows that $q=2p+1$, contradiction.

(vii) $p-k=-p$ and $q-k=-q$. It follows that $p-q=-p+q$, i.e. $p=q$, contradiction.

In conclusion, $p$ and $q$ are twin primes.

Mathematical Reflections 2017, Issue 5 - Problem U425

Problem:
Let $p$ be a prime number and let $G$ be a group of order $p^3$. Define $\Gamma(G)$ as the graph whose vertices represent the noncentral conjugacy class sizes of $G$ and two vertices are joined if and only if the two associated conjugacy class sizes are not coprime. Determine the structure of $\Gamma(G)$.

Proposed by Alessandro Ventullo, Milan, Italy


Solution:
We have two cases.

(i) $G$ is abelian. In such a case, all the conjugacy classes are central, so $\Gamma(G)$ has no vertex, i.e. $\Gamma(G)$ is the null graph.

(ii) $G$ is nonabelian. Since $Z(G)$ is a subgroup of $G$, then $|Z(G)| \ | \ |G|$. Since $G$ is nonabelian, then $|Z(G)| \neq |G|$ and since $G$ is a $p$-group, then $|Z(G)| \neq 1$. It follows that $|Z(G)| \in \{p,p^2\}$. If $|Z(G)|=p^2$, then $|G/Z(G)|=p$, so $G/Z(G)$ is cyclic and this implies that $G$ is abelian, contradiction. So, it must be $|Z(G)|=p$. Now, take a noncentral conjuacy class $\textrm{Cl}(a)$. Clearly, $|\textrm{Cl}(a)| \neq 1$. By the Orbit-Stabilizer Theorem, we have that $$|\textrm{Cl}(a)|=[G:C_G(a)],$$ where $C_G(a)$ is the centralizer of $a$ in $G$. It follows that $|\textrm{Cl}(a)| \ | \ |G|$. Since $Z(G)=\bigcap_{a \in G} C_G(a)$ and $a \in C_G(a)$, but $a \notin Z(G)$, then $Z(G) \subset C_G(a)$, which gives $|Z(G)| < |C_G(a)|$. Since $C_G(a)$ is a subgroup of $G$, then $|C_G(a)| \ | \ |G|$, which implies that $|C_G(a)|=p^2$. So, $|\textrm{Cl}(a)|=p$, i.e. each noncentral conjugacy class has size $p$, so the graph is a complete graph. In order to determine the number of its vertices, we use the Conjugacy Class Equation $$|G|=|Z(G)|+\sum_{i}[G:C_G(x_i)]$$ and we get $$p^3=p+kp,$$ i.e. $k=p^2-1$. We conclude that $\Gamma(G)=K_{p^2-1}$.

Mathematical Reflections 2017, Issue 5 - Problem S423

Problem:
Let $p$ and $q$ be prime numbers such that $p^2+pq+q^2$ is a perfect square. Prove that $p^2-pq+q^2$ is prime.

Proposed by Alessandro Ventullo, Milan, Italy


First solution:
Let $p^2+pq+q^2=n^2$. Then, $(p+q)^2=n^2+pq$ where $n \in \mathbb{N}$, which gives $$(p+q-n)(p+q+n)=pq.$$ If $p=q$, then $(2p-n)(2p+n)=p^2$. Since $2p-n<2p+n$, then $2p-n=1$ and $2p+n=p^2$, i.e. $4p=1+p^2$, which gives no integer solution. If $p \neq q$, assuming without loss of generality that $p<q$, then since $p+q-n<p+q+n$, we have
$$\begin{array}{lll} p+q-n &=& 1 \\ p+q+n &=& pq, \end{array} \qquad \begin{array}{lll} p+q-n &=& p \\ p+q+n &=& q. \end{array}$$
The first system gives $2(p+q)=pq+1$, i.e. $(p-2)(q-2)=3$, which gives $p=3, q=5$. The second equation of the second system gives $p+n=0$, contradiction. So, we get $(p,q) \in \{(3,5),(5,3)\}$ and $p^2-pq+q^2=19$, which is prime.

Second solution:
Observe that $p^2<p^2+pq+q^2<(p+q)^2$ for all primes $p,q$. Hence, $$p^2+pq+q^2=(p+k)^2,$$ where $k \in \{1,2,\ldots,q-1\}$, i.e. $$pq+q^2=2kp+k^2.$$ We get
$$
p(2k-q)=(q-k)(q+k) \qquad (1)
$$
Since the right-hand side is positive, it follows that $q<2k$. Moreover, since $p$ is prime, then $p \ | \ (q-k)$ or $p \ | \ (q+k)$.

(i) If $p \ | \ (q-k)$, then $q-k=ph$ for some $h \in \mathbb{N}$, so equation (1) becomes $$2k-q=h(k+q).$$ It follows that $(k+q) \ | \ (2k-q)$. Since $2k-q=2(k+q)-3q$, then $(k+q) \ | \ 3q$. If $q=3$, there is no solution. If $q \neq 3$, we have $k+q \in \{1,3,q,3q\}$. But $1<q<k+q<2q<3q$, so it must be $k+q=3$. Since $q$ is prime, this gives $q=2$ and $k=1$, but this would imply that $p \ | \ 1$, contradiction.

(ii) If $p \ | \ (q+k)$, then $q+k=ph$ for some $h \in \mathbb{N}$, so equation (1) becomes $$2k-q=h(q-k).$$ It follows that $(q-k) \ | \ (2k-q)$. Since $2k-q=2(k-q)+q$, then $(q-k) \ | \ q$. But $q-k<q$, so $q-k=1$. Equation \eqref{first-eq} becomes $$p(q-2)=2q-1,$$ which implies $(q-2) \ | \ (2q-1)=[2(q-2)+3]$, i.e. $(q-2) \ | \ 3$. So, $q=3$ or $q=5$, which gives $p=5$ or $p=3$ respectively.

Therefore, $(p,q) \in \{(3,5),(5,3)\}$, which gives $p^2-pq+q^2=19$, which is prime.

Conjecture:
Let $k$ be a positive integer such that if $p^2+kpq+q^2$ is a perfect square, then $p^2-kpq+q^2$ is a prime. Then, $k=1$. Me and Robert Bosch tried to disprove this conjecture with Maple for small $k$, but it seems that $k$ is the only positive integer with this property.

Mathematical Reflections 2017, Issue 5 - Problem S422

Problem:
Solve in positive integers the equation $$u^2+v^2+x^2+y^2+z^2=uv+vx-xy+yz+zu+3.$$

Proposed by Proposed by Adrian Andreescu, Dallas, USA


Solution:
The given equation can be written as $$(u-v)^2+(v-x)^2+(x+y)^2+(y-z)^2+(z-u)^2=6.$$
Since $u,v,x,y,z$ are positive integers, then $x+y \geq 2$, which gives $(x+y)^2 \geq 4$. Since $(x+y)^2 \leq 6$, we conclude that $x+y=2$, so $x=y=1$ and
$$(u-v)^2+(v-1)^2+(1-z)^2+(z-u)^2=2.$$
So, exactly two of the summands on the LHS are equal to $1$ and the other are equal to $0$. We have six cases.

(i) $(u-v)^2=(v-1)^2=1$ and $(1-z)^2=(z-u)^2=0$. From the last equations we get $u=z=1$ and from the first equations we get $v=2$.

(ii) $(u-v)^2=(1-z)^2=1$ and $(v-1)^2=(z-u)^2=0$. From the last equations we get $v=1$ and $u=z$ and from the first equations we get $u=z=2$.

(iii) $(u-v)^2=(z-u)^2=1$ and $(v-1)^2=(1-z)^2=0$. From the last equations we get $v=z=1$ and from the first equations we get $u=2$.

(iv) $(v-1)^2=(1-z)^2=1$ and $(u-v)^2=(z-u)^2=0$. From the last equations we get $u=v=z$ and from the first equations we get $u=v=z=2$.

(v) $(v-1)^2=(z-u)^2=1$ and $(u-v)^2=(1-z)^2=0$. From the last equations we get $u=v$ and $z=1$ and from the first equations we get $u=v=2$.

(vi) $(1-z)^2=(z-u)^2=1$ and $(u-v)^2=(v-1)^2=0$. From the last equations we get $u=v=1$ and from the first equations we get $z=2$.

In conclusion, $$(u,v,x,y,z) \in \{(1,2,1,1,1),(2,1,1,1,2),(2,1,1,1,1),(2,2,1,1,2),(2,2,1,1,1),(1,1,1,1,2)\}.$$

Mathematical Reflections 2017, Issue 5 - Problem S421

Problem:
Let $a,b,c$ be positive numbers such that $abc=1$. Prove that $$\dfrac{a^2}{\sqrt{1+a}}+\dfrac{b^2}{\sqrt{1+b}}+\dfrac{c^2}{\sqrt{1+c}} \geq 2.$$

Proposed by Constantinos Metaxas, Athens, Greece


Solution:
We prove the stronger inequality $$\dfrac{a^2}{\sqrt{1+a}}+\dfrac{b^2}{\sqrt{1+b}}+\dfrac{c^2}{\sqrt{1+c}} \geq \dfrac{3}{\sqrt{2}}.$$
Let $f(x)=\dfrac{x^2}{\sqrt{1+x}}$. Since $f''(x)=\dfrac{3x^2+8x+8}{4(x+1)^2\sqrt{x+1}}$, then $f''(x)>0$ for all $x>0$, so $f$ is convex on $(0,+\infty)$. By Jensen's Inequality, we have
$$f\left(\dfrac{a+b+c}{3}\right) \leq \dfrac{f(a)+f(b)+f(c)}{3},$$ i.e.
$$\dfrac{a^2}{\sqrt{1+a}}+\dfrac{b^2}{\sqrt{1+b}}+\dfrac{c^2}{\sqrt{1+c}} \geq 3\cdot \dfrac{\left(\frac{a+b+c}{3}\right)^2}{\sqrt{1+\frac{a+b+c}{3}}}=\dfrac{(a+b+c)^2}{\sqrt{9+3(a+b+c)}}.$$
By the AM-GM Inequality, we have $a+b+c \geq 3\sqrt[3]{abc}=3$. Set $x=a+b+c$. Observe that the function $g(x)=\dfrac{x^2}{\sqrt{9+3x}}$ is increasing on $[3,+\infty)$, so $g(x) \geq g(3)=\dfrac{3}{\sqrt{2}}$ and the conclusion follows.

Mathematical Reflections 2017, Issue 5 - Problem J421

Problem:
Let $a$ and $b$ be positive real numbers. Prove that $$\dfrac{6ab-b^2}{8a^2+b^2}<\sqrt{\dfrac{a}{b}}.$$

Proposed by Adrian Andreescu, Dallas, USA


Solution:
Let $x=\dfrac{a}{b}$. Clearly, $x>0$. The given equality is equivalent to
$$\dfrac{6x-1}{8x^2+1}<\sqrt{x},$$ i.e. $$8x^2\sqrt{x}+\sqrt{x}+1>6x,$$ which is true by the AM-GM Inequality.

Wednesday, November 1, 2017

Mathematical Reflections 2017, Issue 4 - Problem S416

Problem:
Let $f:\mathbb{N} \to \{\pm 1\}$ be a function such that $f(mn)=f(m)f(n)$ for all $m,n \in \mathbb{N}$. Prove that
there are infinitely many $n$ such that $f(n)=f(n+1)$.

Proposed by Oleksi Klurman, University College London, UK


Solution:
Let $n \in \mathbb{N}$. As $f$ is completely multiplicative, then $f(n^2)=(f(n))^2=1$. If there are infinitely many $n$ such that $f(n^2-1)=1$, we are done. So, assume that there are only finitely many $n$ such that $f(n^2-1)=1$. Then, there are infinitely many $n$ such that $f(n^2-1)=-1$. Since $f(n^2-1)=f(n-1)f(n+1)$, then there are infinitely many pairs $\{f(n-1),f(n+1)\}=\{-1,1\}$. Since $f(n)=\pm 1$, it follows that there are infinitely many $n$ such that $f(n)=f(n+1)$.

Mathematical Reflections 2017, Issue 4 - Problem S415

Problem:
Let $$f(x)=\dfrac{(2x-1)6^x}{2^{2x-1}+3^{2x-1}}.$$
Evaluate $$f\left(\dfrac{1}{2018}\right)+f\left(\dfrac{3}{2018}\right)+\ldots+f\left(\dfrac{2017}{2018}\right).$$

Proposed by Titu Andreescu, University of Texas at Dallas, USA


Solution:
Observe that $$f(1-x)=\dfrac{(1-2x)6^{1-x}}{2^{1-2x}+3^{1-2x}}=\dfrac{(1-2x)6^x}{2^{2x-1}+3^{2x-1}}=-f(x),$$ i.e. $f(x)+f(1-x)=0$.
So,
\begin{eqnarray*}
\sum_{k=1}^{1009} f\left(\dfrac{2k-1}{2018}\right)&=&\sum_{k=1}^{504}\left(f\left(\dfrac{2k-1}{2018}\right)+f\left(\dfrac{2018-(2k-1)}{2018}\right)\right)+f\left(\dfrac{1009}{2018}\right)\\&=&f\left(\dfrac{1009}{2018}\right)\\&=&f\left(\dfrac{1}{2}\right)\\&=&0.
\end{eqnarray*}

Mathematical Reflections 2017, Issue 4 - Problem J417

Problem:
Solve in positive real numbers the equation $$\dfrac{x^2+y^2}{1+xy}=\sqrt{2-\dfrac{1}{xy}}.$$

Proposed by Adrian Andreescu, Dallas, Texas, USA


Solution:
Let $s=x+y$ and $p=xy$. Then, the given equation can be written as $$\dfrac{s^2-2p}{1+p}=\sqrt{2-\dfrac{1}{p}}.$$
By the AM-GM Inequality, we have $s^2-2p \geq 2p$, so $$\sqrt{2-\dfrac{1}{p}} \geq \dfrac{2p}{1+p} \iff \dfrac{(p-1)^2(2p+1)}{p(p+1)^2} \leq 0.$$ Since $p \geq 0$, it follows that $p=1$, which gives $s=2$. So, $x+y=2$ and $xy=1$, which yields $(x,y)=(1,1)$.

Mathematical Reflections 2017, Issue 4 - Problem J415

Problem:
Prove that for all real numbers $x,y,z$ at least one of the numbers
$$2^{3x-y}+2^{3x-z}-2^{y+z+1}$$ $$2^{3y-z}+2^{3y-x}-2^{z+x+1}$$ $$2^{3z-x}+2^{3z-y}-2^{x+y+1}$$
is nonnegative.

Proposed by Adrian Andreescu, Dallas, Texas, USA


Solution:
Let $a=2^x$, $b=2^y$, $c=2^z$. Adding the three given numbers, we get
$$\begin{array}{lll} S&=&\left(\dfrac{a^3}{b}+\dfrac{a^3}{c}-2bc\right)+\left(\dfrac{b^3}{c}+\dfrac{b^3}{a}-2ca\right)+\left(\dfrac{c^3}{a}+\dfrac{c^3}{b}-2ab\right)\\&=&\left(\dfrac{a^3}{b}+\dfrac{b^3}{a}-2ab\right)+\left(\dfrac{b^3}{c}+\dfrac{c^3}{b}-2bc\right)+\left(\dfrac{c^3}{a}+\dfrac{a^3}{c}-2ca\right). \end{array}$$
By the AM-GM Inequality, we get
$$\dfrac{a^3}{b}+\dfrac{b^3}{a} \geq 2ab, \qquad \dfrac{b^3}{c}+\dfrac{c^3}{b} \geq 2bc, \qquad \dfrac{c^3}{a}+\dfrac{a^3}{c} \geq 2ca.$$
So, $S \geq 0$ and we conclude that at least one of the three given numbers is nonnegative.

Monday, October 9, 2017

Mathematical Reflections 2017, Issue 3 - Problem O414

Problem:
Characterize all positive integers $n$ with the following property: for any two coprime divisors $a<b$ of $n$, $b-a+1$ is also a divisor of $n$.

Proposed by Vlad Matei, University of Wisconsin, Madison, USA

Solution:
It's easy to see that if $n=p^k$, where $p$ is a prime and $k \in \mathbb{Z}^+$, then $n$ satisfies the condition. Assume that $n$ has at least two prime divisors. Let $n=mp^k$, where $p$ is the smallest prime dividing $n$ and $(m,p)=1$. Clearly $p<m$ and both $p$ and $m$ are divisors of $n$. If $n$ satisfies the condition, then $m-p+1$ is also a divisor of $n$. Let $q$ be a prime such that $q \mid m$. Since $m-q<m-p+1<m$, then $q$ doesn't divide $m-p+1$. It follows that the only prime factor of $m-p+1$ is $p$. Hence, $m-p+1=p^a$ for some positive integer $a \leq k$, i.e. $$m=p^a+p-1.$$ Assume that $a \geq 2$. Since $p^{a-1} \mid n$ and $p^{a-1}<m$, then $m-p^{a-1}+1=p(p^{a-1}-p^{a-2}+1)$ is also a divisor of $n$. As $p^{a-1}-p^{a-2}+1$ is not divisible by $p$, then it must divide $m$. As
$$m=p^a+p-1=(p+1)(p^{a-1}-p^{a-2}+1)+p^{a-2}-2,$$ then $(p^{a-1}-p^{a-2}+1) \mid m$ if and only if $(p^{a-1}-p^{a-2}+1) \mid (p^{a-2}-2)$. We have $$p^{a-1}-p^{a-2}+1>p^{a-2}-2 \iff p^{a-2}(p-2)+3>0,$$ so there are no solutions if $a \geq 2$. If $a=1$, we get $m=2p-1$.

(i) If $k \geq 2$, then $p^2 \mid n$ and $p^2>2p-1$, so $p^2-(2p-1)+1=p^2-2p+2$ is also a divisor of $n$. If $p>2$, then $p^2-2p+2$ is not divisible by $p$, which gives $(p^2-2p+2) \mid m$, i.e. $(p^2-2p+2) \mid (2p-1)$ and this is true only if $p=3$. So, $m=5$ and $n=5\cdot 3^k$. Since $3^k>5$, then also $3^k-5+1=3^k-4$ is a divisor of $n$, which forces $3^k-4=5$, i.e. $k=2$ and $n=45$. If $p=2$, then $m=3$ and $n=3\cdot 2^k$. Since $2^k>3$, then also $2^k-3+1=2(2^{k-1}-1)$ is a divisor of $n$ and this implies $k=2$ or $k=3$. An easy check shows that indeed $n \in \{12,24\}$.

(ii) If $k=1$, then $n=(2p-1)p$. Let $q$ be the smallest prime divisor of $2p-1$. Then $q \mid n$, $p<q$ and so $q-p+1$ is a divisor of $n$. So, $(q-p+1) \mid (2p-1)$ or $(q-p+1) \mid p$. In the first case, by the minimality of $q$, it must be $q<q-p+1$, contradiction. In the second case, $q-p+1=1$ or $q-p+1=p$, which gives $q=2p-1$.

In conclusion, we get $n=p^k$, where $k \in \mathbb{Z}^+$, or $n=(2p-1)p$, where $p$ is prime and $2p-1$ is prime, or $n \in \{12,24,45\}$.

Mathematical Reflections 2017, Issue 3 - Problem O410

Problem:
On each cell of a chess board it is written a number equal to the amount of the rectangles that contain this cell. Find the sum of all the numbers.

Proposed by Robert Bosch, USA 

Solution:
Consider an $n \times n$ chessboard and let $S$ be the required sum. Observe that writing on each cell the number equal to the amount of the rectangles containing the cell is equivalent to perform the following operation on the chessboard: at the beginning write zero on each cell of the chessboard, then for each $i \times j$ rectangle ($1 \leq i,j \leq n$) add $1$ to all its cells. So, we only have to find the total number of rectangles, each counted with the number its of cells. The number of $i \times j$ rectangles is $(n+1-i)(n+1-j)$, where $1 \leq i,j \leq n$. Since each $i \times j$ rectangle contains $ij$ cells, then we have
\begin{eqnarray*} S&=& \sum_{i=1}^n \sum_{j=1}^n ij(n+1-i)(n+1-j) \\ &=& \sum_{i=1}^n i(n+1-i) \sum_{j=1}^n j(n+1-j) \\ &=& \left(\sum_{k=1}^n k(n+1-k)\right)^2 \\ &=& {n+2 \choose 3}^2.
\end{eqnarray*}

Mathematical Reflections 2017, Issue 3 - Problem O409

Problem:
Find all positive integers $n$ for which there are $n+1$ digits in base $10$, not necessarily distinct, such that at least $2n$ permutations of those digits produce $(n+1)$-digit perfect squares, with leading zeros not allowed. Note that two different permutations are considered distinct even if they lead to the same digit string due to repetition among the digits.

Proposed by Titu Andreescu, University of Texas at Dallas, USA

Solution:
We prove that all $n \geq 2$ satisfy the given property. Clearly, $n=1$ doesn't satisfy the given property. If $n=2$, take $144$ and the permutations $\{\textrm{id},(23),(13),(132)\}$ acting on the digits of $144$. If $n=3$, take $1444$ and the permutations $\{\textrm{id},(23),(24),(34),(234),(243)\}$ acting on the digits of $1444$. If $n=5$, take $160000$ and the $4!=24$ permutations acting on the digits of $160000$ moving only the zeros. Now, let $n \geq 4$ be even. Then, $n=2k$ for some integer $k \geq 2$. Observe that there are at least $(2k)!$ permutations acting on the digits of $10^{2k}$ that produces a perfect square (namely, the ones fixing $1$ in the first position and moving the other zeros) and $(2k)! \geq 4k$ for any integer $k \geq 2$. Let $n \geq 7$ be odd. Then, $n=2k-1$ for some integer $k \geq 3$. Observe that there are at least $k!\cdot (k-1)!$ permutations acting on the digits of $\underbrace{11\ldots 11}_{k \textrm{ ones}} \underbrace{55\ldots 55}_{k-1 \textrm{ fives}} 6$ that produces a perfect square and $k! \cdot (k-1)! \geq 2(2k-1)$ for any integer $k \geq 4$. The conclusion follows.

Mathematical Reflections 2017, Issue 3 - Problem U414

Problem:
Let $p < q < 1$ be positive real numbers. Find all functions $f: \mathbb{R} \to \mathbb{R}$ which satisfy the
conditions:

(i) $f(px+f(x))=qf(x)$ for all real numbers $x$,
(ii) $\lim_{x \to 0} \dfrac{f(x)}{x}$ exists and its finite.


Proposed by Florin Stanescu, Gaesti, Romania


Solution:
Clearly, $f(x)=0$ for all $x \in \mathbb{R}$ is a solution to the problem. Let $f \neq 0$. Observe that by condition (ii) it must be $f(0)=0$. We have two cases.

(i) $\displaystyle\lim_{x \to 0} \dfrac{f(x)}{x}=\ell \in \mathbb{R}\setminus\{0\}$. Then, from condition (i), we get
$$\dfrac{f(px+f(x))}{px+f(x)}=\dfrac{qf(x)}{x(p+\frac{f(x)}{x})}$$ and if $x \to 0$ we get $$\ell=\dfrac{q \ell}{p+\ell} \iff \ell=q-p.$$ So, $f(x)=(q-p)x$ is a solution to the problem.

(ii) $\displaystyle\lim_{x \to 0} \dfrac{f(x)}{x}=0$. Then, $f(x) \sim Cx^{1+\delta}$ if $x \to 0$, where $C \neq 0$ and $\delta>0$.
Then, from condition (i), we get
$$\dfrac{f(px+f(x))}{(px+f(x))^{1+\delta}}=\dfrac{qf(x)}{x^{1+\delta}(p+\frac{f(x)}{x})^{1+\delta}}$$ and if $x \to 0$ we get
$$C=\dfrac{qC}{p^{1+\delta}} \iff p^{1+\delta}=q,$$ contradiction.

We conclude that the only solutions are $f(x)=0$ and $f(x)=(q-p)x$.

Mathematical Reflections 2017, Issue 3 - Problem U412

Problem:
Let $P(x)$ be a monic polynomial with real coefficients, of degree $n$, which has $n$ real roots. Prove that if
$$P(c) \leq \left(\dfrac{b^2}{a}\right)^n,$$
then $P(ax^2+2bx+c)$ has at least one real root.

Proposed by Nguyen Viet Hung, Hanoi University of Science, Vietnam

Solution:
If $P(x)$ is an $n$-th degree monic polynomial with real coefficients and with $n$ real roots $\alpha_1,\ldots,\alpha_n$, then
$$P(x)=(x-\alpha_1)(x-\alpha_2)\cdot \ldots \cdot (x-\alpha_n).$$
Hence, $$P(c)=(c-\alpha_1)(c-\alpha_2)\cdot \ldots \cdot (c-\alpha_n) \leq \left(\dfrac{b^2}{a}\right)^n$$
and $$P(ax^2+2bx+c)=(ax^2+2bx+c-\alpha_1)(ax^2+2bx+c-\alpha_2)\cdot \ldots \cdot (ax^2+2bx+c-\alpha_n).$$
Assume by contradiction that $P(ax^2+2bx+c)$ has no real roots. Then, each factor has negative discriminant, i.e.
$$\begin{array}{lll} b^2-a(c-\alpha_1) & < & 0 \\ b^2-a(c-\alpha_2) & < & 0 \\ \vdots & \vdots & \vdots \\ b^2-a(c-\alpha_n) & < & 0. \end{array} \iff \begin{array}{lll} b^2 & < & a(c-\alpha_1) \\ b^2 & < & a(c-\alpha_2) \\ \vdots & \vdots & \vdots \\ b^2 & < & a(c-\alpha_n). \end{array}$$
Multiplying side by side all these inequalities, we get $(b^2)^n < a^n(c-\alpha_1)(c-\alpha_2)\cdot \ldots \cdot (c-\alpha_n)$, i.e.
$$\left(\dfrac{b^2}{a}\right)^n < (c-\alpha_1)(c-\alpha_2)\cdot \ldots \cdot (c-\alpha_n),$$ contradiction.

Mathematical Reflections 2017, Issue 3 - Problem U411

Problem:
Let $e$ be a positive integer. We say that a positive integer $m$ is awesome if $m$ has $\omega^e(m)$ digits in base ten, where $\omega(m)$ is the number of distinct primes that divide $m$. Prove that there are finitely many awesome numbers.

Proposed by Alessandro Ventullo, Milan, Italy


Solution:
Let $\mathbb{P}$ be the set of primes and let
$$\mathcal{E}_n=\left\{\prod_{j=1}^{n^e} p_j^{k_j} : p_j \in \mathbb{P}, k_j \in \mathbb{N}^{\ast} \right\}$$ where the $p_j$ are distinct primes. A positive integer $m$ is awesome if and only if the two following conditions are simultaneously satisfied:

    (a) $m \in \mathcal{E}_n$
    (b) $10^{n^e-1} \leq m < 10^{n^e}$

for some $n \in \mathbb{N}^{\ast}$.
Let $$\mathcal{A}_n=\{m \in \mathcal{E}_n : 10^{n^e-1} \leq m < 10^{n^e}\}$$ be the set of awesome numbers with $n^e$ digits and let $$\mathcal{A}=\bigcup_{n \in \mathbb{N}^*} \mathcal{A}_n.$$ It's easy to see that $\mathcal{A}$ contains all the awesome numbers. \\
In order to prove that $\mathcal{A}$ is finite, we need to prove that there are finitely many nonempty $\mathcal{A}_n$.
We prove that for any fixed exponent $e$, there exists $k \in \mathbb{N}$ such that $\forall n > k$ we have $\mathcal{A}_n= \emptyset$.\\
Since $\mathcal{E}_n \neq \emptyset$ for all $n \in \mathbb{N}^*$, we can deduce that each $\mathcal{E}_n$ has a minimum by the well-ordering principle.
Let $m_n=\min_{m \in \mathcal{E}_n} \{m\}$ for all $n \in \mathbb{N}^*$ and let $$\{m_n\}_{n \in \mathbb{N}^*}=\{m_1, m_2, \ldots\}$$be the sequence whose terms are the all the minima of each $\mathcal{E}_n$.\\
By definition, $$m_n = \prod_{j=1}^{n^e}p^*_j$$ where $p^*_1=2, p^*_2=3, p^*_3=5, \ldots$. The sequence $\{m_n\}$ is a positive term sequence and $$m_n = \prod_{j=1}^{n^2} p^*_j \geq 2^{n^e} \quad \forall n \in \mathbb{N}^*,$$ so $\{m_n\}_{n \in \mathbb{N}}$ diverges by the Comparison Test, i.e. $$\forall M \in \mathbb{R} \quad \exists k \in \mathbb{N} : m_n > M \quad \forall n>k$$ and this holds in particular for $M=10^{n^e}$, which gives $m_n > 10^{n^e}$ for any $n>k$. Since $m_n=\min_{m \in \mathcal{E}_n} \{m\}$, we have that $\mathcal{A}_n=\emptyset$ for any $n > k$ and for any fixed eponent $e$, which is the desired conclusion.

Mathematical Reflections 2017, Issue 3 - Problem U410

Problem:
Let $a,b,c$ be real numbers such that $a+b+c=5$. Prove that $$(a^2+3)(b^2+3)(c^2+3) \geq 192.$$

Proposed by Marius Stanean, Zalau, Romania


Solution:
Let $f(a,b,c)=(a^2+3)(b^2+3)(c^2+3)$ and $g(a,b,c)=a+b+c-5$. Consider the Lagrangian function
$$L(a,b,c,\lambda)=f(a,b,c)-\lambda g(a,b,c)=(a^2+3)(b^2+3)(c^2+3)-\lambda(a+b+c-5),$$
where $\lambda \in \mathbb{R}$. Observe that $f(a,b,c)$ is continuous on the compact set defined by $g(a,b,c)$, so by Weierstrass Theorem, there exists a global minimum. By the method of Lagrange Multipliers, a maximum or a minimum for $f(a,b,c)$ subject to the constraint $g(a,b,c)=0$ must be a stationary point of $L$. Therefore a maximum or a minimum satisfies
$$\renewcommand{\arraystretch}{2} \begin{array}{rcl} \dfrac{\partial L}{\partial a} & = & 0 \\ \dfrac{\partial L}{\partial b} & = & 0 \\  \dfrac{\partial L}{\partial c} & = & 0 \\ \dfrac{\partial L}{\partial \lambda} & = & 0, \end{array}$$ i.e.
$$\begin{array}{rcl} 2a(b^2+3)(c^2+3)+\lambda & = & 0 \\ 2b(a^2+3)(c^2+3)+\lambda & = & 0 \\ 2c(a^2+3)(b^2+3)+\lambda & = & 0 \\ a+b+c-5 & = & 0. \end{array}$$
Subtracting side by side the first two equations and simplifying, then doing the same for the second and the third equation and for the third and the first equation, we obtain
$$\begin{array}{rcl} (a-b)(3-ab) & = & 0 \\ (b-c)(3-bc) & = & 0 \\ (c-a)(3-ca) & = & 0 \\ a+b+c-5 & = & 0. \end{array}$$
So, up to symmetry, we get $$(a,b,c) \in \left\{\left(\dfrac{5}{3},\dfrac{5}{3},\dfrac{5}{3}\right),\left(\dfrac{3}{2},\dfrac{3}{2},2 \right),\left(1,1,3\right)\right\}.$$ Since $f\left(\dfrac{5}{3},\dfrac{5}{3},\dfrac{5}{3}\right)=\left(\dfrac{52}{9}\right)^3$, $f\left(\dfrac{3}{2},\dfrac{3}{2},2\right)=\dfrac{3087}{16}$, $f(1,1,3)=192$, we conclude that $192$ is the constrained minimum, i.e.
$$(a^2+3)(b^2+3)(c^2+3) \geq 192.$$

Mathematical Reflections 2017, Issue 3 - Problem U409

Problem:
Evaluate $$\lim_{x \to 0} \dfrac{2\sqrt{1+x}+2\sqrt{2^2+x}+\ldots+2\sqrt{n^2+x}-n(n+1)}{x}.$$

Proposed by Nguyen Viet Hung, Hanoi University of Science, Vietnam


Solution:
Observe that
$$\renewcommand{\arraystretch}{2} \begin{array}{rcl} \sqrt{1+x}&=&1+\dfrac{1}{2}\cdot x+o(x) \\ \sqrt{2^2+x}=2\sqrt{1+\dfrac{x}{2^2}}&=&2+\dfrac{1}{2}\cdot\dfrac{x}{2}+o(x) \\ \vdots & \vdots & \vdots \\ \sqrt{n^2+x}=n\sqrt{1+\dfrac{x}{n^2}}&=& n+\dfrac{1}{2}\cdot\dfrac{x}{n}+o(x). \end{array}$$
So, $$\begin{array}{lll} 2\sqrt{1+x}+2\sqrt{2^2+x}+\ldots+2\sqrt{n^2+x}&=&2(1+2+\ldots+n)+x\left(1+\dfrac{1}{2}+\ldots+\dfrac{1}{n}\right)+o(x)\\&=&n(n+1)+x\left(1+\dfrac{1}{2}+\ldots+\dfrac{1}{n}\right)+o(x), \end{array}$$ which gives
$$\lim_{x \to 0} \dfrac{2\sqrt{1+x}+2\sqrt{2^2+x}+\ldots+2\sqrt{n^2+x}-n(n+1)}{x}=1+\dfrac{1}{2}+\ldots+\dfrac{1}{n}.$$