Assume that the connected graph $G$ has $n$ vertices all with degree at least three. Prove that there exists a spanning tree of $G$ with more than $\frac{2}{9}n$ leaves.

Each of the numbers $1$ up to and including $2014$ has to be coloured; half of them have to be coloured red the other half blue. Then you consider the number $k$ of positive integers that are expressible as the sum of a red and a blue number. Determine the maximum value of $k$ that can be obtained.

Let $AH$ be an altitude of an acute-angled triangle $ABC$. Points $K$ and $L$ are the projections of $H$ onto sides $AB$ and $AC$. The circumcircle of $ABC$ meets line $KL$ at points $P$ and $Q$, and meets line $AH$ at points $A$ and $T$. Prove that $H$ is the incenter of triangle $PQT$. (M.Plotnikov)

The equation $ 3y^2 \plus{} y \plus{} 4 \equal{} 2(6x^2 \plus{} y \plus{} 2)$ where $ y \equal{} 2x$ is satisfied by: $ \textbf{(A)}\ \text{no value of }x \qquad\textbf{(B)}\ \text{all values of }x \qquad\textbf{(C)}\ x \equal{} 0\text{ only}$ $ \textbf{(D)}\ \text{all integral values of }x\text{ only} \qquad\textbf{(E)}\ \text{all rational values of }x\text{ only}$

Let $\mathbb{R}^{*}$ be the set of non-zero real numbers. Find all functions $f : \mathbb{R}^{*} \to \mathbb{R}^{*}$ such that $f(x^{2}+y) = (f(x))^{2} + \frac{f(xy)}{f(x)}$, for all $x,y \in \mathbb{R}^{*}$ and $-x^{2} \not= y$.

If a b c positive reals smaller than 1, prove: a+b+c+2abc>ab+bc+ca+2(abc)^(1/2)

A four-digit number has the property that the units digit equals the tens digit increased by $1$, the hundreds digit equals twice the tens digit, and the thousands digit is at least twice the units. Determine this four-digit number, knowing that it is twice a prime number.

Let $n$ be a positive integer with $d^2$ positive divisors. We fill a $d\times d$ board with these divisors. At a move, we can choose a row, and shift the divisor from the $i^{\text{th}}$ column to the $(i+1)^{\text{th}}$ column, for all $i=1,2,\ldots, d$ (indices reduced modulo $d$). A configuration of the $d\times d$ board is called [i]feasible[/i] if there exists a column with elements $a_1,a_2,\ldots,a_d,$ in this order, such that $a_1\mid a_2\mid\ldots\mid a_d$ or $a_d\mid a_{d-1}\mid\ldots\mid a_1.$ Determine all values of $n$ for which ragardless of how we initially fill the board, we can reach a feasible configuration after a finite number of moves.

Suppose you are given a fair coin and a sheet of paper with the polynomial $x^m$ written on it. Now for each toss of the coin, if heads show up, you must erase the polynomial $x^r$ (where $r$ is going to change with time - initially it is $m$) written on the paper and replace it with $x^{r-1}$. If tails show up, replace it with $x^{r+1}$. What is the expected value of the polynomial I get after $m$ such tosses? (Note: this is a different concept from the most probable value)

Lucy starts by writing $s$ integer-valued $2022$-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples $\mathbf{v}=(v_1,\ldots,v_{2022})$ and $\mathbf{w}=(w_1,\ldots,w_{2022})$ that she has already written, and apply one of the following operations to obtain a new tuple: \begin{align*} \mathbf{v}+\mathbf{w}&=(v_1+w_1,\ldots,v_{2022}+w_{2022}) \\ \mathbf{v} \lor \mathbf{w}&=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022})) \end{align*} and then write this tuple on the blackboard. It turns out that, in this way, Lucy can write any integer-valued $2022$-tuple on the blackboard after finitely many steps. What is the smallest possible number $s$ of tuples that she initially wrote?

Define a sequence $\{a_i\}$ by $a_1=3$ and $a_{i+1}=3^{a_i}$ for $i\geq 1$. Which integers between $00$ and $99$ inclusive occur as the last two digits in the decimal expansion of infinitely many $a_i$?

[b]p1.[/b] One out of $12$ coins is counterfeited. It is known that its weight differs from the weight of a valid coin but it is unknown whether it is lighter or heavier. How to detect the counterfeited coin with the help of four trials using only a two-pan balance without weights? [b]p2.[/b] Below a $3$-digit number $c d e$ is multiplied by a $2$-digit number $a b$ . Find all solutions $a, b, c, d, e, f, g$ if it is known that they represent distinct digits. $\begin{tabular}{ccccc} & & c & d & e \\ x & & & a & b \\ \hline & & f & e & g \\ + & c & d & e & \\ \hline & b & b & c & g \\ \end{tabular}$ [b]p3.[/b] Find all integer $n$ such that $\frac{n + 1}{2n - 1}$is an integer. [b]p4[/b]. There are several straight lines on the plane which split the plane in several pieces. Is it possible to paint the plane in brown and green such that each piece is painted one color and no pieces having a common side are painted the same color? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Circle $\Gamma$ touches the circumcircle of triangle $ABC$ at point $R$, and it touches the sides $AB$ and $AC$ at points $P$ and $Q$, respectively. Rays $PQ$ and $BC$ intersect at point $X$. The tangent line at point $R$ to the circle $\Gamma$ meets the segment $QX$ at point $Y$. The line segment $AX$ intersects the circumcircle of triangle $APQ$ at point $Z$. Prove that the circumscribed circles of triangles $ABC$ and $XY Z$ are tangent.

Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that the following conditions are true for every pair of positive integers $(x, y)$: $(i)$: $x$ and $f(x)$ have the same number of positive divisors. $(ii)$: If $x \nmid y$ and $y \nmid x$, then: $$\gcd(f(x), f(y)) > f(\gcd(x, y))$$

Let $a,b,c$ be integer numbers such that $(a+b+c) \mid (a^{2}+b^{2}+c^{2})$. Show that there exist infinitely many positive integers $n$ such that $(a+b+c) \mid (a^{n}+b^{n}+c^{n})$. [i]Laurentiu Panaitopol[/i]

Let $n > 1$ be an integer and $\Omega=\{1,2,...,2n-1,2n\}$ the set of all positive integers that are not larger than $2n$. A nonempty subset $S$ of $\Omega$ is called [i]sum-free[/i] if, for all elements $x, y$ belonging to $S, x + y$ does not belong to $S$. We allow $x = y$ in this condition. Prove that $\Omega$ has more than $2^n$ distinct [i]sum-free[/i] subsets.

Vishal starts with $n$ copies of the number $1$ written on the board. Every minute, he takes two numbers $a, b$ and replaces them with either $a+b$ or $\min(a^2, b^2)$. After $n-1$ there is $1$ number on the board. Let the maximal possible value of this number be $f(n)$. Prove $2^{n/3}<f(n)\leq 3^{n/3}$.

Consider the shape shown below, formed by gluing together the sides of seven congruent regular hexagons. The area of this shape is partitioned into $21$ quadrilaterals, all of whose side lengths are equal to the side length of the hexagon and each of which contains a $60^{\circ}$ angle. In how many ways can this partitioning be done? (The quadrilaterals may contain an internal boundary of the seven hexagons.) [asy] draw(origin--origin+dir(0)--origin+dir(0)+dir(60)--origin+dir(0)+dir(60)+dir(0)--origin+dir(0)+dir(60)+dir(0)+dir(60)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)+dir(300)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)+dir(300)+dir(240)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)+dir(300)+dir(240)+dir(300)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)+dir(300)+dir(240)+dir(300)+dir(0)--origin+dir(0)+dir(60)+dir(0)+dir(60)+dir(120)+dir(60)+dir(120)+dir(180)+dir(120)+dir(180)+dir(240)+dir(180)+dir(240)+dir(300)+dir(240)+dir(300)+dir(0)+dir(300)--cycle); draw(2*dir(60)+dir(120)+dir(0)--2*dir(60)+dir(120)+2*dir(0),dashed); draw(2*dir(60)+dir(120)+dir(60)--2*dir(60)+dir(120)+2*dir(60),dashed); draw(2*dir(60)+dir(120)+dir(120)--2*dir(60)+dir(120)+2*dir(120),dashed); draw(2*dir(60)+dir(120)+dir(180)--2*dir(60)+dir(120)+2*dir(180),dashed); draw(2*dir(60)+dir(120)+dir(240)--2*dir(60)+dir(120)+2*dir(240),dashed); draw(2*dir(60)+dir(120)+dir(300)--2*dir(60)+dir(120)+2*dir(300),dashed); draw(dir(60)+dir(120)--dir(60)+dir(120)+dir(0)--dir(60)+dir(120)+dir(0)+dir(60)--dir(60)+dir(120)+dir(0)+dir(60)+dir(120)--dir(60)+dir(120)+dir(0)+dir(60)+dir(120)+dir(180)--dir(60)+dir(120)+dir(0)+dir(60)+dir(120)+dir(180)+dir(240)--dir(60)+dir(120)+dir(0)+dir(60)+dir(120)+dir(180)+dir(240)+dir(300),dashed); [/asy]

[b]p1.[/b] Find all positive integers $n$ such that $n^3 - 14n^2 + 64n - 93$ is prime. [b]p2.[/b] Let $a, b, c$ be real numbers such that $0 \le a, b, c \le 1$. Find the maximum value of $$\frac{a}{1 + bc}+\frac{b}{1 + ac}+\frac{c}{1 + ab}$$ [b]p3.[/b] Find the maximum value of the function $f(x, y, z) = 4x + 3y + 2z$ on the ellipsoid $16x^2 + 9y^2 + 4z^2 = 1$ [b]p4.[/b] Let $x_1,..., x_n$ be numbers such that $x_1+...+x_n = 2009$. Find the minimum value of $x^2_1+...+x^2_n$ (in term of $n$). [b]p5.[/b] Find the number of odd integers between $1000$ and $9999$ that have at least 3 distinct digits. [b]p6.[/b] Let $A_1,A_2,...,A_{2^n-1}$ be all the possible nonempty subsets of $\{1, 2, 3,..., n\}$. Find the maximum value of $a_1 + a_2 + ... + a_{2^n-1}$ where $a_i \in A_i$ for each $i = 1, 2,..., 2^n - 1$. [b]p7.[/b] Find the rightmost digit when $41^{2009}$ is written in base $7$. [b]p8.[/b] How many integral ordered triples $(x, y, z)$ satisfy the equation $x+y+z = 2009$, where $10 \le x < 31$, $100 < z < 310$ and $y \ge 0$. [b]p9.[/b] Scooby has a fair six-sided die, labeled $1$ to $6$, and Shaggy has a fair twenty-sided die, labeled $1$ to $20$. During each turn, they both roll their own dice at the same time. They keep rolling the die until one of them rolls a 5. Find the probability that Scooby rolls a $5$ before Shaggy does. [b]p10.[/b] Let $N = 1A323492110877$ where $A$ is a digit in the decimal expansion of $N$. Suppose $N$ is divisible by $7$. Find $A$. [b]p11.[/b] Find all solutions $(x, y)$ of the equation $\tan^4(x+y)+\cot^4(x+y) = 1-2x-x^2$, where $-\frac{\pi}{2} \le x; y \le \frac{\pi}{2}$ [b]p12.[/b] Find the remainder when $\sum^{50}_{k=1}k!(k^2 + k - 1)$ is divided by $1008$. [b]p13.[/b] The devil set of a positive integer $n$, denoted $D(n)$, is defined as follows: (1) For every positive integer $n$, $n \in D(n)$. (2) If $n$ is divisible by $m$ and $m < n$, then for every element $a \in D(m)$, $a^3$ must be in $D(n)$. Furthermore, call a set $S$ scary if for any $a, b \in S$, $a < b$ implies that $b$ is divisible by $a$. What is the least positive integer $n$ such that $D(n)$ is scary and has at least $2009$ elements? PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In the interior of a square $ABCD$ we construct the equilateral triangles $ABK, BCL, CDM, DAN.$ Prove that the midpoints of the four segments $KL, LM, MN, NK$ and the midpoints of the eight segments $AK, BK, BL, CL, CM, DM, DN, AN$ are the 12 vertices of a regular dodecagon.

Chords $AA^{\prime}$, $BB^{\prime}$, $CC^{\prime}$ of a sphere meet at an interior point $P$ but are not contained in a plane. The sphere through $A$, $B$, $C$, $P$ is tangent to the sphere through $A^{\prime}$, $B^{\prime}$, $C^{\prime}$, $P$. Prove that $\, AA' = BB' = CC'$.

Bisectors $AI$ and $CI$ meet the circumcircle of triangle $ABC$ at points $A_1, C_1$ respectively. The circumcircle of triangle $AIC_1$ meets $AB$ at point $C_0$; point $A_0$ is defined similarly. Prove that $A_0, A_1, C_0, C_1$ are collinear.

Consider a polynomial $P(x) = \prod^9_{j=1}(x+d_j),$ where $d_1, d_2, \ldots d_9$ are nine distinct integers. Prove that there exists an integer $N,$ such that for all integers $x \geq N$ the number $P(x)$ is divisible by a prime number greater than 20. [i]Proposed by Luxembourg[/i]

In a room there are nine men. Among every three of them there are two mutually acquainted. Prove that some four of them are mutually acquainted.

Given a square $ABCD$ of side length $6$, the point $E$ is drawn on the line $AB$ such that the distance $EA$ is less than $EB$ and the triangle $\vartriangle BCE$ has the same area as $ABCD$. Compute the shaded area. [img]https://cdn.artofproblemsolving.com/attachments/a/8/5d945a593aee58af3af94f4e8e967eeaeefa6a.png[/img]