The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge). [i]Proposed by Norman Do, Australia[/i]

A graph contains $p$ vertices numbered from $1$ to $p$, and $q$ edges numbered from $p + 1$ to $p + q$. It turned out that for each edge the sum of the numbers of its ends and of the edge itself equals the same number $s$. It is also known that the numbers of edges starting in all vertices are equal. Prove that \[s = \dfrac{1}{2} (4p+q+3).\]

We have $98$ cards, in each one we will write one of the numbers: $1, 2, 3, 4,...., 97, 98$. We can order the $98$ cards, in a sequence such that two consecutive numbers $X$ and $Y$ and the number $X - Y$ is greater than $48$, determine how and how many ways we can make this sequence!!

Given a chess-board $99\times 99$ with a set $F$ of fields marked on it (the set is different in three tasks). There is a beetle sitting on every field of the set $F$. Suddenly all the beetles have raised into the air and flied to another fields of the same set. The beetles from the neighbouring fields have landed either on the same field or on the neighbouring ones (may be far from their starting point). (We consider the fields to be neighbouring if they have at least one common vertex.) Consider a statement: [i]"There is a beetle, that either stayed on the same field or moved to the neighbouring one".[/i] Is it always valid if the figure $F$ is: a) A central cross, i.e. the union of the $50$-th row and the $50$-th column? b) A window frame, i.e. the union of the $1$-st, $50$-th and $99$-th rows and the $1$-st, $50$-th and $99$-th columns? c) All the chess-board?

[b]p1.[/b] In the following $3$ by $3$ grid, $a, b, c$ are numbers such that the sum of each row is listed at the right and the sum of each column is written below it: [center][img]https://cdn.artofproblemsolving.com/attachments/d/9/4f6fd2bc959c25e49add58e6e09a7b7eed9346.png[/img][/center] What is $n$? [b]p2.[/b] Suppose in your sock drawer of $14$ socks there are 5 different colors and $3$ different lengths present. One day, you decide you want to wear two socks that have both different colors and different lengths. Given only this information, what is the maximum number of choices you might have? [b]p3.[/b] The population of Arveymuddica is $2014$, which is divided into some number of equal groups. During an election, each person votes for one of two candidates, and the person who was voted for by $2/3$ or more of the group wins. When neither candidate gets $2/3$ of the vote, no one wins the group. The person who wins the most groups wins the election. What should the size of the groups be if we want to minimize the minimum total number of votes required to win an election? [b]p4.[/b] A farmer learns that he will die at the end of the year (day $365$, where today is day $0$) and that he has a number of sheep. He decides that his utility is given by ab where a is the money he makes by selling his sheep (which always have a fixed price) and $b$ is the number of days he has left to enjoy the profit; i.e., $365-k$ where $k$ is the day. If every day his sheep breed and multiply their numbers by $103/101$ (yes, there are small, fractional sheep), on which day should he sell them all? [b]p5.[/b] Line segments $\overline{AB}$ and $\overline{AC}$ are tangent to a convex arc $BC$ and $\angle BAC = \frac{\pi}{3}$ . If $\overline{AB} = \overline{AC} = 3\sqrt3$, find the length of arc $BC$. [b]p6.[/b] Suppose that you start with the number $8$ and always have two legal moves: $\bullet$ Square the number $\bullet$ Add one if the number is divisible by $8$ or multiply by $4$ otherwise How many sequences of $4$ moves are there that return to a multiple of $8$? [b]p7.[/b] A robot is shuffling a $9$ card deck. Being very well machined, it does every shuffle in exactly the same way: it splits the deck into two piles, one containing the $5$ cards from the bottom of the deck and the other with the $4$ cards from the top. It then interleaves the cards from the two piles, starting with a card from the bottom of the larger pile at the bottom of the new deck, and then alternating cards from the two piles while maintaining the relative order of each pile. The top card of the new deck will be the top card of the bottom pile. The robot repeats this shuffling procedure a total of n times, and notices that the cards are in the same order as they were when it started shuffling. What is the smallest possible value of $n$? [b]p8.[/b] A secant line incident to a circle at points $A$ and $C$ intersects the circle's diameter at point $B$ with a $45^o$ angle. If the length of $AB$ is $1$ and the length of $BC$ is $7$, then what is the circle's radius? [b]p9.[/b] If a complex number $z$ satisfies $z + 1/z = 1$, then what is $z^{96} + 1/z^{96}$? [b]p10.[/b] Let $a, b$ be two acute angles where $\tan a = 5 \tan b$. Find the maximum possible value of $\sin (a - b)$. [b]p11.[/b] A pyramid, represented by $SABCD$ has parallelogram $ABCD$ as base ($A$ is across from $C$) and vertex $S$. Let the midpoint of edge $SC$ be $P$. Consider plane $AMPN$ where$ M$ is on edge $SB$ and $N$ is on edge $SD$. Find the minimum value $r_1$ and maximum value $r_2$ of $\frac{V_1}{V_2}$ where $V_1$ is the volume of pyramid $SAMPN$ and $V_2$ is the volume of pyramid $SABCD$. Express your answer as an ordered pair $(r_1, r_2)$. [b]p12.[/b] A $5 \times 5$ grid is missing one of its main diagonals. In how many ways can we place $5$ pieces on the grid such that no two pieces share a row or column? [b]p13.[/b] There are $20$ cities in a country, some of which have highways connecting them. Each highway goes from one city to another, both ways. There is no way to start in a city, drive along the highways of the country such that you travel through each city exactly once, and return to the same city you started in. What is the maximum number of roads this country could have? [b]p14.[/b] Find the area of the cyclic quadrilateral with side lengths given by the solutions to $$x^4-10x^3+34x^2- 45x + 19 = 0.$$ [b]p15.[/b] Suppose that we know $u_{0,m} = m^2 + m$ and $u_{1,m} = m^2 + 3m$ for all integers $m$, and that $$u_{n-1,m} + u_{n+1,m} = u_{n,m-1} + u_{n,m+1}$$ Find $u_{30,-5}$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

As in the picture below, the rectangle on the left hand side has been divided into four parts by line segments which are parallel to a side of the rectangle. The areas of the small rectangles are $A,B,C$ and $D$. Similarly, the small rectangles on the right hand side have areas $A^\prime,B^\prime,C^\prime$ and $D^\prime$. It is known that $A\leq A^\prime$, $B\leq B^\prime$, $C\leq C^\prime$ but $D\leq B^\prime$. [asy] import graph; size(12cm); real lsf=0.5; pen dps=linewidth(0.7)+fontsize(10); defaultpen(dps); pen ds=black; real xmin=-4.3,xmax=12.32,ymin=-10.68,ymax=6.3; draw((0,3)--(0,0)); draw((3,0)--(0,0)); draw((3,0)--(3,3)); draw((0,3)--(3,3)); draw((2,0)--(2,3)); draw((0,2)--(3,2)); label("$A$",(0.86,2.72),SE*lsf); label("$B$",(2.38,2.7),SE*lsf); label("$C$",(2.3,1.1),SE*lsf); label("$D$",(0.82,1.14),SE*lsf); draw((5,2)--(11,2)); draw((5,2)--(5,0)); draw((11,0)--(5,0)); draw((11,2)--(11,0)); draw((8,0)--(8,2)); draw((5,1)--(11,1)); label("$A'$",(6.28,1.8),SE*lsf); label("$B'$",(9.44,1.82),SE*lsf); label("$C'$",(9.4,0.8),SE*lsf); label("$D'$",(6.3,0.86),SE*lsf); dot((0,3),linewidth(1pt)+ds); dot((0,0),linewidth(1pt)+ds); dot((3,0),linewidth(1pt)+ds); dot((3,3),linewidth(1pt)+ds); dot((2,0),linewidth(1pt)+ds); dot((2,3),linewidth(1pt)+ds); dot((0,2),linewidth(1pt)+ds); dot((3,2),linewidth(1pt)+ds); dot((5,0),linewidth(1pt)+ds); dot((5,2),linewidth(1pt)+ds); dot((11,0),linewidth(1pt)+ds); dot((11,2),linewidth(1pt)+ds); dot((8,0),linewidth(1pt)+ds); dot((8,2),linewidth(1pt)+ds); dot((5,1),linewidth(1pt)+ds); dot((11,1),linewidth(1pt)+ds); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy] Prove that the big rectangle on the left hand side has area smaller or equal to the area of the big rectangle on the right hand side, i.e. $A+B+C+D\leq A^\prime+B^\prime+C^\prime+D^\prime$.

On an international conference there are 4 official languages. Each two of the attendees can have a conversation on one of the languages. Prove that at least 60% of the attendees can speak the same language.

Consider the set $A=\{1,2,3,4,5,6,7,8,9\}$.A partition $\Pi $ of $A$ is collection of disjoint sets whose union is $A$. For example, $\Pi_1=\{\{1,2\},\{3,4,5\},\{6,7,8,9\}\}$ and $\Pi _2 =\{\{1\},\{2,5\},\{3,7\},\{4,5,6,7,8,9\}\}$ can be considered as partitions of $A$. For, each $\Pi$ partition ,we consider the function $\pi$ defined on the elements of$A$. $\pi (x)$ denotes the cardinality of the subset in $\Pi$ which contains $x$. For, example in case of $\Pi_1$ , $\pi_1(1)=\pi_1(2)=2$, $\pi_1(3)=\pi_1(4)=\pi_1 (5)=3$, and $\pi_1(6)=\pi_1(7)=\pi_1(8)=\pi_1(9)=4$. For $\Pi_2$ we have $\pi_2(1)=1$, $\pi_2(2)=\pi_2(5)=2$, $\pi_2(3)=\pi_2(7)=2$ and $\pi_2(4)=\pi_2(6)=\pi_2(8)=\pi_2(9)=4$ Given any two partitions $\Pi$ and $\Pi '$, show that there are two numbers $x$ and $y$ in $A$, such that $\pi (x)= \pi '(x)$ and $ \pi (y)= \pi'(y)$.[[b]Hint:[/b] Consider the case where there is a block of size greater than or equal to 4 in a partition and the alternative case]

Several paper-made disks (not necessarily equal) are put on the table so that there is some overlapping, but no disk is entirely inside another. The parts that overlap are cut off and removed. Show that the remaining parts cannot be assembled so as to form different disks.

In a board school, there are 9 subjects, 512 students, and 256 rooms (two people in each room.) For every student there is a set (a subset of the 9 subjects) of subjects the student is interested in. Each student has a different set of subjects, (s)he is interested in, from all other students. (Exactly one student has no subjects (s)he is interested in.) Prove that the whole school can line up in a circle in such a way that every pair of the roommates has the two people standing next to each other, and those pairs of students standing next to each other that are not roommates, have the following properties. One of the two students is interested in all the subjects that the other student is interested in, and also exactly one more subject.

In a school there are 2008 students. Students are members of certain committees. A committee has at most 1004 members and every two students join a common committee. (a) Determine the smallest possible number of committees in the school. (b) If it is further required that the union of any two committees consists of at most 1800 students, will your answer in (a) still hold?

In a convex set $S$ that contains the origin it is possible to draw $n$ disjoint unit circles such that viewing from the origin non of the unit circles blocks out a part of another (or a complete) unit circle. Prove that the area of $S$ is at least $\frac{n^2}{100}$.

A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every (directed) edge, so that for every pair of directed edges $\overrightarrow{uv}$ and $\overrightarrow{vw}$, those two edges are in different colors. Note that it is permissible for $\overrightarrow{uv}$ and $\overrightarrow{uw}$ to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each $n$, determine the minimum directed-edge-chromatic-number over all tournaments on $n$ vertices. [i]Proposed by Po-Shen Loh[/i]

There are $2022$ stones on a table. At the start of the game, Teacher Tseng will choose a positive integer $m$ and let Ming and LTF play a game. LTF is the first to move, and he can remove at most $m$ stones on his round. Then the two people take turns removing stone, each round they must remove at least one stone, and they cannot remove more than twice the amount of stones the last person removed. The player unable to move loses. Find the smallest positive integer $m$ such that LTF has a winning strategy. [i]Proposed by ltf0501[/i]

[i]20 problems for 25 minutes.[/i] [b]p1.[/b] Evaluate $20 \times 21 + 2021$. [b]p2.[/b] Let points $A$, $B$, $C$, and $D$ lie on a line in that order. Given that $AB = 5CD$ and $BD = 2BC$, compute $\frac{AC}{BD}$. [b]p3.[/b] There are $18$ students in Vincent the Bug's math class. Given that $11$ of the students take U.S. History, $15$ of the students take English, and $2$ of the students take neither, how many students take both U.S. History and English? [b]p4.[/b] Among all pairs of positive integers $(x, y)$ such that $xy = 12$, what is the least possible value of $x + y$? [b]p5.[/b] What is the smallest positive integer $n$ such that $n! + 1$ is composite? [b]p6.[/b] How many ordered triples of positive integers $(a, b,c)$ are there such that $a + b + c = 6$? [b]p7.[/b] Thomas orders some pizzas and splits each into $8$ slices. Hungry Yunseo eats one slice and then finds that she is able to distribute all the remaining slices equally among the $29$ other math club students. What is the fewest number of pizzas that Thomas could have ordered? [b]p8.[/b] Stephanie has two distinct prime numbers $a$ and $b$ such that $a^2-9b^2$ is also a prime. Compute $a + b$. [b]p9.[/b] Let $ABCD$ be a unit square and $E$ be a point on diagonal $AC$ such that $AE = 1$. Compute $\angle BED$, in degrees. [b]p10.[/b] Sheldon wants to trace each edge of a cube exactly once with a pen. What is the fewest number of continuous strokes that he needs to make? A continuous stroke is one that goes along the edges and does not leave the surface of the cube. [b]p11.[/b] In base $b$, $130_b$ is equal to $3n$ in base ten, and $1300_b$ is equal to $n^2$ in base ten. What is the value of $n$, expressed in base ten? [b]p12.[/b] Lin is writing a book with $n$ pages, numbered $1,2,..., n$. Given that $n > 20$, what is the least value of $n$ such that the average number of digits of the page numbers is an integer? [b]p13.[/b] Max is playing bingo on a $5\times 5$ board. He needs to fill in four of the twelve rows, columns, and main diagonals of his bingo board to win. What is the minimum number of boxes he needs to fill in to win? [b]p14.[/b] Given that $x$ and $y$ are distinct real numbers such that $x^2 + y = y^2 + x = 211$, compute the value of $|x - y|$. [b]p15.[/b] How many ways are there to place 8 indistinguishable pieces on a $4\times 4$ checkerboard such that there are two pieces in each row and two pieces in each column? [b]p16.[/b] The Manhattan distance between two points $(a, b)$ and $(c, d)$ in the plane is defined to be $|a - c| + |b - d|$. Suppose Neil, Neel, and Nail are at the points $(5, 3)$, $(-2,-2)$ and $(6, 0)$, respectively, and wish to meet at a point $(x, y)$ such that their Manhattan distances to$ (x, y)$ are equal. Find $10x + y$. [b]p17.[/b] How many positive integers that have a composite number of divisors are there between $1$ and $100$, inclusive? [b]p18.[/b] Find the number of distinct roots of the polynomial $$(x - 1)(x - 2) ... (x - 90)(x^2 - 1)(x^2 - 2) ... (x^2 - 90)(x^4 - 1)(x^4 - 2)...(x^4 - 90)$$. [b]p19.[/b] In triangle $ABC$, let $D$ be the foot of the altitude from $ A$ to $BC$. Let $P,Q$ be points on $AB$, $AC$, respectively, such that $PQ$ is parallel to $BC$ and $\angle PDQ = 90^o$. Given that $AD = 25$, $BD = 9$, and $CD = 16$, compute $111 \times PQ$. [b]p20.[/b] The simplified fraction with numerator less than $1000$ that is closest but not equal to $\frac{47}{18}$ is $\frac{p}{q}$ , where $p$ and $q$ are relatively prime positive integers. Compute $p$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Is it possible to fill a $3 \times 3$ grid with each of the numbers $1,2,\ldots,9$ once each such that the sum of any two numbers sharing a side is prime?

For $n>1$ consider an $n\times n$ chessboard and place identical pieces at the centers of different squares. [list=i] [*] Show that no matter how $2n$ identical pieces are placed on the board, that one can always find $4$ pieces among them that are the vertices of a parallelogram. [*] Show that there is a way to place $(2n-1)$ identical chess pieces so that no $4$ of them are the vertices of a parallelogram. [/list]

Let $2561$ given points on a circle be colored either red or green. In each step, all points are recolored simultaneously in the following way: if both direct neighbors of a point $P$ have the same color as $P$, then the color of $P$ remains unchanged, otherwise $P$ obtains the other color. Starting with the initial coloring $F_1$, we obtain the colorings $F_2, F_3,\dots$ after several recoloring steps. Determine the smallest number $n$ such that, for any initial coloring $F_1$, we must have $F_n = F_{n+2}$.

(a) Alenka has two jars, each with $6$ marbles labeled with numbers $1$ through $6$. She draws one marble from each jar at random. Denote by $p_n$ the probability that the sum of the labels of the two drawn marbles is $n$. Compute pn for each $n \in N$. (b) Barbara has two jars, each with $6$ marbles which are labeled with unknown numbers. The sets of labels in the two jars may differ and two marbles in the same jar can have the same label. If she draws one marble from each jar at random, the probability that the sum of the labels of the drawn marbles is $n$ equals the probability $p_n$ in Alenka’s case. Determine the labels of the marbles. Find all solution

On the surface of a sphere, a non-intersecting closed curve is drawn. It divides the surface of the sphere in two regions, which are coloured red and blue. Prove that there exist two antipodes of different colours. [i]Note: the curve is colourless.[/i] [i]Proposed by Vlad Spătaru[/i]

There are $64$ towns in a country and some pairs of towns are connected by roads but we do not know these pairs. We may choose any pair of towns and find out whether they are connected or not. Our aim is to determine whether it is possible to travel from any town to any other by a sequence of roads. Prove that there is no algorithm which enables us to do so in less than $2016$ questions. (Proposed by Konstantin Knop)

For a positive integer $n$, a [i]sum-friendly odd partition[/i] of $n$ is a sequence $(a_1, a_2, \ldots, a_k)$ of odd positive integers with $a_1 \le a_2 \le \cdots \le a_k$ and $a_1 + a_2 + \cdots + a_k = n$ such that for all positive integers $m \le n$, $m$ can be [b]uniquely[/b] written as a subsum $m = a_{i_1} + a_{i_2} + \cdots + a_{i_r}$. (Two subsums $a_{i_1} + a_{i_2} + \cdots + a_{i_r}$ and $a_{j_1} + a_{j_2} + \cdots + a_{j_s}$ with $i_1 < i_2 < \cdots < i_r$ and $j_1 < j_2 < \cdots < j_s$ are considered the same if $r = s$ and $a_{i_l} = a_{j_l}$ for $1 \le l \le r$.) For example, $(1, 1, 3, 3)$ is a sum-friendly odd partition of $8$. Find the number of sum-friendly odd partitions of $9999$.

[u]Set 2[/u] [b]p4.[/b] $\vartriangle ABC$ is an isosceles triangle with $AB = BC$. Additionally, there is $D$ on $BC$ with $AC = DA = BD = 1$. Find the perimeter of $\vartriangle ABC$. [b]p5[/b]. Let $r$ be the positive solution to the equation $100r^2 + 2r - 1 = 0$. For an appropriate $A$, the infinite series $Ar + Ar^2 + Ar^3 + Ar^4 +...$ has sum $1$. Find $A$. [b]p6.[/b] Let $N(k)$ denote the number of real solutions to the equation $x^4 -x^2 = k$. As $k$ ranges from $-\infty$ to $\infty$, the value of $N(k)$ changes only a finite number of times. Write the sequence of values of $N(k)$ as an ordered tuple (i.e. if $N(k)$ went from $1$ to $3$ to $2$, you would write $(1, 3, 2)$). PS. You should use hide for answers.

Let $P_1P_2\ldots P_n$ be a convex polygon in the plane. We assume that for any arbitrary choice of vertices $P_i,P_j$ there exists a vertex in the polygon $P_k$ distinct from $P_i,P_j$ such that $\angle P_iP_kP_j=60^{\circ}$. Show that $n=3$. [i]Radu Todor[/i]

$12$ friends play a tennis tournament, where each plays only one game with any of the other eleven. Winner gets one points. Loser getos zero points, and there is no draw. Final points of the participants are $B_1, B_2, ..., B_{12}$. Find the largest possible value of the sum $\Sigma_3=B_1^3+B_2^3+ ... + B_{12}^3$ .