We wish to tile a strip of $n$ $1$-inch by $1$-inch squares. We can use dominos which are made up of two tiles that cover two adjacent squares, or $1$-inch square tiles which cover one square. We may cover each square with one or two tiles and a tile can be above or below a domino on a square, but no part of a domino can be placed on any part of a different domino. We do not distinguish whether a domino is above or below a tile on a given square. Let $t(n)$ denote the number of ways the strip can be tiled according to the above rules. Thus for example, $t(1)=2$ and $t(2)=8$. Find a recurrence relation for $t(n)$, and use it to compute $t(6)$.

Duarte wants to draw a square whose side's length is $2009$ cm and which is divided in $2009\times2009$ squares whose side's length is $1$ cm and whose sides are parallel to the original square's one, without taking the pencil out of the paper. Starting on one of the vertex of the giant square, what is the length of the shortest line that allows him to make this drawing?

Graph $G$ has $n\geq 2$ vertices. Find the largest $m$ such that one of the following is true for always: 1. There exists a cycle with $k\geq m$ vertices. 2. There exists an independent set with $m$ vertices.

We are given a 7x7 square board. In each square, one of the diagonals is traced, and then one of the two formed triangles is colored blue. What is the largest area a continuous blue component can have? (Note: continuous blue component means a set of blue triangles connected via their edges, passing through corners is not permitted)

Peter has a deck of $1001$ cards, and with a blue pen he has written the numbers $1,2,\ldots,1001$ on the cards (one number on each card). He replaced cards in a circle so that blue numbers were on the bottom side of the card. Then, for each card $C$, he took $500$ consecutive cards following $C$ (clockwise order), and denoted by $f(C)$ the number of blue numbers written on those $500$ cards that are greater than the blue number written on $C$ itself. After all, he wrote this $f(C)$ number on the top side of the card $C$ with a red pen. Prove that Peter's friend Basil, who sees all the red numbers on these cards, can determine the blue number on each card.

[b]T[/b]wo ordered pairs $(a,b)$ and $(c,d)$, where $a,b,c,d$ are real numbers, form a basis of the coordinate plane if $ad \neq bc$. Determine the number of ordered quadruples $(a,b,c)$ of integers between $1$ and $3$ inclusive for which $(a,b)$ and $(c,d)$ form a basis for the coordinate plane.

We make groups of numbers. Each group consists of [i]five[/i] distinct numbers. A number may occur in multiple groups. For any two groups, there are exactly four numbers that occur in both groups. (a) Determine whether it is possible to make $2015$ groups. (b) If all groups together must contain exactly [i]six [/i] distinct numbers, what is the greatest number of groups that you can make? (c) If all groups together must contain exactly [i]seven [/i] distinct numbers, what is the greatest number of groups that you can make?

Find all four-digit natural numbers $\overline{xyzw}$ with the property that their sum plus the sum of their digits equals $2003$.

For any positive integer $m$,show that there exist integers $a,b$ satisfying $\left | a \right |\leq m$, $ \left | b \right |\leq m$, $0< a+b\sqrt{2}\leq \frac{1+\sqrt{2}}{m+2}$

There are $n{}$ currencies in a country, numbered from 1 to $n{}.$ In each currency, only non-negative integers are possible amounts of money. A person can have only one currency at any time. A person can exchange all the money he has from currency $i{}$ to currency $j{}$ at the rate of $\alpha_{ij}$ which is a positive real number. If he had $d{}$ units of currency $i{}$ he instead receives $\alpha_{ij}d$ units of currency $j{}$ while this number is rounded to the nearest integer; a number of the form $t-1/2$ is rounded to $t{}$ for any integer $t{}.$ It is known that $\alpha_{ij}\alpha_{jk}=\alpha_{ik}$ and $\alpha_{ii}=1$ for every $i,j,k.$ Can there be a person who can get rich indefinitely? [i]Proposed by I. Bogdanov[/i]

The $14 \times 14$ chessboard squares are colored in pattern, as shown in the picture. Can you choose seven fields blacks and seven white squares of this chessboard in such a way, that there is exactly one selected field in each row and column? Justify your answer. [img]https://cdn.artofproblemsolving.com/attachments/e/4/e8ba46030cd0f0e0511f1f9e723e5bd29e9975.png[/img]

$A$ graph $G$ arises from $G_{1}$ and $G_{2}$ by pasting them along $S$ if $G$ has induced subgraphs $G_{1}$, $G_{2}$ with $G=G_{1}\cup G_{2}$ and $S$ is such that $S=G_{1}\cap G_{2}.$ A is graph is called [i]chordal[/i] if it can be constructed recursively by pasting along complete subgraphs, starting from complete subgraphs. For a graph $G(V,E)$ define its Hilbert polynomial $H_{G}(x)$ to be $H_{G}(x)=1+Vx+Ex^2+c(K_{3})x^3+c(K_{4})x^4+\ldots+c(K_{w(G)})x^{w(G)},$ where $c(K_{i})$ is the number of $i$-cliques in $G$ and $w(G)$ is the clique number of $G$. Prove that $H_{G}(-1)=0$ if and only if $G$ is chordal or a tree.

A rectangle $ABCD$ is given. On the side $AB$, $n$ different points are chosen strictly between $A$ and $B$. Similarly, $m$ different points are chosen on the side $AD$. Lines are drawn from the points parallel to the sides. How many rectangles are formed in this way? (One possibility is shown in the figure.) [img]https://cdn.artofproblemsolving.com/attachments/0/1/dcf48e4ce318fdcb8c7088a34fac226e26e246.png[/img]

Proof that there exist constant $\lambda$, so that for any positive integer $m(\ge 2)$, and any lattice triangle $T$ in the Cartesian coordinate plane, if $T$ contains exactly one $m$-lattice point in its interior(not containing boundary), then $T$ has area $\le \lambda m^3$. PS. lattice triangles are triangles whose vertex are lattice points; $m$-lattice points are lattice points whose both coordinates are divisible by $m$.

Let $d_1, d_2, \ldots, d_n$ be given integers. Show that there exists a graph whose sequence of degrees is $d_1, d_2, \ldots, d_n$ and which contains an perfect matching if, and only if, there exists a graph whose sequence of degrees is $d_2, d_2, \ldots, d_n$ and a graph whose sequence of degrees is $d_1-1, d_2-1, \ldots, d_n-1$.

For any convex polygon $ W $ with area 1, let us denote by $ f(W) $ the area of the convex polygon whose vertices are the centers of all sides of the polygon $ W $. For each natural number $ n \geq 3 $, determine the lower limit and the upper limit of the set of numbers $ f(W) $ when $ W $ runs through the set of all $ n $ convex angles with area 1.

Let $ r$, $ s$ be two positive integers and $ P$ a 'chessboard' with $ r$ rows and $ s$ columns. Let $ M$ denote the maximum value of rooks placed on $ P$ such that no two of them attack each other. (a) Determine $ M$. (b) How many ways to place $ M$ rooks on $ P$ such that no two of them attack each other? [Note: In chess, a rook moves and attacks in a straight line, horizontally or vertically.]

[b]p1.[/b] The length of the side $AB$ of the trapezoid with bases $AD$ and $BC$ is equal to the sum of lengths $|AD|+|BC|$. Prove that bisectors of angles $A$ and $B$ do intersect at a point of the side $CD$. [b]p2.[/b] Polynomials $P(x) = x^4 + ax^3 + bx^2 + cx + 1$ and $Q(x) = x^4 + cx^3 + bx^2 + ax + 1$ have two common roots. Find these common roots of both polynomials. [b]p3.[/b] A girl has a box with $1000$ candies. Outside the box there is an infinite number of chocolates and muffins. A girl may replace: $\bullet$ two candies in the box with one chocolate bar, $\bullet$ two muffins in the box with one chocolate bar, $\bullet$ two chocolate bars in the box with one candy and one muffin, $\bullet$ one candy and one chocolate bar in the box with one muffin, $\bullet$ one muffin and one chocolate bar in the box with one candy. Is it possible that after some time it remains only one object in the box? [b]p4.[/b] There are $9$ straight lines drawn in the plane. Some of them are parallel some of them intersect each other. No three lines do intersect at one point. Is it possible to have exactly $17$ intersection points? [b]p5.[/b] It is known that $x$ is a real number such that $x+\frac{1}{x}$ is an integer. Prove that $x^n+\frac{1}{x^n}$ is an integer for any positive integer $n$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[u]Round 1 [/u] [b]p1.[/b] In the Hundred Acre Wood, all the animals are either knights or liars. Knights always tell the truth and liars always lie. One day in the Wood, Winnie-the-Pooh, a knight, decides to visit his friend Rabbit, also a noble knight. Upon arrival, Pooh finds his friend sitting at a round table with $5$ other guests. One-by-one, Pooh asks each person at the table how many of his two neighbors are knights. Surprisingly, he gets the same answer from everybody! "Oh bother!" proclaims Pooh. "I still don't have enough information to figure out how many knights are at this table." "But it's my birthday," adds one of the guests. "Yes, it's his birthday!" agrees his neighbor. Now Pooh can tell how many knights are at the table. Can you? [b]p2.[/b] Harry has an $8 \times 8$ board filled with the numbers $1$ and $-1$, and the sum of all $64$ numbers is $0$. A magical cut of this board is a way of cutting it into two pieces so that the sum of the numbers in each piece is also $0$. The pieces should not have any holes. Prove that Harry will always be able to find a magical cut of his board. (The picture shows an example of a proper cut.) [img]https://cdn.artofproblemsolving.com/attachments/4/b/98dec239cfc757e6f2996eef7876cbfd79d202.png[/img] [b]p3.[/b] Several girls participate in a tennis tournament in which each player plays each other player exactly once. At the end of the tournament, it turns out that each player has lost at least one of her games. Prove that it is possible to find three players $A$, $B$, and $C$ such that $A$ defeated $B$, $B$ defeated $C$, and $C$ defeated $A$. [b]p4.[/b] $120$ bands are participating in this year's Northwest Grunge Rock Festival, and they have $119$ fans in total. Each fan belongs to exactly one fan club. A fan club is called crowded if it has at least $15$ members. Every morning, all the members of one of the crowded fan clubs start arguing over who loves their favorite band the most. As a result of the fighting, each of them leaves the club to join another club, but no two of them join the same one. Is it true that, no matter how the clubs are originally arranged, all these arguments will eventually stop? [b]p5.[/b] In Infinite City, the streets form a grid of squares extending infinitely in all directions. Bonnie and Clyde have just robbed the Infinite City Bank, located at the busiest intersection downtown. Bonnie sets off heading north on her bike, and, $30$ seconds later, Clyde bikes after her in the same direction. They each bike at a constant speed of $1$ block per minute. In order to throw off any authorities, each of them must turn either left or right at every intersection. If they continue biking in this manner, will they ever be able to meet? [u]Round 2 [/u] [b]p6.[/b] In a certain herd of $33$ cows, each cow weighs a whole number of pounds. Farmer Dan notices that if he removes any one of the cows from the herd, it is possible to split the remaining $32$ cows into two groups of equal total weight, $16$ cows in each group. Show that all $33$ cows must have the same weight. [b]p7.[/b] Katniss is thinking of a positive integer less than $100$: call it $x$. Peeta is allowed to pick any two positive integers $N$ and $M$, both less than $100$, and Katniss will give him the greatest common divisor of $x+M$ and $N$ . Peeta can do this up to seven times, after which he must name Katniss' number $x$, or he will die. Can Peeta ensure his survival? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[b]p1.[/b] What is the maximal number of pieces of two shapes, [img]https://cdn.artofproblemsolving.com/attachments/a/5/6c567cf6a04b0aa9e998dbae3803b6eeb24a35.png[/img] and [img]https://cdn.artofproblemsolving.com/attachments/8/a/7a7754d0f2517c93c5bb931fb7b5ae8f5e3217.png[/img], that can be used to tile a $7\times 7$ square? [b]p2.[/b] Six shooters participate in a shooting competition. Every participant has $5$ shots. Each shot adds from $1$ to $10$ points to shooter’s score. Every person can score totally for all five shots from $5$ to $50$ points. Each participant gets $7$ points for at least one of his shots. The scores of all participants are different. We enumerate the shooters $1$ to $6$ according to their scores, the person with maximal score obtains number $1$, the next one obtains number $2$, the person with minimal score obtains number $6$. What score does obtain the participant number $3$? The total number of all obtained points is $264$. [b]p2.[/b] There are exactly $n$ students in a high school. Girls send messages to boys. The first girl sent messages to $5$ boys, the second to $7$ boys, the third to $6$ boys, the fourth to $8$ boys, the fifth to $7$ boys, the sixth to $9$ boys, the seventh to $8$, etc. The last girl sent messages to all the boys. Prove that $n$ is divisible by $3$. [b]p4.[/b] In what minimal number of triangles can one cut a $25 \times 12$ rectangle in such a way that one can tile by these triangles a $20 \times 15$ rectangle. [b]p5.[/b] There are $2014$ stones in a pile. Two players play the following game. First, player $A$ takes some number of stones (from $1$ to $30$) from the pile, then player B takes $1$ or $2$ stones, then player $A$ takes $2$ or $3$ stones, then player $B$ takes $3$ or $4$ stones, then player A takes $4$ or $5$ stones, etc. The player who gets the last stone is the winner. If no player gets the last stone (there is at least one stone in the pile but the next move is not allowed) then the game results in a draw. Who wins the game using the right strategy? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Ten gamblers start playing with the same amount of money. In turn they cast five dice. If the dice show a total of $n$, the player must pay each other player $\frac{1}{n}$ times the sum which that player owns at the moment. They throw and pay one after the other. At the $10^{\text{th}}$ round (i.e. after each player has cast the five die once), the dice shows a total of $12$ and after the payment it turns out that every player has exactly the same sum as he had in the beginning. Is it possible to determine the totals shown by the dice at the nine former rounds?

There is a football championship with $6$ teams involved, such that for any $2$ teams $A$ and $B$, $A$ plays with $B$ and $B$ plays with $A$ ($2$ such games are distinct). After every match, the winning teams gains $3$ points, the loosing team gains $0$ points and if there is a draw, both teams gain $1$ point each.\\ \\ In the end, the team standing on the last place has $12$ points and there are no $2$ teams that scored the same amount of points.\\ \\ For all the remaining teams, find their final scores and provide an example with the outcomes of all matches for at least one of the possible final situations. $\textit{(Andrei Bâra)}$

At each vertex of a $13$-sided polygon we write one of the numbers $1,2,3,…, 12,13$, without repeating. Then, on each side of the polygon we write the difference of the numbers of the vertices of its ends (the largest minus the smallest). For example, if two consecutive vertices of the polygon have the numbers $2$ and $11$, the number $9$ is written on the side they determine. a) Is it possible to number the vertices of the polygon so that only the numbers $3, 4$ and $5$ are written on the sides? b) Is it possible to number the vertices of the polygon so that only the numbers $3, 4$ and $6$ are written on the sides?

Given a set $I=\{(x_1,x_2,x_3,x_4)|x_i\in\{1,2,\cdots,11\}\}$. $A\subseteq I$, satisfying that for any $(x_1,x_2,x_3,x_4),(y_1,y_2,y_3,y_4)\in A$, there exists $i,j(1\leq i<j\leq4)$, $(x_i-x_j)(y_i-y_j)<0$. Find the maximum value of $|A|$.

On the plane there is a finite set of points $Z$ with the property that no two distances of the points of the set $Z$ are equal. We connect the points $ A, B $ belonging to $ Z $ if and only if $ A $ is the point closest to $ B $ or $ B $ is the point closest to $ A $. Prove that no point in the set $Z$ will be connected to more than five others.