Given $2n$ genuine coins and $2n$ fake coins. The fake coins look the same as genuine coins but weigh less (but all fake coins have the same weight). Show how to identify each coin as genuine or fake using a balance at most $3n$ times.

Baron Minchausen talked to a mathematician. Baron said that in his country from any town one can reach any other town by a road. Also, if one makes a circular trip from any town, one passes through an odd number of other towns. By this, as an answer to the mathematician’s question, Baron said that each town is counted as many times as it is passed through. Baron also added that the same number of roads start at each town in his country, except for the town where he was born, at which a smaller number of roads start. Then the mathematician said that baron lied. How did he conclude that?

The $n$ players of a hockey team gather to select their team captain. Initially, they stand in a circle, and each person votes for the person on their left. The players will update their votes via a series of rounds. In one round, each player $a$ updates their vote, one at a time, according to the following procedure: At the time of the update, if $a$ is voting for $b,$ and $b$ is voting for $c,$ then $a$ updates their vote to $c.$ (Note that $a, b,$ and $c$ need not be distinct; if $b=c$ then $a$'s vote does not change for this update.) Every player updates their vote exactly once in each round, in an order determined by the players (possibly different across different rounds). They repeat this updating procedure for $n$ rounds. Prove that at this time, all $n$ players will unanimously vote for the same person.

Compute the three-digit number that satisfies the following properties: $\bullet$ The hundreds digit and ones digit are the same, but the tens digit is different. $\bullet$ The number is divisible by $9$. $\bullet$ When the number is divided by $5$, the remainder is $1$.

Let $C$ be a coloring of all edges and diagonals of a convex $n$−gon in red and blue (in Romanian, rosu and albastru). Denote by $q_r(C)$ (resp. $q_a(C)$) the number of quadrilaterals having all its edges and diagonals red (resp. blue). Prove: $ \underset{C}{min} (q_r(C)+q_a(C)) \le \frac{1}{32} {n \choose 4}$

The numbers $1$ through $4^{n}$ are written on a board. In each step, Pedro erases two numbers $a$ and $b$ from the board, and writes instead the number $\frac{ab}{\sqrt{2a^2+2b^2}}$. Pedro repeats this procedure until only one number remains. Prove that this number is less than $\frac{1}{n}$, no matter what numbers Pedro chose in each step.

Find all pairs of integers $(c, d)$, both greater than 1, such that the following holds: For any monic polynomial $Q$ of degree $d$ with integer coefficients and for any prime $p > c(2c+1)$, there exists a set $S$ of at most $\big(\tfrac{2c-1}{2c+1}\big)p$ integers, such that \[\bigcup_{s \in S} \{s,\; Q(s),\; Q(Q(s)),\; Q(Q(Q(s))),\; \dots\}\] contains a complete residue system modulo $p$ (i.e., intersects with every residue class modulo $p$).

Find all positive integer $n$ , such that for all 35-element-subsets of $M=(1,2,3,...,50)$ ,there exists at least two different elements $a,b$ , satisfing : $a-b=n$ or $a+b=n$.

Prove that for a given convex polygon of area $A$ and perimeter $P$ there exists a circle of radius $\frac AP$ that is contained in the interior of the polygon.

Let $a_1, a_2, . . ., a_n$ be a finite sequence of $0$ and $1$. Under any two consecutive terms of this sequence $0$ is written if the digits are equal and $1$ is written otherwise. This way a new sequence of length $n -1$ is obtained. By repeating this procedure $n - 1$ times one obtains a triangular table of $0$ and $1$. Find the maximum possible number of ones that can appear on this table

Divide the plane into $1$x$1$ squares formed by the lattice points. Let$S$ be the set-theoretic union of a finite number of such cells, and let $a$ be a positive real number less than or equal to 1/4.Show that S can be covered by a finite number of squares satisfying the following three conditions: 1) Each square in the cover is an array of $1$x$1$ cells 2) The squares in the cover have pairwise disjoint interios and 3)For each square $Q$ in the cover the ratio of the area $S \cap Q$ to the area of Q is at least $a$ and at most $a {(\lfloor a^{-1/2} \rfloor)} ^2$

Given 98 points in a circle. Mary and Joseph play alternatively in the next way: - Each one draw a segment joining two points that have not been joined before. The game ends when the 98 points have been used as end points of a segments at least once. The winner is the person that draw the last segment. If Joseph starts the game, who can assure that is going to win the game.

Prove that an $m \times n$ rectangle can be constructed using copies of the following shape if and only if $mn$ is a multiple of $8$ where $m>1$ and $n>1$ [asy] draw ((0,0)--(0,1)); draw ((0,0)--(1.5,0)); draw ((0,1)--(.5,1)); draw ((.5,1)--(.5,0)); draw ((0,.5)--(1.5,.5)); draw ((1.5,.5)--(1.5,0)); draw ((1,.5)--(1,0)); [/asy]

In a lottery, a person must select six distinct numbers from $1, 2, 3,\dots, 36$ to put on a ticket. The lottery commitee will then draw six distinct numbers randomly from $1, 2, 3, \ldots, 36$. Any ticket with numbers not containing any of these $6$ numbers is a winning ticket. Show that there is a scheme of buying $9$ tickets guaranteeing at least one winning ticket, but $8$ tickets are not enough to guarantee a winning ticket in general.

[u]Round 5[/u] [i]Each of the three problems in this round depends on the answer to two of the other problems. There is only one set of correct answers to these problems; however, each problem will be scored independently, regardless of whether the answers to the other problems are correct. [/i] [b]p13.[/b] Let $B$ be the answer to problem $14$, and let $C$ be the answer to problem $15$. A quadratic function $f(x)$ has two real roots that sum to $2^{10} + 4$. After translating the graph of $f(x)$ left by $B$ units and down by $C$ units, the new quadratic function also has two real roots. Find the sum of the two real roots of the new quadratic function. [b]p14.[/b] Let $A$ be the answer to problem $13$, and let $C$ be the answer to problem $15$. In the interior of angle $\angle NOM = 45^o$, there is a point $P$ such that $\angle MOP = A^o$ and $OP = C$. Let $X$ and $Y$ be the reflections of $P$ over $MO$ and $NO$, respectively. Find $(XY)^2$. [b]p15.[/b] Let $A$ be the answer to problem $13$, and let $B$ be the answer to problem $14$. Totoro hides a guava at point $X$ in a flat field and a mango at point $Y$ different from $X$ such that the length $XY$ is $B$. He wants to hide a papaya at point $Z$ such that $Y Z$ has length $A$ and the distance $ZX$ is a nonnegative integer. In how many different locations can he hide the papaya? [u]Round 6[/u] [b]p16.[/b] Let $ABCD$ be a trapezoid such that $AB$ is parallel to $CD$, $AB = 4$, $CD = 8$, $BC = 5$, and $AD = 6$. Given that point $E$ is on segment $CD$ and that $AE$ is parallel to $BC$, find the ratio between the area of trapezoid $ABCD$ and the area of triangle $ABE$. [b]p17.[/b] Find the maximum possible value of the greatest common divisor of $\overline{MOO}$ and $\overline{MOOSE}$, given that $S$, $O$, $M$, and $E$ are some nonzero digits. (The digits $S$, $O$, $M$, and $E$ are not necessarily pairwise distinct.) [b]p18.[/b] Suppose that $125$ politicians sit around a conference table. Each politician either always tells the truth or always lies. (Statements of a liar are never completely true, but can be partially true.) Each politician now claims that the two people beside them are both liars. Suppose that the greatest possible number of liars is $M$ and that the least possible number of liars is $N$. Determine the ordered pair $(M,N)$. [u]Round 7[/u] [b]p19.[/b] Define a [i]lucky [/i] number as a number that only contains $4$s and $7$s in its decimal representation. Find the sum of all three-digit lucky numbers. [b]p20.[/b] Let line segment $AB$ have length $25$ and let points $C$ and $D$ lie on the same side of line $AB$ such that $AC = 15$, $AD = 24$, $BC = 20$, and $BD = 7$. Given that rays $AC$ and $BD$ intersect at point $E$, compute $EA + EB$. [b]p21.[/b] A $3\times 3$ grid is filled with positive integers and has the property that each integer divides both the integer directly above it and directly to the right of it. Given that the number in the top-right corner is $30$, how many distinct grids are possible? [u]Round 8[/u] [b]p22.[/b] Define a sequence of positive integers $s_1, s_2, ... , s_{10}$ to be [i]terrible [/i] if the following conditions are satisfied for any pair of positive integers $i$ and $j$ satisfying $1 \le i < j \le 10$: $\bullet$ $s_i > s_j $ $\bullet$ $j - i + 1$ divides the quantity $s_i + s_{i+1} + ... + s_j$ Determine the minimum possible value of $s_1 + s_2 + ...+ s_{10}$ over all terrible sequences. [b]p23.[/b] The four points $(x, y)$ that satisfy $x = y^2 - 37$ and $y = x^2 - 37$ form a convex quadrilateral in the coordinate plane. Given that the diagonals of this quadrilateral intersect at point $P$, find the coordinates of $P$ as an ordered pair. [b]p24.[/b] Consider a non-empty set of segments of length $1$ in the plane which do not intersect except at their endpoints. (In other words, if point $P$ lies on distinct segments $a$ and $b$, then $P$ is an endpoint of both $a$ and $b$.) This set is called $3$-[i]amazing [/i] if each endpoint of a segment is the endpoint of exactly three segments in the set. Find the smallest possible size of a $3$-amazing set of segments. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2934024p26255963]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

The edges of a graph $G$ are coloured in two colours. Such that for each colour all the connected components of this graph formed by edges of this colour contains at most $n>1$ vertices. Prove there exists a proper colouring for the vertices of this graph with $n$ colours.

Let $ \sigma = (a_1, a_2, \cdots , a_n)$ be permutation of $ (1, 2 ,\cdots, n)$. A pair $ (a_i, a_j)$ is said to correspond to an [b]inversion[/b] of $\sigma$ if $ i<j$ but $ a_i>a_j$. How many permutations of $ (1,2,\cdots,n)$, $ n \ge 3$, have exactly [b]two[/b] inversions? For example, In the permutation $(2,4,5,3,1)$, there are 6 inversions corresponding to the pairs $ (2,1),(4,3),(4,1),(5,3),(5,1),(3,1)$.

The [i]fractional distance[/i] between two points $(x_1,y_1)$ and $(x_2,y_2)$ is defined as \[ \sqrt{ \left\| x_1 - x_2 \right\|^2 + \left\| y_1 - y_2 \right\|^2},\]where $\left\| x \right\|$ denotes the distance between $x$ and its nearest integer. Find the largest real $r$ such that there exists four points on the plane whose pairwise fractional distance are all at least $r$.

Consider a convex $2000$-gon, no three of whose diagonals have a common point. Each of its diagonals is colored in one of $999$ colors. Prove that there exists a triangle all of whose sides lie on diagonals of the same color. (Vertices of the triangle need not be vertices of the original polygon.)

In an exotic country, the National Bank issues coins that can take any value in the interval $[0, 1]$. Find the smallest constant $c > 0$ such that the following holds, no matter the situation in that country: [i]Any citizen of the exotic country that has a finite number of coins, with a total value of no more than $1000$, can split those coins into $100$ boxes, such that the total value inside each box is at most $c$.[/i]

[b]p1.[/b] Evaluate $6^4 +5^4 +3^4 +2^4$. [b]p2.[/b] What digit is most frequent between $1$ and $1000$ inclusive? [b]p3.[/b] Let $n = gcd \, (2^2 \cdot 3^3 \cdot 4^4,2^4 \cdot 3^3 \cdot 4^2)$. Find the number of positive integer factors of $n$. [b]p4.[/b] Suppose $p$ and $q$ are prime numbers such that $13p +5q = 91$. Find $p +q$. [b]p5.[/b] Let $x = (5^3 -5)(4^3 -4)(3^3 -3)(2^3 -2)(1^3 -1)$. Evaluate $2018^x$ . [b]p6.[/b] Liszt the lister lists all $24$ four-digit integers that contain each of the digits $1,2,3,4$ exactly once in increasing order. What is the sum of the $20$th and $18$th numbers on Liszt’s list? [b]p7.[/b] Square $ABCD$ has center $O$. Suppose $M$ is the midpoint of $AB$ and $OM +1 =OA$. Find the area of square $ABCD$. [b]p8.[/b] How many positive $4$-digit integers have at most $3$ distinct digits? [b]p9.[/b] Find the sumof all distinct integers obtained by placing $+$ and $-$ signs in the following spaces $$2\_3\_4\_5$$ [b]p10.[/b] In triangle $ABC$, $\angle A = 2\angle B$. Let $I$ be the intersection of the angle bisectors of $B$ and $C$. Given that $AB = 12$, $BC = 14$,and $C A = 9$, find $AI$ . [b]p11.[/b] You have a $3\times 3\times 3$ cube in front of you. You are given a knife to cut the cube and you are allowed to move the pieces after each cut before cutting it again. What is the minimumnumber of cuts you need tomake in order to cut the cube into $27$ $1\times 1\times 1$ cubes? p12. How many ways can you choose $3$ distinct numbers fromthe set $\{1,2,3,...,20\}$ to create a geometric sequence? [b]p13.[/b] Find the sum of all multiples of $12$ that are less than $10^4$ and contain only $0$ and $4$ as digits. [b]p14.[/b] What is the smallest positive integer that has a different number of digits in each base from $2$ to $5$? [b]p15.[/b] Given $3$ real numbers $(a,b,c)$ such that $$\frac{a}{b +c}=\frac{b}{3a+3c}=\frac{c}{a+3b},$$ find all possible values of $\frac{a +b}{c}$. [b]p16.[/b] Let S be the set of lattice points $(x, y, z)$ in $R^3$ satisfying $0 \le x, y, z \le 2$. How many distinct triangles exist with all three vertices in $S$? [b]p17.[/b] Let $\oplus$ be an operator such that for any $2$ real numbers $a$ and $b$, $a \oplus b = 20ab -4a -4b +1$. Evaluate $$\frac{1}{10} \oplus \frac19 \oplus \frac18 \oplus \frac17 \oplus \frac16 \oplus \frac15 \oplus \frac14 \oplus \frac13 \oplus \frac12 \oplus 1.$$ [b]p18.[/b] A function $f :N \to N$ satisfies $f ( f (x)) = x$ and $f (2f (2x +16)) = f \left(\frac{1}{x+8} \right)$ for all positive integers $x$. Find $f (2018)$. [b]p19.[/b] There exists an integer divisor $d$ of $240100490001$ such that $490000 < d < 491000$. Find $d$. [b]p20.[/b] Let $a$ and $b$ be not necessarily distinct positive integers chosen independently and uniformly at random from the set $\{1,2, 3, ... ,511,512\}$. Let $x = \frac{a}{b}$ . Find the probability that $(-1)^x$ is a real number. [b]p21[/b]. In $\vartriangle ABC$ we have $AB = 4$, $BC = 6$, and $\angle ABC = 135^o$. $\angle ABC$ is trisected by rays $B_1$ and $B_2$. Ray $B_1$ intersects side $C A$ at point $F$, and ray $B_2$ intersects side $C A$ at point $G$. What is the area of $\vartriangle BFG$? [b]p22.[/b] A level number is a number which can be expressed as $x \cdot \lfloor x \rfloor \cdot \lceil x \rceil$ where $x$ is a real number. Find the number of positive integers less than or equal to $1000$ which are also level numbers. [b]p23.[/b] Triangle $\vartriangle ABC$ has sidelengths $AB = 13$, $BC = 14$, $C A = 15$ and circumcenter $O$. Let $D$ be the intersection of $AO$ and $BC$. Compute $BD/DC$. [b]p24.[/b] Let $f (x) = x^4 -3x^3 +2x^2 +5x -4$ be a quartic polynomial with roots $a,b,c,d$. Compute $$\left(a+1 +\frac{1}{a} \right)\left(b+1 +\frac{1}{b} \right)\left(c+1 +\frac{1}{c} \right)\left(d+1 +\frac{1}{d} \right).$$ [b]p25.[/b] Triangle $\vartriangle ABC$ has centroid $G$ and circumcenter $O$. Let $D$ be the foot of the altitude from $A$ to $BC$. If $AD = 2018$, $BD =20$, and $CD = 18$, find the area of triangle $\vartriangle DOG$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Each of the natural numbers from $1$ to $n$ is colored either red or blue, with each color being used at least once. It turns out that: – every red number is a sum of two distinct blue numbers; and – every blue number is a difference between two red numbers. Determine the smallest possible value of $n$ for which such a coloring exists.

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]

Let $R$ be an $20 \times 18$ grid of points such that adjacent points are $1$ unit apart. A fly starts at a point and jumps in straight lines to other points in $R$ in turn, such that each point in R is visited exactly once and no two jumps intersect at a point other than an endpoint of a jump, for a total of $359$ jumps. Call a jump small if it is of length $1$. What is the least number of small jumps? (The left configuration for a $4 \times 4$ grid has $9$ small jumps and $15$ total jumps, while the right configuration is invalid.)

Let $k$, $\ell $ and $m$ be positive integers. Let $ABCDEF$ be a hexagon that has a center of symmetry whose angles are all $120^\circ$ and let its sidelengths be $AB=k$, $BC=\ell$ and $CD=m$. Let $f(k,\ell,m)$ denote the number of ways we can partition hexagon $ABCDEF$ into rhombi with unit sides and an angle of $120^\circ$. Prove that by fixing $\ell$ and $m$, there exists polynomial $g_{\ell,m}$ such that $f(k,\ell,m)=g_{\ell,m}(k)$ for every positive integer $k$, and find the degree of $g_{\ell,m}$ in terms of $\ell$ and $m$. [i]Submitted by Zoltán Gyenes, Budapest[/i]