Peter buys a lottery ticket on which he enters an $n$-digit number, none of the digits being $0$. On the draw date, the lottery administrators will reveal an $n\times n$ table, each cell containing one of the digits from $1$ to $9$. A ticket wins a prize if it does not match any row or column of this table, read in either direction. Peter wants to bribe the administrators to reveal the digits on some cells chosen by Peter, so that Peter can guarantee to have a winning ticket. What is the minimum number of digits Peter has to know?

A set $S$ has $7$ elements. Several $3$-elements subsets of $S$ are listed, such that any $2$ listed subsets have exactly $1$ common element. What is the maximum number of subsets that can be listed?

$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 ?

In each square of a garden shaped like a $2022 \times 2022$ board, there is initially a tree of height $0$. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn: [list] [*] The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller. [*] The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter. [/list] We say that a tree is [i]majestic[/i] if its height is at least $10^6$. Determine the largest $K$ such that the gardener can ensure there are eventually $K$ majestic trees on the board, no matter how the lumberjack plays.

Let $S$ be a nonempty set of points of the plane. We say that $S$ determines the distance $d > 0$ if there are two points $A, B$ in $S$ such that $AB = d$. Assuming that $S$ does not contain $8$ collinear points and that it determines not more than $91$ distances, prove that $S$ has less than $2004$ elements.

Anton the ant takes a walk along the vertices of a cube. He starts at a vertex and stops when it reaches this point again. Between two vertices it moves over an edge, a side face diagonal or a space diagonal. During the rout it visits each of the other vertices exactly [i]once [/i] and nowhere intersects its road already traveled. (a) Show that Anton walks along at least one edge. (b) Show that Anton walks along at least two edges.

A blackboard contains $2018$ instances of the digit $1$ separated by spaces. Georg and his mother play a game where they take turns filling in one of the spaces between the digits with either a $+$ or a $\times$. Georg begins, and the game ends when all spaces have been filled. Georg wins if the value of the expression is even, and his mother wins if it is odd. Which player may prepare a strategy which secures him/her victory?

What is the greatest amount of rooks that can be placed on an $n\times n$ board, such that each rooks beats an even number of rooks? A rook is considered to beat another rook, if they lie on one vertical or one horizontal line and no rooks are between them. [I]Proposed by D. Karpov[/i]

Three schools $A, B$ and $C$ , each with five players denoted $a_{i}, b_{i}, c_{i}$ respectively, take part in a chess tournament. The tournament is held following the rules: (i) Players from each school have matches in order with respect to indices, and defeated players are eliminated; the first match is between $a_{1}$ and $b_{1}$. (ii) If $y_{j}\in Y$ defeats $x_{i}\in X$ , his next opponent should be from the remaining school if not all of its players are eliminated; otherwise his next oponent is $x_{i+1}$ . The tournament is over when two schools are completely eliminated. (iii) When $x_{i}$ wins a match, its school wins $10^{i-1}$ points. At the end of the tournament, schools $A, B, C$ scored $P_{A}, P_{B}, P_{C}$ respectively. Find the remainder of the number of possible triples $(P_{A}, P_{B}, P_{C})$ upon division by $8.$

$2019$ coins are on the table. Two students play the following game making alternating moves. The first player can in one move take the odd number of coins from $ 1$ to $99$, the second player in one move can take an even number of coins from $2$ to $100$. The player who can not make a move is lost. Who has the winning strategy in this game?

In each of the squares of an $n \times n$ board, with $n \ge 3$, a positive integer is written in such a way that the absolute value of the difference of the numbers written in any two neighboring cells is less than or equal to $2$ (two neighboring cells are those that have a common side). a) Show a $5 \times 5$ board on which $15$ integers have been written different following the indicated rule. b) Find, as a function of $n$, the maximum number of different numbers that can have the board of $n \times n$ squares.

Find the number ot 6-tuples $(x_1, x_2,...,x_6)$, where $x_i=0,1 or 2$ and $x_1+x_2+...+x_6$ is even

Marisa has two identical cubical dice labeled with the numbers $\{1, 2, 3, 4, 5, 6\}$. However, the two dice are not fair, meaning that they can land on each face with different probability. Marisa rolls the two dice and calculates their sum. Given that the sum is $2$ with probability $0.04$, and $12$ with probability $0.01$, the maximum possible probability of the sum being $7$ is $p$. Compute $\lfloor 100p \rfloor$.

We consider all partitions of a positive integer n into a sum of (nonnegative integer) exponents of $2$ (i.e. $1$, $2$, $4$, $8$ , $ . . .$ ). A number in the sum is allowed to repeat an arbitrary number of times (e.g. $7 = 2 + 2 + 1 + 1 + 1$) and two partitions differing only in the order of summands are considered to be equal (e.g. $8 = 4 + 2 + 1 + 1$ and $8 = 1 + 2 + 1 + 4$ are regarded to be the same partition). Let $E(n)$ be the number of partitions in which an even number of exponents appear an odd number of times and $O(n)$ the number of partitions in which an odd number of exponents appear an odd number of times. For example, for $n = 5$ partitions counted in $E(n)$ are $5 = 4 + 1$ and $5 = 2 + 1 + 1 + 1$, whereas partitions counted in O(n) are $5 = 2 + 2 + 1$ and $5 = 1 + 1 + 1 + 1 + 1$, hence $E(5) = O(5) = 2$. Find $E(n) - O(n)$ as a function of $n$.

Given is a floor plan composed of $n$ unit squares. Albert and Berta want to cover this floor with tiles, with all tiles having the shape of a $1\times 2$ domino or a $T$-tetromino. Albert only has tiles from one color, while Berta has two-color dominoes and tetrominoes available in four colors. Albert can use this floor plan in $a$ ways to cover tiles, Berta in $ b$ ways. Assuming that $a \ne 0$, determine the ratio $b/a$.

A square is divided into $n^4$ fields like a chessboard. $n^3$ game pieces are placed on these squares placed, on each at most one. There are the same number of stones in each row. Besides, the whole arrangement symmetrical to one of the diagonals of the square; this diagonal is called $d$. Prove that: a) If $n$ is odd, then there is at least one stone on $d$. b) If $n$ is even, then there is an arrangement of the type described, in which there is no stone on $d$.

[b]p1.[/b] Let $ABCD$ be a square with side length $1$, $\Gamma_1$ be a circle centered at $B$ with radius 1, $\Gamma_2$ be a circle centered at $D$ with radius $1$, $E$ be a point on the segment $AB$ with $|AE| = x$ $(0 < x \le 1)$, and $\Gamma_3$ be a circle centered at $A$ with radius $|AE|$. $\Gamma_3$ intersects $\Gamma_1$ and $\Gamma_2$ inside the square at $G$ and $F$, respectively. Let region $I$ be the region bounded by the segment $GC$ and the minor arc $GC$ of $\Gamma_1$, and region II be the region bounded by the segment $FG$ and the minor arc $FG$ of $\Gamma_3$, as illustrated in the graph below. Let $r(x)$ be the ratio of the area of region I to the area of region II. (i) Find $r(1)$. Justify your answer. (ii) Find an explicit formula of $r(x)$ in terms of $x$ $(0 < x \le 1)$. Justify your answer. [img]https://cdn.artofproblemsolving.com/attachments/e/0/bd2379a1390a578d78dc7e9f4cde756d5f4723.png[/img] [b]p2.[/b] We call a [i]party [/i] any set of people $V$ . If $v_1 \in V$ knows $v_2 \in V$ in a party, we always assume that $v_2$ also knows $v_1$. For a person $v \in V$ in some party, the degree of v, denoted by $deg\,\,(v)$, is the number of people $v$ knows in the party. (i) Suppose that a party has four people with $V = \{v_1, v_2, v_3, v_4\}$, and that $deg\,\,(v_i) = i$ for $i = 1, 2, 3$ show that $deg\,\,(v_4) = 2$. (ii) Suppose that a party is attended by $n = 4k$ ($k \ge 1$) people with $V = \{v_1, v_2, ..., v_{4k}\}$, and that $deg\,\,(v_i) = i$ for $1 \le i \le n - 1$. Show that $deg\,\,(v_n) = \frac{n}{2}$ . [b]p3.[/b] Let $a, b$ be two real number parameters and consider the function $f(x) =\frac{b + \sin x}{a + \cos x}$. (i) Find an example of $(a, b)$ such that $f(x) \ge 2$ for all real numbers $x$. Justify your answer. (ii) If $a > 1$ and the range of the function $f(x)$ (when x varies over the set of all real numbers) is $[-1, 1]$, find the values of $a$ and $b$. Justify your answer. [b]p4.[/b] Let $f$ be the function that assigns to each positive multiple $x$ of $8$ the number of ways in which $x$ can be written as a difference of squares of positive odd integers. (For example, $f(8) = 1$, because $8 = 3^2 -1^2$, and $f(24) = 2$, because $24 = 5^2 - 1^2 = 7^2 - 5^2$.) (a) Determine with proof the value of $f(120)$. (b) Determine with proof the smallest value $x$ for which $f(x) = 8$. (c) Show that the range of this function is the set of all positive integers. [b]p5.[/b] Consider the binomial coefficients $C_{n,r} ={n \choose r}= \frac{n!}{r!(n - r)!}$, for $n \ge 2$. Prove that $C_{n,r}$ are even, for all $1 \le r \le n - 1$, if and only if $n = 2^m$, for some counting number $m$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are: (i) A player cannot choose a number that has been chosen by either player on any previous turn. (ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn. (iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game. The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies. [i]Proposed by Finland[/i]

Let $G = (V, E)$ be a finite simple graph on $n$ vertices. An edge $e$ of $G$ is called a [i]bottleneck[/i] if one can partition $V$ into two disjoint sets $A$ and $B$ such that [list] [*] at most $100$ edges of $G$ have one endpoint in $A$ and one endpoint in $B$; and [*] the edge $e$ is one such edge (meaning the edge $e$ also has one endpoint in $A$ and one endpoint in $B$). [/list] Prove that at most $100n$ edges of $G$ are bottlenecks. [i]Proposed by Yang Liu[/i]

Numbers from $1$ to $49$ are randomly placed in a $35 \times 35$ table such that number $i$ is used exactly $i$ times. Some random cells of the table are removed so that table falls apart into several connected (by sides) polygons. Among them, the one with the largest area is chosen (if there are several of the same largest areas, a random one of them is chosen). What is the largest number of cells that can be removed that guarantees that in the chosen polygon there is a number which occurs at least $15$ times?

Let $n$ be a natural number and $C$ a non-negative real number. Determine the number of sequences of real numbers $1, x_{2}, ..., x_{n}, 1$ such that the absolute value of the difference between any two adjacent terms is equal to $C$.

The [i]base factorial[/i] number system is a unique representation for positive integers where the $n$th digit from the right ranges from $0$ to $n$ inclusive and has place value $n!$ for all $n \ge 1.$ For instance, $71$ can be written in base factorial as $2321_{!} = 2 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + 1 \cdot 1!.$ Let $S_{!}(n)$ be the base $10$ sum of the digits of $n$ when $n$ is written in base factorial. Compute $\sum_{n=1}^{700} S_{!}(n)$ (expressed in base $10$).

On a chessboard with dimensions 1000 by 1000 and squares colored in the usual way in white and black, there is a set A consisting of 1000 squares. Any two fields of set A can be connected by a sequence of fields of set A so that subsequent fields have a common side. Prove that there are at least 250 white fields in set A.

Let $ A,B$ denote two distinct fixed points in space. Let $ X, P$ denote variable points (in space), while $ K,N, n$ denote positive integers. Call $ (X,K,N,P)$ admissible if \[ (N \minus{} K) \cdot PA \plus{} K \cdot PB \geq N \cdot PX.\] Call $ (X,K,N)$ admissible if $ (X,K,N,P)$ is admissible for all choices of $ P.$ Call $ (X,N)$ admissible if $ (X,K,N)$ is admissible for some choice of $ K$ in the interval $ 0 < K < N.$ Finally, call $ X$ admissible if $ (X,N)$ is admissible for some choice of $ N, (N > 1).$ Determine: [b](a)[/b] the set of admissible $ X;$ [b](b)[/b] the set of $ X$ for which $ (X, 1989)$ is admissible but not $ (X, n), n < 1989.$

In a mathematical competition, in which $6$ problems were posed to the participants, every two of these problems were solved by more than $\frac 25$ of the contestants. Moreover, no contestant solved all the $6$ problems. Show that there are at least $2$ contestants who solved exactly $5$ problems each. [i]Radu Gologan and Dan Schwartz[/i]