Given a finite string $S$ of symbols $X$ and $O$, we denote $\Delta(s)$ as the number of$X'$s in $S$ minus the number of $O'$s (For example, $\Delta(XOOXOOX)=-1$). We call a string $S$ [b]balanced[/b] if every sub-string $T$ of (consecutive symbols) $S$ has the property $-1\leq \Delta(T)\leq 2.$ (Thus $XOOXOOX$ is not balanced, since it contains the sub-string $OOXOO$ whose $\Delta$ value is $-3.$ Find, with proof, the number of balanced strings of length $n$.

$200 \times 200$ square is colored in chess order. In one move we can take every $2 \times 3$ rectangle and change color of all its cells. Can we make all cells of square in same color ?

Let \(P\) be a convex polyhedron with the following properties: [b]1)[/b] \(P\) has exactly \(666\) edges. [b]2)[/b] The degrees of all vertices of \(P\) differ by at most \(1\). [b]3)[/b] There is an edge‐coloring of \(P\) with \(k\) colors such that for each color \(c\) and any two distinct vertices \(V_1,V_2\), there exists a path from \(V_1\) to \(V_2\) all of whose edges have color \(c\). Determine the largest positive integer \(k\) for which such a polyhedron \(P\) exists.

Daan distributes the numbers $1$ to $9$ over the nine squares of a $3\times 3$-table (each square receives exactly one number). Then, in each row, Daan circles the median number (the number that is neither the smallest nor the largest of the three). For example, if the numbers $8, 1$, and $2$ are in one row, he circles the number $2$. He does the same for each column and each of the two diagonals. If a number is already circled, he does not circle it again. He calls the result of this process a [i]median table[/i]. Above, you can see a median table that has $5$ circled numbers. (a) What is the [b]smallest [/b] possible number of circled numbers in a median table? [i] Prove that a smaller number is not possible and give an example in which a minimum number of numbers is circled.[/i] (b) What is the [b]largest [/b] possible number of circled numbers in a median table? [i]Prove that a larger number is not possible and give an example in which a maximum number of numbers is circled.[/i] [asy] unitsize (0.8 cm); int i; for (i = 0; i <= 3; ++i) { draw((0,i)--(3,i)); draw((i,0)--(i,3)); } draw(Circle((0.5,2.5),0.3)); draw(Circle((2.5,2.5),0.3)); draw(Circle((1.5,1.5),0.3)); draw(Circle((2.5,1.5),0.3)); draw(Circle((1.5,0.5),0.3)); label("$8$", (0.5,2.5)); label("$1$", (1.5,2.5)); label("$2$", (2.5,2.5)); label("$7$", (0.5,1.5)); label("$6$", (1.5,1.5)); label("$3$", (2.5,1.5)); label("$9$", (0.5,0.5)); label("$5$", (1.5,0.5)); label("$4$", (2.5,0.5)); [/asy]

Among the $5$-sided polygons, as many vertices as possible collinear , that is, belonging to a single line, is three, as shown below. What is the largest number of collinear vertices a $12$-sided polygon can have? [img]https://cdn.artofproblemsolving.com/attachments/1/1/53d419efa4fc4110730a857ae6988fc923eb13.png[/img] Attention: In addition to drawing a $12$-sided polygon with the maximum number of vertices collinear , remember to show that there is no other $12$-sided polygon with more vertices collinear than this one.

For any finite sets $X$ and $Y$ of positive integers, denote by $f_X(k)$ the $k^{\text{th}}$ smallest positive integer not in $X$, and let $$X*Y=X\cup \{ f_X(y):y\in Y\}.$$Let $A$ be a set of $a>0$ positive integers and let $B$ be a set of $b>0$ positive integers. Prove that if $A*B=B*A$, then $$\underbrace{A*(A*\cdots (A*(A*A))\cdots )}_{\text{ A appears $b$ times}}=\underbrace{B*(B*\cdots (B*(B*B))\cdots )}_{\text{ B appears $a$ times}}.$$ [i]Proposed by Alex Zhai, United States[/i]

I've come across a challenging graph theory problem. Roughly translated, it goes something like this: There are n lines drawn on a plane; no two lines are parallel to each other, and no three lines meet at a single point. Those lines would partition the plane down into many 'area's. Suppose we select one point from each area. Also, should two areas share a common side, we connect the two points belonging to the respective areas with a line. A graph consisted of points and lines will have been made. Find all possible 'n' that will make a hamiltonian circuit exist for the given graph

There is a fence that consists of $n$ planks arranged in a line. Each plank is painted with one of the available $100$ colors. Suppose that for any two distinct colors $i$ and $j$, there is a plank with color $i$ located to the left of a (not necessarily adjacent) plank with color $j$. Determine the minimum possible value of $n$.

The numbers from $1$ to $500$ are written on the board. Two players $A$ and $B$ erase alternately one number at a time, and $A$ deletes the first number. If the sum of the last two number on the board is divisible by $3$, $B$ wins, otherwise $A$ wins. Which player can lay out a strategy that ensures this player's victory?

Consider a checkered $3m\times 3m$ square, where $m$ is an integer greater than $1.$ A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F.$ The frog can hop from any cell to either the next cell to the right or the next cell upwards. Some cells can be [i]sticky[/i], and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called [i]blocking[/i] if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is [i] minimal[/i] if it does not contain a smaller blocking set.[list=a][*]Prove that there exists a minimal blocking set containing at least $3m^2-3m$ cells. [*]Prove that every minimal blocking set containing at most $3m^2$ cells.

For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

Nico wants to write the $100$ integers from $1$ to $100$ around a circle in some order and without repetition, such that they have the following property: when moving around the circle clockwise, the sum of the $100$ distances between each number and its next number is equal to $198$. Determine in how many ways the $100$ numbers can be ordered so that Nico achieves his goal. [b]Note:[/b] The distance between two numbers $a$ and $b$ is equal to the absolute value of their difference: $|a - b|$.

[b]p1.[/b] Find all solutions $a, b, c, d, e, f$ if it is known that they represent distinct digits and satisfy the following: $\begin{tabular}{ccccc} & a & b & c & a \\ + & & d & d & e \\ & & & d & e \\ \hline d & f & f & d & d \\ \end{tabular}$ [b]p2.[/b] Snowhite wrote on a piece of paper a whole number greater than $1$ and multiplied it by itself. She obtained a number, all digits of which are $1$: $n^2 = 111...111$ Does she know how to multiply? [b]p3.[/b] Two players play the following game on an $8\times 8$ chessboard. The first player can put a bishop on an arbitrary square. Then the second player can put another bishop on a free square that is not controlled by the first bishop. Then the first player can put a new bishop on a free square that is not controlled by the bishops on the board. Then the second player can do the same, etc. A player who cannot put a new bishop on the board loses the game. Who has a winning strategy? [b]p4.[/b] Four girls Marry, Jill, Ann and Susan participated in the concert. They sang songs. Every song was performed by three girls. Mary sang $8$ songs, more then anybody. Susan sang $5$ songs less then all other girls. How many songs were performed at the concert? [b]p5.[/b] Pinocchio has a $10\times 10$ table of numbers. He took the sums of the numbers in each row and each such sum was positive. Then he took the sum of the numbers in each columns and each such sum was negative. Can you trust Pinocchio's calculations? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A boy and a girl were sitting on a long bench. Then twenty more children one after another came to sit on the bench, each taking a place between already sitting children. Let us call a girl brave if she sat down between two boys, and let us call a boy brave if he sat down between two girls. It happened, that in the end all girls and boys were sitting in the alternating order. Is it possible to uniquely determine the number of brave children?

[b]p1.[/b] Find the largest k such that the equation $x^2 - 2x + k = 0$ has at least one real root. [b]p2.[/b] Indiana Jones needs to cross a flimsy rope bridge over a mile long gorge. It is so dark that it is impossible to cross the bridge without a flashlight. Furthermore, the bridge is so weak that it can only support the weight of two people. The party has only one flashlight, which has a weak beam so whenever two people cross, they are constrained to walk together, at the speed of the slower person. Indiana Jones can cross the bridge in $5$ minutes. His girlfriend can cross in $10$ minutes. His father needs $20$ minutes, and his father’s side kick needs $25$ minutes. They need to get everyone across safely in on hour to escape the bay guys. Can they do it? [b]p3.[/b] There are ten big bags with coins. Nine of them contain fare coins weighing $10$ g. each, and one contains counterfeit coins weighing $9$ g. each. By one weighing on a digital scale find the bag with counterfeit coins. [b]p4.[/b] Solve the equation: $\sqrt{x^2 + 4x + 4} = x^2 + 5x + 5$. [b]p5.[/b] (a) In the $x - y$ plane, analytically determine the length of the path $P \to A \to C \to B \to P$ around the circle $(x - 6)^2 + (y - 8)^2 = 25$ from the point $P(12, 16)$ to itself. [img]https://cdn.artofproblemsolving.com/attachments/f/b/24888b5b478fa6576a54d0424ce3d3c6be2855.png[/img] (b) Determine coordinates of the points $A$ and $B$. [b]p6.[/b] (a) Let $ABCD$ be a convex quadrilateral (it means that diagonals are inside the quadrilateral). Prove that $$Area\,\, (ABCD) \le \frac{|AB| \cdot |AD| + |BC| \cdot |CD|}{2}$$ (b) Let $ABCD$ be an arbitrary quadrilateral (not necessary convex). Prove the same inequality as in part (a). (c) For an arbitrary quadrilateral $ABCD$ prove that $Area\,\, (ABCD) \le \frac{|AB| \cdot |CD| + |BC| \cdot |AD|}{2}$ PS. You should use hide for answers.

Integer $n>2$ is given. Find the biggest integer $d$, for which holds, that from any set $S$ consisting of $n$ integers, we can find three different (but not necesarilly disjoint) nonempty subsets, such that sum of elements of each of them is divisible by $d$.

Two thieves stole an open chain with $2k$ white beads and $2m$ black beads. They want to share the loot equally, by cutting the chain to pieces in such a way that each one gets $k$ white beads and $m$ black beads. What is the minimal number of cuts that is always sufficient?

On the plane 100 lines are drawn, among which there are no parallel lines. From any five of these lines, some three pass through one point. Prove that there are two points such that each line contains at least of of them.

Joining $15^3 = 3375$ cubes of $1$ cm$^3$, bodies with a volume of $3375$ cm$^3$ can be built. Indicate how two bodies $A$ and $B$ are constructed with $3375$ cubes each and such that the lateral surface of $B$ is $10$ times the lateral surface of $A$.

Let $ p$ be an odd prime number and $ n$ a natural number. Then $ n$ is called $ p\minus{}partitionable$ if $ T\equal{}\{1,2,...,n \}$ can be partitioned into (disjoint) subsets $ T_1,T_2,...,T_p$ with equal sums of elements. For example, $ 6$ is $ 3$-partitionable since we can take $ T_1\equal{}\{ 1,6 \}$, $ T_2\equal{}\{ 2,5 \}$ and $ T_3\equal{}\{ 3,4 \}$. $ (a)$ Suppose that $ n$ is $ p$-partitionable. Prove that $ p$ divides $ n$ or $ n\plus{}1$. $ (b)$ Suppose that $ n$ is divisible by $ 2p$. Prove that $ n$ is $ p$-partitionable.

[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].

$A=1\cdot4\cdot7\cdots2014$.Find the last non-zero digit of $A$ if it is known that $A\equiv 1\mod3$.

Given $n \ge 4$ points in the plane such that any four of them are the vertices of a convex quadrilateral, prove that these points are the vertices of a convex polygon.

Let $n$ be a positive integer. In the $\mathit{philand}$ language, words are all finite sequences formed by the letters "$P$", "$H$" and "$I$". Philipe, who speaks only the $\mathit{philand}$ language, writes the word $PHIPHI\ldots PHI$ on a piece of paper, where $PHI$ is repeated $n$ times. He can do the following operations: • Erase two identical letters and write in their place two different letters from the original and from each other; (Ex: $PP\rightarrow HI$) • Erase two distinct letters and rewrite them changing the order in which they appear; (Ex: $PI\rightarrow IP$) • Erase two distinct letters and write the letter distinct from the two he erased. (Ex: $PH\rightarrow I$) Find the largest integer $C$ such that any Philandese word of up to $C$ letters can be written by Philip through the above operations. Note: Operations are taken on adjacent letters.

Let $X=(x_1,x_2,......,x_9)$ be a permutation of the set $\{1,2,\ldots,9\}$ and let $A$ be the set of all such $X$ . For any $X \in A$, denote $f(X)=x_1+2x_2+\cdots+9x_9$ and $ M=\{f(X)|X \in A \}$. Find $|M|$. ($|S|$ denotes number of members of the set $S$.)