Found problems: 85335
Consider a $25\times25$ chessboard with cells $C(i,j)$ for $1\le i,j\le25$. Find the smallest possible number $n$ of colors with which these cells can be colored subject to the following condition: For $1\le i<j\le25$ and for $1\le s<t\le25$, the three cells $C(i,s)$, $C(j,s)$, $C(j,t)$ carry at least two different colors.
(Proposed by Gerhard Woeginger, Austria)
The angles $\alpha, \beta, \gamma$ of a triangle are in arithmetic progression. If $\sin 20\alpha$, $\sin 20\beta$, and $\sin 20\gamma$ are in arithmetic progression, how many different values can $\alpha$ take?
$
\textbf{(A)}\ 1
\qquad\textbf{(B)}\ 2
\qquad\textbf{(C)}\ 3
\qquad\textbf{(D)}\ 4
\qquad\textbf{(E)}\ \text{None of the above}
$
Prove that $27 195^8 - 10 887^8 + 10 152^8$ is divisible by $26 460$.
For any non-negative integer $n$, we say that a permutation $(a_0,a_1,...,a_n)$ of $\{0,1,..., n\} $ is quadratic if $k + a_k$ is a square for $k = 0, 1,...,n$. Show that for any non-negative integer $n$, there exists a quadratic permutation of $\{0,1,..., n\}$.
Given the tetrahedron $ABCD$ whose edges $AB$ and $CD$ have lengths $a$ and $b$ respectively. The distance between the skew lines $AB$ and $CD$ is $d$, and the angle between them is $\omega$. Tetrahedron $ABCD$ is divided into two solids by plane $\epsilon$, parallel to lines $AB$ and $CD$. The ratio of the distances of $\epsilon$ from $AB$ and $CD$ is equal to $k$. Compute the ratio of the volumes of the two solids obtained.
Let $f: \ [0,\ 1] \rightarrow \mathbb{R}$ be an increasing function satisfying the following conditions:
a) $f(0)=0$;
b) $f\left(\frac{x}{3}\right)=\frac{f(x)}{2}$;
c) $f(1-x)=1-f(x)$.
Determine $f\left(\frac{18}{1991}\right)$.
A and B play tennis. The player to first win at least four points and at least two more than the other player wins. We know that A gets a point each time with probability $p\le \frac12$, independent of the game so far. Prove that the probability that A wins is at most $2p^2$.
Let $ N $ be a positive integer. A set $ S \subset \{ 1, 2, \cdots, N \} $ is called [i]allowed[/i] if it does not contain three distinct elements $ a, b, c $ such that $ a $ divides $ b $ and $ b $ divides $c$. Determine the largest possible number of elements in an allowed set $ S $.
$f:\mathbb{R}^2 \to \mathbb{R}^2$ is injective and surjective. Distance of $X$ and $Y$ is not less than distance of $f(X)$ and $f(Y)$. Prove for $A$ in plane:
\[ S(A) \geq S(f(A))\]
where $S(A)$ is area of $A$
Last year, Master Cheung is famous for multi-rotation. This year, he comes to DAMO to make noodles for sweeping monk. One day, software engineer Xiao Li talks with Master Cheung about his job. Xiao Li mainly researches and designs the algorithm to adjust the paramter of different kinds of products. These paramters can normally be obtainly by minimising loss function $f$ on $\mathbb{R}^n$. In the recent project of Xiao Li, this loss function is obtained by other topics. For safety consideration and technique reasons, this topic makes Xiao Li difficult to find the interal details of the function. They only provide a port to calculate the value of $f(\text x)$ for any $\text x\in\mathbb{R}^n$. Therefore, Xiao Li must only use the value of the function to minimise $f$. Also, every times calculating the value of $f$ will use a lot of calculating resources. It is good to know that the dimension $n$ is not very high (around $10$). Also, colleague who provides the function tells Xiao Li to assume $f$ is smooth first.
This problem reminds Master Cheung of his antique radio. If you want to hear a programme from the radio, you need to turn the knob of the radio carefully. At the same time, you need to pay attention to the quality of the radio received, until the quality is the best. In this process, no one knows the relationship between the angle of turning the knob and the quality of the radio received. Master Cheung and Xiao Li realizes that minimising $f$ is same as adjusting the machine with multiple knobs: Assume every weight of $\text x$ is controlled by a knob. $f(\text x)$ is a certain performance of the machine. We only need to adjust every knobs again and again and observes the value of $f$ in the same time. Maybe there is hope to find the best $\text x$. As a result, two people suggest an iteration algorithm (named Automated Forward/Backward Tuning, $\text{AFBT}$, to minimise $f$. In $k$-th iteration, the algorithm adjusts the individual weight of $\text{x}_k$ to $2n$ points $\{\text x_k\pm t_k\text e^i:i=1,...,n\}$, where $t_k$ is the step size; then, make $y_k$ be the smallest one among the value of the function of thosse points. Then check if $\text y_k$ sufficiently makes $f$ decrease; then, take $\text x_{k+1}=\text y_k$, then make the step size doubled. Otherwise, make $\text x_{k+1}=\text x_k$ and makes the step size decrease in half. In the algorithm, $\text e^i$ is the $i$-th coordinate vector in $\mathbb{R}^n$. The weight of $i$-th is $1$. Others are $0$; $\mathbf{1}(\cdot)$ is indicator function. If $f(\text x_k)-f(\text y_k)$ is at least the square of $t_k$, then take the value of $\mathbf{1}(f(\text k)-f(y_k)\ge t^2_k)$ as $1$. Otherwise, take it as $0$.
$\text{AFBT}$ algorithm
Input $\text{x}_0\in \mathbb{R}^n$, $t_0>0$. For $k=0, 1, 2, ...$, perform the following loop:
1: #Calculate loss function.
2: $s_k:=\mathbb{1}[f(\text{x}_k)-f(\text{y}_k)\ge t^2_k]$ #Is it sufficiently decreasing? Yes: $s_k=1$; No: $s_k=0$.
3: $\text{x}_{k+1}:=(1-s_k)\text{x}_k+s_k\text{y}_k$ #Update the point of iteration.
4: $t_{k+1}:=2^{2S_k-1}t_k$ #Update step size. $s_k=1$: Step size doubles; $s_k=0$: Step size decreases by half.
Now, we made assumption to the loss function $f:\mathbb{R}^n\to \mathbb{R}$.
Assumption 1. Let $f$ be a convex function. For any $\text{x}, \text{y}\in \mathbb{R}^n$ and $\alpha \in [0, 1]$, we have $f((1-\alpha)\text{x}+\text{y})\le (1-\alpha)f(\text{x})+\alpha f(\text{y})$.
Assumption 2. $f$ is differentiable on $\mathbb{R}^n$ and $\nabla f$ is L-Lipschitz continuous on $\mathbb{R}^n$.
Assumption 3. The level set of $f$ is bounded. For any $\lambda\in\mathbb{R}$, set $\{\text x\in \mathbb{R}^n:f(\text x)\le \lambda\}$ is all bounded.
Based on assumption 1 and 2, we can prove that $\left\langle \nabla f(\text x),\text y-\text x \right\rangle \le f(\text y)-f(\text x)\le \left\langle \nabla f(\text x),\text y-\text x\right\rangle+\frac{L}{2}||\text x-\text y||^2$
You can refer to any convex analysis textbook for more properties of convex function.
Prove that under the assumption 1-3, for $AFBT$, $\lim_{k \to \infty}f(\text{x}_k)=f^*$
Arthur, Bob, and Carla each choose a three-digit number. They each multiply the digits of their own numbers. Arthur gets 64, Bob gets 35, and Carla gets 81. Then, they add corresponding digits of their numbers together. The total of the hundreds place is 24, that of the tens place is 12, and that of the ones place is 6. What is the difference between the largest and smallest of the three original numbers?
[i]Proposed by Jacob Weiner[/i]
A tetrahedron $ABCD$ is divided into five polyhedra so that each face of the tetrahedron is a face of (exactly) one polyhedron, and that the intersection of any two of the polyhedra is either a common vertex, a common edge, or a common face. What is the smallest possible sum of the numbers of faces of the five polyhedra?
Let p(x) be the polynomial $x^3 + 14x^2 - 2x + 1$. Let $p^n(x)$ denote $p(p^(n-1)(x))$. Show that there is an integer N such that $p^N(x) - x$ is divisible by 101 for all integers x.
Given a tetrahedron $ABCD$ and inside the tetrahedron points $K, L, M, N$ that do not lie on a plane. Denote also the centroids of $P$, $Q$, $R$, $S$ of the tetrahedrons $KBCD$, $ALCD$, $ABMD$, $ABCN$ do not lie on a plane. Let $T$ be the centroid of the tetrahedron ABCD, $T_o$ be the centroid of the tetrahedron $PQRS$ and $T_1$ be the centroid of the tetrahedron $KLMN$.
a) Prove that the points $T, T_0, T_1$ lie in one straight line.
b) Determine the ratio $|T_0T| : |T_0 T_1|$.
Find the maximum value of $M$ for which for all positive real numbers $a, b, c$ we have
\[ a^3+b^3+c^3-3abc \geq M(ab^2+bc^2+ca^2-3abc) \]
Tom throws a football to Wes, who is a distance $l$ away. Tom can control the time of flight $t$ of the ball by choosing any speed up to $v_{\text{max}}$ and any launch angle between $0^\circ$ and $90^\circ$. Ignore air resistance and assume Tom and Wes are at the same height. Which of the following statements is [b]incorrect[/b]?
$ \textbf{(A)}$ If $v_{\text{max}} < \sqrt{gl}$, the ball cannot reach Wes at all. $ \\ $
$ \textbf{(B)}$ Assuming the ball can reach Wes, as $v_{\text{max}}$ increases with $l$ held fixed, the minimum value of $t$ decreases. $ \\ $
$ \textbf{(C)}$ Assuming the ball can reach Wes, as $v_{\text{max}}$ increases with $l$ held fixed, the maximum value of $t$ increases. $ \\ $
$ \textbf{(D)}$ Assuming the ball can reach Wes, as $l$ increases with $v_{\text{max}}$ held fixed, the minimum value of $t$ increases. $ \\ $
$ \textbf{(E)}$ Assuming the ball can reach Wes, as $l$ increases with $v_{\text{max}}$ held fixed, the maximum value of $t$ increases.
For which complex numbers $\alpha$ does there exist a completely multiplicative, complex-valued arithmetic function $f$ such that
\[
\sum_{n<x}f(n)=\alpha x+O(1)\,\,?
\]
Find all injective functions $ f:\mathbb{N} \to \mathbb{N} $ such that $$ f^{f\left(a\right)}\left(b\right)f^{f\left(b\right)}\left(a\right)=\left(f\left(a+b\right)\right)^2 $$ holds for all $ a,b \in \mathbb{N} $. Note that $ f^{k}\left(n\right) $ means $ \underbrace{f(f(\ldots f}_{k}(n) \ldots )) $
There are $2002$ employees in a bank. All the employees came to celebrate the bank's jubilee and were seated around one round table. It is known that the difference in salaries of any two adjacent employees is $2$ or $3$ dollars. Find the maximal difference in salaries of two employees, if it is known all salaries are different.
Abimbola plays a game with a coin. He tosses the coin a number of times, and records whether each toss was a "heads" or "tails". He stops tossing the coin as soon as he tosses an odd number of heads in a row, followed by a tails. (Note that he stops if the number of heads since the previous time that he tosses tails is odd, and he then tosses another tails. If he has not tossed tails previously, then he stops if the total number of heads is odd, and he then tosses tails.) How many different sequences of coin tosses are there such that he stops after the $n^\text{th}$ coin toss?
Let $\bigtriangleup ABC$ be an acute triangle with a point $D$ on side $BC$. Let $J$ be a point on side $AC$ such that $\angle BAD = 2\angle ADJ$, and $\omega$ be the circumcircle of triangle $\bigtriangleup CDJ$. The line $AD$ intersects $\omega$ again at a point $P$, and $Q$ is the feet of the altitude from $J$ to $AB$.\\
Prove that if $JP = JQ$, then the line perpendicular to $DJ$ through $A$ is tangent to $\omega$.
[i]Proposed by Ivan Chan - Malaysia[/i]
In natural numbers $m,n$ Solve : $n(n+1)(n+2)(n+3)=m(m+1)^2(m+2)^3(m+3)^4$
Each edge of a convex polyhedron is shifted such that the obtained edges form the frame of another convex polyhedron. Are these two polyhedra necessarily congruent?
Let $S_n=\sum_{k=0}^{n}\frac{1}{\sqrt{k+1}+\sqrt{k}}$. What is the value of $\sum_{n=1}^{99}\frac{1}{S_n+S_{n-1}}$ ?
A road company is trying to build a system of highways in a country with $21$ cities. Each highway runs between two cities. A trip is a sequence of distinct cities $C_1,\dots, C_n$, for which there is a highway between $C_i$ and $C_{i+1}$. The company wants to fulfill the following two constraints:
(1) for any ordered pair of distinct cities $(C_i, C_j)$, there is exactly one trip starting at $C_i$ and ending at $C_j$.
(2) if $N$ is the number of trips including exactly 5 cities, then $N$ is maximized.
What is this maximum value of $N$?