Problem:
Prove that no matter how we choose $n$ numbers from the set $\{1, 2, \ldots, 2n\}$, one of them
will be a square-free integer.
Solution:
Let $A=\{1,2,\ldots,2n\}$. We will prove that there are at most $n-1$ elements in $A$ which are not square-free integers. The number of the elements in $A$ which are divisible by $p^2$, where $p$ is a prime number, are
$$\left\lfloor \dfrac{2n}{p^2} \right\rfloor \leq \dfrac{2n}{p^2}.$$ Therefore, the number of elements in $A$ which are not square-free integers are $$\sum_{p=2 \atop p \textrm{ prime}}^{n} \left\lfloor \dfrac{2n}{p^2} \right\rfloor \leq \sum_{p=2 \atop p \textrm{ prime}}^{n} \dfrac{2n}{p^2} < \sum_{i=2}^{n} \dfrac{2n}{i^2} < \sum_{i=2}^{n} \dfrac{2n}{i(i-1)}=2n\left(\dfrac{1}{2}-\dfrac{1}{n(n-1)}\right)<n,$$ and the conclusion follows.
Wednesday, May 28, 2014
Mathematical Reflections 2014, Issue 2 - Problem U297
Problem:
Let $a_0 = 0, a_1 = 2$, and $a_{n+1}=\sqrt{2-\dfrac{a_{n-1}}{a_n}}$ for $n \geq 0$. Find $\displaystyle \lim_{n \to \infty} 2^n a_n$.
Solution:
We will show by induction on $n$ that $a_n=2 \sin \dfrac{\pi}{2^n}$ for all $n \in \mathbb{N}$. If $n=0$, it's obvious. Suppose that $a_n=2 \sin \dfrac{\pi}{2^n}$ for some $n \in \mathbb{N}$. Then, $$a_{n+1}=\sqrt{2-\dfrac{2\sin (\pi/2^{n-1})}{2\sin (\pi/2^n)}}=\sqrt{2-\dfrac{4\sin (\pi/2^n)\cos (\pi/2^n)}{2\sin (\pi/2^n)}}=\sqrt{2-2\cos \dfrac{\pi}{2^n}}=2\sin \dfrac{\pi}{2^{n+1}}.$$
Therefore, $$2^n a_n=2^{n+1}\sin\dfrac{\pi}{2^n}=2^{n+1}\left(\dfrac{\pi}{2^n}+o((\pi/2^n)^2)\right),$$ which implies $$\lim_{n \to \infty} 2^n a_n=2\pi.$$
Let $a_0 = 0, a_1 = 2$, and $a_{n+1}=\sqrt{2-\dfrac{a_{n-1}}{a_n}}$ for $n \geq 0$. Find $\displaystyle \lim_{n \to \infty} 2^n a_n$.
Proposed by Titu Andreescu.
Solution:
We will show by induction on $n$ that $a_n=2 \sin \dfrac{\pi}{2^n}$ for all $n \in \mathbb{N}$. If $n=0$, it's obvious. Suppose that $a_n=2 \sin \dfrac{\pi}{2^n}$ for some $n \in \mathbb{N}$. Then, $$a_{n+1}=\sqrt{2-\dfrac{2\sin (\pi/2^{n-1})}{2\sin (\pi/2^n)}}=\sqrt{2-\dfrac{4\sin (\pi/2^n)\cos (\pi/2^n)}{2\sin (\pi/2^n)}}=\sqrt{2-2\cos \dfrac{\pi}{2^n}}=2\sin \dfrac{\pi}{2^{n+1}}.$$
Therefore, $$2^n a_n=2^{n+1}\sin\dfrac{\pi}{2^n}=2^{n+1}\left(\dfrac{\pi}{2^n}+o((\pi/2^n)^2)\right),$$ which implies $$\lim_{n \to \infty} 2^n a_n=2\pi.$$
Mathematical Reflections 2014, Issue 2 - Problem U295
Problem:
Let $a$ be a real number such that $(\lfloor na \rfloor)_{n \geq 1}$ is an arithmetic sequence. Prove that $a$ is an integer.
Solution:
Let $a_n=\lfloor na \rfloor$ and $b_n=n|a|$. By hypothesis, there exists $d \in \mathbb{R}$ such that $a_{n+1}-a_n=d$. Observe that $d \in \mathbb{Z}$ since it is the difference of two integers. Now, $(b_n)_{n \geq 1}$ is positive, increasing and unbounded and $$\lim_{n \to \infty} \dfrac{a_{n+1}-a_n}{b_{n+1}-b_n}=\dfrac{d}{|a|}.$$ By the Stolz-Cesaro Theorem, we obtain $\displaystyle \lim_{n \to \infty} \dfrac{a_n}{b_n}=\dfrac{d}{|a|}$, which gives $$\lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n}=d.$$ Moreover, since $na-1 < \lfloor na \rfloor \leq na$, we have $$\lim_{n \to \infty} \dfrac{na-1}{n} \leq \lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n} \leq \lim_{n \to \infty} \dfrac{na}{n},$$ and by the Squeeze Theorem, we obtain $\displaystyle \lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n}=a$. By uniqueness of the limit, we obtain $a=d$ and the conclusion follows.
Let $a$ be a real number such that $(\lfloor na \rfloor)_{n \geq 1}$ is an arithmetic sequence. Prove that $a$ is an integer.
Proposed by Mihai Piticari.
Solution:
Let $a_n=\lfloor na \rfloor$ and $b_n=n|a|$. By hypothesis, there exists $d \in \mathbb{R}$ such that $a_{n+1}-a_n=d$. Observe that $d \in \mathbb{Z}$ since it is the difference of two integers. Now, $(b_n)_{n \geq 1}$ is positive, increasing and unbounded and $$\lim_{n \to \infty} \dfrac{a_{n+1}-a_n}{b_{n+1}-b_n}=\dfrac{d}{|a|}.$$ By the Stolz-Cesaro Theorem, we obtain $\displaystyle \lim_{n \to \infty} \dfrac{a_n}{b_n}=\dfrac{d}{|a|}$, which gives $$\lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n}=d.$$ Moreover, since $na-1 < \lfloor na \rfloor \leq na$, we have $$\lim_{n \to \infty} \dfrac{na-1}{n} \leq \lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n} \leq \lim_{n \to \infty} \dfrac{na}{n},$$ and by the Squeeze Theorem, we obtain $\displaystyle \lim_{n \to \infty} \dfrac{\lfloor na \rfloor}{n}=a$. By uniqueness of the limit, we obtain $a=d$ and the conclusion follows.
Mathematical Reflections 2014, Issue 2 - Problem J296
Problem:
Several positive integers are written on a board. At each step, we can pick any two
numbers $u$ and $v$, where $u \geq v$, and replace them with $u + v$ and $u - v$. Prove that after
a finite number of steps we can never obtain the initial set of numbers.
Solution:
Let $S$ be the sum of the numbers on the blackboard at a given moment. After removing the numbers $u$ and $v$ and replacing them with $u+v$ and $u-v$ we have that the sum of the numbers on the blackboard is $$S'=S-u-v+(u+v)+(u-v)=S+(u-v)>S.$$ Therefore, after each step the sum of the numbers on the blackboard increases, and this proves that after a finite number of step we can never obtain the original numbers.
Several positive integers are written on a board. At each step, we can pick any two
numbers $u$ and $v$, where $u \geq v$, and replace them with $u + v$ and $u - v$. Prove that after
a finite number of steps we can never obtain the initial set of numbers.
Proposed by Marius Cavachi.
Solution:
Let $S$ be the sum of the numbers on the blackboard at a given moment. After removing the numbers $u$ and $v$ and replacing them with $u+v$ and $u-v$ we have that the sum of the numbers on the blackboard is $$S'=S-u-v+(u+v)+(u-v)=S+(u-v)>S.$$ Therefore, after each step the sum of the numbers on the blackboard increases, and this proves that after a finite number of step we can never obtain the original numbers.
Mathematical Reflections 2014, Issue 2 - Problem J295
Problem:
Let $a,b,c$ be positive integers such that $(a-b)^2+(b-c)^2+(c-a)^2=6abc$. Prove that $a^3+b^3+c^3+1$ is not divisible by $a+b+c+1$.
Solution:
Clearly $$(a-b)^2+(b-c)^2+(c-a)^2=2(a^2+b^2+c^2-ab-bc-ac)$$ which implies $$a^2+b^2+c^2-ab-bc-ac=3abc.$$
Now, using the identity $$a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ac)$$ we obtain that $$a^3+b^3+c^3-3abc=3abc(a+b+c),$$ or $$a^3+b^3+c^3=3abc(a+b+c+1)$$ which means that $a+b+c+1$ divides $a^3+b^3+c^3$. If $a+b+c+1$ divides $a^3+b^3+c^3+1$, then $a+b+c+1$ divides $(a^3+b^3+c^3+1)-(a^3+b^3+c^3)=1$, which is impossible, since $a+b+c+1>1$. Thus, $a^3+b^3+c^3+1$ is not divisible by $a+b+c+1$.
Let $a,b,c$ be positive integers such that $(a-b)^2+(b-c)^2+(c-a)^2=6abc$. Prove that $a^3+b^3+c^3+1$ is not divisible by $a+b+c+1$.
Proposed by Mihaly Bencze.
Solution:
Clearly $$(a-b)^2+(b-c)^2+(c-a)^2=2(a^2+b^2+c^2-ab-bc-ac)$$ which implies $$a^2+b^2+c^2-ab-bc-ac=3abc.$$
Now, using the identity $$a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ac)$$ we obtain that $$a^3+b^3+c^3-3abc=3abc(a+b+c),$$ or $$a^3+b^3+c^3=3abc(a+b+c+1)$$ which means that $a+b+c+1$ divides $a^3+b^3+c^3$. If $a+b+c+1$ divides $a^3+b^3+c^3+1$, then $a+b+c+1$ divides $(a^3+b^3+c^3+1)-(a^3+b^3+c^3)=1$, which is impossible, since $a+b+c+1>1$. Thus, $a^3+b^3+c^3+1$ is not divisible by $a+b+c+1$.
Subscribe to:
Posts (Atom)