We have a machine that has an input and an output. The input is a letter from the finite set $I$ and the output is a lamp that at each moment has one of the colors of the set $C=\{c_1,\dots,c_p\}$. At each moment the machine has an inner state that is one of the $n$ members of finite set $S$. The function $o: S \rightarrow C$ is a surjective function defining that at each state, what color must the lamp be, and the function $t:S \times I \rightarrow S$ is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment. In other words a machine is $M=(S,I,C,o,t)$ such that $S,I,C$ are finite, $t:S \times I \rightarrow S$ , and $o:S \rightarrow C$ is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (a) The machine $M$ has $n$ different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than $n-p$ such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (b) Prove that for a machine $M$ with $n$ different inner states, there exists an algorithm with no more than $n^2$ inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known. Can you prove the above claim for $\frac{n^2}{2}$?

Find, with proof, the number of positive integers whose base-$n$ representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by $\pm 1$ from some digit further to the left. (Your answer should be an explicit function of $n$ in simplest form.)

Prove that the functional equations \[f(x + y) = f(x) + f(y),\] \[ \text{and} \qquad f(x + y + xy) = f(x) + f(y) + f(xy) \quad (x, y \in \mathbb R)\] are equivalent.

Find the least odd positive integer that is the middle number of five consecutive integers that are all composite.

Let $D$ be an interior point of the triangle $ABC$. $CD$ and $AB$ intersect at $D_{c}$, $BD$ and $AC$ intersect at $D_{b}$, $AD$ and $BC$ intersect at $D_{a}$. Prove that there exists a triangle $KLM$ with orthocenter $H$ and the feet of altitudes $H_{k}\in LM, H_{l}\in KM, H_{m}\in KL$, so that $(AD_{c}D) = (KH_{m}H)$ $(BD_{c}D) = (LH_{m}H)$ $(BD_{a}D) = (LH_{k}H)$ $(CD_{a}D) = (MH_{k}H)$ $(CD_{b}D) = (MH_{l}H)$ $(AD_{b}D) = (KH_{l}H)$ where $(PQR)$ denotes the area of the triangle $PQR$

Let $ a$, $ b$, $ c$ be three integers. Prove that there exist six integers $ x$, $ y$, $ z$, $ x^{\prime}$, $ y^{\prime}$, $ z^{\prime}$ such that $ a\equal{}yz^{\prime}\minus{}zy^{\prime};\ \ \ \ \ \ \ \ \ \ b\equal{}zx^{\prime}\minus{}xz^{\prime};\ \ \ \ \ \ \ \ \ \ c\equal{}xy^{\prime}\minus{}yx^{\prime}$.

Prove that $$x^2 +\frac{8}{xy}+ y^2 \ge 8$$ for all positive real numbers $x$ and $y$.

A finite sequence of decimal digits from $\{0,1,\cdots, 9\}$ is said to be [i]common[/i] if for each sufficiently large positive integer $n$, there exists a positive integer $m$ such that the expansion of $n$ in base $m$ ends with this sequence of digits. For example, $0$ is common because for any large $n$, the expansion of $n$ in base $n$ is $10$, whereas $00$ is not common because for any squarefree $n$, the expansion of $n$ in any base cannot end with $00$. Determine all common sequences. [i]Proposed by Wong Jer Ren[/i]

Let $k$ be a prime, such as $k\neq 2, 5$, prove that between the first $k$ terms of the sequens $1, 11, 111, 1111,....,1111....1$, where the last term have $k$ ones, is divisible by $k$.

Let $s_1,s_2,s_3,s_4,...$ be a sequence (infinite list) of $1$s and $0$s. For example $1,0,1,0,1,0,...$, that is, $s_n=1$ if $n$ is odd and $s_n=0$ if $n$ is even, is such a sequence. Prove that it is possible to delete infinitely many terms in $s_1,s_2,s_3,s_4,...$ so that the resulting sequence is the original sequence. For the given example, one can delete $s_3,s_4,s_7,s_8,s_{11},s_{12},...$

Let $G$ be a non-solvable finite group and let $\varepsilon > 0$. Show that there exist a positive integer $k$ and a word $w\in F_k$ such that $w$ assumes the value $1$ with probability less than $\varepsilon$ when its $k$ arguments are considered to be independent and uniformly distributed random variables with values in $G$. (We write $F_k$ for the free group generated by $k$ elements.)

Let $n$ be the number of ordered quadruples $(x_1,x_2,x_3,x_4)$ of positive odd integers that satisfy $\sum_{i=1}^4 x_i=98.$ Find $\frac n{100}.$

In a city at every square exactly three roads meet, one is called street, one is an avenue, and one is a crescent. Most roads connect squares but three roads go outside of the city. Prove that among the roads going out of the city one is a street, one is an avenue and one is a crescent.

$ABCD$ is a rectangle $\overline{AB} = 5\sqrt{3}$, $\overline{AD} = 30$. Extend $\overline{BC}$ past $C$ and construct point $P$ on this extension such that $\angle APD = 60^{\circ}$. Point $H$ is on $\overline{AP}$ such that $\overline{DH} \perp \overline{AP}$. Find the length of $\overline{DH}$. [i]Proposed by Kevin Wu[/i]

Define $p(n)$ to be th product of all non-zero digits of $n$. For instance $p(5)=5$, $p(27)=14$, $p(101)=1$ and so on. Find the greatest prime divisor of the following expression: \[p(1)+p(2)+p(3)+...+p(999).\]

Under the new AMC 10, 12 scoring method, $6$ points are given for each correct answer, $2.5$ points are given for each unanswered question, and no points are given for an incorrect answer. Some of the possible scores between $0$ and $150$ can be obtained in only one way, for example, the only way to obtain a score of $146.5$ is to have 24 correct answers and one unanswered question. Some scores can be obtained in exactly two ways; for example, a score of $104.5$ can be obtained with $17$ correct answers, $1$ unanswered question, and $7$ incorrect, and also with $12$ correct answers and $13$ unanswered questions. There are three scores that can be obtained in exactly three ways. What is their sum? $\textbf{(A) }175\qquad\textbf{(B) }179.5\qquad\textbf{(C) }182\qquad\textbf{(D) }188.5\qquad\textbf{(E) }201$

Prove that $$x\cos x \le \frac{\pi^2}{16}$$ for $0 \le x \le \frac{\pi}{2}$