Let $n$ be a positive integer. Find the number of sequences $a_1,a_2,...,a_k$ of different numbers from $\{ 1,2,3,...,n\}$ with the following property: for every number $a$ of the sequence (except the first one) there exists a previous number $b$ such that their difference is $1$ (so $a-b= \pm 1$)

Two concentric circles are divided by $n$ radii into $2n$ parts. Two parts are called neighbors (of each other) if they share either a common side or a common arc. Initially, there are $4n + 1$ frogs inside the parts. At each second, if there are three or more frogs inside one part, then three of the frogs in the part will jump to its neighbors, with one to each neighbor. Prove that in a finite amount of time, for any part either there are frogs in the part or there are frogs in each of its neighbors

In the cabinet 2004 telephones are located; each two of these telephones are connected by a cable, which is colored in one of four colors. From each color there is one cable at least. Can one always select several telephones in such a way that among their pairwise cable connections exactly 3 different colors occur?

Is it possible to fill an $n \times n$ table with the numbers $-1$, $0$ and $1$ so that all $2n$ sums in each column and each row are different? Solve the problem with a) $n = 5$; b) $n = 10$.

Let $S$ be the set of integers from $1$ to $13$ inclusive. A permutation of $S$ is a function $f : S \to S$ such that $f(x) \ne f(y)$ if $x \ne y$. For how many distinct permutations $f$ does there exists an $n $ such that $f^n(i) = 13 - i + 1$ for all $i$.

There are several dominoes on a board such that each domino occupies two adjacent cells and none of the dominoes are adjacent by side or vertex. The bottom left and top right cells of the board are free. A token starts at the bottom left cell and can move to a cell adjacent by side: one step to the right or upwards at each turn. Is it always possible to move from the bottom left to the top right cell without passing through dominoes if the size of the board is a) $100 \times 101$ cells and b) $100 \times 100$ cells? [i]Nikolay Chernyatiev[/i]

In the following, a rhombus is one with edge length $1$ and interior angles $60^o$ and $120^o$ . Now let $n$ be a natural number and $H$ a regular hexagon with edge length $n$, which is covered with rhombuses without overlapping has been. The rhombuses then appear in three different orientations. Prove that whatever the overlap looks exactly, each of these three orientations can be viewed at the same time.

Suppose $28$ objects are placed along a circle at equal distances. In how many ways can $3$ objects be chosen from among them so that no two of the three chosen objects are adjacent nor diametrically opposite?

There are $n$ coins aligned in a row. In each step, it is allowed to choose a coin with the tail up (but not one of the outermost markers), remove it and reverse the closest coin to the left and the closest coin to the right of it. Initially, all the coins have tails up. Prove that one can achieve the state with only two coins remaining if and only if $n-1$ is not divisible by $3$.

See all the problems from 5-th Kyiv math festival [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=506789#p506789]here[/url] All the positive integers from 1 till 1000 are written on the blackboard in some order and there is a collection of cards each containing 10 numbers. If there is a card with numbers $1\le a_1<a_2<\ldots<a_{10}\le1000$ in collection then it is allowed to arrange in increasing order the numbers at places $a_1, a_2, \ldots, a_{10},$ counting from left to right. What is the smallest amount of cards in the collection which enables us to arrange in increasing order all the numbers for any initial arrangement of them?

Let $n \geq 5$ be an integer. Consider $n$ squares with side lengths $1, 2, \dots , n$, respectively. The squares are arranged in the plane with their sides parallel to the $x$ and $y$ axes. Suppose that no two squares touch, except possibly at their vertices. Show that it is possible to arrange these squares in a way such that every square touches exactly two other squares.

From twenty different books on mathematics and physics, sets are made containing $5$ books on mathematics and $5$ books on physics each. How many math books should there be for the largest number of possible sets?

[u]Round 1[/u] [b]1.1[/b] If the sum of two non-zero integers is $28$, then find the largest possible ratio of these integers. [b]1.2[/b] If Tom rolls a eight-sided die where the numbers $1$ − $8$ are all on a side, let $\frac{m}{n}$ be the probability that the number is a factor of $16$ where $m, n$ are relatively prime positive integers. Find $m + n$. [b]1.3[/b] The average score of $35$ second graders on an IQ test was $180$ while the average score of $70$ adults was $90$. What was the total average IQ score of the adults and kids combined? [u]Round 2[/u] [b]2.1[/b] So far this year, Bob has gotten a $95$ and a 98 in Term $1$ and Term $2$. How many different pairs of Term $3$ and Term $4$ grades can Bob get such that he finishes with an average of $97$ for the whole year? Bob can only get integer grades between $0$ and $100$, inclusive. [b]2.2[/b] If a complement of an angle $M$ is one-third the measure of its supplement, then what would be the measure (in degrees) of the third angle of an isosceles triangle in which two of its angles were equal to the measure of angle $M$? [b]2.3[/b] The distinct symbols $\heartsuit, \diamondsuit, \clubsuit$ and $\spadesuit$ each correlate to one of $+, -, \times , \div$, not necessarily in that given order. Given that $$((((72 \,\, \,\, \diamondsuit \,\, \,\,36) \,\, \,\,\spadesuit \,\, \,\,0 ) \,\, \,\, \diamondsuit \,\, \,\, 32) \,\, \,\, \clubsuit \,\, \,\, 3)\,\, \,\, \heartsuit \,\, \,\, 2 = \,\, \,\, 6,$$ what is the value of $$(((((64 \,\, \,\, \spadesuit \,\, \,\, 8) \heartsuit \,\, \,\, 6) \,\, \,\, \spadesuit \,\, \,\, 5) \,\, \,\, \heartsuit \,\, \,\, 1) \,\, \,\, \clubsuit \,\, \,\, 7) \,\, \,\, \diamondsuit \,\, \,\, 1?$$ [u]Round 3[/u] [b]3.1[/b] How many ways can $5$ bunnies be chosen from $7$ male bunnies and $9$ female bunnies if a majority of female bunnies is required? All bunnies are distinct from each other. [b]3.2[/b] If the product of the LCM and GCD of two positive integers is $2021$, what is the product of the two positive integers? [b]3.3[/b] The month of April in ABMC-land is $50$ days long. In this month, on $44\%$ of the days it rained, and on $28\%$ of the days it was sunny. On half of the days it was sunny, it rained as well. The rest of the days were cloudy. How many days were cloudy in April in ABMC-land? [u]Round 4[/u] [b]4.1[/b] In how many ways can $4$ distinct dice be rolled such that a sum of $10$ is produced? [b]4.2[/b] If $p, q, r$ are positive integers such that $p^3\sqrt{q}r^2 = 50$, find the sum of all possible values of $pqr$. [b]4.3[/b] Given that numbers $a, b, c$ satisfy $a + b + c = 0$, $\frac{a}{b}+\frac{b}{c}+\frac{c}{a}= 10$, and $ab + bc + ac \ne 0$, compute the value of $\frac{-a^2 - b^2 - a^2}{ab + bc + ac}$. PS. You should use hide for answers. Rounds 5-8 have been posted [url=https://artofproblemsolving.com/community/c3h2826137p24988781]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Consider a triangular grid of equilateral triangles with unit sides. Assume that $\mathcal{P}$ is a non-self-intersecting polygon with perimeter 1399 and sides from the grid. Prove that $\mathcal{P}$ has either an internal or an external 120-degree angle. [i]Proposed by Seyed Hessam Firouzi[/i]

Let $n$ be a positive integer relatively prime to $6$. We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

Finite number of dwarfs excavates ore in the mine with infinite number of levels. Each day at the same time one dwarf from each level, inhabited with exactly $n = 2, 3, ... $ dwarfs, move $n-1$ levels down. Prove that after some moment there will be no more then one dwarf on each level.

In country there are two capitals ($A$ and $B$) and finite number of towns. Some towns (or town with one of capital) connected with roads (one-way). (between every two towns or capital and town there are arbitrary number of roads) such that exist at least one way from $A$ to $B$. Given, that any two ways from $A$ to $B$ have at least one common road. Prove, that exist one road, such that all ways from $A$ to $B$ pass through this road.

[u]Round 5[/u] [b]5.1.[/b] A triangle has lengths such that one side is $12$ less than the sum of the other two sides, the semi-perimeter of the triangle is $21$, and the largest and smallest sides have a difference of $2$. Find the area of this triangle. [b]5.2.[/b] A rhombus has side length $85$ and diagonals of integer lengths. What is the sum of all possible areas of the rhombus? [b]5.3.[/b] A drink from YAKSHAY’S SHAKE SHOP is served in a container that consists of a cup, shaped like an upside-down truncated cone, and a semi-spherical lid. The ratio of the radius of the bottom of the cup to the radius of the lid is $\frac23$ , the volume of the combined cup and lid is $296\pi$, and the height of the cup is half of the height of the entire drink container. What is the volume of the liquid in the cup if it is filled up to half of the height of the entire drink container? [u]Round 6[/u] [i]Each answer in the next set of three problems is required to solve a different problem within the same set. There is one correct solution to all three problems; however, you will receive points for any correct answer regardless whether other answers are correct.[/i] [b]6.1.[/b] Let the answer to problem $2$ be $b$. There are b people in a room, each of which is either a truth-teller or a liar. Person $1$ claims “Person $2$ is a liar,” Person $2$ claims “Person $3$ is a liar,” and so on until Person $b$ claims “Person $1$ is a liar.” How many people are truth-tellers? [b]6.2.[/b] Let the answer to problem $3$ be $c$. What is twice the area of a triangle with coordinates $(0, 0)$, $(c, 3)$ and $(7, c)$ ? [b]6.3.[/b] Let the answer to problem $ 1$ be $a$. Compute the smaller zero to the polynomial $x^2 - ax + 189$ which has $2$ integer roots. [u]Round 7[/u] [b]7.1. [/b]Sir Isaac Neeton is sitting under a kiwi tree when a kiwi falls on his head. He then discovers Neeton’s First Law of Kiwi Motion, which states: [i]Every minute, either $\left\lfloor \frac{1000}{d} \right\rfloor$ or $\left\lceil \frac{1000}{d} \right\rceil$ kiwis fall on Neeton’s head, where d is Neeton’s distance from the tree in centimeters.[/i] Over the next minute, $n$ kiwis fall on Neeton’s head. Let $S$ be the set of all possible values of Neeton’s distance from the tree. Let m and M be numbers such that $m < x < M$ for all elements $x$ in $S$. If the least possible value of $M - m$ is $\frac{2000}{16899}$ centimeters, what is the value of $n$? Note that $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$, and $\lceil x \rceil$ is the least integer greater than or equal to $x$. [b]7.2.[/b] Nithin is playing chess. If one queen is randomly placed on an $ 8 \times 8$ chessboard, what is the expected number of squares that will be attacked including the square that the queen is placed on? (A square is under attack if the queen can legally move there in one move, and a queen can legally move any number of squares diagonally, horizontally or vertically.) [b]7.3.[/b] Nithin is writing binary strings, where each character is either a $0$ or a $1$. How many binary strings of length $12$ can he write down such that $0000$ and $1111$ do not appear? [u]Round 8[/u] [b]8.[/b] What is the period of the fraction $1/2018$? (The period of a fraction is the length of the repeated portion of its decimal representation.) Your answer will be scored according to the following formula, where $X$ is the correct answer and $I$ is your input. $$max \left\{ 0, \left\lceil min \left\{13 - \frac{|I-X|}{0.1 |I|}, 13 - \frac{|I-X|}{0.1 |I-2X|} \right\} \right\rceil \right\}$$ PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2765571p24215461]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Arthur and Renate play a game on a $7 \times 7$ board. Arthur has two red tiles, initially placed on the cells in the bottom left and the upper right corner. Renate has two black tiles, initially placed on the cells in the bottom right and the upper left corner. In a move, a player can choose one of his two tiles and move them to a horizontally or vertically adjacent cell. The players alternate, with Arthur beginning. Arthur wins when both of his tiles are in horizontally or vertically adjacent cells after some number of moves. Can Renate prevent him from winning?

On the planet Automory, there are infinitely many inhabitants. Every Automorian loves exactly one Automorian and honours exactly one Automorian. Additionally, the following can be noticed: $\bullet$ each Automorian is loved by some Automorian; $\bullet$ if Automorian $A$ loves Automorian $B$, then also all Automorians honouring $A$ love $B$, $\bullet$if Automorian $A$ honours Automorian $B$, then also all Automorians loving $A$ honour $B$. Is it correct to claim that every Automorian honours and loves the same Automorian?

A hundred tourists arrive to a hotel at night. They know that in the hotel there are single rooms numbered as $1, 2, \ldots , n$, and among them $k{}$ (the tourists do not know which) are under repair, the other rooms are free. The tourists, one after another, check the rooms in any order (maybe different for different tourists), and the first room not under repair is taken by the tourist. The tourists don’t know whether a room is occupied until they check it. However it is forbidden to check an occupied room, and the tourists may coordinate their strategy beforehand to avoid this situation. For each $k{}$ find the smallest $n{}$ for which the tourists may select their rooms for sure. [i]Fyodor Ivlev[/i]

A Tetris Figure is every figure in the plane which consists of $4$ unit squares connected by their sides (and don’t overlap). Two Tetris Figures are the same if one can be rotated in the plane to become the other. a) Prove that there exist exactly $7$ different Tetris Figures. b) Is it possible to fill a $4 \times 7$ rectangle by using once each of the $7$ different Tetris Figures?

Divide each side of a triangle into $50$ equal parts, and each point of the division is joined to the opposite vertex by a segment. Calculate the number of intersection points determined by these segments. Clarification : the vertices of the original triangle are not considered points of intersection or division.

In how many ways can Eve fill each of the six squares of a $2 \times 3$ grid with either a $0$ or a $1$, such that Anne can then divide the grid into three congruent rectangles: one containing two $0$s, one containing two $1$s, and one containing a $0$ and a $1$? [i]Proposed by Michael Tang[/i]

During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of mathematicians, there was some moment when both were asleep simultaneously. Prove that, at some moment, three of them were sleeping simultaneously.