Several boys and girls are dancing a waltz at a ball. Is it possible that each girl can always get to dance the next dance with a boy who is either more handsome or more clever than for the previous dance, and that each time one of the girls gets to dance the next dance with a boy who is more handsome and more clever? (The numbers of boys and girls are equal and all are dancing.) (AY Belov)

For each subset $A$ of $\{1,2, \dots, n \} $, let $M_A$ be the difference between the largest of the elements of $A$ and the smallest of the elements of $A $. Finds the sum of all values ​​of $M_A$ when all possible subsets $A$ of $\{1,2, \dots, n \} $ are considered.

A $20 \times 20$ treasure map is glued to a torus. A treasure is hidden in a cell of this map. We can ask questions about $1\times 4$ or $4 \times 1$ rectangles so that we find out if there is a treasure in this rectangle or not. The answers to all questions are absolutely true, but they are given only after all rectangles we want to ask are set. What is the least amount of questions needed to be asked so that we can be sure to find the treasure? (If you describe the position of the cells in a torus with numbers $(i, j)$ of row and column, $1 \leq i, j \leq 20$, then two cells are neighbors, if and only if two of the coordinates they have are the same, and the other two differ by $1$ mod $20$.)

In a blackboard there are $K$ circles in a row such that one of the numbers $1,...,K$ is assigned to each circle from the left to the right. Change of situation of a circle is to write in it or erase the number which is assigned to it.At the beginning no number is written in its own circle. For every positive divisor $d$ of $K$ ,$1\leq d\leq K$ we change the situation of the circles in which their assigned numbers are divisible by $d$,performing for each divisor $d$ $K$ changes of situation. Determine the value of $K$ for which the following holds;when this procedure is applied once for all positive divisors of $K$ ,then all numbers $1,2,3,...,K$ are written in the circles they were assigned in.

There are $n$ blocks placed on the unit squares of a $n \times n$ chessboard such that there is exactly one block in each row and each column. Find the maximum value $k$, in terms of $n$, such that however the blocks are arranged, we can place $k$ rooks on the board without any two of them threatening each other. (Two rooks are not threatening each other if there is a block lying between them.)

A natural number $n$, which is at most $500$, has the property that when one chooses at at random among the numbers $1, 2, 3,...,499, 500$, then the probability is $\frac{1}{100}$ for $m$ to add up to $n$. Determine the largest possible value of $n$.

[hide=instructions]Time limit: 20 minutes. Fill in the crossword above with answers to the problems below. Notice that there are three directions instead of two. You are probably used to "down" and "across," but this crossword has "1," $e^{4\pi i/3}$, and $e^{5\pi i/3}$. You can think of these labels as complex numbers pointing in the direction to fill in the spaces. In other words "1" means "across", $e^{4\pi i/3}$ means "down and to the left," and $e^{5\pi i/3}$ means "down and to the right." To fill in the answer to, for example, $12$ across, start at the hexagon labeled $12$, and write the digits, proceeding to the right along the gray line. (Note: $12$ across has space for exactly $5$ digits.) Each hexagon is worth one point, and must be filled by something from the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Note that $\pi$ is not in the set, and neither is $i$, nor $\sqrt2$, nor $\heartsuit$,etc. None of the answers will begin with a $0$. "Concatenate $a$ and $b$" means to write the digits of $a$, followed by the digits of $b$. For example, concatenating $10$ and $3$ gives $103$. (It's not the same as concatenating $3$ and $10$.) Calculators are allowed! THIS SHEET IS PROVIDED FOR YOUR REFERENCE ONLY. DO NOT TURN IN THIS SHEET. TURN IN THE OFFICIAL ANSWER SHEET PROVIDED TO THE TEAM. OTHERWISE YOU WILL GET A SCORE OF ZERO! ZERO! ZERO! AND WHILE SOMETIMES "!" MEANS FACTORIAL, IN THIS CASE IT DOES NOT. Good luck, and have fun![/hide] [img]https://cdn.artofproblemsolving.com/attachments/b/f/f7445136e40bf4889a328da640f0935b2b8b82.png[/img] [u][b][i]Across[/i][/b][/u] (1) [b]A 3.[/b] (3 digits) Suppose you draw $5$ vertices of a convex pentagon (but not the sides!). Let $N$ be the number of ways you can draw at least $0$ straight line segments between the vertices so that no two line segments intersect in the interior of the pentagon. What is $N - 64$? (Note what the question is asking for! You have been warned!) [b]A 5.[/b] (3 digits) Among integers $\{1, 2,..., 10^{2012}\}$, let $n$ be the number of numbers for which the sum of the digits is divisible by $5$. What are the first three digits (from the left) of $n$? [b]A 6.[/b] (3 digits) Bob is punished by his math teacher and has to write all perfect squares, one after another. His teacher's blackboard has space for exactly $2012$ digits. He can stop when he cannot fit the next perfect square on the board. (At the end, there might be some space left on the board - he does not write only part of the next perfect square.) If $n^2$ is the largest perfect square he writes, what is $n$? [b]A 8. [/b](3 digits) How many positive integers $n$ are there such that $n \le 2012$, and the greatest common divisor of $n$ and $2012$ is a prime number? [b]A 9.[/b] (4 digits) I have a random number machine generator that is very good at generating integers between $1$ and $256$, inclusive, with equal probability. However, right now, I want to produce a random number between $1$ and $n$, inclusive, so I do the following: $\bullet$ I use my machine to generate a number between $1$ and $256$. Call this $a$. $\bullet$ I take a and divide it by $n$ to get remainder $r$. If $r \ne 0$, then I record $r$ as the randomly generated number. If $r = 0$, then I record $n$ instead. Note that this process does not necessarily produce all numbers with equal probability, but that is okay. I apply this process twice to generate two numbers randomly between $1$ and $10$. Let $p$ be the probability that the two numbers are equal. What is $p \cdot 2^{16}$? [b]A 12.[/b] (5 digits) You and your friend play the following dangerous game. You two start off at some point $(x, y)$ on the plane, where $x$ and $y$ are nonnegative integers. When it is player $A$'s turn, A tells his opponent $B$ to move to another point on the plane. Then $A$ waits for a while. If $B$ is not eaten by a tiger, then $A$ moves to that point as well. From a point $(x, y)$ there are three places $A$ can tell $B$ to walk to: leftwards to $(x - 1, y)$, downwards to $(x, y-1)$, and simultaneously downwards and leftwards to $(x-1, y-1)$. However, you cannot move to a point with a negative coordinate. Now, what was this about being eaten by a tiger? There is a tiger at the origin, which will eat the first person that goes there! Needless to say, you lose if you are eaten. Consider all possible starting points $(x, y)$ with $0 \le x \le 346$ and $0 \le y \le 346$, and $x$ and $y$ are not both zero. Also suppose that you two play strategically, and you go first (i.e., by telling your friend where to go). For how many of the starting points do you win? [b][u][i]Down and to the left [/i][/u][/b] $e^{4\pi i/3}$ [b]DL 2.[/b] (2 digits) ABCDE is a pentagon with $AB = BC = CD = \sqrt2$, $\angle ABC = \angle BCD = 120$ degrees, and $\angle BAE = \angle CDE = 105$ degrees. Find the area of triangle $\vartriangle BDE$. Your answer in its simplest form can be written as $\frac{a+\sqrt{b}}{c}$ , where where $a, b, c$ are integers and $b$ is square-free. Find $abc$. [b]DL 3.[/b] (3 digits) Suppose $x$ and $y$ are integers which satisfy $$\frac{4x^2}{y^2} + \frac{25y^2}{x^2} = \frac{10055}{x^2} +\frac{4022}{y^2} +\frac{2012}{x^2y^2}- 20. $$ What is the maximum possible value of $xy -1$? [b]DL 5.[/b] (3 digits) Find the area of the set of all points in the plane such that there exists a square centered around the point and having the following properties: $\bullet$ The square has side length $7\sqrt2$. $\bullet$ The boundary of the square intersects the graph of $xy = 0$ at at least $3$ points. [b]DL 8.[/b] (3 digits) Princeton Tiger has a mom that likes yelling out math problems. One day, the following exchange between Princeton and his mom occurred: $\bullet$ Mom: Tell me the number of zeros at the end of $2012!$ $\bullet$ PT: Huh? $2012$ ends in $2$, so there aren't any zeros. $\bullet$ Mom: No, the exclamation point at the end was not to signify me yelling. I was not asking about $2012$, I was asking about $2012!$. What is the correct answer? [b]DL 9.[/b] (4 digits) Define the following: $\bullet$ $A = \sum^{\infty}_{n=1}\frac{1}{n^6}$ $\bullet$ $B = \sum^{\infty}_{n=1}\frac{1}{n^6+1}$ $\bullet$ $C = \sum^{\infty}_{n=1}\frac{1}{(n+1)^6}$ $\bullet$ $D = \sum^{\infty}_{n=1}\frac{1}{(2n-1)^6}$ $\bullet$ $E = \sum^{\infty}_{n=1}\frac{1}{(2n+1)^6}$ Consider the ratios $\frac{B}{A}, \frac{C}{A}, \frac{D}{A} , \frac{E}{A}$. Exactly one of the four is a rational number. Let that number be $r/s$, where $r$ and $s$ are nonnegative integers and $gcd \,(r, s) = 1$. Concatenate $r, s$. (It might be helpful to know that $A = \frac{\pi^6}{945}$ .) [b]DL 10.[/b] (3 digits) You have a sheet of paper, which you lay on the xy plane so that its vertices are at $(-1, 0)$, $(1, 0)$, $(1, 100)$, $(-1, 100)$. You remove a section of the bottom of the paper by cutting along the function $y = f(x)$, where $f$ satisfies $f(1) = f(-1) = 0$. (In other words, you keep the bottom two vertices.) You do this again with another sheet of paper. Then you roll both of them into identical cylinders, and you realize that you can attach them to form an $L$-shaped elbow tube. We can write $f\left( \frac13 \right)+f\left( \frac16 \right) = \frac{a+\sqrt{b}}{\pi c}$ , where $a, b, c$ are integers and $b$ is square-free. $Find a+b+c$. [b]DL 11.[/b] (3 digits) Let $$\Xi (x) = 2012(x - 2)^2 + 278(x - 2)\sqrt{2012 + e^{x^2-4x+4}} + 1392 + (x^2 - 4x + 4)e^{x^2-4x+4}$$ find the area of the region in the $xy$-plane satisfying: $$\{x \ge 0 \,\,\, and x \le 4 \,\,\, and \,\,\, y \ge 0 \,\,\, and \,\,\, y \le \sqrt{\Xi(x)}\}$$ [b]DL 13.[/b] (3 digits) Three cones have bases on the same plane, externally tangent to each other. The cones all face the same direction. Two of the cones have radii of $2$, and the other cone has a radius of $3$. The two cones with radii $2$ have height $4$, and the other cone has height $6$. Let $V$ be the volume of the tetrahedron with three of its vertices as the three vertices of the cones and the fourth vertex as the center of the base of the cone with height $6$. Find $V^2$. [b][u][i]Down and to the right[/i][/u][/b] $e^{5\pi i/3}$ [b]DR 1.[/b] (2 digits) For some reason, people in math problems like to paint houses. Alice can paint a house in one hour. Bob can paint a house in six hours. If they work together, it takes them seven hours to paint a house. You might be thinking "What? That's not right!" but I did not make a mistake. When Alice and Bob work together, they get distracted very easily and simultaneously send text messages to each other. When they are texting, they are not getting any work done. When they are not texting, they are painting at their normal speeds (as if they were working alone). Carl, the owner of the house decides to check up on their work. He randomly picks a time during the seven hours. The probability that they are texting during that time can be written as $r/s$, where r and s are integers and $gcd \,(r, s) = 1$. What is $r + s$? [b]DR 4.[/b] (3 digits) Let $a_1 = 2 +\sqrt2$ and $b_1 =\sqrt2$, and for $n \ge 1$, $a_{n+1} = |a_n - b_n|$ and $b_{n+1} = a_n + b_n$. The minimum value of $\frac{a^2_n+a_nb_n-6b^2_n}{6b^2_n-a^2_n}$ can be written in the form $a\sqrt{b} - c$, where $a, b, c$ are integers and $b$ is square-free. Concatenate $c, b, a$ (in that order!). [b]DR 7.[/b] (3 digits) How many solutions are there to $a^{503} + b^{1006} = c^{2012}$, where $a, b, c$ are integers and $|a|$,$|b|$, $|c|$ are all less than $2012$? PS. You should use hide for answers.

A positive integer $n$ is called [i]nice[/i] if it has at least $3$ proper divisors and it is equal to the sum of its three largest proper divisors. For example, $6$ is [i]nice[/i] because its largest three proper divisors are $3,2,1$ and $6=3+2+1$. Find the number of [i]nice[/i] integers not greater than $3000$.

Prove that for every positive integer $t$ there is a unique permutation $a_0, a_1, \ldots , a_{t-1}$ of $0, 1, \ldots , t-1$ such that, for every $0 \leq i \leq t-1$, the binomial coefficient $\binom{t+i}{2a_i}$ is odd and $2a_i \neq t+i$.

For any sequence ($a_1,a_2,...,a_{2013}$) of integers, we call a triple ($i,j, k$) satisfying $1 \le i < j < k \le 2013$ to be [i]progressive [/i] if $a_k-a_j = a_j -a_i = 1$. Determine the maximum number of progressive triples that a sequence of $2013$ integers could have.

Two right isosceles triangles of legs equal to $1$ are glued together to form either an isosceles triangle - called [i]t-shape[/i] - of leg $\sqrt2$, or a parallelogram - called [i]p-shape[/i] - of sides $1$ and $\sqrt2$. Find all integers $m$ and $n, m, n \ge 2$, such that a rectangle $m \times n$ can be tilled with t-shapes and p-shapes.

Jody has $6$ distinguishable balls and $6$ distinguishable sticks, all of the same length. How many ways are there to use the sticks to connect the balls so that two disjoint non-interlocking triangles are formed? Consider rotations and reflections of the same arrangement to be indistinguishable.

Ryan Murphy is playing poker. He is dealt a hand of $5$ cards. Given that the probability that he has a straight hand (the ranks are all consecutive; e.g. $3,4,5,6,7$ or $9,10,J,Q,K$) or $3$ of a kind (at least $3$ cards of the same rank; e.g. $5, 5, 5, 7, 7$ or $5, 5, 5, 7,K$) is $m/n$ , where $m$ and $n$ are relatively prime positive integers, find $m +n$. [i]Proposed by Aditya Rao[/i]

Let ${n}$ be a fixed positive integer. ${A}$ and ${B}$ play the following game: $2023$ coins marked $1, 2, \dots, 2023$ lie on a circle (the marks are considered in module $2023$) and each coin has two sides. Initially, all coins are head up and ${A}$'s goal is to make as many coins with tail up. In each operation, ${A}$ choose two coins marked ${k}$ and $k+3$ with head up (if ${A}$ can't choose, the game ends) and ${B}$ choose a coin marked $k+1$ or $k+2$ and flip it. If at some moment there are ${n}$ coins with tail up, ${A}$ wins. Find the largest ${n}$ such that ${A}$ has a winning strategy.

In the center of a square is a rabbit and at each vertex of this even square, a wolf. The wolves only move along the sides of the square and the rabbit moves freely in the plane. Knowing that the rabbit move at a speed of $10$ km / h and that the wolves move to a maximum speed of $14$ km / h, determine if there is a strategy for the rabbit to leave the square without being caught by the wolves.

Given two forests $A$ and $B$ with \(V(A) = V(B)\), that is the graphs are over same vertex set. Suppose $A$ has [b]strictly more[/b] edges than $B$. Prove that there exists an edge of $A$ which if included in the edge set of $B$, then $B$ will still remain a forest. Graphs are undirected

(I'll skip over the whole "dressing" of the graph in cities and flights [color=#FF0000][Mod edit: Shu has posted the "dressed-up" version below][/color]) For an ordinary directed graph, show that there is a subset A of vertices such that: $1.$ There are no edges between the vertices of A. $2.$ For any vertex $v$, there is either a direct way from $v$ to a vertex in A, or a way passing through only one vertex and ending in A (like $v$ ->$v'$-> $a$, where $a$ is a vertex in A)

Find all positive integers $n$ such that one can place checkers on a $n\times n$ checkerboard such that any square chosen from the checkerboard has exactly $2$ adjacent squares with checkers on it. Two squares are considered adjacent if they both share a common side

The cheering team of Ubon Ratchathani University sits on the amphitheater that has $441$ seats arranged into a $21\times 21$ grid. Every seat is occupied by exactly one person, and each person has a blue sign and a yellow sign. Count the number of ways for each person to raise one sign so that each row and column has an odd number of people raising a blue sign.

In a group of mathematicians, every mathematician has some friends (the relation of friend is reciprocal). Prove that there exists a mathematician, such that the average of the number of friends of all his friends is no less than the average of the number of friends of all these mathematicians.

What is the greatest number of parts into which the plane can be cut by the edges of $ n $ squares?

$2n-1$ distinct positive real numbers with sum $S $ are given. Prove that there are at least $\binom {2n-2}{n-1}$ different ways to choose $n $ numbers among them such that their sum is at least $\frac {S}{2}$. [i]Proposed by Amirhossein Gorzi[/i]

Let $n$ be a positive integer.Consider all $2^n$ binary strings of length $n$.We say two of these strings are neighbors if they differ in exactly 1 digit.We have colored $m$ strings.In each moment,we can color any uncolored string which is neighbor with at least 2 colored strings.After some time,all the strings are colored.Find the minimum possible value of $m$.

A single segment contains several non-intersecting red segments, the total length of which is greater than $0.5$. Are there necessarily two red dots at the distance: a) $1/99$ b) $1/100$ ?

In a mathematical contest, three problems, $A,B,C$ were posed. Among the participants ther were 25 students who solved at least one problem each. Of all the contestants who did not solve problem $A$, the number who solved $B$ was twice the number who solved $C$. The number of students who solved only problem $A$ was one more than the number of students who solved $A$ and at least one other problem. Of all students who solved just one problem, half did not solve problem $A$. How many students solved only problem $B$?