We have an $n \times n$ square divided into unit squares. Each side of unit square is called unit segment. Some isoceles right triangles of hypotenuse $2$ are put on the square so all their vertices are also vertices of unit squares. For which $n$ it is possible that every unit segment belongs to exactly one triangle(unit segment belongs to a triangle even if it's on the border of the triangle)?

There are $n$ boxes ${B_1},{B_2},\ldots,{B_n}$ from left to right, and there are $n$ balls in these boxes. If there is at least $1$ ball in ${B_1}$, we can move one to ${B_2}$. If there is at least $1$ ball in ${B_n}$, we can move one to ${B_{n - 1}}$. If there are at least $2$ balls in ${B_k}$, $2 \leq k \leq n - 1$ we can move one to ${B_{k - 1}}$, and one to ${B_{k + 1}}$. Prove that, for any arrangement of the $n$ balls, we can achieve that each box has one ball in it.

[b]Problem 3.[/b] Let $n\geq 3$ is given natural number, and $M$ is the set of the first $n$ primes. For any nonempty subset $X$ of $M$ with $P(X)$ denote the product of its elements. Let $N$ be a set of the kind $\ds\frac{P(A)}{P(B)}$, $A\subset M, B\subset M, A\cap B=\emptyset$ such that the product of any 7 elements of $N$ is integer. What is the maximal number of elements of $N$? [i]Alexandar Ivanov[/i]

The plane is colored with two colors so that the following property holds: for each real $a>0$ there is an equilateral triangle of side length $a$ whose $3$ vertices are of the same color. Prove that for any three numbers $a,b,c>0$ for which the sum of any two is greater than the third there is a triangle with sides $a$, $b$, and $c$ whose $3$ vertices are of the same color.

A [i]calendar[/i] is a (finite) rectangular grid. A calendar is [i]valid[/i] if it satisfies the following conditions: (i) Each square of the calendar is colored white or red, and there are exactly 10 red squares. (ii) Suppose that there are $N$ columns of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the top row to the bottom row, and within each row from left to right, there do not exist $N$ consecutive numbers such that the squares they are in are all white. (iii) Suppose that there are $M$ rows of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the left-most column to the right-most column, and within each column from bottom to top, there do not exist $M$ consecutive numbers such that the squares they are in are all white. In other words, if we rotate the calendar clockwise by $90^{\circ}$, the resulting calendar still satisfies (ii). How many different kinds of valid calendars are there? (Remark: During the actual exam, the contestants were confused about what counts as different calendars. So although this was not in the actual exam, I would like to specify that two calendars are considered different if they have different side lengths or if the $10$ red squares are at different locations.)

[u]Round 6[/u] [b]p16.[/b] Given that $x$ and $y$ are positive real numbers such that $x^3+y = 20$, the maximum possible value of $x + y$ can be written as $\frac{a\sqrt{b}}{c}$ +d where $a$, $b$, $c$, and $d$ are positive integers such that $gcd(a,c) = 1$ and $b$ is square-free. Find $a +b +c +d$. [b]p17.[/b] In $\vartriangle DRK$ , $DR = 13$, $DK = 14$, and $RK = 15$. Let $E$ be the intersection of the altitudes of $\vartriangle DRK$. Find the value of $\lfloor DE +RE +KE \rfloor$. [b]p18.[/b] Subaru the frog lives on lily pad $1$. There is a line of lily pads, numbered $2$, $3$, $4$, $5$, $6$, and $7$. Every minute, Subaru jumps from his current lily pad to a lily pad whose number is either $1$ or $2$ greater, chosen at random from valid possibilities. There are alligators on lily pads $2$ and $5$. If Subaru lands on an alligator, he dies and time rewinds back to when he was on lily pad number $1$. Find the expected number of jumps it takes Subaru to reach pad $7$. [u]Round 7[/u] This set has problems whose answers depend on one another. [b]p19.[/b] Let $B$ be the answer to Problem $20$ and let $C$ be the answer to Problem $21$. Given that $$f (x) = x^3-Bx-C = (x-r )(x-s)(x-t )$$ where $r$, $s$, and $t$ are complex numbers, find the value of $r^2+s^2+t^2$. [b]p20.[/b] Let $A$ be the answer to Problem $19$ and let $C$ be the answer to Problem $21$. Circles $\omega_1$ and $\omega_2$ meet at points $X$ and $Y$ . Let point $P \ne Y$ be the point on $\omega_1$ such that $PY$ is tangent to $\omega_2$, and let point $Q \ne Y$ be the point on $\omega_2$ such that $QY$ is tangent to $\omega_1$. Given that $PX = A$ and $QX =C$, find $XY$ . [b]p21.[/b] Let $A$ be the answer to Problem $19$ and let $B$ be the answer to Problem $20$. Given that the positive difference between the number of positive integer factors of $A^B$ and the number of positive integer factors of $B^A$ is $D$, and given that the answer to this problem is an odd prime, find $\frac{D}{B}-40$. [u]Round 8[/u] [b]p22.[/b] Let $v_p (n)$ for a prime $p$ and positive integer $n$ output the greatest nonnegative integer $x$ such that $p^x$ divides $n$. Find $$\sum^{50}_{i=1}\sum^{i}_{p=1} { v_p (i )+1 \choose 2},$$ where the inner summation only sums over primes $p$ between $1$ and $i$ . [b]p23.[/b] Let $a$, $b$, and $c$ be positive real solutions to the following equations. $$\frac{2b^2 +2c^2 -a^2}{4}= 25$$ $$\frac{2c^2 +2a^2 -b^2}{4}= 49$$ $$\frac{2a^2 +2b^2 -c^2}{4}= 64$$ The area of a triangle with side lengths $a$, $b$, and $c$ can be written as $\frac{x\sqrt{y}}{z}$ where $x$ and $z$ are relatively prime positive integers and $y$ is square-free. Find $x + y +z$. [b]p24.[/b] Alan, Jiji, Ina, Ryan, and Gavin want to meet up. However, none of them know when to go, so they each pick a random $1$ hour period from $5$ AM to $11$ AM to meet up at Alan’s house. Find the probability that there exists a time when all of them are at the house at one time. [b]Round 9 [/b] [b]p25.[/b] Let $n$ be the number of registered participantsin this $LMT$. Estimate the number of digits of $\left[ {n \choose 2} \right]$ in base $10$. If your answer is $A$ and the correct answer is $C$, then your score will be $$\left \lfloor \max \left( 0,20 - \left| \ln \left( \frac{A}{C}\right) \cdot 5 \right|\right| \right \rfloor.$$ [b]p26.[/b] Let $\gamma$ be theminimum value of $x^x$ over all real numbers $x$. Estimate $\lfloor 10000\gamma \rfloor$. If your answer is $A$ and the correct answer is $C$, then your score will be $$\left \lfloor \max \left( 0,20 - \left| \ln \left( \frac{A}{C}\right) \cdot 5 \right|\right| \right \rfloor.$$ [b]p27.[/b] Let $$E = \log_{13} 1+log_{13}2+log_{13}3+...+log_{13}513513.$$ Estimate $\lfloor E \rfloor$. If your answer is $A$ and the correct answer is $C$, your score will be $$\left \lfloor \max \left( 0,20 - \left| \ln \left( \frac{A}{C}\right) \cdot 5 \right|\right| \right \rfloor.$$ PS. You should use hide for answers. Rounds 1-5 have been posted [url=https://artofproblemsolving.com/community/c3h3167127p28823220]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

The cube $nxnxn$ consists of $n^3$ unit cubes $1x1x1$, and at least one of these unit cubes is black. Show that we can always cut the cube in $2$ parallelepiped pieces so that each piece contains exactly one black 1x1 square .

Let $n$ be a positive integer. At most how many distinct unit vectors can be selected in $\mathbb{R}^n$ such that from any three of them, at least two are orthogonal?

The checkered plane is divided into dominoes. What is the maximum $k{}$ for which it is always possible to choose a $100\times 100$ checkered square containing at least $k{}$ whole dominoes? [i]Proposed by S. Berlov[/i]

Some of the vertices of a convex $n$-gon are connected by segments, such that any two of them have no common interior point. Prove that, for any $n$ points in general position, there exists a one-to-one correspondence between the points and the vertices of the $n$ gon, such that any two segments between the points, corresponding to the respective segments from the $n$ gon, have no common interior point.

Consider $998$ red points on the plane with no three collinear. We select $k$ blue points in such a way that inside each triangle whose vertices are red points, there is a blue point as well. Find the smallest $k$ for which the described selection of blue points is possible for any configuration of $998$ red points.

[u]Round 1[/u] [b]p1.[/b] Alex is writing a sequence of $A$’s and $B$’s on a chalkboard. Any $20$ consecutive letters must have an equal number of $A$’s and $B$’s, but any 22 consecutive letters must have a different number of $A$’s and $B$’s. What is the length of the longest sequence Alex can write?. [b]p2.[/b] A positive number is placed on each of the $10$ circles in this picture. It turns out that for each of the nine little equilateral triangles, the number on one of its corners is the sum of the numbers on the other two corners. Is it possible that all $10$ numbers are different? [img]https://cdn.artofproblemsolving.com/attachments/b/f/c501362211d1c2a577e718d2b1ed1f1eb77af1.png[/img] [b]p3.[/b] Pablo and Nina take turns entering integers into the cells of a $3 \times 3$ table. Pablo goes first. The person who fills the last empty cell in a row must make the numbers in that row add to $0$. Can Nina ensure at least two of the columns have a negative sum, no matter what Pablo does? [b]p4. [/b]All possible simplified fractions greater than $0$ and less than $1$ with denominators less than or equal to $100$ are written in a row with a space before each number (including the first). Zeke and Qing play a game, taking turns choosing a blank space and writing a “$+$” or “$-$” sign in it. Zeke goes first. After all the spaces have been filled, Zeke wins if the value of the resulting expression is an integer. Can Zeke win no matter what Qing does? [img]https://cdn.artofproblemsolving.com/attachments/3/6/15484835686fbc2aa092e8afc6f11cd1d1fb88.png[/img] [b]p5.[/b] A police officer patrols a town whose map is shown. The officer must walk down every street segment at least once and return to the starting point, only changing direction at intersections and corners. It takes the officer one minute to walk each segment. What is the fastest the officer can complete a patrol? [img]https://cdn.artofproblemsolving.com/attachments/0/c/d827cf26c8eaabfd5b0deb92612a6e6ebffb47.png[/img] [u]Round 2[/u] [b]p6.[/b] Prove that among any $3^{2022}$ integers, it is possible to find exactly $3^{2021}$ of them whose sum is divisible by $3^{2021}$. [b]p7.[/b] Given a list of three numbers, a zap consists of picking two of the numbers and decreasing each of them by their average. For example, if the list is $(5, 7, 10)$ and you zap $5$ and $10$, whose average is $7.5$, the new list is $(-2.5, 7, 2.5)$. Is it possible to start with the list $(3, 1, 4)$ and, through some sequence of zaps, end with a list in which the sum of the three numbers is $0$? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $ n $ be a natural number. Consider all permutations $ ({{a} _ {1}}, \ \ldots, \ {{a} _ {2n}}) $ of the first $ 2n $ natural numbers such that the numbers $ | {{a} _ {i +1}} - {{a} _ {i}} |, \ i = 1, \ \ldots, \ 2n-1, $ are pairwise different. Prove that $ {{a} _ {1}} - {{a} _ {2n}} = n $ if and only if $ 1 \le {{a} _ {2k}} \le n $ for all $ k = 1, \ \ldots, \ n $.

In a classroom, $28$ students are divided into $4$ groups of $7$, and in each group the students are labeled $1, 2,..., 7$ in some order. Show that no matter how the labels are assigned, there must be four students of the same gender who come from two groups and share the same two labels.

Akello divides a square up into finitely many white and red rectangles, each (rectangle) with sides parallel to the sides of the parent square. Within each white rectangle, she writes down the value of its width divided by its height, while within each red rectangle, she writes down the value of its height divided by its width. Finally, she calculates $x$, the sum of these numbers. If the total area of the white rectangles equals the total area of the red rectangles, what is the least possible value of $x$ she can get?

[u]Set 6[/u] [b]B16.[/b] Let $\ell_r$ denote the line $x + ry + r^2 = 420$. Jeffrey draws the lines $\ell_a$ and $\ell_b$ and calculates their single intersection point. [b]B17.[/b] Let set $L$ consist of lines of the form $3x + 2ay = 60a + 48$ across all real constants a. For every line $\ell$ in $L$, the point on $\ell$ closest to the origin is in set $T$ . The area enclosed by the locus of all the points in $T$ can be expressed in the form nπ for some positive integer $n$. Compute $n$. [b]B18.[/b] What is remainder when the $2020$-digit number $202020 ... 20$ is divided by $275$? [u]Set 7[/u] [b]B19.[/b] Consider right triangle $\vartriangle ABC$ where $\angle ABC = 90^o$, $\angle ACB = 30^o$, and $AC = 10$. Suppose a beam of light is shot out from point $A$. It bounces off side $BC$ and then bounces off side $AC$, and then hits point $B$ and stops moving. If the beam of light travelled a distance of $d$, then compute $d^2$. [b]B20.[/b] Let $S$ be the set of all three digit numbers whose digits sum to $12$. What is the sum of all the elements in $S$? [b]B21.[/b] Consider all ordered pairs $(m, n)$ where $m$ is a positive integer and $n$ is an integer that satisfy $$m! = 3n^2 + 6n + 15,$$ where $m! = m \times (m - 1) \times ... \times 1$. Determine the product of all possible values of $n$. [u]Set 8[/u] [b]B22.[/b] Compute the number of ordered pairs of integers $(m, n)$ satisfying $1000 > m > n > 0$ and $6 \cdot lcm(m - n, m + n) = 5 \cdot lcm(m, n)$. [b]B23.[/b] Andrew is flipping a coin ten times. After every flip, he records the result (heads or tails). He notices that after every flip, the number of heads he had flipped was always at least the number of tails he had flipped. In how many ways could Andrew have flipped the coin? [b]B24.[/b] Consider a triangle $ABC$ with $AB = 7$, $BC = 8$, and $CA = 9$. Let $D$ lie on $\overline{AB}$ and $E$ lie on $\overline{AC}$ such that $BCED$ is a cyclic quadrilateral and $D, O, E$ are collinear, where $O$ is the circumcenter of $ABC$. The area of $\vartriangle ADE$ can be expressed as $\frac{m\sqrt{n}}{p}$, where $m$ and $p$ are relatively prime positive integers, and $n$ is a positive integer not divisible by the square of any prime. What is $m + n + p$? [u]Set 9[/u] [i]This set consists of three estimation problems, with scoring schemes described.[/i] [b]B25.[/b] Submit one of the following ten numbers: $$3 \,\,\,\, 6\,\,\,\, 9\,\,\,\, 12\,\,\,\, 15\,\,\,\, 18\,\,\,\, 21\,\,\,\, 24\,\,\,\, 27\,\,\,\, 30.$$ The number of points you will receive for this question is equal to the number you selected divided by the total number of teams that selected that number, then rounded up to the nearest integer. For example, if you and four other teams select the number $27$, you would receive $\left\lceil \frac{27}{5}\right\rceil = 6$ points. [b]B26.[/b] Submit any integer from $1$ to $1,000,000$, inclusive. The standard deviation $\sigma$ of all responses $x_i$ to this question is computed by first taking the arithmetic mean $\mu$ of all responses, then taking the square root of average of $(x_i -\mu)^2$ over all $i$. More, precisely, if there are $N$ responses, then $$\sigma =\sqrt{\frac{1}{N} \sum^N_{i=1} (x_i -\mu)^2}.$$ For this problem, your goal is to estimate the standard deviation of all responses. An estimate of $e$ gives $\max \{ \left\lfloor 130 ( min \{ \frac{\sigma }{e},\frac{e}{\sigma }\}^{3}\right\rfloor -100,0 \}$ points. [b]B27.[/b] For a positive integer $n$, let $f(n)$ denote the number of distinct nonzero exponents in the prime factorization of $n$. For example, $f(36) = f(2^2 \times 3^2) = 1$ and $f(72) = f(2^3 \times 3^2) = 2$. Estimate $N = f(2) + f(3) +.. + f(10000)$. An estimate of $e$ gives $\max \{30 - \lfloor 7 log_{10}(|N - e|)\rfloor , 0\}$ points. PS. You had better use hide for answers. First sets have been posted [url=https://artofproblemsolving.com/community/c4h2777391p24371239]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Prove that from any sequence of $1996$ real numbers $a_1$, $a_2$,$...$, $a_{1996}$ one can choose one or several numbers standing successively one after another so that their sum differs from an integer by less than $0.001$. (A Kanel)

[b]p1.[/b] (a) Suppose $101$ Dalmatians chase $2012$ squirrels. Each squirrel gets chased by at most one Dalmatian, and each Dalmatian chases at least one squirrel. Show that two Dalmatians chase the same number of squirrels. (b) What is the largest number of Dalmatians that can chase $2012$ squirrels in a way that each Dalmatian chases at least one squirrel and no two Dalmatians chase the same number of squirrels? [b]p2.[/b] Lucy and Linus play the following game. They start by putting the integers $1, 2, 3, ..., 2012$ in a hat. In each round of the game, Lucy and Linus each draw a number from the hat. If the two numbers are $a$ and $b$, they throw away these numbers and put the number $|a - b|$ back into the hat. After $2011$ rounds, there is only one number in the hat. If it is even, Lucy wins. If it is odd, Linus wins. (a) Prove that there is a sequence of drawings that makes Lucy win. (b) Prove that Lucy always wins. [b]p3.[/b] Suppose $x$ is a positive real number and $x^{1990}$, $x^{2001}$, and $x^{2012}$ differ by integers. Prove that $x$ is an integer. [b]p4.[/b] Suppose that each point in three-dimensional space is colored with one of five colors and suppose that each color is used at least once. Prove that there is some plane that contains at least four of the colors. [b]p5.[/b] Two circles, $C_1$ and $C_2$, are tangent at point $A$, with $C_1$ lying inside $C_2$ (and $C_1 \ne C_2$). The line through their centers intersects $C_1$ at $B_1$ and $C_2$ at $B_2$. A line $L$ is drawn through $A$ and it intersects $C_1$ at $P_1$ (with $P_1 \ne A$) and intersects $C_2$ at $P_2$ (with $P_2 \ne A$). The perpendicular from $P_2$ to the line $B_1B_2$ intersects the line $B_1B_2$ at $F$. Prove that if the line $P_1F$ is tangent to $C_1$ then $F$ is the midpoint of the line segment $B_1B_2$. [img]https://cdn.artofproblemsolving.com/attachments/9/e/4db59be9fa764d3e910a828ed3296907ca5657.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

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 natural numbers \( n \) for which it is possible to construct an \( n \times n \) square using only tetrominoes like the one below:

A set $ X$ of positive integers is called [i]nice[/i] if for each pair $ a$, $ b\in X$ exactly one of the numbers $ a \plus{} b$ and $ |a \minus{} b|$ belongs to $ X$ (the numbers $ a$ and $ b$ may be equal). Determine the number of nice sets containing the number 2008. [i]Author: Fedor Petrov[/i]

We are given a graph $G$ with $n$ edges. For each edge, we write down the lesser degree of two vertices at the end of that edge. Prove that the sum of the resulting $n$ numbers is at most $100n\sqrt{n}$.

Let $n$ be a positive integer. Let $G (n)$ be the number of $x_1,..., x_n, y_1,...,y_n \in \{0,1\}$, for which the number $x_1y_1 + x_2y_2 +...+ x_ny_n$ is even, and similarly let $U (n)$ be the number for which this sum is odd. Prove that $$\frac{G(n)}{U(n)}= \frac{2^n + 1}{2^n - 1}.$$

Let $\ell = 1$, $M = 23$, $N = 45$, and $u = 67$. Compute the number of ordered pairs of nonnegative integers $(X, Y)$ with $X \leq M - \ell$ and $Y \leq N + u$ such that the sum \[ \sum_{k=\ell}^{u} \binom{X + k}{M}\cdot\binom{Y - k}{N} \] is divisible by $89$ (for integers $a$ and $b$, define the binomial coefficient $\tbinom{a}{b}$ to be the number of $b$-element subsets of any given $a$-element set, which is $0$ when $a < 0$, $b < 0$, or $b > a$).