In a text editor program, initially there is a footprint symbol (L) that we want to multiply. Unfortunately, our computer has been the victim of a hacker attack, and only two functions are working: Copy and Paste, each costing 1 Dürer dollar to use. Using the Copy function, we can select one or more consecutive symbols from the existing ones, and the computer memorizes their number. When using the Paste function, the computer adds as many new footprint symbols to the sequence as were selected in the last Copy. If no Copy has been done yet, Paste cannot be used. Let $D(n)$ denote the minimum number of Dürer dollars required to obtain exactly $n$ footprint symbols. Prove that for any positive integer $k$, there exists a positive integer $N$ such that \[D(N)=D(N+1)+1=D(N+2)=D(N+3)+1=D(N+4)=\ldots=D(N+2k-1)+1=D(N+2k).\] [i]Based on a problem of the Dürer Competition[/i]

Frog is in the origin of decartes coordinate system. Every second frog jumpes horizontally or vertically in some of the $4$ adjacent points which coordinates are integers. Find number of different points in which frog can be found in $2015$ seconds.

[hide=E stands for Euclid , L stands for Lobachevsky]they had two problem sets under those two names[/hide] [b]E1.[/b] How many positive divisors does $72$ have? [b]E2 / L2.[/b] Raymond wants to travel in a car with $3$ other (distinguishable) people. The car has $5$ seats: a driver’s seat, a passenger seat, and a row of $3$ seats behind them. If Raymond’s cello must be in a seat next to him, and he can’t drive, but every other person can, how many ways can everyone sit in the car? [b]E3 / L3.[/b] Peter wants to make fruit punch. He has orange juice ($100\%$ orange juice), tropical mix ($25\%$ orange juice, $75\%$ pineapple juice), and cherry juice ($100\%$ cherry juice). If he wants his final mix to have $50\%$ orange juice, $10\%$ cherry juice, and $40\%$ pineapple juice, in what ratios should he mix the $3$ juices? Please write your answer in the form (orange):(tropical):(cherry), where the three integers are relatively prime. [b]E4 / L4.[/b] Points $A, B, C$, and $D$ are chosen on a circle such that $m \angle ACD = 85^o$, $m\angle ADC = 40^o$,and $m\angle BCD = 60^o$. What is $m\angle CBD$? [b]E5.[/b] $a, b$, and $c$ are positive real numbers. If $abc = 6$ and $a + b = 2$, what is the minimum possible value of $a + b + c$? [b]E6 / L5.[/b] Circles $A$ and $B$ are drawn on a plane such that they intersect at two points. The centers of the two circles and the two intersection points lie on another circle, circle $C$. If the distance between the centers of circles $A$ and $B$ is $20$ and the radius of circle $A$ is $16$, what is the radius of circle $B$? [b]E7.[/b] Point $P$ is inside rectangle $ABCD$. If $AP = 5$, $BP = 6$, and $CP = 7$, what is the length of $DP$? [b]E8 / L6.[/b] For how many integers $n$ is $n^2 + 4$ divisible by $n + 2$? [b]E9. [/b] How many of the perfect squares between $1$ and $10000$, inclusive, can be written as the sum of two triangular numbers? We define the $n$th triangular number to be $1 + 2 + 3 + ... + n$, where $n$ is a positive integer. [b]E10 / L7.[/b] A small sphere of radius $1$ is sitting on the ground externally tangent to a larger sphere, also sitting on the ground. If the line connecting the spheres’ centers makes a $60^o$ angle with the ground, what is the radius of the larger sphere? [b]E11 / L8.[/b] A classroom has $12$ chairs in a row and $5$ distinguishable students. The teacher wants to position the students in the seats in such a way that there is at least one empty chair between any two students. In how many ways can the teacher do this? [b]E12 / L9.[/b] Let there be real numbers $a$ and $b$ such that $a/b^2 + b/a^2 = 72$ and $ab = 3$. Find the value of $a^2 + b^2$. [b]E13 / L10.[/b] Find the number of ordered pairs of positive integers $(x, y)$ such that $gcd \, (x, y)+lcm \, (x, y) =x + y + 8$. [b]E14 / L11.[/b] Evaluate $\sum_{i=1}^{\infty}\frac{i}{4^i}=\frac{1}{4} +\frac{2}{16} +\frac{3}{64} +...$ [b]E15 / L12.[/b] Xavier and Olivia are playing tic-tac-toe. Xavier goes first. How many ways can the game play out such that Olivia wins on her third move? The order of the moves matters. [b]L1.[/b] What is the sum of the positive divisors of $100$? [b]L13.[/b] Let $ABCD$ be a convex quadrilateral with $AC = 20$. Furthermore, let $M, N, P$, and $Q$ be the midpoints of $DA, AB, BC$, and $CD$, respectively. Let $X$ be the intersection of the diagonals of quadrilateral $MNPQ$. Given that $NX = 12$ and $XP = 10$, compute the area of $ABCD$. [b]L14.[/b] Evaluate $(\sqrt3 + \sqrt5)^6$ to the nearest integer. [b]L15.[/b] In Hatland, each citizen wears either a green hat or a blue hat. Furthermore, each citizen belongs to exactly one neighborhood. On average, a green-hatted citizen has $65\%$ of his neighbors wearing green hats, and a blue-hatted citizen has $80\%$ of his neighbors wearing blue hats. Each neighborhood has a different number of total citizens. What is the ratio of green-hatted to blue-hatted citizens in Hatland? (A citizen is his own neighbor.) PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $ G$ be a simple graph. Suppose that size of largest independent set in $ G$ is $ \alpha$. Prove that: a) Vertices of $ G$ can be partitioned to at most $ \alpha$ paths. b) Suppose that a vertex and an edge are also cycles. Prove that vertices of $ G$ can be partitioned to at most $ \alpha$ cycles.

We consider a polyhedra which has exactly two vertices adjacent with an odd number of edges, and these two vertices are lying on the same edge. Prove that for all integers $n\geq 3$ there exists a face of the polyhedra with a number of sides not divisible by $n$.

Show that one can color all the points of a plane using only two colors such that no line segment has all points of the same color.

There are $N$ acute triangles on the plane. Their vertices are all integer points, their areas are all equal to $2^{2020}$, but no two of them are congruent. Find the maximum possible value of $N$. Note: $(x,y)$ is an integer point if and only if $x$ and $y$ are both integers. [i]Proposed by CSJL[/i]

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

Given a finite number of boys and girls, a [i]sociable set of boys[/i] is a set of boys such that every girl knows at least one boy in that set; and a [i]sociable set of girls[/i] is a set of girls such that every boy knows at least one girl in that set. Prove that the number of sociable sets of boys and the number of sociable sets of girls have the same parity. (Acquaintance is assumed to be mutual.) [i](Poland) Marek Cygan[/i]

The integers from $1$ to $25,$ inclusive, are randomly placed into a $5$ by $5$ grid such that in each row, the numbers are increasing from left to right. If the columns from left to right are numbered $1,2,3,4,$ and $5,$ then the expected column number of the entry $23$ can be written as $\tfrac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Find $a+b.$

A plane has several seats on it, each with its own price, as shown below(attachment). $2n-2$ passengers wish to take this plane, but none of them wants to sit with any other passenger in the same column or row. The captain realize that, no matter how he arranges the passengers, the total money he can collect is the same. Proof this fact, and compute how much money the captain can collect.

Let $n$ be a positive integer. On a $2n\times 2n$ board, the $2n^2$ squares were painted white and the other $2n^2$ squares were painted black. One operation is to choose a $2\times 2$ subtable and mirror its $4$ cells about the vertical or horizontal axis of symmetry of that subtable. For what values of $n$ is it always possible to obtain a chess-like coloring from any initial coloring?

Prove that every finite triangle-free graph can be embedded as an induced subgraph in a finite triangle-free graph of diameter 2.

Every single point on the plane with integer coordinates is coloured either red, green or blue. Find the least possible positive integer $n$ with the following property: no matter how the points are coloured, there is always a triangle with area $n$ that has its $3$ vertices with the same colour.

Given a figure, containing $16$ segments. You should prove that there is no curve, that intersect each segment exactly once. The curve may be not closed, may intersect itself, but it is not allowed to touch the segments or to pass through the vertices. [asy] draw((0,0)--(6,0)--(6,3)--(0,3)--(0,0)); draw((0,3/2)--(6,3/2)); draw((2,0)--(2,3/2)); draw((4,0)--(4,3/2)); draw((3,3/2)--(3,3)); [/asy]

Consider a $1$-indexed array that initially contains the integers $1$ to $10$ in increasing order. The following action is performed repeatedly (any number of times): [code] def action(): Choose an integer n between 1 and 10 inclusive Reverse the array between indices 1 and n inclusive Reverse the array between indices n+1 and 10 inclusive (If n = 10, we do nothing) [/code] How many possible orders can the array have after we are done with this process?

3. Eight farmers have a checkered $8 \times 8$ field. There is a fence along the boundary of the field. The entire field is completely covered with berries (there is a berry in every point of the field, except the points of the fence). The farmers divided the field along the grid lines in 8 plots of equal area (every plot is a polygon), however they did not demarcate their boundaries. Each farmer takes care of berries only inside his own plot (not on its boundaries). A farmer will notice a loss only if at least two berries disappeared inside his plot. There is a crow which knows all of the above, except the location of boundaries of plots. Can the crow carry off 9 berries from the field so that for sure no farmer will notice this? Tatiana Kazitsyna

King George has decided to connect the $1680$ islands in his kingdom by bridges. Unfortunately the rebel movement will destroy two bridges after all the bridges have been built, but not two bridges from the same island. What is the minimal number of bridges the King has to build in order to make sure that it is still possible to travel by bridges between any two of the $1680$ islands after the rebel movement has destroyed two bridges?

Let $n$ be a positive integer. Find the smallest positive integer $k$ with the property that for any colouring nof the squares of a $2n$ by $k$ chessboard with $n$ colours, there are $2$ columns and $2$ rows such that the $4$ squares in their intersections have the same colour.

A circle is divided by $2n$ points into $2n$ equal arcs. Let $P_1, P_2, \ldots, P_{2n}$ be an arbitrary permutation of the $2n$ division points. Prove that the polygonal line $P_1 P_2 \cdots P_{2n} P_1$ contains at least two parallel segments.

Given a real number $\alpha$ in whose decimal representation $\alpha=0,a_1a_2a_3\dots$ each decimal digit $a_i$ $(i=1,2,3,\dots)$ is a prime number. The decimal digits are arranged along the path indicated by arrows in the accompanying figure, which can be thought of as continuing infinitely to the right and downward. For each $m\geq 1$, the decimal representation of a real number $z_m$ is formed by writing before the decimal point the digit 0 and after the decimal point the sequence of digits of the $m$-th row from the top read from left to right from the adjacent arrangement. In an analogous way, for all $n\geq 1$, the real numbers $s_n$ are formed with the digits of the $n$-th column from the left to be read from top to bottom. For example, $z_3=0,a_5a_6a_7a_{12}a_{23}a_{28}\dots$ and $s_2=0,a_2a_3a_6a_{15}a_{18}a_{35}\dots$. Show: (a) If $\alpha$ is rational, then all $z_m$ and all $s_n$ are rational. (b) The converse of the statement formulated in (a) is false.

For a sequence $x_1,x_2,\ldots,x_n$ of real numbers, we define its $\textit{price}$ as \[\max_{1\le i\le n}|x_1+\cdots +x_i|.\] Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_1$ such that $|x_1 |$ is as small as possible; among the remaining numbers, he chooses $x_2$ such that $|x_1 + x_2 |$ is as small as possible, and so on. Thus, in the $i$-th step he chooses $x_i$ among the remaining numbers so as to minimise the value of $|x_1 + x_2 + \cdots x_i |$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$. Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G\le cD$. [i]Proposed by Georgia[/i]

Suppose $A\subseteq \{0,1,\dots,29\}$. It satisfies that for any integer $k$ and any two members $a,b\in A$($a,b$ is allowed to be same), $a+b+30k$ is always not the product of two consecutive integers. Please find $A$ with largest possible cardinality.

There are 100 students taking an exam. The professor calls them one by one and asks each student a single person question: “How many of 100 students will have a “passed” mark by the end of this exam?” The students answer must be an integer. Upon receiving the answer, the professor immediately publicly announces the student’s mark which is either “passed” or “failed.” After all the students have got their marks, an inspector comes and checks if there is any student who gave the correct answer but got a “failed” mark. If at least one such student exists, then the professor is suspended and all the marks are replaced with “passed.” Otherwise no changes are made. Can the students come up with a strategy that guarantees a “passed” mark to each of them? [i] Denis Afrizonov [/i]

Three integers $A, B, C$ are written on a whiteboard. Every move, Mr. Doba can either subtract $1$ from all numbers on the board, or choose two numbers on the board and subtract $1$ from both of them whilst leaving the third untouched. For how many ordered triples $(A, B, C)$ with $1 \le A < B < C\le 20$ is it possible for Mr. Doba to turn all three of the numbers on the board to $0$?