A connected graph is given. Prove that its vertices can be coloured blue and green and some of its edges marked so that every two vertices are connected by a path of marked edges, every marked edge connects two vertices of different colour and no two green vertices are connected by an edge of the original graph.

There are some ink-blots on a white paper square with side length $a$. The area of each blot is not greater than $1$ and every line parallel to any one of the sides of the square intersects no more than one blot. Prove that the total area of the blots is not greater than $a$. (A. Razborov, Moscow)

Consider a $2^k$-tuple of numbers $(a_1,a_2,\dots,a_{2^k})$ all equal to $1$ or $-1$. In one step, we transform it to $(a_1a_2,a_2a_3,\dots,a_{2^k}a_1)$. Prove that eventually, we will obtain a $2^k$-tuple consisting only of $1$'s.

If $A$ and $B$ are points of the plane, then by $A * B$ we denote a point symmetric to $A$ with respect to $B$. Is it possible, by applying the operation $*$ several times, to obtain from the three vertices of a given square its fourth vertex?

Let $S$ be a set of points in the plane satisfying the following conditions: (a) there are seven points in $S$ that form a convex heptagon; and (b) for any five points in $S$, if they form a convex pentagon, then there is point in $S$ lies in the interior of the pentagon. Determine the minimum value of the number of elements in $S$.

There are $n$ (an even number) bags. Each bag contains atleast one apple and at most $n$ apples. The total number of apples is $2n$. Prove that it is always possible to divide the bags into two parts such that the number of apples in each part is $n$.

In a career in mathematics, $7$ courses are taught, among which students can choose the ones you want. Determine the number of students in the career, knowing that: $\bullet$ No two students have chosen the same courses. $\bullet$ Any two students have at least one course in common. $\bullet$ If the race had one more student, it would not be possible to do both.

There are $n$ circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he reaches an intersection with another circle. Then he continues his journey on this new circle and also changes the direction of moving, i.e. from clockwise to anticlockwise or $\textit{vice versa}$. Suppose that Turbo’s path entirely covers all circles. Prove that $n$ must be odd. [i]Proposed by Tejaswi Navilarekallu, India[/i]

[b]p1.[/b] Let $A\% B = BA - B - A + 1$. How many digits are in the number $1\%(3\%(3\%7))$ ? [b]p2. [/b]Three circles, of radii $1, 2$, and $3$ are all externally tangent to each other. A fourth circle is drawn which passes through the centers of those three circles. What is the radius of this larger circle? [b]p3.[/b] Express $\frac13$ in base $2$ as a binary number. (Which, similar to how demical numbers have a decimal point, has a “binary point”.) [b]p4. [/b] Isosceles trapezoid $ABCD$ with $AB$ parallel to $CD$ is constructed such that $DB = DC$. If $AD = 20$, $AB = 14$, and $P$ is the point on $AD$ such that $BP + CP$ is minimized, what is $AP/DP$? [b]p5.[/b] Let $f(x) = \frac{5x-6}{x-2}$ . Define an infinite sequence of numbers $a_0, a_1, a_2,....$ such that $a_{i+1} = f(a_i)$ and $a_i$ is always an integer. What are all the possible values for $a_{2014}$ ? [b]p6.[/b] $MATH$ and $TEAM$ are two parallelograms. If the lengths of $MH$ and $AE$ are $13$ and $15$, and distance from $AM$ to $T$ is $12$, find the perimeter of $AMHE$. [b]p7.[/b] How many integers less than $1000$ are there such that $n^n + n$ is divisible by $5$ ? [b]p8.[/b] $10$ coins with probabilities of $1, 1/2, 1/3 ,..., 1/10$ of coming up heads are flipped. What is the probability that an odd number of them come up heads? [b]p9.[/b] An infinite number of coins with probabilities of $1/4, 1/9, 1/16, ...$ of coming up heads are all flipped. What is the probability that exactly $ 1$ of them comes up heads? [b]p10.[/b] Quadrilateral $ABCD$ has side lengths $AB = 10$, $BC = 11$, and $CD = 13$. Circles $O_1$ and $O_2$ are inscribed in triangles $ABD$ and $BDC$. If they are both tangent to $BD$ at the same point $E$, what is the length of $DA$ ? PS. You had better use hide for answers.

Let $m$ be an integer, $m \ge 2$. Each student in a school is practising $m$ hobbies the most. Among any $m$ students there exist two students who have a common hobby. Find the smallest number of students for which there must exist a hobby which is practised by at least $3$ students .

The checker is standing on the corner field of a $n\times n$ chess-board. Each of two players moves it in turn to the neighbour (i.e. that has the common side) field. It is forbidden to move to the field, the checker has already visited. That who cannot make a move losts. a) Prove that for even $n$ the first can always win, and if $n$ is odd, than the second can always win. b) Who wins if the checker stands initially on the neighbour to the corner field?

We are given $1999$ coins. No two coins have the same weight. A machine is provided which allows us with one operation to determine, for any three coins, which one has the middle weight. Prove that the coin that is the $1000$th by weight can be determined using no more than $1000000$ operations and that this is the only coin whose position by weight can be determined using this machine.

Given two points $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$ on the plane, denote by $\mathcal{R}(p_1,p_2)$ the rectangle with sides parallel to the coordinate axes and with $p_1$ and $p_2$ as opposite corners, that is, \[\{(x,y)\in \mathbb{R}^2:\min\{x_1, x_2\}\leq x\leq \max\{x_1, x_2\},\min\{y_1, y_2\}\leq y\leq \max\{y_1, y_2\}\}.\] Find the largest value of $k$ for which the following statement is true: for all sets $\mathcal{S}\subset\mathbb{R}^2$ with $|\mathcal{S}|=2024$, there exist two points $p_1, p_2\in\mathcal{S}$ such that $|\mathcal{S}\cap\mathcal{R}(p_1, p_2)|\geq k$.

Gandalf (the wizard) and Bilbo (the assistant) are presenting a magic trick to Nitzan (the audience). While Gandalf leaves the room, Nitzan chooses a number $1\leq x\leq 2^{2022}$ and shows it to Bilbo. Now bilbo writes on the board a long row of $N$ digits, each of which is $0$ or $1$. After this Nitzan can, if he wishes, switch the order of two consecutive digits in the row, but only once. Then Gandalf returns to the room, looks at the row, and guesses the number $x$. Can Bilbo and Gandalf come up with a strategy that allows Gandalf to guess $x$ correctly no matter how Nitzan acts, if [b]a)[/b] $N=2500$? [b]b)[/b] $N=2030$? [b]c)[/b] $N=2040$?

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?

We wish to lay down boards on a floor with width $B$ in the direction across the boards. We have $n$ boards of width $b$, and $B/b$ is an integer, and $nb \le B$. There are enough boards to cover the floor, but the boards may have different lengths. Show that we can cut the boards in such a way that every board length on the floor has at most one join where two boards meet end to end. [img]https://cdn.artofproblemsolving.com/attachments/f/f/24ce8ae05d85fd522da0e18c0bb8017ca3c8e8.png[/img]

Let us consider mathematical crossword which we fill with numbers $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ such that: 1) All digits occur exactly twice 2) $10$ horizontally divides $4$ vertically 3) $4 \cdot$ ($4$ horizontally - $4$ vertically +$5$) equals $1$ vertically 4) $36$ divides $1$ horizontally and $5$ vertically 5) $9$ vertically divides $5$ vertically In how many ways we can solve this mathematical crossword? [img]https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvOC85LzgyNjUzYmNkNTVmNDE1YTg4OWVkNzAzYzE1M2JkZWE0MThiYWY1LnBuZw==&rn=Y3Jvc3N3b3JkLnBuZw==[/img]

Consider a $3\times7$ grid of squares. Each square may be coloured green or white. [list] (a) Is it possible to find a colouring so that no subrectangle has all four corner squares of the same colour? (b) Is it possible for a $4\times 6$ grid? [/list] [i]Subrectangles must have their corners at grid-points of the original diagram. The corner squares of a subrectangle must be different. The original diagram is a subrectangle of itself.[/i]

Let $n$ be an integer greater than $1$ and let $X$ be an $n$-element set. A non-empty collection of subsets $A_1, ..., A_k$ of $X$ is tight if the union $A_1 \cup \cdots \cup A_k$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_i$s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight. [i]Note[/i]. A subset $A$ of $X$ is proper if $A\neq X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

Consider the square grid with $A=(0,0)$ and $C=(n,n)$ at its diagonal ends. Paths from $A$ to $C$ are composed of moves one unit to the right or one unit up. Let $C_n$ (n-th catalan number) be the number of paths from $A$ to $C$ which stay on or below the diagonal $AC$. Show that the number of paths from $A$ to $C$ which cross $AC$ from below at most twice is equal to $C_{n+2}-2C_{n+1}+C_n$

Let $$C=\{1,22,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20\}$$ and let $$S=\{4,5,9,14,23,37\}$$ Find two sets $A$ and $B$ with the properties (a) $A\cap B=\emptyset$. (b) $A\cup B=C$. (c) The sum of two distinct elements of $A$ is not in $S$. (d) The sum of two distinct elements of $B$ is not in $S$.

Let $n \ge 5$ be an integer. Prove that $n$ is prime if and only if for any representation of $n$ as a sum of four positive integers $n = a + b + c + d$, it is true that $ab \ne cd$.

Let $n$ be a positive integer. Ana and Banana play a game. Banana thinks of a function $f\colon\mathbb{Z}\to\mathbb{Z}$ and a prime number $p$. He tells Ana that $f$ is nonconstant, $p<100$, and $f(x+p)=f(x)$ for all integers $x$. Ana's goal is to determine the value of $p$. She writes down $n$ integers $x_1,\dots,x_n$. After seeing this list, Banana writes down $f(x_1),\dots,f(x_n)$ in order. Ana wins if she can determine the value of $p$ from this information. Find the smallest value of $n$ for which Ana has a winning strategy. [i]Anthony Wang[/i]

For positive integers $a$ and $b$, an $(a,b)$-shuffle of a deck of $a+b$ cards is any shuffle that preserves the relative order of the top $a$ cards and the relative order of the bottom $b$ cards. Let $n$, $k$, $a_1$, $a_2$, $\dots$, $a_k$, $b_1$, $b_2$, $\dots$, $b_k$ be fixed positive integers such that $a_i+b_i=n$ for all $1\leq i\leq k$. Big Bird has a deck of $n$ cards and will perform an $(a_i,b_i)$-shuffle for each $1\leq i\leq k$, in ascending order of $i$. Suppose that Big Bird can reverse the order of the deck. Prove that Big Bird can also achieve any of the $n!$ permutations of the cards. [i]Linus Tang[/i]

We wish to find the sum of $40$ given numbers utilizing $40$ processors. Initially, we have the number $0$ on the screen of each processor. Each processor adds the number on its screen with a number entered directly (only the given numbers could be entered directly to the processors) or transferred from another processor in a unit time. Whenever a number is transferred from a processor to another, the former processor resets. Find the least time needed to find the desired sum.