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}$?

Let $\vartriangle AMO$ be an equilateral triangle. Let $U$ and $G$ lie on side $AM$, and let $S$ and $N$ lie on side $AO$ such that $AU =UG = GM$ and $AS = SN = NO$. Find the value of $\frac{[MONG]}{[U S A]}$

Let $ABC$ be a triangle and let $I$ and $O$ denote its incentre and circumcentre respectively. Let $\omega_A$ be the circle through $B$ and $C$ which is tangent to the incircle of the triangle $ABC$; the circles $\omega_B$ and $\omega_C$ are defined similarly. The circles $\omega_B$ and $\omega_C$ meet at a point $A'$ distinct from $A$; the points $B'$ and $C'$ are defined similarly. Prove that the lines $AA',BB'$ and $CC'$ are concurrent at a point on the line $IO$. [i](Russia) Fedor Ivlev[/i]

Prove that any rational $r \in (0, 1)$ can be written uniquely in the form $$r=\frac{a_1}{1!}+\frac{a_2}{2!}+\frac{a_3}{3!}+\cdots+\frac{a_k}{k!}$$ where $a_i\text{’s}$ are nonnegative integers with $a_i\leq i-1$ for all $i$.

We call a subset $S$ of vertices of graph $G$, $2$-dominating, if and only if for every vertex $v\notin S,v\in G$, $v$ has at least two neighbors in $S$. prove that every $r$-regular $(r\ge3)$ graph has a $2$-dominating set with size at most $\frac{n(1+\ln(r))}{r}$.(15 points) time of this exam was 3 hours

[i]20 problems for 25 minutes.[/i] [b]p1.[/b] Ben was trying to solve for $x$ in the equation $6 + x = 1$. Unfortunately, he was reading upside-down and misread the equation as $1 = x + 9$. What is the positive difference between Ben's answer and the correct answer? [b]p2.[/b] Anjali and Meili each have a chocolate bar shaped like a rectangular box. Meili's bar is four times as long as Anjali's, while Anjali's is three times as wide and twice as thick as Meili's. What is the ratio of the volume of Anjali's chocolate to the volume of Meili's chocolate? [b]p3.[/b] For any two nonnegative integers $m, n$, not both zero, define $m?n = m^n + n^m$. Compute the value of $((2?0)?1)?7$. [b]p4.[/b] Eliza is making an in-scale model of the Phillips Exeter Academy library, and her prototype is a cube with side length $6$ inches. The real library is shaped like a cube with side length $120$ feet, and it contains an entrance chamber in the front. If the chamber in Eliza's model is $0.8$ inches wide, how wide is the real chamber, in feet? [b]p5.[/b] One day, Isaac begins sailing from Marseille to New York City. On the exact same day, Evan begins sailing from New York City to Marseille along the exact same route as Isaac. If Marseille and New York are exactly $3000$ miles apart, and Evan sails exactly 40 miles per day, how many miles must Isaac sail each day to meet Evan's ship in $30$ days? [b]p6.[/b] The conversion from Celsius temperature C to Fahrenheit temperature F is: $$F = 1.8C + 32.$$ If the lowest temperature at Exeter one day was $20^o$ F, and the next day the lowest temperature was $5^o$ C higher, what would be the lowest temperature that day, in degrees Fahrenheit? [b]p7.[/b] In a school, $60\%$ of the students are boys and $40\%$ are girls. Given that $40\%$ of the boys like math and $50\%$ of the people who like math are girls, what percentage of girls like math? [b]p8.[/b] Adam and Victor go to an ice cream shop. There are four sizes available (kiddie, small, medium, large) and seventeen different flavors, including three that contain chocolate. If Victor insists on getting a size at least as large as Adam's, and Adam refuses to eat anything with chocolate, how many different ways are there for the two of them to order ice cream? [b]p9.[/b] There are $10$ (not necessarily distinct) positive integers with arithmetic mean $10$. Determine the maximum possible range of the integers. (The range is defined to be the nonnegative difference between the largest and smallest number within a list of numbers.) [b]p10.[/b] Find the sum of all distinct prime factors of $11! - 10! + 9!$. [b]p11.[/b] Inside regular hexagon $ZUMING$, construct square $FENG$. What fraction of the area of the hexagon is occupied by rectangle $FUME$? [b]p12.[/b] How many ordered pairs $(x, y)$ of nonnegative integers satisfy the equation $4^x \cdot 8^y = 16^{10}$? [b]p13.[/b] In triangle $ABC$ with $BC = 5$, $CA = 13$, and $AB = 12$, Points $E$ and $F$ are chosen on sides $AC$ and $AB$, respectively, such that $EF \parallel BC$. Given that triangle $AEF$ and trapezoid $EFBC$ have the same perimeter, find the length of $EF$. [b]p14.[/b] Find the number of two-digit positive integers with exactly $6$ positive divisors. (Note that $1$ and $n$ are both counted among the divisors of a number $n$.) [b]p15.[/b] How many ways are there to put two identical red marbles, two identical green marbles, and two identical blue marbles in a row such that no red marble is next to a green marble? [b]p16.[/b] Every day, Yannick submits $8$ more problems to the EMCC problem database than he did the previous day. Every day, Vinjai submits twice as many problems to the EMCC problem database as he did the previous day. If Yannick and Vinjai initially both submit one problem to the database on a Monday, on what day of the week will the total number of Vinjai's problems first exceed the total number of Yannick's problems? [b]p17.[/b] The tiny island nation of Konistan is a cone with height twelve meters and base radius nine meters, with the base of the cone at sea level. If the sea level rises four meters, what is the surface area of Konistan that is still above water, in square meters? [b]p18.[/b] Nicky likes to doodle. On a convex octagon, he starts from a random vertex and doodles a path, which consists of seven line segments between vertices. At each step, he chooses a vertex randomly among all unvisited vertices to visit, such that the path goes through all eight vertices and does not visit the same vertex twice. What is the probability that this path does not cross itself? [b]p19.[/b] In a right-angled trapezoid $ABCD$, $\angle B = \angle C = 90^o$, $AB = 20$, $CD = 17$, and $BC = 37$. A line perpendicular to $DA$ intersects segment $BC$ and $DA$ at $P$ and $Q$ respectively and separates the trapezoid into two quadrilaterals with equal area. Determine the length of $BP$. [b]p20.[/b] A sequence of integers $a_i$ is defined by $a_1 = 1$ and $a_{i+1} = 3i - 2a_i$ for all integers $i \ge 1$. Given that $a_{15} = 5476$, compute the sum $a_1 + a_2 + a_3 + ...+ a_{15}$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

The root(s) of $ \frac {15}{x^2 \minus{} 4} \minus{} \frac {2}{x \minus{} 2} \equal{} 1$ is (are): $ \textbf{(A)}\ \minus{} 5\text{ and }3 \qquad\textbf{(B)}\ \pm 2 \qquad\textbf{(C)}\ 2\text{ only} \qquad\textbf{(D)}\ \minus{} 3\text{ and }5 \qquad\textbf{(E)}\ 3\text{ only}$

Evaluate: $ \sum\limits_{n\equal{}1}^\infty \arctan{\left(\frac{1}{n^2\minus{}n\plus{}1}\right)}$

Points $ P,Q,R$ are given in the plane. It is known that there is a triangle $ ABC$ such that $ P$ is the midpoint of $ BC$, $ Q$ the point on side $ CA$ with $ \frac{CQ}{QA}\equal{}2$, and $ R$ the point on side $ AB$ with $ \frac{AR}{RB}\equal{}2$. Determine with proof how the triangle $ ABC$ may be reconstructed from $ P,Q,R$.

Consider the set: $A = \{1, 2,..., 100\}$ Prove that if we take $11$ different elements from $A$, there are $x, y$ such that $x \neq y$ and $0 < |\sqrt{x} - \sqrt{y}| < 1$

Given a triangle $ABC$ where $|BC| = a, |CA| = b$ and $|AB| = c$, prove that the equality $\frac{1}{a + b}+\frac{1}{b + c}=\frac{3}{a + b + c}$ holds if and only if $\angle ABC = 60^o$.

Let \( \triangle ABC \) be an equilateral triangle, and let \( M \) be the midpoint of \( BC \). Let \( C_1 \) be the circumcircle of triangle \( \triangle ABC \) and \( C_2 \) the circumcircle of triangle \( \triangle ABM \). Determine the ratio between the areas of the circles \( C_1 \) and \( C_2 \).

Suppose $S$ cans of soda can be purchased from a vending machine for $Q$ quarters. Which of the following expressions describes the number of cans of soda that can be purchased for $D$ dollars, where $1$ dollar is worth $4$ quarters? $\textbf{(A) }\frac{4DQ}S\qquad\textbf{(B) }\frac{4DS}Q\qquad\textbf{(C) }\frac{4Q}{DS}\qquad\textbf{(D) }\frac{DQ}{4S}\qquad\textbf{(E) }\frac{DS}{4Q}$

$ABCD$ is a quadrilateral. The bisectors of $\angle A$ and $\angle B$ meet at $E$. The line through $E$ parallel to $CD$ meets $AD$ at $L$ and $BC$ at $M$. Show that $LM = AL + BM$.

If \[\frac{1} {x} + \frac{1} {2x^2} +\frac{1} {4x^3}+\frac{1}{8x^4}+\frac{1}{16x^5}+\cdots=\frac{1} {64}, \] and $x$ can be expressed in the form $\frac{m}{n},$ where $m,n$ are relatively prime positive integers, find $m+n$. [i]Author: Ray Li[/i]

There exist unique positive integers $ x$ and $ y$ that satisfy the equation $ x^2 \plus{} 84x \plus{} 2008 \equal{} y^2$. Find $ x \plus{} y$.

Let $ S\subseteq\mathbb{R}$ be a set of real numbers. We say that a pair $ (f, g)$ of functions from $ S$ into $ S$ is a [i]Spanish Couple[/i] on $ S$, if they satisfy the following conditions: (i) Both functions are strictly increasing, i.e. $ f(x) < f(y)$ and $ g(x) < g(y)$ for all $ x$, $ y\in S$ with $ x < y$; (ii) The inequality $ f\left(g\left(g\left(x\right)\right)\right) < g\left(f\left(x\right)\right)$ holds for all $ x\in S$. Decide whether there exists a Spanish Couple [list][*] on the set $ S \equal{} \mathbb{N}$ of positive integers; [*] on the set $ S \equal{} \{a \minus{} \frac {1}{b}: a, b\in\mathbb{N}\}$[/list] [i]Proposed by Hans Zantema, Netherlands[/i]

Find the second smallest positive integer $n$ such that when $n$ is divided by $5,$ the remainder is $3,$ and when $n$ is divided by $7,$ the remainder is $4.$

Determine all values of $a \in R$ such that there exists a function $f : [0, 1] \to R$ fulfilling the following inequality for all $x \ne y$: $$|f(x) - f(y)| \ge a.$$

In the round robin chess tournament organized in a school every two students played one match among themselves. Find the minimal possible number of students in the school if each girl student has at least 21 wins in matches against boy students and each boy student has at least 12 wins in matches against girl students.

Start with a finite sequence $ a_1,a_2,\dots,a_n$ of positive integers. If possible, choose two indices $ j < k$ such that $ a_j$ does not divide $ a_k$ and replace $ a_j$ and $ a_k$ by $ \gcd(a_j,a_k)$ and $ \text{lcm}\,(a_j,a_k),$ respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: $ \gcd$ means greatest common divisor and lcm means least common multiple.)

Let $ABC$ be a triangle with $CA \neq CB$. Let $D$, $F$, and $G$ be the midpoints of the sides $AB$, $AC$, and $BC$ respectively. A circle $\Gamma$ passing through $C$ and tangent to $AB$ at $D$ meets the segments $AF$ and $BG$ at $H$ and $I$, respectively. The points $H'$ and $I'$ are symmetric to $H$ and $I$ about $F$ and $G$, respectively. The line $H'I'$ meets $CD$ and $FG$ at $Q$ and $M$, respectively. The line $CM$ meets $\Gamma$ again at $P$. Prove that $CQ = QP$. [i]Proposed by El Salvador[/i]

The diagram shows a large circular dart board with four smaller shaded circles each internally tangent to the larger circle. Two of the internal circles have half the radius of the large circle, and are, therefore, tangent to each other. The other two smaller circles are tangent to these circles. If a dart is thrown so that it sticks to a point randomly chosen on the dart board, then the probability that the dart sticks to a point in the shaded area is $\dfrac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$. [asy] size(150); defaultpen(linewidth(0.8)); filldraw(circle((0,0.5),.5),gray); filldraw(circle((0,-0.5),.5),gray); filldraw(circle((2/3,0),1/3),gray); filldraw(circle((-2/3,0),1/3),gray); draw(unitcircle); [/asy]

In $\vartriangle ABC$, $m\angle A = 90^o$, $m\angle B = 45^o$, and $m\angle C = 45^o$. Point $P$ inside $\vartriangle ABC$ satisfies $m \angle BPC =135^o$. Given that $\vartriangle PAC$ is isosceles, the largest possible value of $\tan \angle PAC$ can be expressed as $s+t\sqrt{u}$, where $s$ and $t$ are integers and $u$ is a positive integer not divisible by the square of any prime. Compute $100s + 10t + u$.

Solve equation : $\sqrt{x+\sqrt{4x+\sqrt{16x}+..+\sqrt{4^nx+3}}}-\sqrt{x}=1$