Let $P_{n}$ denote the number of paths in the coordinate plane traveling from $(0, 0)$ to $(n, 0)$ with three kinds of moves: [i]upstep[/i] $u = [1, 1]$, [i]downstep[/i] $d = [1,-1]$, and [i]flatstep[/i] $f = [1, 0]$ with the path always staying above the line $y = 0.$ Let $C_{n}= \frac{1}{n+1}\binom{2n}{n}$ be the $n^{th}$ Catalan number. Prove that $P_{n}= \sum_{i = 0}^\infty \binom{n}{2i}C_{i}$ and $C_{n}= \sum_{i = 0}^{2n}(-1)^{i}\binom{2n}{i}P_{2n-i}.$ [hide="Solution to Part 1"] Let a path string, $S_{k}$, denote a string of $u, d, f$ corresponding to upsteps, downsteps, and flatsteps of length $k$ which successfully travels from $(0, 0)$ to $(n, 0)$ without passing below $y = 0.$ Also, let each entry of a path string be a slot. Lastly, denote $u_{k}, d_{k}, f_{k}$ to be the number of upsteps, downsteps, and flatsteps, respectively, in $S_{k}.$ Note that in our situation, all such path strings are in the form $S_{n},$ so all our path strings have $n$ slots. Since the starting and ending $y$ values are the same, the number of upsteps must equal the number of downsteps. Let us observe the case when there are $2k$ downsteps and upsteps totally. Thus, there are $\binom{n}{2k}$ ways to choose the slots in which the upsteps and the downsteps appear. Now, we must arrange the downsteps and upsteps in such a way that $d_{n}= u_{n}$ and a greater number of upsteps preceed downsteps, as the path is always above $y = 0$. Note that a bijection exists between this and the number of ways to binary bracket $k$ letters. The number of binary brackets of $k$ letters is just the $k^{th}$ Catalan number. We then place the flatsteps in the rest of the slots. Thus, there are a total of $\sum_{k = 0}^\infty \binom{n}{2k}C_{k}$ ways to get an $S_{n}.$ [/hide]

Two unit cubes have a common center. Is it always possible to number the vertices of each cube from $1$ to $8$ so that the distance between each pair of identically numbered vertices would be at most $4/5$? What about at most $13/16$?

Prove that for all positive integers $n$ there exists a single positive integer divisible with $5^n$ which in decimal base is written using $n$ digits from the set $\{1,2,3,4,5\}$.

The hypotenuse $ c$ and one arm $ a$ of a right triangle are consecutive integers. The square of the second arm is: $ \textbf{(A)}\ ca \qquad\textbf{(B)}\ \frac {c}{a} \qquad\textbf{(C)}\ c \plus{} a \qquad\textbf{(D)}\ c \minus{} a \qquad\textbf{(E)}\ \text{none of these}$

Let $0 < \alpha, \beta, \gamma < \frac{\pi}{2}$ and $\sin^{3} \alpha + \sin^{3} \beta + \sin^3 \gamma = 1$. Prove that \[ \tan^{2} \alpha + \tan^{2} \beta + \tan^{2} \gamma \geq \frac{3 \sqrt{3}}{2} . \]

Is it possible to choose five different positive integers so that the sum of any three of them is a prime number?

Sides of a triangle are equal to $3$, $4$ and $5$. Each side is extended until it intersects the bisector of the external angle to the angle opposite to it. Three such points are obtained in all. Prove that one of the three points we get is the midpoint of the segment joining the other two points. (V. Prasolov)

Let $T$ be the answer to question $16$. Compute the number of distinct real roots of the polynomial $x^4 + 6x^3 +\frac{T}{2}x^2 + 6x + 1$.

Let $O$ be the centre of a regular $n$-gon whose vertices are labelled $A_1$,$...$, $A_n$. Let $a_1>a_2>...>a_n>0$. Prove that the vector $$a_1\overrightarrow{OA_1}+a_2\overrightarrow{OA_2}+...+a_n\overrightarrow{OA_n}$$ is not equal to the zero vector. (D. Fomin, Alexey Kirichenko)

There is a rectangular sheet of paper on an infinite blackboard. Marvin secretly chooses a convex $2024$-gon $P$ that lies fully on the piece of paper. Tigerin wants to find the vertices of $P$. In each step, Tigerin can draw a line $g$ on the blackboard that is fully outside the piece of paper, then Marvin replies with the line $h$ parallel to $g$ that is the closest to $g$ which passes through at least one vertex of $P$. Prove that there exists a positive integer $n$, independent of the choice of the polygon, such that Tigerin can always determine the vertices of $P$ in at most $n$ steps.

In an acute-angled triangle $ABC$, $A_1$ and $B_1$ are the feet of the altitudes from $A$ and $B$ respectively, and $M$ is the midpoint of $AB$. a) Prove that $MA_1$ is tangent to the circumcircle of triangle $A_1B_1C$. b) Prove that the circumcircles of triangles $A_1B_1C,BMA_1$, and $AMB_1$ have a common point.

A regular triangular pyramid $ABCD$ with the base side $AB=a$ and the lateral edge $AD=b$ is given. Let $M$ and $N$ be the midpoints of $AB$ and $CD$ respectively. A line $\alpha$ through $MN$ intersects the edges $AD$ and $BC$ at $P$ and $Q$, respectively. (a) Prove that $AP/AD=BQ/BC$. (b) Find the ratio $AP/AD$ which minimizes the area of $MQNP$.

Dedalo buys a finite number of binary strings, each of finite length and made up of the binary digits 0 and 1. For each string, he pays $(\frac{1}{2})^L$ drachmas, where $L$ is the length of the string. The Minotaur is able to escape the labyrinth if he can find an infinite sequence of binary digits that does not contain any of the strings Dedalo bought. Dedalo’s aim is to trap the Minotaur. For instance, if Dedalo buys the strings $00$ and $11$ for a total of half a drachma, the Minotaur is able to escape using the infinite string $01010101 \ldots$. On the other hand, Dedalo can trap the Minotaur by spending $75$ cents of a drachma: he could for example buy the strings $0$ and $11$, or the strings $00, 11, 01$. Determine all positive integers $c$ such that Dedalo can trap the Minotaur with an expense of at most $c$ cents of a drachma.

Given real numbers $(a_i)$ and $(b_i)$ (for $i=1,2,3,4$) such that $a_1 b _2 \ne a_2 b_1 .$ Consider the set of all solutions $(x_1 ,x_2 ,x_3 , x_4)$ of the simultaneous equations $$ a_1 x_1 +a _2 x_2 +a_3 x_3 +a_4 x_4 =0 \;\; \text{and}\;\; b_1 x_1 +b_2 x_2 +b_3 x_3 +b_4 x_4 =0 $$ for which no $x_i$ is zero. Each such solution generates a $4$-tuple of plus and minus signs (by considering the sign of $x_i$). [list=a] [*] Determine, with proof, the maximum number of distinct $4$-tuples possible. [*] Investigate necessary and sufficient conditions on $(a_i)$ and $(b_i)$ such that the above maximum of distinct $4$-tuples is attained.

A rectangle-shaped puzzle is assembled with $2000$ pieces that are all equal rectangles, and similar to the large rectangle, so that the sides of the small rectangles are parallel to those of the large one. The shortest side of each piece measures $1$. Determine what is the minimum possible value of the area of the large rectangle.

Let $\triangle ABC$ be an acute triangle with $AB =AC$ and let $D$ be a point on the side $BC$. The circle with centre $D$ passing through $C$ intersects $\odot(ABD)$ at points $P$ and $Q$, where $Q$ is the point closer to $B$. The line $BQ$ intersects $AD$ and $AC$ at points $X$ and $Y$ respectively. Prove that quadrilateral $PDXY$ is cyclic.

The incircle of the triangle $ ABC $ touches the sides of $ AB, BC, CA $ at points $ C_0, A_0, B_0 $, respectively. Let the point $ M $ be the midpoint of the segment connecting the vertex $ C_0 $ with the intersection point of the altitudes of the triangle $ A_0B_0C_0 $, point $ N $ be the midpoint of the arc $ ACB $ of the circumscribed circle of the triangle $ ABC $. Prove that line $ MN $ passes through the center of incircle of triangle $ ABC $.

Let $\{a_n \}_n$ be a sequence of real numbers such there there are countably infinite distinct subsequences converging to the same point. We call two subsequences distinct if they do not have a common term. Which of the following statements always holds: (A) $\{a_n \}_n$ is bounded (B) $\{a_n \}_n$ is unbounded (C) The set of convergent subsequence $\{a_n \}_n$ is countable (D) None of these

In the parallelogram $CMNP$ extend the bisectors of angles $MCN$ and $PCN$ and intersect with extensions of sides PN and $MN$ at points $A$ and $B$, respectively. Prove that the bisector of the original angle $C$ of the the parallelogram is perpendicular to $AB$. [img]https://cdn.artofproblemsolving.com/attachments/f/3/fde8ef133758e06b1faf8bdd815056173f9233.png[/img]

Evaluate $ \int_1^e \frac {(1 \plus{} 2x^2)\ln x}{\sqrt {1 \plus{} x^2}}\ dx$.

Let $n\ge 2$ be a positive integer. Find the positive integers $x$ \[\sqrt{x+\sqrt{x+\ldots +\sqrt{x}}}<n \] for any number of radicals.

A ladder style tournament is held with $2016$ participants. The players begin seeded $1,2,\cdots 2016$. Each round, the lowest remaining seeded player plays the second lowest remaining seeded player, and the loser of the game gets eliminated from the tournament. After $2015$ rounds, one player remains who wins the tournament. If each player has probability of $\tfrac{1}{2}$ to win any game, then the probability that the winner of the tournament began with an even seed can be expressed has $\tfrac{p}{q}$ for coprime positive integers $p$ and $q$. Find the remainder when $p$ is divided by $1000$. [i]Proposed by Nathan Ramesh

Let $\mathbb{Q}_{>0}$ denote the set of all positive rational numbers. Determine all functions $f:\mathbb{Q}_{>0}\to \mathbb{Q}_{>0}$ satisfying $$f(x^2f(y)^2)=f(x)^2f(y)$$ for all $x,y\in\mathbb{Q}_{>0}$

Let the incircle of a nonisosceles triangle $ABC$ touch $AB$, $AC$ and $BC$ at points $D$, $E$ and $F$ respectively. The corresponding excircle touches the side $BC$ at point $N$. Let $T$ be the common point of $AN$ and the incircle, closest to $N$, and $K$ be the common point of $DE$ and $FT$. Prove that $AK||BC$.

Calculate $\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \frac{cos(x)^7}{e^x+1} dx$.