In a convex $n$-gon, several diagonals are drawn. Among these diagonals, a diagonal is called [i]good[/i] if it intersects exactly one other diagonal drawn (in the interior of the $n$-gon). Find the maximum number of good diagonals.

All cells of the checkered plane are painted in $5$ colors so that in any figure of the species [img]https://cdn.artofproblemsolving.com/attachments/f/f/49b8d6db20a7e9cca7420e4b51112656e37e81.png[/img] all colors are different. Prove that in any figure of the species $ \begin{tabular}{ | l | c| c | c | r| } \hline & & & &\\ \hline \end{tabular}$, all colors are different..

Let $n$ and $k$ be two integers with $n>k\geqslant 1$. There are $2n+1$ students standing in a circle. Each student $S$ has $2k$ [i]neighbors[/i] - namely, the $k$ students closest to $S$ on the left, and the $k$ students closest to $S$ on the right. Suppose that $n+1$ of the students are girls, and the other $n$ are boys. Prove that there is a girl with at least $k$ girls among her neighbors. [i]Proposed by Gurgen Asatryan, Armenia[/i]

A $7\times 7$ square is cut into pieces following types: [img]https://cdn.artofproblemsolving.com/attachments/e/d/458b252c719946062b655340cbe8415d1bdaf9.png[/img] Show that exactly one of the pieces is of type (b). [img]https://cdn.artofproblemsolving.com/attachments/4/9/f3dd0e13fed9838969335c82f5fe866edc83e8.png[/img]

A planar polygon $A_1A_2A_3 . . .A_{n-1}A_n$ ($n > 4$) is made of rigid rods that are connected by hinges. Is it possible to bend the polygon (at hinges only!) into a triangle?

Let $n$ be a positive integer, which gives remainder $4$ of dividing by $8$. Numbers $1 = k_1 < k_2 < ... < k_m = n$ are all positive diivisors of $n$. Show that if $i \in \{ 1, 2, ..., m - 1 \}$ isn't divisible by $3$, then $k_{i + 1} \le 2k_{i}$.

Let $n$ be a fixed positive integer. Let $$A=\begin{bmatrix} a_{11} & a_{12} & \cdots &a_{1n} \\ a_{21} & a_{22} & \cdots &a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{n1} & a_{n2} & \cdots &a_{nn} \end{bmatrix}\quad \text{and} \quad B=\begin{bmatrix} b_{11} & b_{12} & \cdots &b_{1n} \\ b_{21} & b_{22} & \cdots &b_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ b_{n1} & b_{n2} & \cdots &b_{nn} \end{bmatrix}\quad$$ be two $n\times n$ tables such that $\{a_{ij}|1\le i,j\le n\}=\{b_{ij}|1\le i,j\le n\}=\{k\in N^*|1\le k\le n^2\}$. One can perform the following operation on table $A$: Choose $2$ numbers in the same row or in the same column of $A$, interchange these $2$ numbers, and leave the remaining $n^2-2$ numbers unchanged. This operation is called a [b]transposition[/b] of $A$. Find, with proof, the smallest positive integer $m$ such that for any tables $A$ and $B$, one can perform at most $m$ transpositions such that the resulting table of $A$ is $B$.

Given 2n+3 points in the plane, no three on a line and no four on a circle, prove that it is always possible to find a circle C that goes through three of the given points and splits the other 2n in half, that is, has n on the inside and n on the outside.

A Haiku is a Japanese poem of seventeen syllables, in three lines of five, seven, and five. Take five good haikus Scramble their lines randomly What are the chances That you end up with Five completely good haikus (With five, seven, five)? Your answer will be m over n where m,n Are numbers such that m,n positive Integers where gcd Of m,n is 1. Take this answer and Add the numerator and Denominator. [i]Proposed by Jeff Lin[/i]

There are three stacks of tokens on the table: the first contains $a,$ the second contains $b,$ and the third contains $c$ where $a \ge b \ge c.$ Players $A$ and $B$ take turns playing a game of swapping tokens. $A$ starts first. On each turn, the player who gets his turn chooses two stacks, then takes at least one token from the stack with the lowest number of tokens and places them on the stack with the highest number of tokens. If the number of tokens in the two piles he/she chooses is equal, then he/she takes at least one token from any of them and puts it in the other. If only one pile remains after a player's move, that player is considered a winner. At what values of $a, b, c$ who has the winning strategy ($A$ or $B$)?

On the table there are $20$ coins of weights $1,2,3,\ldots,15,37,38,39,40$ and $41$ grams. They all look alike but their colours are all distinct. Now Miss Adams knows the weight and colour of each coin, but Mr. Bean knows only the weights of the coins. There is also a balance on the table, and each comparison of weights of two groups of coins is called an operation. Miss Adams wants to tell Mr. Bean which coin is the $1$ gram coin by performing some operations. What is the minimum number of operations she needs to perform?

An infinite number of squares on an infinitely square grid paper are painted red. Show that you can draw a number of squares on the paper, with sides along the grid lines, such that: (1) no square in the grid belongs to more than one square (an edge, on the other hand, may belong to more than one square) (2) each red square is located in one of the squares and the number of red squares in such square is at least $1/5$ and at most $4/5$ of the number of squares in the square. [hide=original wording] Ett andligt antal rutor pa ett oandligt rutat papper ar malade roda. Visa att man pa papperet kan rita in ett antal kvadrater, med sidor utefter rutnatets linjer, sadana att : (1) ingen ruta i natet tillhor mer an en kvadrat (en kant kan daremot tillhora mer an en kvadrat), (2) varje rod ruta ligger i nagon av kvadraterna och antalet roda rutor i en sadan kvadratar minst 1/5 och hogst 4/5 av antalet rutor i kvadraten. [url=http://www.mattetavling.se/wp-content/uploads/2011/01/Final10.pdf]source[/url][/hide] PS. I always post the original wording when I doubt about my (using Google) translation.

A calculator can square a number or add $1$ to it. It cannot add $1$ two times in a row. By several operations it transformed a number $x$ into a number $S > x^n + 1$ ($x, n,S$ are positive integers). Prove that $S > x^n + x - 1$.

If $\{a_1,a_2,a_3,\ldots,a_n\}$ is a set of real numbers, indexed so that $a_1<a_2<a_3<\cdots<a_n,$ its complex power sum is defined to be $a_1i+a_2i^2+a_3i^3+\cdots+a_ni^n,$ where $i^2=-1.$ Let $S_n$ be the sum of the complex power sums of all nonempty subsets of $\{1,2,\ldots,n\}.$ Given that $S_8=-176-64i$ and $S_9=p+qi,$ were $p$ and $q$ are integers, find $|p|+|q|.$

Two people A and B play a game in the $m \times n$ grid ($m,n \in \mathbb{N^*}$). Each person respectively (A plays first) draw a segment between two point of the grid such that this segment doesn't contain any point (except the 2 ends) and also the segment (except the 2 ends) doesn't intersect with any other segments. The last person who can't draw is the loser. Which one (of A and B) have the winning tactics?

[b]p1.[/b] Suppose $5$ bales of hay are weighted two at a time in all possible ways. The weights obtained are $110$, $112$, $113$, $114$, $115$, $116$, $117$, $118$, $120$, $121$. What is the difference between the heaviest and the lightest bale? [b]p2.[/b] Paul and Paula are playing a game with dice. Each have an $8$-sided die, and they roll at the same time. If the number is the same they continue rolling; otherwise the one who rolled a higher number wins. What is the probability that the game lasts at most $3$ rounds? [b]p3[/b]. Find the unique positive integer $n$ such that $\frac{n^3+5}{n^2-1}$ is an integer. [b]p4.[/b] How many numbers have $6$ digits, some four of which are $2, 0, 1, 4$ (not necessarily consecutive or in that order) and have the sum of their digits equal to $9$? [b]p5.[/b] The Duke School has $N$ students, where $N$ is at most $500$. Every year the school has three sports competitions: one in basketball, one in volleyball, and one in soccer. Students may participate in all three competitions. A basketball team has $5$ spots, a volleyball team has $6$ spots, and a soccer team has $11$ spots on the team. All students are encouraged to play, but $16$ people choose not to play basketball, $9$ choose not to play volleyball and $5$ choose not to play soccer. Miraculously, other than that all of the students who wanted to play could be divided evenly into teams of the appropriate size. How many players are there in the school? [b]p6.[/b] Let $\{a_n\}_{n\ge 1}$ be a sequence of real numbers such that $a_1 = 0$ and $a_{n+1} =\frac{a_n-\sqrt3}{\sqrt3 a_n+1}$ . Find $a_1 + a_2 +.. + a_{2014}$. [b]p7.[/b] A soldier is fighting a three-headed dragon. At any minute, the soldier swings her sword, at which point there are three outcomes: either the soldier misses and the dragon grows a new head, the soldier chops off one head that instantaneously regrows, or the soldier chops off two heads and none grow back. If the dragon has at least two heads, the soldier is equally likely to miss or chop off two heads. The dragon dies when it has no heads left, and it overpowers the soldier if it has at least five heads. What is the probability that the soldier wins [b]p8.[/b] A rook moves alternating horizontally and vertically on an infinite chessboard. The rook moves one square horizontally (in either direction) at the first move, two squares vertically at the second, three horizontally at the third and so on. Let $S$ be the set of integers $n$ with the property that there exists a series of moves such that after the $n$-th move the rock is back where it started. Find the number of elements in the set $S \cap \{1, 2, ..., 2014\}$. [b]p9.[/b] Find the largest integer $n$ such that the number of positive integer divisors of $n$ (including $1$ and $n$) is at least $\sqrt{n}$. [b]p10.[/b] Suppose that $x, y$ are irrational numbers such that $xy$, $x^2 + y$, $y^2 + x$ are rational numbers. Find $x + y$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Consider the set $S = \{1,2,3, ...,1441\}$. 1. Nora counts thoses subsets of $S$ having exactly two elements, tbe sum of which is even. Rania counts those subsets of $S$ having exactly two elements, the sum of which is odd. Determine the numbers counted by Nora and Rania. 2. Let $t$ be the number of subsets of $S$ which have at least two elements and the product of the elements is even. Determine the greatest power of $2$ which divides $t$. 3. Ahmad counts the subsets of $S$ having $77$ elements such that in each subset the sum of the elements is even. Bushra counts the subsets of $S$ having $77$ elements such that in each subset the sum of the elements is odd. Whose number is bigger? Determine the difference between the numbers found by Ahmad and Bushra.

Nelson is having his friend drop his unique bouncy ball from a $12$ foot building, and Nelson will only catch the ball at the peak of its trajectory between bounces. On any given bounce, there is an $80\%$ chance that the next peak occurs at $\frac13$ the height of the previous peak and a $20\%$ chance that the next peak occurs at $3$ times the height of the previous peak (where the first peak is at $12$ feet). If Nelson can only reach $4$ feet into the air and will catch the ball as soon as possible, the probability that Nelson catches the ball after exactly $13$ bounces is $2^a \times 3^b \times 5^c \times 7^d \times 11^e$ for integers $a, b, c, d$, and $e$. Find $|a| + |b| + |c| + |d| + |e|$.

The vertices of a regular $2012$-gon are labelled with the numbers $1$ through $2012$ in some order. Call a vertex a peak if its label is larger than the label of its two neighbours, and a valley if its label is smaller than the label of its two neighbours. Show that the total number of peaks is equal to the total number of valleys.

In a $12\times 12$ grid, colour each unit square with either black or white, such that there is at least one black unit square in any $3\times 4$ and $4\times 3$ rectangle bounded by the grid lines. Determine, with proof, the minimum number of black unit squares.

In a $50\times 50$ checkered square, each cell is colored in one of the 100 given colors so that all colors are used and there does not exist a monochromatic domino. Galia wants to repaint all the cells of one of the colors in a different color (from the given 100 colors) so that a monochromatic domino still won't exist. Is it true that Galia will surely be able to do this [i]Proposed by G. Sharafutdinova[/i]

A family of sets $F$ is called perfect if the following condition holds: For every triple of sets $X_1, X_2, X_3\in F$, at least one of the sets $$ (X_1\setminus X_2)\cap X_3,$$ $$(X_2\setminus X_1)\cap X_3$$ is empty. Show that if $F$ is a perfect family consisting of some subsets of a given finite set $U$, then $\left\lvert F\right\rvert\le\left\lvert U\right\rvert+1$. [i]Proposed by Michał Pilipczuk[/i]

There are red and blue balls in an urn : $1024$ in total. In one round, we do the following: we draw the balls from the urn two by two. After all balls have been drawn, we put a new ball back into the urn for each pair of drawn balls: the colour of the new ball depends on that of the drawn pair. For two red balls drawn, we put back a red ball. For two blue balls, we put back a blue ball. For a red and a blue ball, we put back a black ball. For a red and a black ball, we put back a red ball. For a blue and a black ball, we put back a blue ball. Finally, for two black balls we put back a black ball. Then the next round begins. After $10$ rounds, a single ball remains in the urn, which is red. What is the maximal number of blue balls that might have been in the urn at the very beginning?

A convex $n$-gon and its $n-3$ diagonals which have no common point inside the polygon form a [i]subdivision graph[/i]. Show that if and only if $3|n$, there exists a [i]subdivision graph [/i]that can be drawn in one closed stroke. (i.e. start from a certain vertex, get through every edges and diagonals exactly one time, finally back to the starting vertex.)

Humberto and Luciano use the break between classes to have fun with the following game: Humberto writes a list of distinct positive integers on a green sheet of paper and hands it to Luciano. Luciano then writes on a board all the possible sums, without repetitions, of one or more different numbers written on the green sheet. For example, if Humberto writes $1$, $3$ and $4$ on the green sheet, Luciano will write $1$, $3$, $4$, $5$, $7$ and $8$ on the board. (a) Let $n$ be a positive integer. Determine all positive integers $k$ such that Humberto can write a list of $n$ numbers on the green sheet in order to guarantee that Luciano will write exactly $k$ numbers on the board. (b) Luciano now decides to write a list of $m$ distinct positive integers on a yellow sheet of paper. Determine the smallest positive integer $m$ such that it is possible for Luciano to write this list so that, for any list that Humberto writes on the green sheet, with a maximum of $2023$ numbers, not all the numbers on the yellow sheet will be written on the board.