This ISL 2005 problem has not been used in any TST I know. A pity, since it is a nice problem, but in its shortlist formulation, it is absolutely incomprehensible. Here is a mathematical restatement of the problem: Let $k$ be a nonnegative integer. A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex $v$ is called an [i]extended successor[/i] of a vertex $u$ if there is a chain of vertices $u_{0}=u$, $u_{1}$, $u_{2}$, ..., $u_{t-1}$, $u_{t}=v$ with $t>0$ such that the vertex $u_{i+1}$ is a successor of the vertex $u_{i}$ for every integer $i$ with $0\leq i\leq t-1$. A vertex is called [i]dynastic[/i] if it has two successors and each of these successors has at least $k$ extended successors. Prove that if the forest has $n$ vertices, then there are at most $\frac{n}{k+2}$ dynastic vertices.

Several irrational numbers are written on a blackboard. It is known that for every two numbers $ a$ and $ b$ on the blackboard, at least one of the numbers $ a\over b\plus{}1$ and $ b\over a\plus{}1$ is rational. What maximum number of irrational numbers can be on the blackboard? [i]Author: Alexander Golovanov[/i]

Each square of the chessboard was painted in one of eight colors in such a way that the number of squares colored by all the colors are equal. Is it always possible to put $8$ rooks not threatening each other on multi-colored cells?

Ari chooses $7$ balls at random from $n$ balls numbered $1$ to$ n$. If the probability that no two of the drawn balls have consecutive numbers equals the probability of exactly one pair of consecutive numbers in the chosen balls, find $n$.

$S,T$ are two trees without vertices of degree 2. To each edge is associated a positive number which is called length of this edge. Distance between two arbitrary vertices $v,w$ in this graph is defined by sum of length of all edges in the path between $v$ and $w$. Let $f$ be a bijective function from leaves of $S$ to leaves of $T$, such that for each two leaves $u,v$ of $S$, distance of $u,v$ in $S$ is equal to distance of $f(u), f(v)$ in $T$. Prove that there is a bijective function $g$ from vertices of $S$ to vertices of $T$ such that for each two vertices $u,v$ of $S$, distance of $u,v$ in $S$ is equal to distance of $g(u)$ and $g(v)$ in $T$.

We consider the $n$ vertices of a regular polygon with $n$ sides. There is a set of triangles with vertices at these $n$ points with the property that for each triangle in the set, the sides of at least one are not the side of any other triangle in the set. What is the largest amount of triangles that can have the set? [hide=original wording]Consideramos los n vértices de un polígono regular de n lados. Se tiene un conjunto de triángulos con vértices en estos n puntos con la propiedad que para cada triángulo del conjunto, al menos uno de sus lados no es lado de ningún otro triángulo del conjunto. ¿Cuál es la mayor cantidad de triángulos que puede tener el conjunto?[/hide]

[b]p1.[/b] Compute the value of $N$, where $$N = 818^3 - 6 \cdot 818^2 \cdot 209 + 12 \cdot 818 \cdot 209^2 - 8 \cdot 209^3$$ [b]p2.[/b] Suppose $x \le 2019$ is a positive integer that is divisible by $2$ and $5$, but not $3$. If $7$ is one of the digits in $x$, how many possible values of $x$ are there? [b]p3.[/b] Find all non-negative integer solutions $(a,b)$ to the equation $$b^2 + b + 1 = a^2.$$ [b]p4.[/b] Compute the remainder when $\sum^{2019}_{n=1} n^4$ is divided by $53$. [b]p5.[/b] Let $ABC$ be an equilateral triangle and $CDEF$ a square such that $E$ lies on segment $AB$ and $F$ on segment $BC$. If the perimeter of the square is equal to $4$, what is the area of triangle $ABC$? [img]https://cdn.artofproblemsolving.com/attachments/1/6/52d9ef7032c2fadd4f97d7c0ea051b3766b584.png[/img] [b]p6.[/b] $$S = \frac{4}{1\times 2\times 3}+\frac{5}{2\times 3\times 4} +\frac{6}{3\times 4\times 5}+ ... +\frac{101}{98\times 99\times 100}$$ Let $T = \frac54 - S$. If $T = \frac{m}{n}$ , where $m$ and $n$ are relatively prime integers, find the value of $m + n$. [b]p7.[/b] Find the sum of $$\sum^{2019}_{i=0}\frac{2^i}{2^i + 2^{2019-i}}$$ [b]p8.[/b] Let $A$ and $B$ be two points in the Cartesian plane such that $A$ lies on the line $y = 12$, and $B$ lies on the line $y = 3$. Let $C_1$, $C_2$ be two distinct circles that intersect both $A$ and $B$ and are tangent to the $x$-axis at $P$ and $Q$, respectively. If $PQ = 420$, determine the length of $AB$. [b]p9.[/b] Zion has an average $2$ out of $3$ hit rate for $2$-pointers and $1$ out of $3$ hit rate for $3$-pointers. In a recent basketball match, Zion scored $18$ points without missing a shot, and all the points came from $2$ or $3$-pointers. What is the probability that all his shots were $3$-pointers? [b]p10.[/b] Let $S = \{1,2, 3,..., 2019\}$. Find the number of non-constant functions $f : S \to S$ such that $$f(k) = f(f(k + 1)) \le f(k + 1) \,\,\,\, for \,\,\,\, all \,\,\,\, 1 \le k \le 2018.$$ Express your answer in the form ${m \choose n}$, where $m$ and $n$ are integers. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[b]p1.[/b] Consider a cube with side length $2$. Take any one of its vertices and consider the three midpoints of the three edges emanating from that vertex. What is the distance from that vertex to the plane formed by those three midpoints? [b]p2.[/b] Digits $H$, $M$, and $C$ satisfy the following relations where $\overline{ABC}$ denotes the number whose digits in base $10$ are $A$, $B$, and $C$. $$\overline{H}\times \overline{H} = \overline{M}\times \overline{C} + 1$$ $$\overline{HH}\times \overline{H} = \overline{MC}\times \overline{C} + 1$$ $$\overline{HHH}\times \overline{H} = \overline{MCC}\times \overline{C} + 1$$ Find $\overline{HMC}$. [b]p3.[/b] Two players play the following game on a table with fair two-sided coins. The first player starts with one, two, or three coins on the table, each with equal probability. On each turn, the player flips all the coins on the table and counts how many coins land heads up. If this number is odd, a coin is removed from the table. If this number is even, a coin is added to the table. A player wins when he/she removes the last coin on the table. Suppose the game ends. What is the probability that the first player wins? [b]p4.[/b] Cyclic quadrilateral $[BLUE]$ has right $\angle E$. Let $R$ be a point not in $[BLUE]$. If $[BLUR] =[BLUE]$, $\angle ELB = 45^o$, and $\overline{EU} = \overline{UR}$, find $\angle RUE$. [b]p5.[/b] There are two tracks in the $x, y$ plane, defined by the equations $$y =\sqrt{3 - x^2}\,\,\, \text{and} \,\,\,y =\sqrt{4- x^2}$$ A baton of length $1$ has one end attached to each track and is allowed to move freely, but no end may be picked up or go past the end of either track. What is the maximum area the baton can sweep out? [b]p6.[/b] For integers $1 \le a \le 2$, $1 \le b \le 10$,$ 1 \le c \le 12$, $1 \le d \le 18$, let $f(a, b, c, d)$ be the unique integer between $0$ and $8150$ inclusive that leaves a remainder of a when divided by $3$, a remainder of $b$ when divided by $11$, a remainder of $c$ when divided by $13$, and a remainder of $d$ when divided by $19$. Compute $$\sum_{a+b+c+d=23}f(a, b, c, d).$$ [b]p7.[/b] Compute $\cos ( \theta)$ if $$\sum^{\infty}_{n=0} \frac{ \cos (n\theta)}{3^n} = 1.$$ [b]p8.[/b] How many solutions does this equation $$\left(\frac{a+b}{2}\right)^2=\left(\frac{b+c}{2019}\right)^2$$ have in positive integers $a, b, c$ that are all less than $2019^2$? [b]p9.[/b] Consider a square grid with vertices labeled $1, 2, 3, 4$ clockwise in that order. Fred the frog is jumping between vertices, with the following rules: he starts at the vertex label $1$, and at any given vertex he jumps to the vertex diagonally across from him with probability $\frac12$ and the vertices adjacent to him each with probability $\frac14$ . After $2019$ jumps, suppose the probability that the sum of the labels on the last two vertices he has visited is $3$ can be written as $2^{-m} -2^{-n}$ for positive integers $m,n$. Find $m + n$. [b]p10.[/b] The base ten numeral system uses digits $0-9$ and each place value corresponds to a power of $10$. For example, $$2019 = 2 \cdot 10^3 + 0 \cdot 10^2 + 1 \cdot 10^1 + 9 \cdot 10^0.$$ Let $\phi =\frac{1 +\sqrt5}{2}$. We can define a similar numeral system, base , where we only use digits $0$ and $1$, and each place value corresponds to a power of . For example, $$11.01 = 1 \cdot \phi^1 + 1 \cdot \phi^0 + 0 \cdot \phi^{-1} + 1 \cdot \phi^{-2}$$ Note that base  representations are not unique, because, for example, $100_{\phi} = 11_{\phi}$. Compute the base $\phi$ representation of $7$ with the fewest number of $1$s. [b]p11.[/b] Let $ABC$ be a triangle with $\angle BAC = 60^o$ and with circumradius $1$. Let $G$ be its centroid and $D$ be the foot of the perpendicular from $A$ to $BC$. Suppose $AG =\frac{\sqrt6}{3}$ . Find $AD$. [b]p12.[/b] Let $f(a, b)$ be a function with the following properties for all positive integers $a \ne b$: $$f(1, 2) = f(2, 1)$$ $$f(a, b) + f(b, a) = 0$$ $$f(a + b, b) = f(b, a) + b$$ Compute: $$\sum^{2019}_{i=1} f(4^i - 1, 2^i) + f(4^i + 1, 2^i)$$ [b]p13.[/b] You and your friends have been tasked with building a cardboard castle in the two-dimensional Cartesian plane. The castle is built by the following rules: 1. There is a tower of height $2^n$ at the origin. 2. From towers of height $2^i \ge 2$, a wall of length $2^{i-1}$ can be constructed between the aforementioned tower and a new tower of height $2^{i-1}$. Walls must be parallel to a coordinate axis, and each tower must be connected to at least one other tower by a wall. If one unit of tower height costs $\$9$ and one unit of wall length costs $\$3$ and $n = 1000$, how many distinct costs are there of castles that satisfy the above constraints? Two castles are distinct if there exists a tower or wall that is in one castle but not in the other. [b]p14.[/b] For $n$ digits, $(a_1, a_2, ..., a_n)$ with $0 \le a_i < n$ for $i = 1, 2,..., n$ and $a_1 \ne 0$ define $(\overline{a_1a_2 ... a_n})_n$ to be the number with digits $a_1$, $a_2$, $...$, $a_n$ written in base $n$. Let $S_n = \{(a_1, a_2, a_3,..., a_n)| \,\,\, (n + 1)| (\overline{a_1a_2 ... a_n})_n, a_1 \ge 1\}$ be the set of $n$-tuples such that $(\overline{a_1a_2 ... a_n})_n$ is divisible by $n + 1$. Find all $n > 1$ such that $n$ divides $|S_n| + 2019$. [b]p15.[/b] Let $P$ be the set of polynomials with degree $2019$ with leading coefficient $1$ and non-leading coefficients from the set $C = \{-1, 0, 1\}$. For example, the function $f = x^{2019} - x^{42} + 1$ is in $P$, but the functions $f = x^{2020}$, $f = -x^{2019}$, and $f = x^{2019} + 2x^{21}$ are not in $P$. Define a [i]swap [/i]on a polynomial $f$ to be changing a term $ax^n$ to $bx^n$ where $b \in C$ and there are no terms with degree smaller than $n$ with coefficients equal to $a$ or $b$. For example, a swap from $x^{2019} + x^{17} - x^{15} + x^{10}$ to $x^{2019} + x^{17} - x^{15} - x^{10}$ would be valid, but the following swaps would not be valid: $$x^{2019} + x^3 \,\,\, \text{to} \,\,\, x^{2019}$$ $$x^{2019} + x^3 \,\,\, \text{to} \,\,\, x^{2019} + x^3 + x^2$$ $$x^{2019} + x^2 + x + 1 \,\,\, \text{to} \,\,\, x^{2019} - x^2 - x - 1$$ Let $B$ be the set of polynomials in $P$ where all non-leading terms have the same coefficient. There are $p$ polynomials that can be reached from each element of $B$ in exactly $s$ swaps, and there exist $0$ polynomials that can be reached from each element of $B$ in less than $s$ swaps. Compute $p \cdot s$, expressing your answer as a prime factorization. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $k$ be a positive integer. Show that for all $n>k$ there exist convex figures $F_{1},\ldots, F_{n}$ and $F$ such that there doesn't exist a subset of $k$ elements from $F_{1},..., F_{n}$ and $F$ is covered for this elements, but $F$ is covered for every subset of $k+1$ elements from $F_{1}, F_{2},....., F_{n}$.

$D_n$ is a set of domino pieces. For each pair of non-negative integers $(a, b)$ with $a \le b \le n$, there is one domino, denoted $[a, b]$ or $[b, a]$ in $D_n$. A [i]ring [/i] is a sequence of dominoes $[a_1, b_1], [a_2, b_2], ... , [a_k, b_k]$ such that $b_1 = a_2, b_2 = a_3, ... , b_{k-1} = a_k$ and $b_k = a_1$. Show that if $n$ is even there is a ring which uses all the pieces. Show that for n odd, at least $(n+1)/2$ pieces are not used in any ring. For $n$ odd, how many different sets of $(n+1)/2$ are there, such that the pieces not in the set can form a ring?

Find all positive integers $n \ge 4$ for which there are $n$ points in general position on the plane such that an arbitrary triangle with vertices belonging to the convex hull of these $n$ points, containing exactly one of $n - 3$ points inside remained.

On the board are written numbers $1, 2,. . . , 33$. In one step we select two numbers written on the product of which is the square of the natural number, we wipe off the two chosen numbers and write the square root of their product on the board. This way we continue to the board only the numbers remain so that the product of neither of them is a square. (In one we can also wipe out two identical numbers and replace them with the same number.) Prove that at least $16$ numbers remain on the board.

Players $A$ and $B$ play a game on a blackboard that initially contains 2020 copies of the number 1 . In every round, player $A$ erases two numbers $x$ and $y$ from the blackboard, and then player $B$ writes one of the numbers $x+y$ and $|x-y|$ on the blackboard. The game terminates as soon as, at the end of some round, one of the following holds: [list] [*] $(1)$ one of the numbers on the blackboard is larger than the sum of all other numbers; [*] $(2)$ there are only zeros on the blackboard. [/list] Player $B$ must then give as many cookies to player $A$ as there are numbers on the blackboard. Player $A$ wants to get as many cookies as possible, whereas player $B$ wants to give as few as possible. Determine the number of cookies that $A$ receives if both players play optimally.

A group consists of $n$ tourists. Among every three of them there are at least two that are not familiar. For any partition of the group into two busses, there are at least two familiar tourists in one bus. Prove that there is a tourist who is familiar with at most two fifth of all the tourists.

Let $N$ be a positive integer. Consider a $N \times N$ array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A [i]move[/i] consists of choosing a row or a column and changing the color of every cell in the chosen row or column. What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?

In a football season, even number $n$ of teams plays a simple series, i.e. each team plays once against each other team. Show that ona can group the series into $n-1$ rounds such that in every round every team plays exactly one match.

In every cell of a table with $n$ rows and ten columns, a digit is written. It is known that for every row $A$ and any two columns, you can always find a row that has different digits from $A$ only when it intersects with two columns. Prove that $n\geq512$.

Beto plays the following game with his computer: initially the computer randomly picks $30$ integers from $1$ to $2015$, and Beto writes them on a chalkboard (there may be repeated numbers). On each turn, Beto chooses a positive integer $k$ and some if the numbers written on the chalkboard, and subtracts $k$ from each of the chosen numbers, with the condition that the resulting numbers remain non-negative. The objective of the game is to reduce all $30$ numbers to $0$, in which case the game ends. Find the minimal number $n$ such that, regardless of which numbers the computer chooses, Beto can end the game in at most $n$ turns.

To [i]dissect [/i] a polygon means to divide it into several regions by cutting along finitely many line segments. For example, the diagram below shows a dissection of a hexagon into two triangles and two quadrilaterals: [img]https://cdn.artofproblemsolving.com/attachments/0/a/378e477bcbcec26fc90412c3eada855ae52b45.png[/img] An [i]integer-ratio[/i] right triangle is a right triangle whose side lengths are in an integer ratio. For example, a triangle with sides $3,4,5$ is an[i] integer-ratio[/i] right triangle, and so is a triangle with sides $\frac52 \sqrt3 ,6\sqrt3, \frac{13}{2} \sqrt3$. On the other hand, the right triangle with sides$ \sqrt2 ,\sqrt5, \sqrt7$ is not an [i]integer-ratio[/i] right triangle. Determine, with proof, all integers $n$ for which it is possible to completely [i]dissect [/i] a regular $n$-sided polygon into [i]integer-ratio[/i] right triangles.

There are a number of cards on a table. A number is written on each card. The "pick and replace" operation involves the following: two random cards are taken from the table and replaced by one new card. If the numbers $a$ and $b$ appear on the two packed cards, the number $a + b + ab$ is set on the new card. If we start with ten cards with the numbers $1, 2, 3, 4, 5, 6, 7, 8, 9$ and $10$ respectively, what value(s) can the number have that "grab and replace" nine times is on the only card still on the table? Prove your answer

In a country with $n$ towns, all the direct flights are of double destinations (back and forth). There are $r>2014$ rootes between different pairs of towns, that include no more than one intermediate stop (direction of each root matters). Find the minimum possible value of $n$ and the minimum possible $r$ for that value of $n$.

Let $ n $ be a natural number. Consider all permutations $ ({{a} _ {1}}, \ \ldots, \ {{a} _ {2n}}) $ of the first $ 2n $ natural numbers such that the numbers $ | {{a} _ {i +1}} - {{a} _ {i}} |, \ i = 1, \ \ldots, \ 2n-1, $ are pairwise different. Prove that $ {{a} _ {1}} - {{a} _ {2n}} = n $ if and only if $ 1 \le {{a} _ {2k}} \le n $ for all $ k = 1, \ \ldots, \ n $.

Ahmad and Salem play the following game. Ahmad writes two integers (not necessarily different) on a board. Salem writes their sum and product. Ahmad does the same thing: he writes the sum and product of the two numbers which Salem has just written. They continue in this manner, not stopping unless the two players write the same two numbers one after the other (for then they are stuck!). The order of the two numbers which each player writes is not important. Thus if Ahmad starts by writing $3$ and $-2$, the first five moves (or steps) are as shown: (a) Step 1 (Ahmad) $3$ and $-2$ (b) Step 2 (Salem) $1$ and $-6$ (c) Step 3 (Ahmad) $-5$ and $-6$ (d) Step 4 (Salem) $-11$ and $30$ (e) Step 5 (Ahmad) $19$ and $-330$ (i) Describe all pairs of numbers that Ahmad could write, and ensure that Salem must write the same numbers, and so the game stops at step 2. (ii) What pair of integers should Ahmad write so that the game finishes at step 4? (iii) Describe all pairs of integers which Ahmad could write at step 1, so that the game will finish after finitely many steps. (iv) Ahmad and Salem decide to change the game. The first player writes three numbers on the board, $u, v$ and $w$. The second player then writes the three numbers $u + v + w,uv + vw + wu$ and $uvw$, and they proceed as before, taking turns, and using this new rule describing how to work out the next three numbers. If Ahmad goes first, determine all collections of three numbers which he can write down, ensuring that Salem has to write the same three numbers at the next step.

For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

Let $n \geq 2$ be a positive integer. Let $\mathcal{R}$ be a connected set of unit squares on a grid. A [i]bar[/i] is a rectangle of length or width $1$ which is fully contained in $\mathcal{R}$. A bar is [i]special[/i] if it is not fully contained within any larger bar. Given that $\mathcal{R}$ contains special bars of sizes $1 \times 2,1 \times 3,\ldots,1 \times n$, find the smallest possible number of unit squares in $\mathcal{R}$. [i]Srinivas Arun[/i]