Let $A_1, A_2, ..., A_k$ be $5$-element subsets of set $\{1, 2, ..., 23\}$ such that, for all $1 \le i < j \le k$ set $A_i \cap A_j$ has at most three elements. Show that $k \le 2018$.

Let $p$ be a permutation of the set $S_n = \{1, 2, \dots, n\}$. An element $j \in S_n$ is called a fixed point of $p$ if $p(j) = j$. Let $f_n$ be the number of permutations having no fixed points, and $g_n$ be the number with exactly one fixed point. Show that $|f_n - g_n| = 1$.

I have an $n \times n$ sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let $b(n)$ be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants $c$ and $d$ such that \[ \dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn \] for all $n > 0$.

Let $n\geq 3$ a positive integer. In each cell of a $n\times n$ chessboard one must write $1$ or $2$ in such a way the sum of all written numbers in each $2\times 3$ and $3\times 2$ sub-chessboard is even. How many different ways can the chessboard be completed?

How many of the base-ten numerals for the positive integers less than or equal to 2017 contain the digit 0? $\textbf{(A)} \text{ 469} \qquad \textbf{(B)} \text{ 471} \qquad \textbf{(C)} \text{ 475} \qquad \textbf{(D)} \text{ 478} \qquad \textbf{(E)} \text{ 481}$

The four bottom corners of a cube are colored red, green, blue, and purple. How many ways are there to color the top four corners of the cube so that every face has four different colored corners? Prove that your answer is correct.

On the coast of a circular island there are eight different cities. Initially there are no routes between the cities. We have to construct five straight two-way routes, which do not intersect, so that from each city there are one or two routes. In how many ways can this happen?

For each positive integer $ n$, let $ f(n)$ denote the number of ways of representing $ n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $ f(4) \equal{} 4$, because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1. Prove that, for any integer $ n \geq 3$ we have $ 2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}$.

A positive integer is called [i]vaivém[/i] when, considering its representation in base ten, the first digit from left to right is greater than the second, the second is less than the third, the third is bigger than the fourth and so on alternating bigger and smaller until the last digit. For example, $2021$ is [i]vaivém[/i], as $2 > 0$ and $0 < 2$ and $2 > 1$. The number $2023$ is not [i]vaivém[/i], as $2 > 0$ and $0 < 2$, but $2$ is not greater than $3$. a) How many [i]vaivém[/i] positive integers are there from $2000$ to $2100$? b) What is the largest [i]vaivém[/i] number without repeating digits? c) How many distinct $7$-digit numbers formed by all the digits $1, 2, 3, 4, 5, 6$ and $7$ are [i]vaivém[/i]?

Let $\mathcal{A}_n$ be the set of $n$-tuples $x = (x_1, ..., x_n)$ with $x_i \in \{0, 1, 2\}$. A triple $x, y, z$ of distinct elements of $\mathcal{A}_n$ is called [i]good[/i] if there is some $i$ such that $\{x_i, y_i, z_i\} = \{0, 1, 2\}$. A subset $A$ of $\mathcal{A}_n$ is called [i]good[/i] if every three distinct elements of $A$ form a good triple. Prove that every good subset of $\mathcal{A}_n$ has at most $2(\frac{3}{2})^n$ elements.

How many integers between $100$ and $999$, inclusive, have the property that some permutation of its digits is a multiple of $11$ between $100$ and $999$? For example, both $121$ and $211$ have this property. $ \textbf{(A) }226\qquad \textbf{(B) } 243 \qquad \textbf{(C) } 270 \qquad \textbf{(D) }469\qquad \textbf{(E) } 486$

Let $p$ be an odd prime. Determine the number of nonempty subsets from $\{1, 2, \dots, p - 1\}$ for which the sum of its elements is divisible by $p$.

How many three-digit numbers $\underline{abc}$ have the property that when it is added to $\underline{cba}$, the number obtained by reversing its digits, the result is a palindrome? (Note that $\underline{cba}$ is not necessarily a three-digit number since before reversing, $c$ may be equal to $0$.)

On the circle with center 0 and radius 1 the point $A_0$ is fixed and points $A_1, A_2, \ldots, A_{999}, A_{1000}$ are distributed in such a way that the angle $\angle A_00A_k = k$ (in radians). Cut the circle at points $A_0, A_1, \ldots, A_{1000}.$ How many arcs with different lengths are obtained. ?

Evariste has drawn twelve triangles as follows, so that two consecutive triangles share exactly one edge. [img]https://cdn.artofproblemsolving.com/attachments/6/2/50377e7ad5fb1c40e36725e43c7eeb1e3c2849.png[/img] Sophie colors every triangle side in red, green or blue. Among the $3^{24}$ possible colorings, how many have the property that every triangle has one edge of each color?

Consider a $m\times n$ rectangular board consisting of $mn$ unit squares. Two of its unit squares are called [i]adjacent[/i] if they have a common edge, and a [i]path[/i] is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called [i]non-intersecting[/i] if they don't share any common squares. Each unit square of the rectangular board can be colored black or white. We speak of a [i]coloring[/i] of the board if all its $mn$ unit squares are colored. Let $N$ be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let $M$ be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge. Prove that $N^{2}\geq M\cdot 2^{mn}$.

Supppose five points in a plane are situated so that no two of the straight lines joining them are parallel, perpendicular, or coincident. From each point perpendiculars are drawn to all the lines joining the other four points. Determine the maxium number of intersections that these perpendiculars can have.

Each square in a $5 \times 5$ grid is either filled or empty, and has up to eight adjacent neighboring squares, where neighboring squares share either a side or a corner. The grid is transformed by the following rules: [list] [*] Any filled square with two or three filled neighbors remains filled. [*] Any empty square with exactly three filled neighbors becomes a filled square. [*] All other squares remain empty or become empty. [/list] A sample transformation is shown in the figure below. [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,gray+opacity(0.5),invisible); } ds((1,1)); ds((2,1)); ds((3,1)); ds((1,3)); for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } label("Initial", (2.5,-1)); draw((6,2.5)--(8,2.5),Arrow); ds((10,2)); ds((11,1)); ds((11,0)); for (int i = 0; i <= 5; ++i) { draw((9,i)--(14,i)); draw((i+9,0)--(i+9,5)); } label("Transformed", (11.5,-1)); [/asy] Suppose the $5 \times 5$ grid has a border of empty squares surrounding a $3 \times 3$ subgrid. How many initial configurations will lead to a transformed grid consisting of a single filled square in the center after a single transformation? (Rotations and reflections of the same configuration are considered different.) [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,gray+opacity(0.5),invisible); } for (int i = 1; i < 4; ++ i) { for (int j = 1; j < 4; ++j) { label("?",(i + 0.5, j + 0.5)); } } for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } label("Initial", (2.5,-1)); draw((6,2.5)--(8,2.5),Arrow); ds((11,2)); for (int i = 0; i <= 5; ++i) { draw((9,i)--(14,i)); draw((i+9,0)--(i+9,5)); } label("Transformed", (11.5,-1)); [/asy] $$\textbf{(A) 14}~\textbf{(B) 18}~\textbf{(C) 22}~\textbf{(D) 26}~\textbf{(E) 30}$$

How many binary strings of length $10$ do not contain the substrings $101$ or $010$?

Five towns are connected by a system of roads. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).

$n$ men and one woman are in the meeting room with $n+1$ chairs, each of them having their own seat. Show that the following two number of cases are equal. (1) Number of cases to choose one man to get out of the room, and make the left $n-1$ men to sit to each other's chair. (2) Number of cases to make $n+1$ people to sit to each other's chair.

In a game, a player can level up to 16 levels. In each level, the player can upgrade an ability spending that level on it. There are three kinds of abilities, however, one ability can not be upgraded before level 6 for the first time. And that special ability can not be upgraded before level 11. Other abilities can be upgraded at any level, any times (possibly 0), but the special ability needs to be upgraded exactly twice. In how many ways can these abilities be upgraded?

Let $ n$ and $ k$ be positive integers with $ k \geq n$ and $ k \minus{} n$ an even number. Let $ 2n$ lamps labelled $ 1$, $ 2$, ..., $ 2n$ be given, each of which can be either [i]on[/i] or [i]off[/i]. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on). Let $ N$ be the number of such sequences consisting of $ k$ steps and resulting in the state where lamps $ 1$ through $ n$ are all on, and lamps $ n \plus{} 1$ through $ 2n$ are all off. Let $ M$ be number of such sequences consisting of $ k$ steps, resulting in the state where lamps $ 1$ through $ n$ are all on, and lamps $ n \plus{} 1$ through $ 2n$ are all off, but where none of the lamps $ n \plus{} 1$ through $ 2n$ is ever switched on. Determine $ \frac {N}{M}$. [i]Author: Bruno Le Floch and Ilia Smilga, France[/i]

We call a table of size $n \times n$ self-describing if each cell of the table contains the total number of even numbers in its row and column other than itself. How many self-describing tables of size a) $3 \times 3$ exist? b) $4 \times 4$ exist? c) $5 \times 5$ exist? Two tables are different if they differ in at least one cell.

2500 chess kings have to be placed on a $100 \times 100$ chessboard so that [b](i)[/b] no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex); [b](ii)[/b] each row and each column contains exactly 25 kings. Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.) [i]Proposed by Sergei Berlov, Russia[/i]