Calculate number of the hamiltonian cycles of the graph below: (15 points)

A $7 \times 7$ square is made up of $16$ $1 \times 3$ tiles and $1$ $1 \times 1$ tile. Prove that the $1 \times 1$ tile lies either at the centre of the square or adjoins one of its boundaries .

Given an integer number $n \geq 3$, consider $n$ distinct points on a circle, labelled $1$ through $n$. Determine the maximum number of closed chords $[ij]$, $i \neq j$, having pairwise non-empty intersections. [i]János Pach[/i]

[u]Round 1[/u] [b]p1.[/b] The temperature inside is $28^o$ F. After the temperature is increased by $5^o$ C, what will the new temperature in Fahrenheit be? [b]p2.[/b] Find the least positive integer value of $n$ such that $\sqrt{2021+n}$ is a perfect square. [b]p3.[/b] A heart consists of a square with two semicircles attached by their diameters as shown in the diagram. Given that one of the semicircles has a diameter of length $10$, then the area of the heart can be written as $a +b\pi$ where $a$ and $b$ are positive integers. Find $a +b$. [img]https://cdn.artofproblemsolving.com/attachments/7/b/d277d9ebad76f288504f0d5273e19df568bc44.png[/img] [u]Round 2[/u] [b]p4.[/b] An $L$-shaped tromino is a group of $3$ blocks (where blocks are squares) arranged in a $L$ shape, as pictured below to the left. How many ways are there to fill a $12$ by $2$ rectangle of blocks (pictured below to the right) with $L$-shaped trominos if the trominos can be rotated or reflected? [img]https://cdn.artofproblemsolving.com/attachments/d/c/cf37cdf9703ae0cd31c38af23b6874fddb3c12.png[/img] [b]p5.[/b] How many permutations of the word $PIKACHU$ are there such that no two vowels are next to each other? [b]p6.[/b] Find the number of primes $n$ such that there exists another prime $p$ such that both $n +p$ and $n-p$ are also prime numbers. [u]Round 3[/u] [b]p7.[/b] Maisy the Bear is at the origin of the Cartesian Plane. WhenMaisy is on the point $(m,n)$ then it can jump to either $(m,n +1)$ or $(m+1,n)$. Let $L(x, y)$ be the number of jumps it takes forMaisy to reach point (x, y). The sum of $L(x, y)$ over all lattice points $(x, y)$ with both coordinates between $0$ and $2020$, inclusive, is denoted as $S$. Find $\frac{S}{2020}$ . [b]p8.[/b] A circle with center $O$ and radius $2$ and a circle with center $P$ and radius $3$ are externally tangent at $A$. Points $B$ and $C$ are on the circle with center $O$ such that $\vartriangle ABC$ is equilateral. Segment $AB$ extends past $B$ to point $D$ and $AC$ extends past $C$ to point $E$ such that $BD = CE = \sqrt3$. The area of $\vartriangle DEP$ can be written as $\frac{a\sqrt{b}}{c}$ where $a$, $b$, and $c$ are integers such that $b$ is squarefree and $gcd (a,c) = 1$. Find $a +b +c$. [b]p9.[/b] Find the number of trailing zeroes at the end of $$\prod^{2021}_{i=1}(2021+i -1) = (2021)(2022)...(4041).$$ [u]Round 4[/u] [b]p10.[/b] Let $a, b$, and $c$ be side lengths of a rectangular prism with space diagonal $10$. Find the value of $$(a +b)^2 +(b +c)^2 +(c +a)^2 -(a +b +c)^2.$$ [b]p11.[/b] In a regular heptagon $ABCDEFG$, $\ell$ is a line through $E$ perpendicular to $DE$. There is a point $P$ on $\ell$ outside the heptagon such that $PA = BC$. Find the measure of $\angle EPA$. [b]p12.[/b] Dunan is being "$SUS$". The word "$SUS$" is a palindrome. Find the number of palindromes that can be written using some subset of the letters $\{S, U, S, S, Y, B, A, K, A\}$. PS. You should use hide for answers. Rounds 5-8 have been posted [url=https://artofproblemsolving.com/community/c3h3166494p28814284]here [/url] and 9-12 [url=https://artofproblemsolving.com/community/c3h3166500p28814367]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

An ant crawls along the edges of a cube turning only at its vertices. It has visited one of the vertices $25$ times. Is it possible that it has visited each of the other $7$ vertices exactly $20$ times? (S Tokarev)

Let $\mathcal{F}$ be the set of all the functions $f : \mathcal{P}(S) \longrightarrow \mathbb{R}$ such that for all $X, Y \subseteq S$, we have $f(X \cap Y) = \min (f(X), f(Y))$, where $S$ is a finite set (and $\mathcal{P}(S)$ is the set of its subsets). Find \[\max_{f \in \mathcal{F}}| \textrm{Im}(f) |. \]

Let $A_{1}A_{2}B_{1}B_{2}$ be a convex quadrilateral. At adjacent vertices $A_{1}$ and $A_{2}$ there are two Argentinian cities. At adjacent vertices $B_{1}$ and $B_{2}$ there are two Brazilian cities. There are $a$ Argentinian cities and $b$ Brazilian cities in the quadrilateral interior, no three of which collinear. Determine if it's possible, independently from the cities position, to build straight roads, each of which connects two Argentinian cities ou two Brazilian cities, such that: $\bullet$ Two roads does not intersect in a point which is not a city; $\bullet$ It's possible to reach any Argentinian city from any Argentinian city using the roads; and $\bullet$ It's possible to reach any Brazilian city from any Brazilian city using the roads. If it's always possible, construct an algorithm that builds a possible set of roads.

An ant decides to walk on the perimeter of an $ABC$ triangle. The ant can start at any vertex. Whenever the ant is in a vertex, it chooses one of the adjacent vertices and walks directly (in a straight line) to the chosen vertex. a) In how many ways can the ant walk around each vertex exactly twice? b) In how many ways can the ant walk around each vertex exactly three times? Note: For each item, consider that the starting vertex is visited.

Given any odd integer $n>3$ that is not divisible by $3$, determine whether it is possible to fill an $n \times n$ grid with $n^2$ integers such that (each cell filled with a number, the number at the intersection of the $i$-th row and $j$-th column is denoted as $a_{ij}$): $\cdot$ Each row and each column contains a permutation of the numbers $0,1,2, \cdots, n-1$. $\cdot$ The pairs $(a_{ij},a_{ji})$ for $i<j$ are all distinct.

Determine whether it is possible to place the integers $1, 2,...,2012$ in a circle in such a way that the $2012$ products of adjacent pairs of numbers leave pairwise distinct remainders when divided by $2013$.

A quota of diplomas at the All-Russian Olympiad should be strictly less than $45\%$. More than $20$ students took part in the olympiad. After the olympiad the Authorities declared the results low because the quota of diplomas was significantly less than $45\%$. The Jury responded that the quota was already maximum possible on this olympiad or any other olympiad with smaller number of participants. Then the Authorities ordered to increase the number of participants for the next olympiad so that the quota of diplomas became at least two times closer to $45\%$. Prove that the number of participants should be at least doubled.

A person enters the social network facebook. He befriends at least one person a day for the first $30$ days. At the end of those $30$ days, it has been exactly $45$ friends. Prove that there is a sequence of consecutive days where made exactly $14$ friends.

In the plane there are $2014$ plotted points, such that no $3$ are collinear. For each pair of plotted points, draw the line that passes through them. prove that for every three of marked points there are always two that are separated by an amount odd number of lines.

A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?

[u]Round 5[/u] [b]p13.[/b] Jason flips a coin repeatedly. The probability that he flips $15$ heads before flipping $4$ tails can be expressed as $\frac{a}{2^b}$ where $a$ and $b$ are positive integers and $a$ is odd. Find $a +b$. [b]p14.[/b] Triangle $ABC$ has side lengths $AB = 3$, $BC = 3$, and $AC = 4$. Let D be the intersection of the angle bisector of $\angle B AC$ and segment $BC$. Let the circumcircle of $\vartriangle B AD$ intersect segment $AC$ at a point $E$ distinct from $A$. The length of $AE$ can be expressed as $\frac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Find $a +b$. [b]p15.[/b] The sum of the squares of all values of $x$ such that $\{(x -2)(x -3)\} = \{(x -1)(x -6)\}$ and $\lfloor x^2 -6x +6 \rfloor= 9$ can be written as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Find $a +b$. Note: $\{a\}$ is the fractional part function, and returns $a -\lfloor a \rfloor$ . [u]Round 6[/u] [b]p16.[/b] Maisy the Polar Bear is at the origin of the Polar Plane ($r = 0, \theta = 0$). Maisy’s location can be expressed as $(r,\theta)$, meaning it is a distance of $r$ away from the origin and at a angle of $\theta$ degrees counterclockwise from the $x$-axis. When Maisy is on the point $(m,n)$ then it can jump to either $(m,n +1)$ or $(m+1,n)$. Maisy cannot jump to any point it has been to before. Let $L(r,\theta)$ be the number of paths Maisy can take to reach point $(r,\theta)$. The sum of $L(r,\theta)$ over all points where $r$ is an integer between $1$ and $2020$ and $\theta$ is an integer between $0$ and $359$ can be written as $\frac{n^k-1}{m}$ for some minimum value of $n$, such that $n$, $k$, and $m$ are all positive integers. Find $n +k +m$. [b]p17.[/b] A circle with center $O$ and radius $2$ and a circle with center $P$ and radius $3$ are externally tangent at $A$. Points $B$ and $C$ are on the circle with center $O$ such that $\vartriangle ABC$ is equilateral. Segment $AB$ extends past $B$ to point $D$ and $AC$ extends past $C$ to point $E$ such that $BD = CE = \sqrt3$. A line through $D$ is tangent to circle $P$ at $F$. Find $DF^2$. [img]https://cdn.artofproblemsolving.com/attachments/2/7/0ee8716cebd6701fcae6544d9e39e68fff35f5.png[/img] [b]p18.[/b] Find the number of trailing zeroes at the end of $$\prod^{2021}_{i=1} (2021i -1) = (2020)(4041)...(2021^2 -1).$$ [u]Round 7[/u] [b]p19.[/b] A function $f (n)$ is defined as follows: $$f (n) = \begin{cases} \frac{n}{3} \,\,\, if \,\,\, n \equiv 0 (mod \, 3) \\ n^2 +4n -5 \,\,\,if \,\,\,n \equiv 1 (mod \, 3) \\ n^2 +n -2 \,\,\, if \,\,\,n \equiv 2 (mod \, 3) \end{cases}$$ Find the number of integer values of $n$ between $2$ and $1000$ inclusive such that $f ( f (... f (n))) = 1$ for some number of applications of $f (n)$. [b]p20.[/b] In the diagram below, the larger circle with diameter $AW$ has radius $16$. $ABCD$ and $WXY Z$ are rhombi where $\angle B AD = \angle XWZ = 60^o$ and $AC = CY = YW$. $M$ is the midpoint of minor arc $AW$, as shown. Let $I$ be the center of the circle with diameter $OM$. Circles with center $P$ and $G$ are tangent to lines $AD$ and $WZ$, respectively, and also tangent to the circle with center $I$ . Given that $IP \perp AD$ and $IG \perp WZ$, the area of $\vartriangle PIG$ can be written as $a +b\sqrt{c}$ where $a$, $b$, and $c$ are positive integers and $c$ is not divisible by the square of a prime. Find $a +b +c$. [b]p21.[/b] In a list of increasing consecutive positive integers, the first item is divisible by $1$, the second item is divisible by $4$, the third item is divisible by $7$, and this pattern increases up to the seventh item being divisible by $19$. Find the remainder when the least possible value of the first item in the list is divided by $100$. [u]Round 8[/u] [b]p22.[/b] Let the answer to Problem $24$ be $C$. Jacob never drinks more than $C$ cups of coffee in a day. He always drinks a positive integer number of cups. The probability that he drinks $C +1-X$ cups is $X$ times the probability he drinks $C$ cups of coffee for any positive number $X$ from $1$ to $C$ inclusive. Find the expected number of cups of coffee he drinks. [b]p23.[/b] Let the answer to Problem $22$ be $A$. Three lines are drawn intersecting the interior of a triangle with side lengths $26$, $28$, and $30$ such that each line is parallel and a distance A away from a respective side. The perimeter of the triangle formed by the three new lines can be expressed as $\frac{a}{b}$ for relatively prime integers $a$ and $b$. Find $a +b$. [b]p24.[/b] Let the answer to Problem $23$ be $B$. Given that $ab-c = bc-a = ca-b$ and $a^2+b^2+c^2 = B +2$, find the sum of all possible values of $|a +b +c|$. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h3166489p28814241]here [/url] and 9-12 [url=https://artofproblemsolving.com/community/c3h3166500p28814367]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Arrange arbitrarily $1,2,\ldots ,25$ on a circumference. We consider all $25$ sums obtained by adding $5$ consecutive numbers. If the number of distinct residues of those sums modulo $5$ is $d$ $(0\le d\le 5)$,find all possible values of $d$.

Three legendary knights are fighting against a multiheaded dragon. Whenever the first knight attacks, he cuts off half of the current number of heads plus one more. Whenever the second knight attacks, he cuts off one third of the current number of heads plus two more. Whenever the third knight attacks, he cuts off one fourth of the current number of heads plus three more. They repeatedly attack in an arbitrary order so that at each step an integer number of heads is being cut off. If all the knights cannot attack as the number of heads would become non-integer, the dragon eats them. Will the knights be able to cut off all the dragon’s heads if it has $41!$ heads? Alexey Zaslavsky

On an infinite “squared” sheet six squares are shaded as in the diagram. On some squares there are pieces. It is possible to transform the positions of the pieces according to the following rule: if the neighbour squares to the right and above a given piece are free, it is possible to remove this piece and put pieces on these free squares. The goal is to have all the shaded squares free of pieces. Is it possible to reach this goal if (a) In the initial position there are $6$ pieces and they are placed on the $6$ shaded squares? (b) In the initial position there is only one piece, located in the bottom left shaded square? [img]https://cdn.artofproblemsolving.com/attachments/2/d/0d5cbc159125e2a84edd6ac6aca5206bf8d83b.png[/img] (M Kontsevich, Moscow)

Nonnegative real numbers $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{n}$ are such that $p_{1}+\cdots+p_{n}=q_{1}+\cdots+q_{n}$ Among all the matrices with nonnegative entries having $p_i$ as sum of the $i$-th row's entries and $q_j$ as sum of the $j$-th column's entries, find the maximum sum of the entries on the main diagonal.

Is it possible to paint the cells of a $5\times 5$ board in $4$ colors so that the cells standing at the intersection of any two rows and any two columns were painted in at least $ 3$ colors?

Let $m$ and $n$ be odd positive integers. Each square of an $m$ by $n$ board is coloured red or blue. A row is said to be red-dominated if there are more red squares than blue squares in the row. A column is said to be blue-dominated if there are more blue squares than red squares in the column. Determine the maximum possible value of the number of red-dominated rows plus the number of blue-dominated columns. Express your answer in terms of $m$ and $n$.

Let $n\ge 2$ be an integer. Consider a $2n+1\times 2n+1$ board. All cells lying both in an even row and an even column have been removed. The remaining cells form a [i]labyrinth[/i]. An ant takes a walk in the labyrinth. A single step of the ant consists of moving to a neighbouring cell. Determine, in terms of $n$, the smallest possible number of steps so that every cell of the labirynth is visited by the ant. The ant chooses the start cell. The start cell and the end cell are considered visited. Each cell could be visited several times. The picture depicts the labyrinth for $n=3$ and possible steps of the ant in its four locations.

Let $x_1, x_2 \ldots , x_5$ be real numbers. Find the least positive integer $n$ with the following property: if some $n$ distinct sums of the form $x_p+x_q+x_r$ (with $1\le p<q<r\le 5$) are equal to $0$, then $x_1=x_2=\cdots=x_5=0$.

$N$ in natural. There are natural numbers from $N^3$ to $N^3+N$ on the board. $a$ numbers was colored in red, $b$ numbers was colored in blue. Sum of red numbers in divisible by sum of blue numbers. Prove, that $b|a$

Given three colors and a rectangle m × n dice unit, we want to color each segment constituting one side of a square drive with one of three colors so that each square unit have two sides of one color and two sides another color. How many colorings we have?