There are $1000$ tickets with the numbers $000, 001, ... , 999$, and $100$ boxes with the numbers $00, 01, ... , 99$. You may put a ticket in a box, if you can obtain the box number from the ticket number by deleting one digit. Prove that: a) You can put all the tickets in $50$ boxes; b) $40$ boxes is not enough for that; c) it is impossible to use less than $50$ boxes. d) Consider $10000$ $4$-digit tickets, and you are allowed to delete two digits. Prove that $34$ boxes is enough for storing all the tickets. e) What is the minimal used boxes set in the case of $k$-digit tickets?

An $\textrm{alien}$ script has $n$ letters $b_1,b_2,\dots,b_n$. For some $k<n/2$ assume that all words formed by any of the $k$ letters (written left to right) are meaningful. These words are called $k$-words. Such a $k$-word is considered $\textbf{sacred}$ if: i. no letter appears twice and, ii. if a letter $b_i$ appears in the word then the letters $b_{i-1}$ and $b_{i+1}$ do not appear. (Here $b_{n+1} = b_1$ and $b_0 = b_n$). For example, if $n = 7$ and $k = 3$ then $b_1b_3b_6, b_3b_1b_6, b_2b_4b_6$ are sacred $3$-words. On the other hand $b_1b_7b_4, b_2b_2b_6$ are not sacred. What is the total number of sacred $k$-words? Use your formula to find the answer for $n = 10$ and $k = 4$.

A set $ X$ of positive integers is called [i]nice[/i] if for each pair $ a$, $ b\in X$ exactly one of the numbers $ a \plus{} b$ and $ |a \minus{} b|$ belongs to $ X$ (the numbers $ a$ and $ b$ may be equal). Determine the number of nice sets containing the number 2008. [i]Author: Fedor Petrov[/i]

Suppose that the vertices of a regular polygon of $20$ sides are coloured with three colours - red, blue and green - such that there are exactly three red vertices. Prove that there are three vertices $A,B,C$ of the polygon having the same colour such that triangle $ABC$ is isosceles.

The positive integers from 1 to $n^2$ are placed arbitrarily on the $n^2$ squares of a $n\times n$ chessboard. Two squares are called [i]adjacent[/i] if they have a common side. Show that two opposite corner squares can be joined by a path of $2n-1$ adjacent squares so that the sum of the numbers placed on them is at least $\left\lfloor \frac{n^3} 2 \right\rfloor + n^2 - n + 1$. [i]Radu Gologan[/i]

A plane is coloured into black and white squares in a chessboard pattern. Then, all the white squares are coloured red and blue such that any two initially white squares that share a corner are different colours. (One is red and the other is blue.) Let $\ell$ be a line not parallel to the sides of any squares. For every line segment $I$ that is parallel to $\ell$, we can count the difference between the length of its red and its blue areas. Prove that for every such line $\ell$ there exists a number $C$ that exceeds all those differences that we can calculate.

You are given a rectangular playing field of size $13 \times 2$ and any number of dominoes of sizes $2\times 1$ and $3\times 1$. The playing field should be seamless with such dominoes and without overlapping, with no domino protruding beyond the playing field may. Furthermore, all dominoes must be aligned in the same way, i. e. their long sides must be parallel to each other. How many such coverings are possible? (Walther Janous)

$n$ points are marked on a plane. Each pair of these points is connected with a segment. Each segment is painted one of four different colors. Find the largest possible value of $n$ such that one can paint the segments so that for any four points there are four segments (connecting these four points) of four different colors. (E. Barabanov)

On a circle there're $1000$ marked points, each colored in one of $k$ colors. It's known that among any $5$ pairwise intersecting segments, endpoints of which are $10$ distinct marked points, there're at least $3$ segments, each of which has its endpoints colored in different colors. Determine the smallest possible value of $k$ for which it's possible.

We have a $2\times n$ rectangle. We call each $1\times1$ square a room and we show the room in the $i^{th}$ row and $j^{th}$ column as $(i,j)$. There are some coins in some rooms of the rectangle. If there exist more than $1$ coin in each room, we can delete $2$ coins from it and add $1$ coin to its right adjacent room OR we can delete $2$ coins from it and add $1$ coin to its up adjacent room. Prove that there exists a finite configuration of allowable operations such that we can put a coin in the room $(1,n)$.

Compute the number of ways to color $3$ cells in a $3\times 3$ grid so that no two colored cells share an edge.

Let $n$ be a positive integer and let $(a_1,a_2,\ldots ,a_{2n})$ be a permutation of $1,2,\ldots ,2n$ such that the numbers $|a_{i+1}-a_i|$ are pairwise distinct for $i=1,\ldots ,2n-1$. Prove that $\{a_2,a_4,\ldots ,a_{2n}\}=\{1,2,\ldots ,n\}$ if and only if $a_1-a_{2n}=n$.

We are given a lattice and two pebbles $A$ and $B$ that are placed at two lattice points. At each step we are allowed to relocate one of the pebbles to another lattice point with the condition that the distance between pebbles is preserved. Is it possible after finite number of steps to switch positions of the pebbles?

Given $k$ parallel lines $l_1, \ldots, l_k$ and $n_i$ points on the line $l_i, i = 1, 2, \ldots, k$, find the maximum possible number of triangles with vertices at these points.

Let $m$ and $n$ be positive integers and $S$ be a subset with $(2^m-1)n+1$ elements of the set $\{1,2,3,\ldots, 2^mn\}$. Prove that $S$ contains $m+1$ distinct numbers $a_0,a_1,\ldots, a_m$ such that $a_{k-1} \mid a_{k}$ for all $k=1,2,\ldots, m$.

A $3 \times 3$ square is filled with numbers: $a, b, c, d, e, f, g, h, i$ in the following way: [img]https://cdn.artofproblemsolving.com/attachments/8/9/737c41e9d0dbfdc81be1b986b8e680290db55e.png[/img] Given that the square is magic (sums of the numbers in each row, column and each of two diagonals are the same), show that a) $2(a + c + g + i) = b + d + f + h + 4e$. (3) b) $2(a^3 + c^3 + g^3 + i^3) = b^3 + d^3 + f^3 + h^3 + 4e^3$. (3)

1. The transformation $ n \to 2n \minus{} 1$ or $ n \to 3n \minus{} 1$, where $ n$ is a positive integer, is called the 'change' of $ n$. Numbers $ a$ and $ b$ are called 'similar', if there exists such positive integer, that can be got by finite number of 'changes' from both $ a$ and $ b$. Find all positive integers 'similar' to $ 2005$ and less than $ 2005$.

Consider a chessboard $6 \times 6$, made up of $36$ single squares. We want to place $6$ chess rooks on this board, one rook on each square, so that there are no two rooks on the same row, nor two rooks on the same column. Note that, once the rooks have been placed in this way, we have that, for every square where a rook has not been placed, there is a rook in the same row as it and a rook in the same column as it. We will say that such rooks are in line with this square. For each of those $30$ houses without rooks, color it green if the two rooks aligned with that same house are the same distance from it, and color it yellow otherwise. For example, when we place the $6$ rooks ($T$) as below, we have: (a) Is it possible to place the rooks so that there are $30$ green squares? (b) Is it possible to place the rooks so that there are $30$ yellow squares? (c) Is it possible to place the rooks so that there are $15$ green and $15$ yellow squares?

Let $ n$ be a positive integer, and let $ \left( a_{1},\ a_{2} ,\ ...,\ a_{n}\right)$, $ \left( b_{1},\ b_{2},\ ...,\ b_{n}\right)$ and $ \left( c_{1},\ c_{2},\ ...,\ c_{n}\right)$ be three sequences of integers such that for any two distinct numbers $ i$ and $ j$ from the set $ \left\{ 1,2,...,n\right\}$, none of the seven integers $ a_{i}\minus{}a_{j}$; $ \left( b_{i}\plus{}c_{i}\right) \minus{}\left( b_{j}\plus{}c_{j}\right)$; $ b_{i}\minus{}b_{j}$; $ \left( c_{i}\plus{}a_{i}\right) \minus{}\left( c_{j}\plus{}a_{j}\right)$; $ c_{i}\minus{}c_{j}$; $ \left( a_{i}\plus{}b_{i}\right) \minus{}\left( a_{j}\plus{}b_{j}\right)$; $ \left( a_{i}\plus{}b_{i}\plus{}c_{i}\right) \minus{}\left( a_{j}\plus{}b_{j}\plus{}c_{j}\right)$ is divisible by $ n$. Prove that: [b]a)[/b] The number $ n$ is odd. [b]b)[/b] The number $ n$ is not divisible by $ 3$. [hide="Source of the problem"][i]Source of the problem:[/i] This question is a generalization of one direction of Theorem 2.1 in: Dean Alvis, Michael Kinyon, [i]Birkhoff's Theorem for Panstochastic Matrices[/i], American Mathematical Monthly, 1/2001 (Vol. 108), pp. 28-37. The original Theorem 2.1 is obtained if you require $ b_{i}\equal{}i$ and $ c_{i}\equal{}\minus{}i$ for all $ i$, and add in a converse stating that such sequences $ \left( a_{1},\ a_{2},\ ...,\ a_{n}\right)$, $ \left( b_{1},\ b_{2},\ ...,\ b_{n}\right)$ and $ \left( c_{1} ,\ c_{2},\ ...,\ c_{n}\right)$ indeed exist if $ n$ is odd and not divisible by $ 3$.[/hide]

In a $4\times 4$ grid of unit squares, five squares are chosen at random. The probability that no two chosen squares share a side is $\tfrac mn$ for positive relatively prime integers $m$ and $n$. Find $m+n$. [i]Proposed by David Altizio[/i]

[b]p1.[/b] A very large lucky number $N$ consists of eighty-eight $8$s in a row. Find the remainder when this number $N$ is divided by $6$. [b]p2.[/b] If $3$ chickens can lay $9$ eggs in $4$ days, how many chickens does it take to lay $180$ eggs in $ 8$ days? [b]p3.[/b] Find the ordered pair $(x, y)$ of real numbers satisfying the conditions $x > y$, $x+y = 10$, and $xy = -119$. [b]p4.[/b] There is pair of similar triangles. One triangle has side lengths $4, 6$, and $9$. The other triangle has side lengths $ 8$, $12$ and $x$. Find the sum of two possible values of $x$. [b]p5.[/b] If $x^2 +\frac{1}{x^2} = 3$, there are two possible values of $x +\frac{1}{x}$. What is the smaller of the two values? [b]p6.[/b] Three flavors (chocolate strawberry, vanilla) of ice cream are sold at Brian’s ice cream shop. Brian’s friend Zerg gets a coupon for $10$ free scoops of ice cream. If the coupon requires Zerg to choose an even number of scoops of each flavor of ice cream, how many ways can he choose his ice cream scoops? (For example, he could have $6$ scoops of vanilla and $4$ scoops of chocolate. The order in which Zerg eats the scoops does not matter.) [b]p7.[/b] David decides he wants to join the West African Drumming Ensemble, and thus he goes to the store and buys three large cylindrical drums. In order to ensure none of the drums drop on the way home, he ties a rope around all of the drums at their mid sections so that each drum is next to the other two. Suppose that each drum has a diameter of $3.5$ feet. David needs $m$ feet of rope. Given that $m = a\pi + b$, where $a$ and $b$ are rational numbers, find sum $a + b$. [b]p8.[/b] Segment $AB$ is the diameter of a semicircle of radius $24$. A beam of light is shot from a point $12\sqrt3$ from the center of the semicircle, and perpendicular to $AB$. How many times does it reflect off the semicircle before hitting $AB$ again? [b]p9.[/b] A cube is inscribed in a sphere of radius $ 8$. A smaller sphere is inscribed in the same sphere such that it is externally tangent to one face of the cube and internally tangent to the larger sphere. The maximum value of the ratio of the volume of the smaller sphere to the volume of the larger sphere can be written in the form $\frac{a-\sqrt{b}}{36}$ , where $a$ and $b$ are positive integers. Find the product $ab$. [b]p10.[/b] How many ordered pairs $(x, y)$ of integers are there such that $2xy + x + y = 52$? [b]p11.[/b] Three musketeers looted a caravan and walked off with a chest full of coins. During the night, the first musketeer divided the coins into three equal piles, with one coin left over. He threw it into the ocean and took one of the piles for himself, then went back to sleep. The second musketeer woke up an hour later. He divided the remaining coins into three equal piles, and threw out the one coin that was left over. He took one of the piles and went back to sleep. The third musketeer woke up and divided the remaining coins into three equal piles, threw out the extra coin, and took one pile for himself. The next morning, the three musketeers gathered around to divide the coins into three equal piles. Strangely enough, they had one coin left over this time as well. What is the minimum number of coins that were originally in the chest? [b]p12.[/b] The diagram shows a rectangle that has been divided into ten squares of different sizes. The smallest square is $2 \times 2$ (marked with *). What is the area of the rectangle (which looks rather like a square itself)? [img]https://cdn.artofproblemsolving.com/attachments/4/a/7b8ebc1a9e3808096539154f0107f3e23d168b.png[/img] [b]p13.[/b] Let $A = (3, 2)$, $B = (0, 1)$, and $P$ be on the line $x + y = 0$. What is the minimum possible value of $AP + BP$? [b]p14.[/b] Mr. Mustafa the number man got a $6 \times x$ rectangular chess board for his birthday. Because he was bored, he wrote the numbers $1$ to $6x$ starting in the upper left corner and moving across row by row (so the number $x + 1$ is in the $2$nd row, $1$st column). Then, he wrote the same numbers starting in the upper left corner and moving down each column (so the number $7$ appears in the $1$st row, $2$nd column). He then added up the two numbers in each of the cells and found that some of the sums were repeated. Given that $x$ is less than or equal to $100$, how many possibilities are there for $x$? [b]p15.[/b] Six congruent equilateral triangles are arranged in the plane so that every triangle shares at least one whole edge with some other triangle. Find the number of distinct arrangements. (Two arrangements are considered the same if one can be rotated and/or reflected onto another.) PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

The checker moves from the lower left corner of the board $100 \times 100$ to the right top corner, moving at each step one cell to the right or one cell up. Let $a$ be the number of paths in which exactly $70$ steps the checker take under the diagonal going from the lower left corner to the upper right corner, and $b$ is the number of paths in which such steps are exactly $110$. What is more: $a$ or $b$?

[b]p1.[/b] Solve: $INK + INK + INK + INK + INK + INK = PEN$ ($INK$ and $PEN$ are $3$-digit numbers, and different letters stand for different digits). [b]p2. [/b]Two people play a game. They put $3$ piles of matches on the table: the first one contains $1$ match, the second one $3$ matches, and the third one $4$ matches. Then they take turns making moves. In a move, a player may take any nonzero number of matches FROM ONE PILE. The player who takes the last match from the table loses the game. a) The player who makes the first move can win the game. What is the winning first move? b) How can he win? (Describe his strategy.) [b]p3.[/b] The planet Naboo is under attack by the imperial forces. Three rebellion camps are located at the vertices of a triangle. The roads connecting the camps are along the sides of the triangle. The length of the first road is less than or equal to $20$ miles, the length of the second road is less than or equal to $30$ miles, and the length of the third road is less than or equal to $45$ miles. The Rebels have to cover the area of this triangle with a defensive field. What is the maximal area that they may need to cover? [b]p4.[/b] Money in Wonderland comes in $\$5$ and $\$7$ bills. What is the smallest amount of money you need to buy a slice of pizza that costs $\$ 1$ and get back your change in full? (The pizza man has plenty of $\$5$ and $\$7$ bills.) For example, having $\$7$ won't do, since the pizza man can only give you $\$5$ back. [b]p5.[/b] (a) Put $5$ points on the plane so that each $3$ of them are vertices of an isosceles triangle (i.e., a triangle with two equal sides), and no three points lie on the same line. (b) Do the same with $6$ points. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be a positive integer. $2n+1$ tokens are in a row, each being black or white. A token is said to be [i]balanced[/i] if the number of white tokens on its left plus the number of black tokens on its right is $n$. Determine whether the number of [i]balanced[/i] tokens is even or odd.