$ T$ is a subset of $ {1,2,...,n}$ which has this property : for all distinct $ i,j \in T$ , $ 2j$ is not divisible by $ i$ . Prove that : $ |T| \leq \frac {4}{9}n + \log_2 n + 2$

Emily draws six dots on a piece of paper such that no three lie on a straight line, then draws a line segment connecting each pair of dots. She then colors five of these segments red. Her coloring is said to be $\emph{red-triangle-free}$ if for every set of three points from her six drawn points there exists an uncolored segment connecting two of the three points. In how many ways can Emily color her drawing such that it is red-triangle-free?

Moor and nine friends are seated around a circular table. Moor starts out holding a bottle, and whoever holds the bottle passes it to the person on his left or right with equal probability until everyone has held the bottle. Compute the expected distance between Moor and the last person to receive the bottle, where distance is the fewest number of times the bottle needs to be passed in order to go back to Moor.

Let $n \geq 2$ be an integer. Consider an $n\times n$ chessboard with the usual chessboard colouring. A move consists of choosing a $1\times 1$ square and switching the colour of all squares in its row and column (including the chosen square itself). For which $n$ is it possible to get a monochrome chessboard after a finite sequence of moves?

A certain Oxford professor, assigned to espionage cryptography services British, role played by Dirk Bogarde in a film, recruits his proposing small attention exercises, such as mentally reading a word the other way around. Frequently he does it with his own name: $SEBASTIAN$, what will there be to read $NAITSABES$. He wonders if there is any movement of the plane or of space that transforms one of these words in the other, just as they appear written. And if it had been called $AVITO$, like a certain Unamuno character? Give a reasoned explanation for each answer.

Homer Grog has written the numbers $1, 3, 4, 5, 7, 9, 11, 13, 15,17$, one number on each note. He arranges the bills in a circle and tries to get the largest sum $S$ of the numbers of three consecutive bills to be the least possible. What is the smallest value $S$ can assume?

Let $n$ be an even integer greater than $2$. On the vertices of a regular polygon with n sides we can place red or blue chips. Two players, $A$ and $B$, play alternating turns of the next mode: each player, on their turn, chooses two vertices that have no tiles and places on one of them a red chip and in the other a blue chip. The goal of $A$ is to get three vertices consecutive with tiles of the same color. $B$'s goal is to prevent this from happening. To the beginning of the game there are no tiles in any of the vertices. Show that regardless of who starts to play, Player $B$ can always achieve his goal.

Lines parallel to the sides of an equilateral triangle are drawn so that they cut each of the sides into $10$ equal segments and the triangle into $100$ congruent triangles. Each of these $100$ triangles is called a “cell”. Also lines parallel to each of the sides of the original triangle are drawn through each of the vertices of the original triangle. The cells between any two adjacent parallel lines form a “stripe”. What is the maximum number of cells that can be chosen so that no two chosen cells belong to one stripe? (R Zhenodarov)

Ahmad and Salem play the following game. Ahmad writes two integers (not necessarily different) on a board. Salem writes their sum and product. Ahmad does the same thing: he writes the sum and product of the two numbers which Salem has just written. They continue in this manner, not stopping unless the two players write the same two numbers one after the other (for then they are stuck!). The order of the two numbers which each player writes is not important. Thus if Ahmad starts by writing $3$ and $-2$, the first five moves (or steps) are as shown: (a) Step 1 (Ahmad) $3$ and $-2$ (b) Step 2 (Salem) $1$ and $-6$ (c) Step 3 (Ahmad) $-5$ and $-6$ (d) Step 4 (Salem) $-11$ and $30$ (e) Step 5 (Ahmad) $19$ and $-330$ (i) Describe all pairs of numbers that Ahmad could write, and ensure that Salem must write the same numbers, and so the game stops at step 2. (ii) What pair of integers should Ahmad write so that the game finishes at step 4? (iii) Describe all pairs of integers which Ahmad could write at step 1, so that the game will finish after finitely many steps. (iv) Ahmad and Salem decide to change the game. The first player writes three numbers on the board, $u, v$ and $w$. The second player then writes the three numbers $u + v + w,uv + vw + wu$ and $uvw$, and they proceed as before, taking turns, and using this new rule describing how to work out the next three numbers. If Ahmad goes first, determine all collections of three numbers which he can write down, ensuring that Salem has to write the same three numbers at the next step.

A collection of $2n$ letters contains $2$ each of $n$ different letters. The collection is partitioned into $n$ pairs, each pair containing $2$ letters, which may be the same or different. Denote the number of distinct partitions by $u_n$. (Partitions differing in the order of the pairs in the partition or in the order of the two letters in the pairs are not considered distinct.) Prove that $u_{n+1}=(n+1)u_n - \frac{n(n-1)}{2} u_{n-2}.$ [i]Similar Problem :[/i] A pack of $2n$ cards contains $n$ pairs of $2$ identical cards. It is shuffled and $2$ cards are dealt to each of $n$ different players. Let $p_n$ be the probability that every one of the $n$ players is dealt two identical cards. Prove that $\frac{1}{p_{n+1}}=\frac{n+1}{p_n} + \frac{n(n-1)}{2p_{n-2}}.$

Michael is trying to drive a bus from his home, $(0,0)$, to school, located at $(6,6)$. There are horizontal and vertical roads at every line $x=0,1,\ldots,6$ and $y=0,1,\ldots,6$. The city has placed $6$ roadblocks on lattice point intersections $(x,y)$ with $0\leq x,y \leq 6$. Michael notices that the only path he can take that only goes up and to the right is directly up from $(0,0)$ to $(0,6)$, and then right to $(6,6)$. How many sets of $6$ locations could the city have blocked?

Players $ A,B$ alternately move a knight on a $ 1994\times 1994$ chessboard. Player $ A$ makes only horizontal moves, i.e. such that the knight is moved to a neighboring row, while $ B$ makes only vertical moves. Initally player $ A$ places the knight to an arbitrary square and makes the first move. The knight cannot be moved to a square that was already visited during the game. A player who cannot make a move loses. Prove that player $ A$ has a winning strategy.

Georg writes the numbers from $1$ to $15$ on different pieces of paper. He attempts to sort these pieces of paper into two stacks so that none of the stacks contains two numbers whose sum is a square number.Prove that this is impossible. (The square numbers are the numbers $0 = 0^2$, $1 = 1^2$, $4 = 2^2$, $9 = 3^2$ etc.)

We are given $n$ points in space. Some pairs of these points are connected by line segments so that the number of segments equals $[n^2/4],$ and a connected triangle exists. Prove that any point from which the maximal number of segments starts is a vertex of a connected triangle.

[b]p1[/b]. Consider the following four statements referring to themselves: 1. At least one of these statements is true. 2. At least two of these statements are false. 3. At least three of these statements are true. 4. All four of these statements are false. Determine which statements are true and which are false. Justify your answer. [b]p2.[/b] Let $f(x) = a_{2017}x^{2017} + a_{2016}x^{2016} + ... + a_1x + a_0$ where the coefficients $a_0, a_1, ... , a_{2017}$ have not yet been determined. Alice and Bob play the following game: $\bullet$ Alice and Bob alternate choosing nonzero integer values for the coefficients, with Alice going first. (For example, Alice’s first move could be to set $a_{18}$ to $-3$.) $\bullet$ After all of the coefficients have been chosen: - If f(x) has an integer root then Alice wins. - If f(x) does not have an integer root then Bob wins. Determine which player has a winning strategy and what the strategy is. Make sure to justify your answer. [b]p3.[/b] Suppose that a circle can be inscribed in a polygon $P$ with $2017$ equal sides. Prove that $P$ is a regular polygon; that is, all angles of $P$ are also equal. [b]p4.[/b] A $3 \times 3 \times 3$ cube of cheese is sliced into twenty-seven $ 1 \times 1 \times 1$ blocks. A mouse starts anywhere on the outside and eats one of the $1\times 1\times 1$ cubes. He then moves to an adjacent cube (in any direction), eats that cube, and continues until he has eaten all $27$ cubes. (Two cubes are considered adjacent if they share a face.) Prove that no matter what strategy the mouse uses, he cannot eat the middle cube last. [Note: One should neglect gravity – intermediate configurations don’t collapse.] p5. Suppose that a constant $c > 0$ and an infinite sequence of real numbers $x_0, x_1, x_2, ...$ satisfy $x_{k+1} =\frac{x_k + 1}{1 - cx_k}$ for all $k \ge 0$. Prove that the sequence $x_0, x_1, x_2, ....$ contains infinitely many positive terms and also contains infinitely many negative terms. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time: [list] [*] Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged. [/list] Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. [i]Proposed by Adrian Beker, Croatia[/i]

Determine the largest integer $k(n)$ with the following properties: There exist $k(n)$ different subsets of a given set with $n$ elements such that each two of them have a non-empty intersection.

Given a $2\times 5$ rectangle is divided into unit squares as figure below. [img]https://cdn.artofproblemsolving.com/attachments/6/a/9432bbf40f6d89ee1cbb507e1a3f65326c6a13.png[/img] How many ways are there to write the letters $H, A, N, O, I$ into all of the unit squares, such that two neighbor squares (the squares with a common side) do not contain the same letters? (Each unit square is filled by only one letter and each letter may be used several times or not used as well.)

We are given $2001$ balloons and a positive integer $k$. Each balloon has been blown up to a certain size (not necessarily the same for each balloon). In each step it is allowed to choose at most $k$ balloons and equalize their sizes to their arithmetic mean. Determine the smallest value of $k$ such that, whatever the initial sizes are, it is possible to make all the balloons have equal size after a finite number of steps.

What is the minimum $n$ so that grid $nxn$ can be covered with equal number of 2x2 squares and angle triminoes (2x2 without one square)

$7$ boys each went to a shop $3$ times. Each pair met at the shop. Show that $3$ must have been in the shop at the same time.

Consider the following table where initially all squares contain zeros: $ \begin{tabular}{ | l | c | r| } \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{tabular} $ To change the table, the following operation is allowed: a $2 \times 2$ square formed by adjacent squares is chosen, and a unit is added to all its numbers. Complete the following table, knowing that it was obtained by a sequence of permitted operations $ \begin{tabular}{ | l | c | r| } \hline 14 & & \\ \hline 19 & 36 & \\ \hline & 16 & \\ \hline \end{tabular} $

The table size $8 \times 8$ contains the numbers $1,2,...,8$ in each amount as much as you want provided that two numbers that are adjacent vertically, horizontally, diagonally are relative primes. Prove that some number appears in the table at least $12$ times. [i](PP-nine)[/i]

If the polynomials $f(x)$ and $g(x)$ are written on a blackboard then we can also write down the polynomials $f(x)\pm g(x), f(x)g(x), f(g(x))$ and $cf(x)$, where $c$ is an arbitrary real constant. The polynomials $x^3 - 3x^2 + 5$ and $x^2 - 4x$ are written on the blackboard. Can we write a nonzero polynomial of the form $x^n - 1$ after a finite number of steps? Justify your answer.

Let $ n > 1, n \in \mathbb{Z}$ and $ B \equal{}\{1,2,\ldots, 2^n\}.$ A subset $ A$ of $ B$ is called weird if it contains exactly one of the distinct elements $ x,y \in B$ such that the sum of $ x$ and $ y$ is a power of two. How many weird subsets does $ B$ have?