The ruler of Laputa will set up a train network between cities in the state, which satisfies the following conditions: - [i]Uniformity[/i]: From one city to another, by train, possibly through exchanges. - [i]Prohibition N[/i]: There exist no four cities $A, B, C, D$ such that there are direct routes between $A$ and $B, B$ and $C$, and $C$ and $D$, but taking a shortcut is not possible, that is, there are no direct rout between $A$ and $C, B$ and $D$, or $A$ and $D$. In addition, a direct airliner connection will be established exactly between their city pairs, with no direct train connection. Prove that the airline network is not connected when there is more than one city.

Let $n>1$ be an integer. Given a simple graph $G$ on $n$ vertices $v_1, v_2, \dots, v_n$ we let $k(G)$ be the minimal value of $k$ for which there exist $n$ $k$-dimensional rectangular boxes $R_1, R_2, \dots, R_n$ in a $k$-dimensional coordinate system with edges parallel to the axes, so that for each $1\leq i<j\leq n$, $R_i$ and $R_j$ intersect if and only if there is an edge between $v_i$ and $v_j$ in $G$. Define $M$ to be the maximal value of $k(G)$ over all graphs on $n$ vertices. Calculate $M$ as a function of $n$.

Given 365 cards, in which distinct numbers are written. We may ask for any three cards, the order of numbers written in them. Is it always possible to find out the order of all 365 cards by 2000 such questions?

A conference is attended by $n (n\ge 3)$ scientists. Each scientist has some friends in this conference (friendship is mutual and no one is a friend of him/herself). Suppose that no matter how we partition the scientists into two nonempty groups, there always exist two scientists in the same group who are friends, and there always exist two scientists in different groups who are friends. A proposal is introduced on the first day of the conference. Each of the scientists' opinion on the proposal can be expressed as a non-negative integer. Everyday from the second day onwards, each scientists' opinion is changed to the integer part of the average of his/her friends' opinions from the previous day. Prove that after a period of time, all scientists have the same opinion on the proposal.

Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n + 1$ smaller rectangles. [i]Proposed by Serbia[/i]

At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid? [i]Proposed by Evan Chen[/i]

In a forest each of $n$ animals ($n\ge 3$) lives in its own cave, and there is exactly one separate path between any two of these caves. Before the election for King of the Forest some of the animals make an election campaign. Each campaign-making animal visits each of the other caves exactly once, uses only the paths for moving from cave to cave, never turns from one path to another between the caves and returns to its own cave in the end of its campaign. It is also known that no path between two caves is used by more than one campaign-making animal. a) Prove that for any prime $n$, the maximum possible number of campaign-making animals is $\frac{n-1}{2}$. b) Find the maximum number of campaign-making animals for $n=9$.

Determine the greatest positive integer $k$ that satisfies the following property: The set of positive integers can be partitioned into $k$ subsets $A_1, A_2, \ldots, A_k$ such that for all integers $n \geq 15$ and all $i \in \{1, 2, \ldots, k\}$ there exist two distinct elements of $A_i$ whose sum is $n.$ [i]Proposed by Igor Voronovich, Belarus[/i]

At an international conference there are four official languages. Any two participants can speak in one of these languages. Show that at least $60\%$ of the participants can speak the same language. [i]Mihai Baluna[/i]

Dilhan is running around a track for $12$ laps. If halfway through a lap, Dilhan has his phone on him, he has a $\frac{1}{3}$ chance to drop it there. If Dilhan runs past his phone on the ground, he will attempt to pick it up with a $\frac{2}{3}$ chance of success, and won't drop it for the rest of the lap. He starts with his phone at the start of the 5K, what is the chance he still has it when he finished the 5K? [i]Proposed by Zack Lee, Daniel Li, Dilhan Salgado[/i]

[b]p1.[/b] The number $2020$ is very special: the sum of its digits is equal to the product of its nonzero digits. How many such four digit numbers are there? (Numbers with only one nonzero digit, like $3000$, also count) [b]p2.[/b] A locker has a combination which is a sequence of three integers between $ 0$ and $49$, inclusive. It is known that all of the numbers in the combination are even. Let the total of a lock combination be the sum of the three numbers. Given that the product of the numbers in the combination is $12160$, what is the sum of all possible totals of the locker combination? [b]p3.[/b] Given points $A = (0, 0)$ and $B = (0, 1)$ in the plane, the set of all points P in the plane such that triangle $ABP$ is isosceles partitions the plane into $k$ regions. The sum of the areas of those regions that are bounded is $s$. Find $ks$. [b]p4.[/b] Three families sit down around a circular table, each person choosing their seat at random. One family has two members, while the other two families have three members. What is the probability that every person sits next to at least one person from a different family? [b]p5.[/b] Jacob and Alexander are walking up an escalator in the airport. Jacob walks twice as fast as Alexander, who takes $18$ steps to arrive at the top. Jacob, however, takes $27$ steps to arrive at the top. How many of the upward moving escalator steps are visible at any point in time? [b]p6.[/b] Points $A, B, C, D, E$ lie in that order on a circle such that $AB = BC = 5$, $CD = DE = 8$, and $\angle BCD = 150^o$ . Let $AD$ and $BE$ intersect at $P$. Find the area of quadrilateral $PBCD$. [b]p7.[/b] Ivan has a triangle of integers with one number in the first row, two numbers in the second row, and continues up to eight numbers in the eighth row. He starts with the first $8$ primes, $2$ through $19$, in the bottom row. Each subsequent row is filled in by writing the least common multiple of two adjacent numbers in the row directly below. For example, the second last row starts with$ 6, 15, 35$, etc. Let P be the product of all the numbers in this triangle. Suppose that P is a multiple of $a/b$, where $a$ and $b$ are positive integers and $a > 1$. Given that $b$ is maximized, and for this value of $b, a$ is also maximized, find $a + b$. [b]p8.[/b] Let $ABCD$ be a cyclic quadrilateral. Given that triangle $ABD$ is equilateral, $\angle CBD = 15^o$, and $AC = 1$, what is the area of $ABCD$? [b]p9.[/b] Let $S$ be the set of all integers greater than $ 1$. The function f is defined on $S$ and each value of $f$ is in $S$. Given that $f$ is nondecreasing and $f(f(x)) = 2x$ for all $x$ in $S$, find $f(100)$. [b]p10.[/b] An [i]origin-symmetric[/i] parallelogram $P$ (that is, if $(x, y)$ is in $P$, then so is $(-x, -y)$) lies in the coordinate plane. It is given that P has two horizontal sides, with a distance of $2020$ between them, and that there is no point with integer coordinates except the origin inside $P$. Also, $P$ has the maximum possible area satisfying the above conditions. The coordinates of the four vertices of P are $(a, 1010)$, $(b, 1010)$, $(-a, -1010)$, $(-b, -1010)$, where a, b are positive real numbers with $a < b$. What is $b$? [b]p11.[/b] What is the remainder when $5^{200} + 5^{50} + 2$ is divided by $(5 + 1)(5^2 + 1)(5^4 + 1)$? [b]p12.[/b] Let $f(n) = n^2 - 4096n - 2045$. What is the remainder when $f(f(f(... f(2046)...)))$ is divided by $2047$, where the function $f$ is applied $47$ times? [b]p13.[/b] What is the largest possible area of a triangle that lies completely within a $97$-dimensional hypercube of side length $1$, where its vertices are three of the vertices of the hypercube? [b]p14.[/b] Let $N = \left \lfloor \frac{1}{61} \right \rfloor + \left \lfloor\frac{3}{61} \right \rfloor+\left \lfloor \frac{3^2}{61} \right \rfloor+... +\left \lfloor\frac{3^{2019}}{61} \right \rfloor$. Given that $122N$ can be expressed as $3^a - b$, where $a, b$ are positive integers and $a$ is as large as possible, find $a + b$. Note: $\lfloor x \rfloor$ is defined as the greatest integer less than or equal to $x$. [b]p15.[/b] Among all ordered triples of integers $(x, y, z)$ that satisfy $x + y + z = 8$ and $x^3 + y^3 + z^3 = 134$, what is the maximum possible value of $|x| + |y| + |z|$? PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Once upon a time, there was a tribe called the Goblin Tribe, and their regular game was ''The ATM Game (Level Giveaway)'' . The game stats with a number of Goblin standing in a circle. Then the Chieftain assigns a Level to each Goblin, which can be the same or different (Level is a number which is a non-negative integer). Start play by selecting a Goblin with Level $k$ ($k \not=). 0$) comes up. Let's assume Goblin $A$. Goblin $A$ explodes itself. Goblin A's Level becomes $0$. After that, Level of Goblin $k$ next to Goblin $A$ clockwise gets Level $1$. Prove that: 1.) If after that Goblin $k$ next to Goblin $A$ explodes itself and keep doing this, $k'$ next to that Goblin clockwise explodes itself. Prove that the level of each Goblin will be the same again. 2) 2.) If after that we can choose any Goblin whose level is not $0$ to explode itself. And keep doing this. Prove that no matter what the initial level is, we can make each level the way we want. But there is a condition that the sum of all Goblin's levels must be equal to the beginning. [i](gools)[/i]

On a $50 \times 50$ chessboard, we put, in the lower left corner, a die whose faces are numbered from $1$ to $6$. By convention, the sum of digits on two opposite side of the die equals $7$. Adama wants to move the die to the diagonally opposite corner using the following rule: at each step, Adama can roll the die only on to its right side, or to its top side. We suppose that whenever the die lands on a square, the number on its bottom face is printed on the square. By the end of these operations, Adama wants to find the sum of the $99$ numbers appearing on the chessboard. What are the maximum and minimum possible values of this sum?

Let $\Omega =\{ (x,y,z)\in \mathbb{Z}^3:y+1\geqslant x\geqslant y\geqslant z\geqslant 0\}$. A frog moves along the points of $\Omega$ by jumps of length $1$. For every positive integer $n$, determine the number of paths the frog can take to reach $(n,n,n)$ starting from $(0,0,0)$ in exactly $3n$ jumps. [i]Proposed by Fedor Petrov and Anatoly Vershik, St. Petersburg State University[/i]

Robert has two stacks of five cards numbered 1--5, one of which is randomly shuffled while the other is in numerical order. They pick one of the stacks at random and turn over the first three cards, seeing that they are 1, 2, and 3 respectively. What is the probability the next card is a 4? [i]Proposed by Connor Gordon[/i]

Given $30$ equal cups with milk. An elf tries to make the amount of milk equal in all the cups. He takes a pair of cups and aligns the milk level in two cups. Can there be such an initial distribution of milk in the cups, that the elf will not be able to achieve his goal in a finite number of operations?

In a board of $2021 \times 2021$ grids, we pick $k$ unit squares such that every picked square shares vertice(s) with at most $1$ other picked square. Determine the maximum of $k$.

Let $n$ and $k$ be positive integers and $G$ be a complete graph on $n$ vertices. Each edge of $G$ is colored one of $k$ colors such that every triangle consists of either three edges of the same color or three edges of three different colors. Furthermore, there exist two different-colored edges. Prove that $n\le(k-1)^2$. [i]Linus Tang[/i]

Let $n$ be a positive integer. A regular hexagon $ABCDEF$ with side length $n$ is partitioned into $6n^2$ equilateral triangles with side length $1$. The hexagon is covered by $3n^2$ rhombuses with internal angles $60^{\circ}$ and $120^{\circ}$ such that each rhombus covers exactly two triangles and every triangle is covered by exactly one rhombus. Show that the diagonal $AD$ divides in half exactly $n$ rhombuses.

Let $n \ge 2$ be an integer. A cube of size $n \times n \times n$ is dissected into $n^3$ unit cubes. A nonzero real number is written at the center of each unit cube so that the sum of the $n^2$ numbers in each slab of size $1 \times n \times n$, $n \times 1 \times n$, or $n \times n \times 1$ equals zero. (There are a total of $3n$ such slabs, forming three groups of $n$ slabs each such that slabs in the same group are parallel and slabs in different groups are perpendicular.) Could it happen that some plane in three-dimensional space separates the positive and the negative written numbers? (The plane should not pass through any of the numbers.) [i]Nikolai Beluhov[/i]

Square $ABCD$ is divided into $n^2$ equal small squares by lines parallel to its sides.A spider starts from $A$ and moving only rightward or upwards,tries to reach $C$.Every "movement" of the spider consists of $k$ steps rightward and $m$ steps upwards or $m$ steps rightward and $k$ steps upwards(it can follow any possible order for the steps of each "movement").The spider completes $l$ "movements" and afterwards it moves without limitation (it still moves rightwards and upwards only).If $n=m\cdot l$,find the number of the possible paths the spider can follow to reach $C$.Note that $n,m,k,l\in \mathbb{N^{*}}$ with $k<m$.

[b]p1.[/b] How many lines of symmetry does a square have? [b]p2.[/b] Compute$ 1/2 + 1/6 + 1/12 + 1/4$. [b]p3.[/b] What is the maximum possible area of a rectangle with integer side lengths and perimeter $8$? [b]p4.[/b] Given that $1$ printer weighs $400000$ pennies, and $80$ pennies weighs $2$ books, what is the weight of a printer expressed in books? [b]p5.[/b] Given that two sides of a triangle are $28$ and $3$ and all three sides are integers, what is the sum of the possible lengths of the remaining side? [b]p6.[/b] What is half the sum of all positive integers between $1$ and $15$, inclusive, that have an even number of positive divisors? [b]p7.[/b] Austin the Snowman has a very big brain. His head has radius $3$, and the volume of his torso is one third of his head, and the volume of his legs combined is one third of his torso. If Austin's total volume is $a\pi$ where $a$ is an integer, what is $a$? [b]p8.[/b] Neethine the Kiwi says that she is the eye of the tiger, a fighter, and that everyone is gonna hear her roar. She is standing at point $(3, 3)$. Neeton the Cat is standing at $(11,18)$, the farthest he can stand from Neethine such that he can still hear her roar. Let the total area of the region that Neeton can stand in where he can hear Neethine's roar be $a\pi$ where $a$ is an integer. What is $a$? [b]p9.[/b] Consider $2018$ identical kiwis. These are to be divided between $5$ people, such that the first person gets $a_1$ kiwis, the second gets $a_2$ kiwis, and so forth, with $a_1 \le a_2 \le a_3 \le a_4 \le a_5$. How many tuples $(a_1, a_2, a_3, a_4, a_5)$ can be chosen such that they form an arithmetic sequence? [b]p10.[/b] On the standard $12$ hour clock, each number from $1$ to $12$ is replaced by the sum of its divisors. On this new clock, what is the number of degrees in the measure of the non-reflex angle between the hands of the clock at the time when the hour hand is between $7$ and $6$ while the minute hand is pointing at $15$? [b]p11.[/b] In equiangular hexagon $ABCDEF$, $AB = 7$, $BC = 3$, $CD = 8$, and $DE = 5$. The area of the hexagon is in the form $\frac{a\sqrt{b}}{c}$ with $b$ square free and $a$ and $c$ relatively prime. Find $a+b+c$ where $a, b,$ and $c$ are integers. [b]p12.[/b] Let $\frac{p}{q} = \frac15 + \frac{2}{5^2} + \frac{3}{5^3} + ...$ . Find $p + q$, where $p$ and $q$ are relatively prime positive integers. [b]p13.[/b] Two circles $F$ and $G$ with radius $10$ and $4$ respectively are externally tangent. A square $ABMC$ is inscribed in circle $F$ and equilateral triangle $MOP$ is inscribed in circle $G$ (they share vertex $M$). If the area of pentagon $ABOPC$ is equal to $a + b\sqrt{c}$, where $a$, $b$, $c$ are integers $c$ is square free, then find $a + b + c$. [b]p14.[/b] Consider the polynomial $P(x) = x^3 + 3x^2 + ax + 8$. Find the sum of all integer $a$ such that the sum of the squares of the roots of $P(x)$ divides the sum of the coecients of $P(x)$. [b]p15.[/b] Nithin and Antonio play a number game. At the beginning of the game, Nithin picks a prime $p$ that is less than $100$. Antonio then tries to find an integer $n$ such that $n^6 + 2n^5 + 2n^4 + n^3 + (n^2 + n + 1)^2$ is a multiple of $p$. If Antonio can find such a number n, then he wins, otherwise, he loses. Nithin doesn't know what he is doing, and he always picks his prime randomly while Antonio always plays optimally. The probability of Antonio winning is $a/b$ where $a$ and $b$ are relatively prime positive integers. Find$a + b$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $A = \{1,2,..., 100\}$ and $B$ is a subset of $A$ having $48$ elements. Show that $B$ has two distint elements $x$ and $y$ whose sum is divisible by $11$.

A chess-board $6\times 6$ is tiled with the $2\times 1$ dominos. Prove that you can cut the board onto two parts by a straight line that does not cut dominos.

In a wrestling tournament, there are $100$ participants, all of different strengths. The stronger wrestler always wins over the weaker opponent. Each wrestler fights twice and those who win both of their fights are given awards. What is the least possible number of awardees?