Consider constructing a tower of tables of numbers as follows. The first table is a one by one array containing the single number $1$. The second table is a two by two array formed underneath the first table and built as followed. For each entry, we look at the terms in the previous table that are directly up and to the left, up and to the right, and down and to the right of the entry, and we fill that entry with the sum of the numbers occurring there. If there happens to be no term at a particular location, it contributes a value of zero to the sum. [img]https://cdn.artofproblemsolving.com/attachments/d/8/ab56dddfc23e84348e205f031001d157cb8386.png[/img] The diagram above shows how we compute the second table from the first. The diagram below shows how to then compute the third table from the second. [img]https://cdn.artofproblemsolving.com/attachments/9/3/e1d8cf0fd0b71b970625a4fa97bc2912492a78.png[/img] For example, the entry in the middle row and middle column of the third table is equal the sum of the top left entry $1$, the top right entry $0$, and the bottom right entry $1$ from the second table, which is just $2$. Similarly, to compute the bottom rightmost entry in the third table, we look above it to the left and see that the entry in the second table’s bottom rightmost entry is $1$. There are no entries from the second table above it and to the right or below it and to the right, so we just take this entry in the third table to be $1$. We continue constructing the tower by making more tables from the previous tables. Find the entry in the third (from the bottom) row of the third (from the left) column of the tenth table in this resulting tower.

Let $n$ and $\ell$ be integers such that $n \ge 3$ and $1 < \ell < n$. A country has $n$ cities. Between any two cities $A$ and $B$, either there is no flight from $A$ to $B$ and also none from $B$ to $A$, or there is a unique [i]two-way trip[/i] between them. A [i]two-way trip[/i] is a flight from $A$ to $B$ and a flight from $B$ to $A$. There exist two cities such that the least possible number of flights required to travel from one of them to the other is $\ell$. Find the maximum number of two-way trips among the $n$ cities.

You have the following pieces: one $4\times 1$ rectangle, two $3\times 1$ rectangles, three $2\times 1$ rectangles, and four $1\times 1$ squares. Ariel and Bernardo play the following game on a board of $n\times n$, where $n$ is a number that Ariel chooses. In each move, Bernardo receives a piece $R$ from Ariel. Next, Bernardo analyzes if he can place $R$ on the board so that it has no points in common with any of the previously placed pieces (not even a common vertex). If there is such a location for $R$, Bernardo must choose one of them and place $R$. The game stops if it is impossible to place $R$ in the way explained, and Bernardo wins. Ariel wins only if all $10$ pieces have been placed on the board. a) Suppose Ariel gives Bernardo the pieces in decreasing order of size. What is the smallest n that guarantees Ariel victory? b) For the $n$ found in a), if Bernardo receives the pieces in increasing order of size, is Ariel guaranteed victory? Note: Each piece must cover exactly a number of unit squares on the board equal to its own size. The sides of the pieces can coincide with parts of the edge of the board.

For two positive integers $a$ and $b$, Ivica and Marica play the following game: Given two piles of $a$ and $b$ cookies, on each turn a player takes $2n$ cookies from one of the piles, of which he eats $n$ and puts $n$ of them on the other pile. Number $n$ is arbitrary in every move. Players take turns alternatively, with Ivica going first. The player who cannot make a move, loses. Assuming both players play perfectly, determine all pairs of numbers $(a, b)$ for which Marica has a winning strategy. Proposed by Petar Orlić

Find the smallest positive integer $ K$ such that every $ K$-element subset of $ \{1,2,...,50 \}$ contains two distinct elements $ a,b$ such that $ a\plus{}b$ divides $ ab$.

Given a $ n \times n$ grid board . How many ways can an $X$ and an $O$ be placed in such a way that they are not in adjacent squares?

In each vertex of a regular $n$-gon $A_1A_2...A_n$ there is a unique pawn. In each step it is allowed: 1. to move all pawns one step in the clockwise direction or 2. to swap the pawns at vertices $A_1$ and $A_2$. Prove that by a finite series of such steps it is possible to swap the pawns at vertices: a) $A_i$ and $A_{i+1}$ for any $ 1 \leq i < n$ while leaving all other pawns in their initial place b) $A_i$ and $A_j$ for any $ 1 \leq i < j \leq n$ leaving all other pawns in their initial place. [i]Proposed by Matija Bucic[/i]

On a $30\times 30$ board both rows $ 1$ to $30$ and columns are numbered, in addition, to each box is assigned the number $ij$, where the box is in row $i$ and column $j$. $N$ columns and $m$ rows are chosen, where $1 <n$ and $m <30$, and the cells that are simultaneously in any of the rows and in any of the selected columns are painted blue. They paint the others red . (a) Prove that the sum of the numbers in the blue boxes cannot be prime. (b) Can the sum of the numbers in the red cells be prime?

Find the number of ordered pairs $(A,B)$ such that the following conditions hold: $\bullet$ $A$ and $B$ are disjoint subsets of $\{1, 2, . . . , 50\}$. $\bullet$ $|A| = |B| = 25$ $\bullet$ The median of $B$ is $1$ more than the median of $A$.

There are 2000 cities in Graphland; some of them are connected by roads. For every city the number of roads going from it is counted. It is known that there are exactly two equal numbers among all the numbers obtained. What can be these numbers?

Consider a $25\times25$ chessboard with cells $C(i,j)$ for $1\le i,j\le25$. Find the smallest possible number $n$ of colors with which these cells can be colored subject to the following condition: For $1\le i<j\le25$ and for $1\le s<t\le25$, the three cells $C(i,s)$, $C(j,s)$, $C(j,t)$ carry at least two different colors. (Proposed by Gerhard Woeginger, Austria)

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies. [i]Proposed by Tejaswi Navilarekallu, India[/i]

Ward and Gabrielle are playing a game on a large sheet of paper. At the start of the game, there are $999$ ones on the sheet of paper. Ward and Gabrielle each take turns alternatingly, and Ward has the first turn. During their turn, a player must pick two numbers a and b on the sheet such that $gcd(a, b) = 1$, erase these numbers from the sheet, and write the number $a + b$ on the sheet. The first player who is not able to do so, loses. Determine which player can always win this game.

A board of $2n$ x $2n$ is colored chess style, a movement is the changing of colors of a $2$ x $2$ square. For what integers $n$ is possible to complete the board with one color using a finite number of movements?

Find the number of rectangles who have the following properties: a) Have for vertices, points $(x,y)$ of plane $Oxy$ with $x,y$ non negative integers and $ x \le 8$ , $y\le 8$ b) Have sides parallel to axes c) Have area $E$, with $30<E\le 40$

In the plane are given $n^2 + 1$ points, no three of which lie on a line. Each line segment connecting a pair of these points is colored by either red or blue. A [i]path [/i] of length $k$ is a sequence of $k$ segments where the end of each segment (except for the last one) is the beginning of the next one. A path is [i]simple [/i] if it does not intersect itself. Prove that there exists a monochromatic simple path of length $n$.

In a $2\times n$ array we have positive reals s.t. the sum of the numbers in each of the $n$ columns is $1$. Show that we can select a number in each column s.t. the sum of the selected numbers in each row is at most $\frac{n+1}4$.

Consider a grid of black and white squares with $3$ rows and $n$ columns. If there is a non-empty sequence of white squares $s_1$, $...$, $s_m$ such that $s_1$ is in the top row and $s_m$ is in the bottom row and consecutive squares in the sequence share an edge, then we say that the grid percolates. Let $T_n$ be the number of grids which do not percolate. There exists constants a, b such that $\frac{T_n}{ab^n}$ approaches $ 1$ as $n$ approaches $\infty$. Then $b$ is expressible as $(x+ \sqrt{y})/z$ for squarefree $y$ and coprime $x, z$. Find $x + y + z$.

Let $n\geq 3$ be an integer. Find the number of ways in which one can place the numbers $1, 2, 3, \ldots, n^2$ in the $n^2$ squares of a $n \times n$ chesboard, one on each, such that the numbers in each row and in each column are in arithmetic progression.

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

A team contest between $n$ participants is to be held. Each of these participants has exactly $k$ enemies among the other participants. (If $A$ is an enemy of $B$, then $B$ is an enemy of $A$. Nobody is his own enemy.) Assume that there are no three participants such that every two of them are enemies of each other. A [i]subversive enmity[/i] will mean an (un-ordered) pair of two participants which are enemies of each other and which belong to one and the same team. Show that one can divide the participants into two teams such that the number of subversive enmities is $\leq\frac{k\left(n-2k\right)}{2}$. (The teams need not be of equal size.) [i]Note.[/i] The actual source of this problem is: Glenn Hopkins, William Staton, [i]Maximal Bipartite Subgraphs[/i], Ars Combinatoria 13 (1982), pp. 223-226. It should be noticed that $\frac{k\left(n-2k\right)}{2}\leq\frac{n^{2}}{16}$, so the bound in the problem can be replaced by $\frac{n^{2}}{16}$ (which makes it weaker, but independent of $k$). darij

We have sheet of paper, divided on $100\times 100$ unit squares. In some squares we put rightangled isosceles triangles with leg =$1$ ( Every triangle lies in one unit square and is half of this square). Every unit grid segment( boundary too) is under one leg of triangle. Find maximal number of unit squares, that don`t contains triangles.

Find the smallest positive integer ${k}$ with the following properties $:{}{}{}{}{}$If each positive integer is arbitrarily colored red or blue${}{}{},$ there may be ${}{}{}{}9$ distinct red positive integers $x_1,x_2,\cdots ,x_9,$ satisfying $$x_1+x_2+\cdots +x_8<x_9,$$ or there are $10{}{}{}{}{}{}$ distinct blue positive integers $y_1,y_2,\cdots ,y_{10}$ satisfiying $${y_1+y_2+\cdots +y_9<y_{10}}.$$

All the numbers $1,2,...,9$ are written in the cells of a $3\times 3$ table (exactly one number in a cell) . Per move it is allowed to choose an arbitrary $2\times2$ square of the table and either decrease by $1$ or increase by $1$ all four numbers of the square. After some number of such moves all numbers of the table become equal to some number $a$. Find all possible values of $a$. I.Voronovich

In a rectangular array of nonnegative reals with $m$ rows and $n$ columns, each row and each column contains at least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements are the same. Prove that $m=n$.