Tag Info

New answers tagged

1

Maybe if we write $N=\lfloor 10^{2008}\cdot 0.\overline{111}\rfloor=\dfrac{10^{2008}-1}{9}$. Then we must have $$ \sqrt{N}\approx\sqrt{N+\tfrac19}=\sqrt{\frac{10^{2008}}{9}}=\frac{10^{1004}}3=10^{1004}\cdot 0.\overline{333} $$ and with the derivative of the square root function $f(x)=\sqrt x$ being $f'(x)=\frac{1}{2\sqrt x}$ the difference between $\sqrt{N}$ ...


2

Note that $N=\frac{10^{2008}-1}{9}$. One can use the Taylor series of $\sqrt{x}$ at $a=10^{2008}$ to solve this problem. More precisely, let $f(a)=\sqrt a$, $$f(x)=f(a)+(x-a)f'(a)+\frac{f''(a)}2(x-a)^2+\cdots$$ Or $$\sqrt{9N}=10^{1004}-\frac{1}{2\cdot 10^{1004}}-\frac{3}{4\cdot 10^{3\cdot 1004}}+\cdots$$ That means $$3\sqrt{N}=10^{1004}-5\cdot ...


1

The point is that $x^{2^k}$ and $y^{2^k}$ are either both congruent to 1 or both congruent to -1 mod 4. Thus when you add them, you get something congruent to 2 mod 4, and if something is congruent to 2 mod 4, it has exactly one power of 2 in its prime factorization.


1

Maybe we need to take a few steps back ( though I imagine this has all been covered in your course). If $a$ is any real number other than $1$ and $r$ is a positive integer, then $1 + a + a^{2} +\ldots +a^{r-1} = \frac{a^{r}-1}{a-1}.$ If you need to verify that, multiply the left side by $a-1$ and notice that there is a lot of cancellation. If $b$ is another ...


0

$$\begin{align}S&=3+3\cdot 4+3\cdot 4^2+3\cdot 4^3+...+3\cdot 4^{\log_2 n-1}\\ &=3[1+4+4^2+4^3+...+4^{\log_2 n-1}]\\ 4S&=3[\quad\;\; 4+4^2+4^3+...+4^{\log_2n-1}+4^{\log_2 n}] \quad \quad \text{as $n=1,2,4,8,...,2^m,...$} \end{align}$$ Subtracting: $$\begin{align} 3S&=3[4^{\log_2n}-1]\\ &=3[2^{2\log_2n}-1]\\ &=3[(2^{\log_2 n})^2-1]\\ ...


0

If $\log $ is 2-base logarithm, you have: $\;\;\; 3+4 \cdot 3+4^2 \cdot 3+ \cdots + 4^{\log n -1} \cdot 3 \\ = 4-1+4(4-1)+4^2(4-1)+4^3(4-1)+\cdots+4^{\log n -1} \cdot (4-1) \\ = 4-1+4^2-4+4^3-4^2+\cdots+4^{\log n}-4^{\log n-1} \\ = 4^{\log n}-1 \\ = 2^{2\log n}-1 \\ = n^2-1$ $\textbf{Edit}$ In sigma notation : $$\sum_{i=1}^{\log n}3\cdot ...


2

The answer is 1. The result is known as Goldbach-Euler theorem. See Wikipedia entry for "proof". For rigorous proof, you could consider sum of reciprocals of all perfect powers, $S$. Note that sum equals $$ S = \sum_{x \in B}\sum_{n = 2}^{\infty}\frac{1}{x^{n}} = ...


-1

I get the same result as Barak, as follows: $$\sum\limits_{k\in A}\frac{1}{k-1}>\sum\limits_{k\in A}\frac{1}{k}$$ Now fix $n\in\mathbb{N}$. For each $n$ the latter sum includes (all of) $\zeta(2)-1$, $\zeta(3)-1$, ..., $\zeta(n)-1$, therefore, $$\sum\limits_{k\in A}\frac{1}{k}\sim\sum\limits_{k=2}^n\zeta(k)-(n-1)$$ and we have (see here) ...


0

Not a complete answer to your question, but if $A$ is a multi-set (where any element may appear more than once), then your series is larger than the sum of all the following series put together: $\sum\limits_{n=2}^{\infty}\frac{1}{2^n}=\frac{1}{2-1}-\frac{1}{2}=\frac{1}{2}$ $\sum\limits_{n=2}^{\infty}\frac{1}{3^n}=\frac{1}{3-1}-\frac{1}{3}=\frac{1}{6}$ ...


0

I guess you assume $x,y\geq 0$, for otherwise it will not hold. It is obvious that $f(x)=x^{1/3}$ is a concave function. Jensen's inequality shows that: $$ x^{1/3}/2+y^{1/3}/2\leq(x/2+y/2)^{1/3} $$ or rather $$ x^{1/3}+y^{1/3}\leq 2^{2/3}(x+y)^{1/3} $$ When $x,y\leq 0$, $f(x)=x^{1/3}$ becomes a convex function and we should rather have: $$ ...


1

If you set $x=y$ and turn the inequality to an equation, the given equation in $K,x$ has the solution $K=4^{1/3}$, for all $x$. Then this is a good candidate for a tentative proof.


0

For any $x\in (0,2)$ we have: $$\log\frac{1+x/2}{1-x/2}=\sum_{k=0}^{+\infty}\frac{x^{2k+1}}{4^k(2k+1)}>x,$$ hence: $$\sum_{i=p}^{q}\frac{1}{i}<\sum_{i=p}^{q}\log\frac{2i+1}{2i-1}=\log\frac{2q+1}{2p-1},$$ establishing a much stronger inequality - that appears, for instance, in the proof of the Polya-Vinogradov inequality.


2

Since $\dfrac{1}{i} \le \dfrac{1}{p}$ for $p \le i \le q$, and $0 < q-(p-1) < q+\frac{1}{2}$, and $p > p - \frac{1}{2} > 0$, we have $\displaystyle\sum_{i = p}^{q}\dfrac{1}{i} \le \sum_{i = p}^{q}\dfrac{1}{p} = \dfrac{q-(p-1)}{p} < \dfrac{q+\frac{1}{2}}{p-\frac{1}{2}}$, as desired.


0

You can "unofficially" (well, nobody really keeps track) participate in (mostly short answer, but some proof-based) student-run contests like the NIMO and OMO (see http://internetolympiad.org/), or the (proof-based) Olympiad-style ELMO (see this year's AoPS-version of the contest). Of course, AoPS also has a good repository of past contest problems; in ...


0

Since $N$ only goes up to $10^{16}$, and $M$ fits into 32 bits you can solve this problem in a matter of seconds on a computer that supports 64 bit integers. First solve for the modulus $A$ of $10^8$ ones modulo $M$, by iteratively multiplying by $10$ and adding $1$ and then taking the modulus modulo $M$. Also solve for $B = 10^{10^8 +1}$ modulo $M$. Then ...


3

This is a well-known fact in the theory of Farey series. You have $aq>bp$ and $pd>qc$, so the integers $\delta_1=aq-bp$ and $\delta_2=dp-cq$ are both $\geq 1$. Now $$ d\delta_1+b\delta_2=(ad-bc)q=q $$ It follows that $q\geq b+d$.


4

Suppose there exist $a, b, c, x, y, z > 0$ such that $$a+b+c=4,$$ $$ax+by+cz = xyz,$$ $$x+y+z \leq 4.$$ Observe that we have $$axyz + bxyz + cxyz = 4xyz,$$ so that $$axyz + bxyz + cxyz = 4ax + 4by + 4cz,$$ and hence $$ax(yz-4) + by(xz-4) + cz(xy-4) = 0.$$ Since $x+y+z \leq 4$ and $a, b, c, x, y, z > 0,$ what follow are the inequalities $$xy, yz, xz ...


0

Technically, $yz=y \cdot 15$ for $0 \leq y \leq 15$ are all possible answers given the current wording of the problem. This is because $min(T(y),T(15))=T(15)$ for all $0 \leq y \leq 15$.


3

Macavity's way is certainly the most elegant. Here is a way to do it just using Cauchy-Schwarz and AM-GM. Use Cauchy-Schwarz inequality to get: $$(x+y+z)\left(\frac{a^3}{x}+\frac{b^3}{y}+\frac{c^3}{z}\right)\geq (a^{3/2}+b^{3/2}+c^{3/2})^2$$ So to prove your inequality, it suffices to show that $$ (a^{3/2}+b^{3/2}+c^{3/2})^2 \geq \frac{(a+b+c)^3}{3}$$ ...


5

Holder's Inequality gives: $$\left( \frac{a^3}x + \frac{b^3}y + \frac{c^3}z \right)(x + y + z)(1+1+1) \ge (a+b+c)^3 $$


2

${\bf Hint}\ \ n-m\mid n^k-m^k.\ $ So $\,\ m=-(n\!+\!1),\,\ k\,$ odd ${\rm yields}\ \ 2n\!+\!1\mid n^k\!+(n\!+\!1)^k.\,\ $ Yours is case $\,k=n.$ Remark $\ $ The above divisibility can be viewed as a special case of the Factor Theorem $\, x-y\,\ \mid\,\ f(x)-f(y)\ $ for any polynomial $\,f\,$ or, by the Polynomial Congruence Theorem $\,x\equiv ...


6

The key is the following known observation: If $n=2k+1$ then $$a^{n}+b^n=a^{2k+1}+b^{2k+1}=(a+b)( \mbox{junk} )$$ Thus, for all $n$ odd, $a+b$ divides $a^n+b^n$.


2

The official solution is wrong. The equality happens when $$\frac{a^2}{17}=\frac1{2a}$$ or $a^3=\frac{17}2<a^3$. Note that in your solution, the equality does not happen either. Edit: I would solve the problem as follows. Let $a=x-y,b=y-z$ then $ab(a+b)=17$ and we need to minimize ...


2

In the second solution, when $=$ in $\ge$ is satisfied, $a=b=c$. But then, $abc=17$ and $a+b=c$ makes the contradiction.


1

Given a row $r$, define the pattern of the row to be the set of indices $i$ such that the $i$th number in row $r$ is different from the $i$th number in the first row. Clearly, the first row has pattern $\emptyset$, and if two rows have different patterns, they must be different. We claim that, given your constraints, if $p$ is a pattern with an even number ...


1

Here is a related problem: Show that a matrix is nilpotent. The proof for this one is almost the same. We have $$AB=-BA$$, thus it follows by multiplying $B$ on the right, that $$AB^2 = -BAB = B^2 A$$ Then by induction, we have $$AB^n=(-1)^nB^nA.$$ Now, following the solution in the link: we have $$B^n = B^{n-1}B = B^{n-1}(AX+XA) = A (-1)^{n-1} ...


2

Your argument is wrong in several places. There are $(n-k+1)^2$ possible $k\times k$ squares that need to be considered. If you only consider a few of them, say a nonoverlapping subset, you will only consider $\lfloor \frac nk\rfloor^2$ such squares. Then indeed, if $\lfloor \frac nk\rfloor^2>n$, you can be sure that there exists a $k\times k$ that ...


1

$y$ and $z$ are $10$ and $15$, because from $9$, you can move to $100$ via $10$ in $1+T(10)$ steps or via $15$ in $1+T(15)$ steps. Taking the minimum gives $T(9)=1+\min(T(10),T(15))$. Now, we have $yz=10\cdot 15=150$. EDIT: A problem like this is usually solved using Dynamic Programming. In this case, we calculate all $T(i)$ starting at $T(100)$ and going ...


3

I assume that we are talking about real values, so that we may suppose $a_n\ge0$. And as you have already disposed of $a_n>1$, we may assume that $0\le a_n\le1$. So, let your $v_n$ be $\cos^2\theta_n$, that is, $$a_n=\cos^{4028}\theta_n\ .$$ Then $$\cos^2\theta_{n+1}=(2\cos^2\theta_n-1)^2=\cos^2(2\theta_n)\ .$$ The sequence will be periodic if and only ...


1

Total race = 1000m Length of pool = 50m To complete 1000m one has to complete 20 rounds of 50 each. They will meet at the same side only at 26th round as 2 & 3.25 LCM is 26 but we know race ends after 20 rounds. So they will meet at each round except the first as they are starting from the same side and Dexter will take an early lead. 20-1 = 19


1

As @Michael says, you can count the diagonals in one direction, and note that you can't have both ends of a long diagonal, which then reduces the number by $1$ As for configurations, note that the bishops on black squares and those on white squares are completely independent of each other. So, for example, the black-squared bishops could be on the first and ...


0

Count the number of NE-SW diagonals, including both corners.


0

Two of the given points and the center of the sphere determine a plane. Because the plane goes through the center of the sphere, it splits the sphere into two hemispheres. Because there are five points total, one of the closed hemispheres must contain four points; two on the boundary and two in the interior. QED Three points don't "form" a plane, but they ...


6

Since you have a quartic, there are potentially 4 real solutions. Note that any solution to $x = x^2 - 3x - 2$ is also a solution to the given equation. Hence, $x^2 - 4x - 2$ is a factor of the quartic. Now find the other factor, and solve both quadratics. Alternatively, see this almost 10 year old thread on the Art of Problem Solving Forum, or this ...


1

It seems like you're right, Kasper. A trigonometric substituition would solve the equation completely. I'll write the solution I arrived at: Finding inequalities is helpful to motivate the right subtituition. We know that both $\frac{1}{x^2}$ and $\frac{1}{(4-\sqrt{3}x)^2}$ are positive, so we can say that: $$\frac{1}{x^2}<1\Leftrightarrow ...


1

$$\begin{align} \frac1A={B+C\over BC-1} &\iff BC-AB-AC-1=0 \\&\iff (B-A)(C-A)=BC-BA-BC+A^2=A^2+1. \end{align}$$ Thus as Robert Isreal pointed out, to minimize $B+C$, you have to find a divisor of $A^2+1$ that is closest to $\sqrt{A^2+1}$, and let it be $B-A$.


2

Write your equation as $$B = \dfrac{AC+1}{C-A}$$ Let $C = A + x$, so this becomes $$ B =A + \dfrac{A^2+1}{x}$$ Thus $x$ must divide $A^2+1$, and $B + C = 2A + x + \dfrac{A^2+1}{x}$. You'll want a divisor of $A^2+1$ that is closest to $\sqrt{A^2+1}$ (on one side or the other).


1

After giving this more thought, I see that the answer is in fact 2, and that this is the correct answer for any right triangle. The diagram provided by Quang Hoang is very well done, and Quang's observation about the congruent triangles is insightful, but I don't see how it settles the issue. Here is my most recent response to the original question: ...


4

Since $2\cdot 31<63$, there are at least three numbers such that $a_i\equiv a_j\equiv a_k\pmod{31}$. Similarly, there are two numbers such that $a_m\equiv a_n\pmod{32}$. Of $a_i$, $a_j$ and $a_k$, take the ones of same parity. We are done.


1

I hope that the solution is clear from the picture: $\angle PAD=\angle PMB$ because $P$ lies on the circumcircle of $\triangle ACM$, similar for $\angle ADP=\angle PBM$ $AD=BM(=AM)$ as $\angle A=90^\circ$. Therefore $\triangle APD$ and $\triangle MPB$ are congruent.


1

Given that the sets are $S_1,\ldots,S_k$, with the inclusion-exclusion principle you can count the number of $k$-uples $(s_1,\ldots,s_k)$ in which $s_i$ belongs to $S_i$, then subtract the number of $k$-uples in which the same $s$ appears at least twice, then add the number of $k$-uples in which the same $s$ appears at least three times an so on. Hence we ...


8

This is pretty standard. Since the equation is symmetric in $A,B,C$, it suffices to find all solutions with $A \leq B \leq C$ and then by permutations you get all of them. Then $$ABC = A+B+C \leq C+C+C =3C$$ which implies $AB \leq 3$. Now, since $A \leq B$, there are only three possibilities such that $A B \leq 3$. In each of them $ABC=A+B+C$ becomes a ...


2

In your example, we could take $A=\{1,2,3,4\}$ and $B=\{1,2,3,5\}$. Then $$f(\{1,2,3\})=\min\{f(\{1,2,3,4\}),f(\{1,2,3,5\})$$The same holds for all other pairs of sets containing $\{1,2,3\}$. I'll call a function $f$ admissible if $$f(A\cap B)=\min\{f(A), f(B)\}$$ holds for all subset $A,B$ of $\{1,\cdots,n\}$. We will use the shorthand $[n]=\{1,\cdots,n\}$. ...


1

I started to really like this problem after the first month! We will prove that the $(n+2)$-gon is always the solution for $n$-triangles, by method of elimination. Definitions: $A_n$ is a solution satisfying the given conditions for $n$ triangles. By nature $A_n$ is a polygon or a collection of disjoint polygons. $h(A_n)$ will denote the hull of ...


5

I am lucky to study with two IMO medalists in the university. I would say that they are almost 50/50 talent & hard work. Their mind generally works a bit faster than mine; nevertheless when discussing problem sets, I notice that they spend almost as much time to solve a problem set as me. But the most important thing that I noticed is that they have ...


8

Short answer: it's a lot of practice. Math is like music, it requires tons of practice before you can reach superstar status. The most talented musicians are those who spend thousands of hours practicing their instrument. It's the same for mathematicians. Math and music actually stimulate/rely on similar areas of the brain and I've read that practicing one ...


6

This is an opinionated question. While true math "prodigies" may exist, I think that hard work and determination outweighs this quality. Also, understand that people don't "practice" to do well in Math Olympiads. People learn and practice math because they enjoy doing it, and through competitions one can evaluate oneself to see how well he has done. True ...


1

One solution is "clear" at $\frac{2}{\sqrt{3}}$. I was motivated to look for something like this by trying to write $1$ as the sum of two simple fractions, and the presence of $3$ and $4$. It's also halfway between the two vertical asymptotes of $\frac1{x^2}+\frac{1}{\left(4-\sqrt{3}x\right)^2}$, and in a sketch of that function (which clearly is never ...


1

If you do a substitution $t = x \sqrt 3$, you get $$ \frac 3 {t^2} + \frac 1{(4 - t)^2} = 1 \implies t^4 - 8t^3 + 12 t^2 + 24t - 48=0 $$ You can check that $t = 2$ is a solution, so $P_4(t) = (t-2)P_3(t)$, therefore $x = \frac 2{\sqrt 3}$ is a solution of the initial equations.



Top 50 recent answers are included