November 7th
Given a sequence $a_1,a_2,\ldots $ of non-negative real numbers satisfying the conditions: 1. $a_n + a_{2n} \geq 3n$; 2. $a_{n+1}+n \leq 2\sqrt{a_n \left(n+1\right)}$ for all $n\in\mathbb N$ (where $\mathbb N=\left\{1,2,3,...\right\}$). (1) Prove that the inequality $a_n \geq n$ holds for every $n \in \mathbb N$. (2) Give an example of such a sequence.
Click for solution (a) We have $a_{n+1} + n \leq 2\sqrt{a_n\cdot\left(n+1\right)}$ by our problem hypothesis. On the other hand, the AM-GM inequality yields $2\sqrt{a_n\cdot\left(n+1\right)} \leq a_n + \left(n+1\right)$. Thus, $a_{n+1} + n \leq a_n + \left(n+1\right)$, so that $a_{n+1} - a_n \leq 1$. Similarly, $a_{n+2} - a_{n+1} \leq 1$, $a_{n+3} - a_{n+2} \leq 1$, ..., $a_{2n-1} - a_{2n-2} \leq 1$, $a_{2n} - a_{2n-1} \leq 1$. Adding these inequalities together, we get $a_{2n} - a_n$ $= \left(a_{2n} - a_{2n-1}\right) + \left(a_{2n-1} - a_{2n-2}\right) + ... + \left(a_{n+3} - a_{n+2}\right) + \left(a_{n+2} - a_{n+1}\right) + \left(a_{n+1} - a_n\right)$ $\leq 1 + 1 + ... + 1 + 1 + 1 = n$, so that $a_n - a_{2n} \geq -n$. Adding this to $a_n + a_{2n} \geq 3n$, we get $2a_n \geq 2n$, so that $a_n \geq n$, what proves (a). (b) Just take $a_n = n+1$ for every n. The condition $a_n + a_{2n} \geq 3n$ is clearly satisfied ($\left(n+1\right)+\left(2n+1\right) = 3n+2 \geq 3n$), and the condition $a_{n+1} + n \leq 2\sqrt{a_n\cdot\left(n+1\right)}$ is also satisfied (even the $\leq$ sign can be replaced by the = sign, since $a_{n+1} + n = \left(n+2\right) + n = 2\left(n+1\right) = 2\sqrt{\left(n+1\right)^2}$ $= 2\sqrt{\left(n+1\right)\cdot\left(n+1\right)} = 2\sqrt{a_n\cdot\left(n+1\right)}$ ). Darij
Let $ P(x)$ be a polynomial with a non-negative coefficients. Prove that if the inequality $ P\left(\frac {1}{x}\right)P(x)\geq 1$ holds for $ x = 1$, then this inequality holds for each positive $ x$.
Click for solution Yes, I know, this was one of the proposed solutions. Another one, not using Cauchy, goes as follows: With $P\left( x\right) =\sum_{k=0}^{n}a_{k}x^{n}$, where all $a_{i}$ are positive, we have $P\left( x\right) \cdot P\left( \frac{1}{x}\right) =\sum_{k=0}^{n}a_{k}x^{k}\cdot \sum_{k=0}^{n}\frac{a_{k}}{x^{k}}=\sum_{0\leq i\leq n,\;0\leq j\leq n}\left( a_{i}x^{i}\cdot \frac{a_{j}}{x^{j}}\right) $ $=\sum_{0\leq i\leq n,\;0\leq j\leq n}\left( a_{i}a_{j}x^{i-j}\right) =\sum_{i=0}^{n}a_{i}^{2}+\sum_{0\leq i<j\leq n}\left( a_{i}a_{j}x^{i-j}+a_{j}a_{i}x^{j-i}\right)$ $=\sum_{i=0}^{n}a_{i}^{2}+\sum_{0\leq i<j\leq n}\left( a_{i}a_{j}\left( x^{i-j}+\frac{1}{x^{i-j}}\right) \right) $ $\geq \sum_{i=0}^{n}a_{i}^{2}+\sum_{0\leq i<j\leq n}\left( 2a_{i}a_{j}\right) \text{\ \ \ \ \ \ \ \ \ \ (since }x^{i-j}+\frac{1}{x^{i-j}}\geq 2\text{)} $ $=\left( \sum_{k=0}^{n}a_{k}\right) ^{2}=\left( P\left( 1\right) \right)^{2}\geq 1$ (but I guess it's just the same). Darij
Let $p, q, r$ be positive real numbers and $n$ a natural number. Show that if $pqr = 1$, then \[ \frac{1}{p^n+q^n+1} + \frac{1}{q^n+r^n+1} + \frac{1}{r^n+p^n+1} \leq 1. \]
Click for solution Here is my solution: The first thing that is clear is that it's enough to prove the inequality $\frac{1}{a+b+1} + \frac{1}{b+c+1} + \frac{1}{c+a+1} \leq 1$ for any three positive numbers a, b, c with abc = 1; then, by applying this to the numbers $a=p^n$, $b=q^n$, $c=r^n$ (note that pqr = 1 clearly implies $p^n q^n r^n = 1$), we will get the inequality $\frac{1}{p^n+q^n+1} + \frac{1}{q^n+r^n+1} + \frac{1}{r^n+p^n+1} \leq 1$ for every n. Proofs of $\frac{1}{a+b+1} + \frac{1}{b+c+1} + \frac{1}{c+a+1} \leq 1$ can be found in the thread http://www.mathlinks.ro/Forum/viewtopic.php?t=19469
Let $x_1$, $x_2$, ..., $x_n$ be real numbers with arithmetic mean $X$. Prove that there is a positive integer $K$ such that for any integer $i$ satisfying $0\leq i<K$, we have $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq X$. (In other words, prove that there is a positive integer $K$ such that the arithmetic mean of each of the lists $\left\{x_1,x_2,...,x_K\right\}$, $\left\{x_2,x_3,...,x_K\right\}$, $\left\{x_3,...,x_K\right\}$, ..., $\left\{x_{K-1},x_K\right\}$, $\left\{x_K\right\}$ is not greater than $X$.)
Click for solution By "shifting" the numbers $x_1$, $x_2$, ..., $x_n$ (i. e. adding one and the same real number to each of them), we can make the arithmetic mean X of these numbers become 0. Then, we have to prove that there is a positive integer K such that for any natural number i satisfying $1\leq i<K$, we have $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq 0$. But clearly, since K - i > 0, the inequality $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq 0$ is equivalent to $\sum_{j=i+1}^{K} x_j \leq 0$. And now everything is clear: Choose K in such a way that among all possible sums $S_k = \sum_{j=1}^{k} x_j$, for $1\leq k\leq n$, the sum $S_K$ is the minimal one. Then, for any natural number i satisfying $1\leq i<K$, we have $S_K \leq S_i$, and thus $\sum_{j=i+1}^{K} x_j = \sum_{j=1}^{K} x_j - \sum_{j=1}^{i} x_j = S_K - S_i \leq 0$, so that the number K satisfies the condition of the problem. PS This is actually Darij's solution, re-posted.
Determine the range of the following function defined for integer $k$, \[f(k)=(k)_3+(2k)_5+(3k)_7-6k\] where $(k)_{2n+1}$ denotes the multiple of $2n+1$ closest to $k$
A positive integer is written on each of the six faces of a cube. For each vertex of the cube we compute the product of the numbers on the three adjacent faces. The sum of these products is $1001$. What is the sum of the six numbers on the faces?
Click for solution Call a, b, c, d, e, f the positive integers written on the six faces of the cube; hereby, assume that the numbers a and b are written on opposite faces, so are the numbers c and d, and so are the numbers e and f. Since all numbers a, b, c, d, e, f are positive integers, they are all $\geq 1$, and thus the numbers a + b, c + d and e + f are positive integers $\geq 2$. Now, according to the problem, we have ace + acf + bce + bcf + bde + bdf + ade + adf = 1001. In other words, (a + b) (c + d) (e + f) = 1001. But since the canonical representation of 1001 is $1001 = 7 \cdot 11 \cdot 13$, the only way to represent 1001 as a product of three positive integers $\geq 2$ is $1001 = 7 \cdot 11 \cdot 13$. Since we know that the numbers a + b, c + d and e + f are positive integers $\geq 2$, we thus see that the numbers a + b, c + d, e + f equal to the numbers 7, 11, 13 in some order. Hence, the sum of the six numbers on the faces of the cube is a + b + c + d + e + f = (a + b) + (c + d) + (e + f) = 7 + 11 + 13 = 31. What we learn from this problem is that the identity ace + acf + bce + bcf + bde + bdf + ade + adf = (a + b) (c + d) (e + f) can sometimes be helpful in problems concerning numbers written on the faces of a cube, and that the canonical representation of 1001 can be of use not only in questions about digits. This is in fact Darij's solution, re-posted.
Find all sets $X$ consisting of at least two positive integers such that for every two elements $m,n\in X$, where $n>m$, there exists an element $k\in X$ such that $n=mk^2$.
Click for solution I will show that all such sets X are sets of the forms $\left\{a;\;a^3\right\}$, where a can be an arbitrary integer > 1. In fact, let X be a set consisting of at least two positive integers such that for every two elements m and n of the set X, where n > m, there exists an element k of X such that $n=mk^2$. In other words, we demand that for every two elements m and n of the set X, where n > m, the ratio $\frac{n}{m}$ is the square of an element of X. Write our set X in the form $\left\{a_1;\;a_2;\;...\right\}$, where $a_1 < a_2 < ...$. Hereby, the dots don't imply that the set X must be infinite; the set X can be finite as well. We don't know a priori how many elements X has, but we know that the set X has at least 2 elements, so that we can consider the smallest two elements $a_1$ and $a_2$ of X. First we show that 1 is not an element of X. In fact, if 1 were an element of x, it would be the smallest element of X; thus, we would have $a_1=1$, and since $a_2 > 1$, it would follow that $\frac{a_2}{1}$ is the square of an element of X; in other words, $a_2$ is the square of an element of X; but this latter element of X would be > 1 and $< a_2$ (this is because $a_2 > 1$), what contradicts the assumption that there is no element of X between $1=a_1$ and $a_2$ (in fact, remember that $a_1 < a_2 < ...$). Hence, 1 is not an element of X. Thus, all elements of X are > 1, i. e. we have $1 < a_1 < a_2 < ...$. Since $a_2 > a_1$, the ratio $\frac{a_2}{a_1}$ is the square of an element of X. But this latter element of X can only be $a_1$, since $\sqrt{\frac{a_2}{a_1}} \leq \frac{a_2}{a_1} < a_2$ (because of $1 < a_1$), and $a_1$ is the only element of the set X which is $< a_2$. Hence, $\frac{a_2}{a_1} = a_1^2$, and $a_2 = a_1^3$. If the set X has only 2 elements, then this already yields our family of solutions: $X = \left\{a;\;a^3\right\}$, where a is an arbitrary integer > 1. Now consider the case when the set X has at least 3 elements, i. e. there is an element $a_3$. Since $a_3 > a_1$, the ratio $\frac{a_3}{a_1}$ is the square of an element of X. But this latter element of X must be either $a_1$ or $a_2$, since $\sqrt{\frac{a_3}{a_1}} \leq \frac{a_3}{a_1} < a_3$ (this is because $1 < a_1$), and $a_1$ and $a_2$ are the only elements of the set X which are $< a_3$. In the case $\frac{a_3}{a_1}=a_1^2$, we get $a_3=a_1^3$, so that $a_3=a_2$, contradicting with $a_2 < a_3$. Hence, only the case $\frac{a_3}{a_1}=a_2^2$ remains possible; since $a_2=a_1^3$, we thus have $a_3=a_1a_2^2=a_1\left(a_1^3\right)^2=a_1^7$. But on the other hand, since $a_3 > a_2$, the ratio $\frac{a_3}{a_2}$ is the square of an element of X. But $\frac{a_3}{a_2} = \frac{a_1^7}{a_1^3} = a_1^4 = \left(a_1^2\right)^2$, and $a_1^2$ is not an element of X (in fact, if it would be an element of X, it would lie between $a_1$ and $a_3 = a_1^7$, so it would be equal to $a_2$, but $a_2 = a_1^3 \neq a_1^2$). So we get a contradiction, and hence, the set X cannot have more than 2 elements. And thus, the family of solutions we found above, $X = \left\{a;\;a^3\right\}$ for $a \in \left\{2;\;3;\;4;\;...\right\}$, yields all solutions. This is in fact Darij's solution, re-posted.
Let $f\left(x\right)$ be a non-constant polynomial with integer coefficients, and let $u$ be an arbitrary positive integer. Prove that there is an integer $n$ such that $f\left(n\right)$ has at least $u$ distinct prime factors and $f\left(n\right) \neq 0$.
Click for solution My solution: I will reduce the problem to the following lemma: Lemma 1. The set of all primes p such that there is an integer x satisfying p | f(x) is infinite. This Lemma will be proved later. Now I will solve the problem with the help of this lemma. Since the set of all primes p such that there is an integer x satisfying p | f(x) is infinite, we can take u primes $p_1$, $p_2$, ..., $p_u$ out of this set, and there are some integers $x_1$, $x_2$, ..., $x_u$ such that $p_i \mid f\left(x_i\right)$ for every i with $1\leq i\leq u$. Now, if $y_i$ is an integer such that $y_i \equiv x_i \; \mathrm{mod} \; p_i$, then $p_i \mid y_i-x_i$, while $y_i-x_i \mid f\left(y_i\right)-f\left(x_i\right)$ (this is just because f(x) is a polynomial with integer coefficients), so that $p_i \mid f\left(y_i\right)-f\left(x_i\right)$, and since $p_i \mid f\left(x_i\right)$, this yields $p_i \mid f\left(y_i\right)$. Now, since the numbers $p_1$, $p_2$, ..., $p_u$ are prime and thus pairwisely coprime, the Chinese Remainder Theorem shows that there are infinitely many integers Y such that $Y \equiv x_i \; \mathrm{mod} \; p_i$ for every i with $1\leq i\leq u$. Among these infinitely many integers Y, there is at least one such that $f\left(Y\right) \neq 0$ (else, the polynomial f(x) would have infinitely many zeros, what is not possible for a non-constant polynomial). Denote this number Y satisfying $f\left(Y\right) \neq 0$ by n. Hence, for these number n, we have $f\left(n\right) \neq 0$ and $n \equiv x_i \; \mathrm{mod} \; p_i$ for every i such that $1\leq i\leq u$. But the latter congruence yields $p_i \mid f\left(n\right)$ for every i with $1\leq i\leq u$. In other words, the number f(n) is divisible by all the u primes $p_1$, $p_2$, ..., $p_u$, and hence, this number f(n) has at least u prime factors. This solves the problem. Now let's prove Lemma 1. Assume the contrary, i. e. assume that the set of all primes p such that there is an integer x satisfying p | f(x) is finite. Let this set be $\left\{p_1;\;p_2;\;...;\;p_s\right\}$, where s is a positive integer. Then, for every integer x, the value f(x) has the form $f\left(x\right)= \pm p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$, where $e_1$, $e_2$, ..., $e_s$ are nonnegative integers. Hence, of course, $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$. On the other hand, let our polynomial f(x) be $f\left(x\right) = a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0$, with integer coefficients $a_m$, $a_{m-1}$, ..., $a_1$, $a_0$. Hereby, of course, m is the degree of our polynomial. Since a polynomial of degree m cannot achieve one and the same value more than m times (without being a constant polynomial), our polynomial f(x) achieves every of its values at most m times. Clearly, this yields that the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times (in fact, for each value v, we have f(x) = v for at most m different values of x and we have f(x) = -v for at most m different values of x, so that we can have $\left|f\left(x\right)\right| = v$ for at most 2m different values of x). Let B be an arbitrary positive integer. Then, for every positive integer x with $x\leq 2mB$, the triangle inequality shows that $\left|f\left(x\right)\right| = \left|a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0\right|$ $\leq \left|a_m x^m \right| + \left|a_{m-1} x^{m-1}\right| + ... + \left|a_1 x \right| + \left|a_0\right|$ $= \left|a_m \right| x^m + \left|a_{m-1}\right| x^{m-1} + ... + \left|a_1\right| x + \left|a_0\right|$ (since x is positive) $\leq \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$ (since $x\leq 2mB$). In other words, we have $\left|f\left(x\right)\right| \leq t\left(B\right)$, where $t\left(B\right) = \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$. Of course, t(B) is a polynomial of B, and actually a polynomial which is always nonnegative for B > 0. This will become important later. Now, consider the interval [1; 2mB]. To each of the 2mB integers in this interval, there corresponds a value of the function $\left|f\left(x\right)\right|$ at this integer. Since the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times, at least $\frac{2mB}{2m}=B$ of these values are different. But every such value is $\leq t\left(B\right)$ on the one hand, and on the other hand, every such value can be written in the form $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$. Hence, there are at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$. Let r be such a number $r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$, with $r\leq t\left(B\right)$. Then, if we would have $e_1 > \log_2 t\left(B\right)$, we would get $r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s} \geq p_1^{e_1} > p_1^{\log_2 t\left(B\right)}$ $\geq 2^{\log_2 t\left(B\right)}$ (since $p_1\geq 2$, as any prime is $\geq 2$) $=t\left(B\right)$, what contradicts $r\leq t\left(B\right)$. Thus, $e_1 \leq \log_2 t\left(B\right)$. Similarly, $e_2 \leq \log_2 t\left(B\right)$, ..., $e_s \leq \log_2 t\left(B\right)$. Therefore, all the integers $e_1$, $e_2$, ..., $e_s$ lie in the interval $\left[0;\;\log_2 t\left(B\right)\right]$. Consequently, the number of all possible numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$ doesn't exceed $\left(\log_2 t\left(B\right) +1\right)^s$. But remember that we have found at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$. Hence, $B \leq \left(\log_2 t\left(B\right) +1\right)^s$. And this holds for every positive integer B ! But it is not hard to show that, for every polynomial t(B) and for every integer s, there is a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$. In fact, this is equivalent to $\sqrt[s]{B_1} > \log_2 t\left(B_1\right) +1$, what, using the substitution $C_1=\sqrt[s]{B_1}$, takes the form $C_1 > \log_2 t\left(C_1^s\right) +1$; since $\log_2 t\left(C_1^s\right) + 1 = \log_2 \left(2t\left(C_1^s\right)\right)$, this is equivalent to $C_1 > \log_2 \left(2t\left(C_1^s\right)\right)$. And this is clear, since $2t\left(C_1^s\right)$ is a polynomial of $C_1$ (since t is a polynomial), and a linear function always overtakes the logarithm of a polynomial. Hence, we have found a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$, contradicting our previous result $B \leq \left(\log_2 t\left(B\right) +1\right)^s$ for every positive integer B; hence, we have a contradiction, and Lemma 1 is proven. My apologies for the style. It's just the first time I solve and write down the solution of a slightly nontrivial number theory problem.
A set $S$ of $n-1$ natural numbers is given ($n\ge 3$). There exist at least at least two elements in this set whose difference is not divisible by $n$. Prove that it is possible to choose a non-empty subset of $S$ so that the sum of its elements is divisible by $n$.
Click for solution here's a generalization: lemma: let $T$ be a set of $k$ natural numbers. if there is no way to choose a non-empty subset of $T$ such that the sum of elements is divisible by $n$, then there are at least $k$ different sums of elements of non-empty subsets of $T$ modulo $n$ and it are $k$ iff all elements of $T$ are equal modulo $n$. proof: reduce everything modulo $n$. we don't get a zero by the condition; let the elements be $a_1,...,a_k$. if $a_1+...+a_i=a_1+...+a_j$ for some $i\neq j$, we would have a zero sum. thus, all the sums $a_1+...+a_i$ are different giving $k$ different values. now assume it are only $k$. if $a_2\neq a_1$ we have $a_2=a_1+...+a_i$ for some $i\geq 2$ giving a zero sum, contradiction; thus $a_2=a_1$. by reordering the numbers, we get all numbers to be equal. now, let $T=S$ where $k=n-1$. the lemma implies that there are at least $n$ different sums of non-empty subsets of $S$; by the pigeonhole principle, we get a zero sum.
Is there an infinite sequence of prime numbers $p_1$, $p_2$, $\ldots$, $p_n$, $p_{n+1}$, $\ldots$ such that $|p_{n+1}-2p_n|=1$ for each $n \in \mathbb{N}$?
Click for solution This is rather easy. Take $p>3$ to be a term of such a sequence. If it's $3k+2$, then the next one has to be $2p+1$, and the next one has to be $2(2p+1)+1$, and so on (all the terms are of the form $3k+2$). Something similar happens if $p=3k+1$, so let's assume $p=3k+2$ (the other case is similar). The terms of the sequence are of the form $2^np+2^n-1$. If $n=p-1$, then $p|2^np+2^n-1$, so this term of the sequence is not a prime, which yields a contradiction, so the answer is "no" (no such sequences exist).
Given a table $m\times n$, in each cell of which a number $+1$ or $-1$ is written. It is known that initially exactly one $-1$ is in the table, all the other numbers being $+1$. During a move, it is allowed to chose any cell containing $-1$, replace this $-1$ by $0$, and simultaneously multiply all the numbers in the neighbouring cells by $-1$ (we say that two cells are neighbouring if they have a common side). Find all $(m,n)$ for which using such moves one can obtain the table containing zeros only, regardless of the cell in which the initial $-1$ stands.
There are $2n$ different numbers in a row. By one move we can interchange any two numbers or interchange any $3$ numbers cyclically (choose $a,b,c$ and place $a$ instead of $b$, $b$ instead of $c$, $c$ instead of $a$). What is the minimal number of moves that is always sufficient to arrange the numbers in increasing order ?
Click for solution 1) One can easy prove that it is possible to properly place at least two numbers. So we need at most $n$ interchanges. 2) Consider permutation $(2n,2n-1,n+1,n,...,2,1)$. Divide row into two parts: first $n$ numbers and second $n$ numbers. Then there are $2n$ numbers, which are not in parts they supposed to be. Moreover, each turn we can place at most two numbers into appropriate part. So we need at least $n$ turns.
The $25$ member states of the European Union set up a committee with the following rules: 1) the committee should meet daily; 2) at each meeting, at least one member should be represented; 3) at any two different meetings, a different set of member states should be represented; 4) at $n^{th}$ meeting, for every $k<n$, the set of states represented should include at least one state that was represented at the $k^{th}$ meeting. For how many days can the committee have its meetings?
Click for solution looks like we're interested in the maximal number of subsets of a set with $n$ elements (here $n=25$) s.t. each two have non-void intersection. I think this number is $2^{n-1}$. First of all, $2^{n-1}$ works, since we can take all the sets having containing a certain element. On the other hand, this number is maximal, because if we have a set, we exclude its complement, so the number of sets we don't have is at least as large as the number of sets we have, meaning that our family of chosen sets has at most $\frac{\mathcal P}2=2^{n-1}$ elements ($\mathcal P$ is the set of subsets of our set). Am I wrong?
We say that a pile is a set of four or more nuts. Two persons play the following game. They start with one pile of $n \geq 4$ nuts. During a move a player takes one of the piles that they have and split it into two nonempty sets (these sets are not necessarily piles, they can contain arbitrary number of nuts). If the player cannot move, he loses. For which values of $n$ does the first player have a winning strategy?
Click for solution Call a set of piles a 'game'. If the player moving next in a game can win, the game is called 'winning' otherwise 'losing'. We have a clue observation: If set A is losing and set B is losing then the union of these two sets is also losing. This observation helps us proving by induction that if the set consists of two $piles$ containing the same number of nuts $mod$ $4$ then it's losing. Particularly this proves Myth's conjencture: B can move $4k+2,4l+1$ into the losing $4k+1,4l+1$. But Myth's conjencture proves that the losing piles are only those with $4k+3$ nuts. QED I think
A circle is divided into $13$ segments, numbered consecutively from $1$ to $13$. Five fleas called $A,B,C,D$ and $E$ are sitting in the segments $1,2,3,4$ and $5$. A flea is allowed to jump to an empty segment five positions away in either direction around the circle. Only one flea jumps at the same time, and two fleas cannot be in the same segment. After some jumps, the fleas are back in the segments $1,2,3,4,5$, but possibly in some other order than they started. Which orders are possible ?
Click for solution I remember having solved this before the crash. Represent the motion on a circle numbered differently, so that each movement on the initial circle is translated to the second circle as one step (instead of $5$ steps at a time). We number the $13$ segmnents of the new circle in the following way, in a counterclockwise direction: $1,6,11,3,8,13,5,10,2,7,12,4,9$. We can now see that because of the constraint that no two fleas can share a square, the fleas cannot jump over one another, so the only possible permutations are the cyclic permutations, and only those.
Through a point $P$ exterior to a given circle pass a secant and a tangent to the circle. The secant intersects the circle at $A$ and $B$, and the tangent touches the circle at $C$ on the same side of the diameter through $P$ as the points $A$ and $B$. The projection of the point $C$ on the diameter is called $Q$. Prove that the line $QC$ bisects the angle $\angle AQB$.
Click for solution Let the lines CQ and AB meet at X. From the definition of the line CQ, it directly follows that the line CQ is the polar of the point P with respect to our circle. Hence, by the harmonic property of a polar, the point X, where this line CQ meets the line AB, is the harmonic conjugate of the point P with respect to the segment AB. In other words, the points P and X divide the segment AB harmonically. Hence, the rays QP and QX divide the angle formed by the rays QA and QB harmonically. But on the other hand, we know that the rays QP and QX are perpendicular (in fact, the ray QP is the diameter of the circle through the point P, and the ray QX is the ray CQ). It is well-known that if two perpendicular rays divide an angle harmonically, then these two rays are the two angle bisectors (internal and external) of the angle. Hence, the rays QP and QX are the two angle bisectors of the angle AQB. Since the ray QX is the ray QC, it follows that the ray QC bisects the angle AQB. Proof complete. This is in fact Darij's solution, re-posted.
Consider a rectangle with sidelengths 3 and 4, pick an arbitrary inner point on each side of this rectangle. Let $x, y, z$ and $u$ denote the side lengths of the quadrilateral spanned by these four points. Prove that $25 \leq x^2+y^2+z^2+u^2 \leq 50$.
Click for solution Let ABCD be our rectangle, with AB = CD = 3 and BC = DA = 4, and let X, Y, Z, U be the four inner points of its sides AB, BC, CD, DA, respectively, such that XY = x, YZ = y, ZU = z and UX = u. Call AX = a, BY = b, CZ = c and DU = d. Then, BX = AB - AX = 3 - a, CY = BC - BY = 4 - b, DZ = CD - CZ = 3 - c and AU = DA - DU = 4 - d. The Pythagoras theorem, applied to the right-angled triangle XBY, yields $x^2=XY^2=BX^2+BY^2=\left(3-a\right)^2+b^2$. Similarly, $y^2=\left(4-b\right)^2+c^2$, $z^2=\left(3-c\right)^2+d^2$ and $u^2=\left(4-d\right)^2+a^2$. Hence, $x^2+y^2+z^2+u^2$ $=\left(\left(3-a\right)^2+b^2\right)+\left(\left(4-b\right)^2+c^2\right)+\left(\left(3-c\right)^2+d^2\right)+\left(\left(4-d\right)^2+a^2\right)$ $=\left(\left(3-a\right)^2+a^2\right)+\left(\left(4-b\right)^2+b^2\right)+\left(\left(3-c\right)^2+c^2\right)+\left(\left(4-d\right)^2+d^2\right)$. Now, since a = AX, and X is an inner point of the side AB of the rectangle, we have 0 < a < 3. Hence, AM-QM yields $\frac{\left(3-a\right)^2+a^2}{2}\geq\left(\frac{\left(3-a\right)+a}{2}\right)^2$ and thus $\left(3-a\right)^2+a^2 \geq 2\left(\frac{\left(3-a\right)+a}{2}\right)^2 = 2\left(\frac32\right)^2 = \frac92$. Similarly, $\left(4-b\right)^2+b^2 \geq 8$, $\left(3-c\right)^2+c^2 \geq \frac92$ and $\left(4-d\right)^2+d^2 \geq 8$, so that $x^2+y^2+z^2+u^2$ $=\left(\left(3-a\right)^2+a^2\right)+\left(\left(4-b\right)^2+b^2\right)+\left(\left(3-c\right)^2+c^2\right)+\left(\left(4-d\right)^2+d^2\right)$ $\geq \frac92+8+\frac92+8=25$. This proves the left part of the inequality $25 \leq x^2+y^2+z^2+u^2 \leq 50$. Remains to prove the right part. Since 0 < a < 3, we have $9-\left(\left(3-a\right)^2+a^2\right) = 2a\left(3-a\right) > 0$, so that $\left(3-a\right)^2+a^2 < 9$. Similarly, $\left(4-b\right)^2+b^2 < 16$, $\left(3-c\right)^2+c^2 < 9$ and $\left(4-d\right)^2+d^2 < 16$. Thus, $x^2+y^2+z^2+u^2$ $=\left(\left(3-a\right)^2+a^2\right)+\left(\left(4-b\right)^2+b^2\right)+\left(\left(3-c\right)^2+c^2\right)+\left(\left(4-d\right)^2+d^2\right)$ $< 9+16+9+16=50$. This proves even more than the right part of the inequality $25 \leq x^2+y^2+z^2+u^2 \leq 50$; this even proves that the right $\leq$ sign can be replaced by an < sign. (In fact, the problem proposer probably used the $\leq$ sign since he allowed the points X, Y, Z, U to coincide with the vertices of the rectangle; in the solution above, I don't allow this). This is in fact Darij's solution, re-posted.
A ray emanating from the vertex $A$ of the triangle $ABC$ intersects the side $BC$ at $X$ and the circumcircle of triangle $ABC$ at $Y$. Prove that $\frac{1}{AX}+\frac{1}{XY}\geq \frac{4}{BC}$.
Click for solution We have to prove $\frac{1}{AX}+\frac{1}{XY}\geq \frac{4}{BC}$. After multiplication with BC, this inequality takes the form $\frac{BC}{AX}+\frac{BC}{XY}\geq 4$. But BC = BX + CX; thus, we can rewrite this inequality as $\frac{BX}{AX}+\frac{CX}{AX}+\frac{BX}{XY}+\frac{CX}{XY} \geq 4$. But this is clear, since $BX\cdot CX=AX\cdot XY$ by the Intersecting Chords Theorem, so that $\frac{BX\cdot CX}{AX\cdot XY}=1$, and thus AM-GM yields $\frac{BX}{AX}+\frac{CX}{AX}+\frac{BX}{XY}+\frac{CX}{XY} \geq 4\sqrt[4]{\frac{BX}{AX}\cdot\frac{CX}{AX}\cdot\frac{BX}{XY}\cdot\frac{CX}{XY}}$ $=4\sqrt[4]{\left(\frac{BX\cdot CX}{AX\cdot XY}\right)^2}=4\sqrt[4]{1^2}=4$.
Let $D$ be the midpoint of the side $BC$ of a triangle $ABC$. Let $M$ be a point on the side $BC$ such that $\angle BAM = \angle DAC$. Further, let $L$ be the second intersection point of the circumcircle of the triangle $CAM$ with the side $AB$, and let $K$ be the second intersection point of the circumcircle of the triangle $BAM$ with the side $AC$. Prove that $KL \parallel BC$.
Click for solution My solution: Since < BAM = < DAC, the line AM is the reflection of the line AD in the angle bisector of the angle CAB. But the line AD is a median of triangle ABC; hence, the line AM is a symmedian of triangle ABC. Since a symmedian from a vertex of a triangle divides the opposite side in the ratio of the squares of the two adjacent sides, we have $\frac{BM}{CM} = \frac{BA^2}{CA^2}$. On the other hand, since the points A, C, L and M lie on one circle, the Intersecting Chords Theorem yields $BM\cdot BC = BL\cdot BA$, and since the points A, B, K and M lie on one circle, the Intersecting Chords Theorem yields $CM\cdot CB = CK\cdot CA$. Hence, $\frac{BA^2}{CA^2} = \frac{BM}{CM} = \frac{BM\cdot BC}{CM\cdot CB} = \frac{BL\cdot BA}{CK\cdot CA}$. Consequently, $\frac{BA}{CA} = \frac{BL}{CK}$. This yields KL || BC after Thales. PS. I was asked about how to prove the following fact which I used: darij grinberg wrote: Since a symmedian from a vertex of a triangle divides the opposite side in the ratio of the squares of the two adjacent sides, we have $\frac{BM}{CM} = \frac{BA^2}{CA^2}$. Now I posted a proof of this fact at http://www.mathlinks.ro/Forum/viewtopic.php?t=58872 (post #1 Theorem 5). To make it short, it is a particular case of the Steiner theorem, which tells that if M and N are two points on the line BC such that the lines AM and AN are isogonal cevians with respect to triangle ABC, then $\frac{BM}{CM}\cdot\frac{BN}{CN}=\frac{BA^2}{CA^2}$. Darij
Three fixed circles pass through the points $A$ and $B$. Let $X$ be a variable point on the first circle different from $A$ and $B$. The line $AX$ intersects the other two circles at $Y$ and $Z$ (with $Y$ between $X$ and $Z$). Show that the ratio $\frac{XY}{YZ}$ is independent of the position of $X$.