It is known that in a set of five coins three are genuine (and have the same weight) while two coins are fakes, each of which has a different weight from a genuine coin. What is the smallest number of weighings on a scale with two cups that is needed to locate one genuine coin?

$10$ numbers are placed on a circle. Their sum is equal to $100$. A sum of any three neighbouring numbers is no less than $29$. Find the minimal number $A$ such that for any such set of 10 numbers none of them is greater than $A$. Prove that this value for $A$ is really minimal. (A. Tolpygo, Kiev)

A phone company starts a new type of service. A new customer can choose $k$ phone numbers in this network which are call-free, whether that number is calling or is being called. A group of $n$ students want to use the service. (a) If $n\geq 2k+2$, show that there exist 2 students who will be charged when speaking. (b) It $n=2k+1$, show that there is a way to arrange the free calls so that everybody can speak free to anybody else in the group. [i]Valentin Vornicu[/i]

Certain king of a certain state wants to build $n$ cities and $n-1$ roads, connecting them to provide a possibility to move from every city to every city. (Each road connects two cities, the roads do not intersect, and don't come through another city.) He wants also, to make the shortests distances between the cities, along the roads, to be $1,2,3,...,n(n-1)/2$ kilometres. Is it possible for a) $n=6$ b) $n=1986$ ?

The plane is covered with circles in such a way that the center of each circle does not belong to any other circle. Prove that each point of the plane belongs to at most five circles.

A mysterious machine contains a secret combination of $2016$ integer numbers $x_1,x_2,\ldots,x_{2016}$. It is known that all the numbers in the combination are equal but one. One may ask questions to the machine by giving to it a sequence of $2016$ integer numbers $y_1,\ldots,y_{2016}$, and the machine answers by telling the value of the sum \[ x_1y_1+\dots+x_{2016}y_{2016}. \] After answering the first question, the machine accepts a second question and then a third one, and so on. Determine how many questions are necessary to determine the combination: (a) knowing that the number which is different from the others is equal to zero; (b) not knowing what the number different from the others is.

On a table, we have ten thousand matches, two of which are inside a bowl. Anna and Bernd play the following game: They alternate taking turns and Anna begins. A turn consists of counting the matches in the bowl, choosing a proper divisor $d$ of this number and adding $d$ matches to the bowl. The game ends when more than $2024$ matches are in the bowl. The person who played the last turn wins. Prove that Anna can win independently of how Bernd plays. [i](Richard Henner)[/i]

Ana has a scale that shows which side weight more or if both side are equal. She has $4$ weights which look the same but they weight $1001g, 1002g, 1004g$ and $1005g$, respectively. Is it possible for Ana to find out the weight of each of them with only $4$ measurements?

A pack of $2n$ cards contains $n$ different pairs of cards. Each pair consists of two identical cards, either of which is called the twin of the other. A game is played between two players $A$ and $B$. A third person called the [i]dealer[/i] shuffles the pack and deals the cards one by one face upward onto the table. One of the players, called the [i]receiver[/i], takes the card dealt, provided he does not have already its twin. If he does already have the twin, his opponent takes the dealt card and becomes the receiver. $A$ is initially the receiver and takes the first card dealt. The player who first obtains a complete set of $n$ different cards wins the game. What fraction of all possible arrangements of the pack lead to $A$ winning? Prove the correctness of your answer.

Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which \[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\] Find the number of elements of the set $A_n$. [i]Proposed by Vidan Govedarica, Serbia[/i]

Given are $n$ pairwise intersecting convex $k$-gons on the plane. Any of them can be transferred to any other by a homothety with a positive coefficient. Prove that there is a point in a plane belonging to at least $1 +\frac{n-1}{2k}$ of these $k$-gons.

In a summer camp that is going to last $n$ weeks, you want to divide the time into $3$ periods so that each period starts on a Monday and ends on a Sunday. The first period will be dedicated to artistic work, the second will be for sports and in the third there will be a technological workshop. During each term, a Monday will be chosen for an expert on the topic of the term to give a talk. Let $C(n)$ be the number of ways in which the activity calendar can be made. (For example, if $n=10$ one way the calendar could be done is by putting the first four weeks for art and the artist talk on the first Monday; the next $5$ weeks could be for sports, with the athlete visit on the fourth Monday of that period; the remaining week would be for the technology workshop and the talk would be on Monday of that week.) Calculate $C(8)$.

More than five competitors participated in a chess tournament. Each competitor played exactly once against each of the other competitors. Five of the competitors they each lost exactly two games. All other competitors each won exactly three games. There were no draws in the tournament. Determine how many competitors there were and show a tournament that verifies all conditions.

Let $n$ be a positive integer. A [i]Nordic[/i] square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a [i]valley[/i]. An [i]uphill path[/i] is a sequence of one or more cells such that: (i) the first cell in the sequence is a valley, (ii) each subsequent cell in the sequence is adjacent to the previous cell, and (iii) the numbers written in the cells in the sequence are in increasing order. Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square. Author: Nikola Petrović

There are $10001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There are a total of $k$ societies. Suppose that the following conditions hold: [i]i.)[/i] Each pair of students are in exactly one club. [i]ii.)[/i] For each student and each society, the student is in exactly one club of the society. [i]iii.)[/i] Each club has an odd number of students. In addition, a club with ${2m+1}$ students ($m$ is a positive integer) is in exactly $m$ societies. Find all possible values of $k$. [i]Proposed by Guihua Gong, Puerto Rico[/i]

Let $m,n \geqslant 2$ be integers, let $X$ be a set with $n$ elements, and let $X_1,X_2,\ldots,X_m$ be pairwise distinct non-empty, not necessary disjoint subset of $X$. A function $f \colon X \to \{1,2,\ldots,n+1\}$ is called [i]nice[/i] if there exists an index $k$ such that \[\sum_{x \in X_k} f(x)>\sum_{x \in X_i} f(x) \quad \text{for all } i \ne k.\] Prove that the number of nice functions is at least $n^n$.

[b]p1.[/b] Let $X,Y ,Z$ be nonzero real numbers such that the quadratic function $X t^2 - Y t + Z = 0$ has the unique root $t = Y$ . Find $X$. [b]p2.[/b] Let $ABCD$ be a kite with $AB = BC = 1$ and $CD = AD =\sqrt2$. Given that $BD =\sqrt5$, find $AC$. [b]p3.[/b] Find the number of integers $n$ such that $n -2016$ divides $n^2 -2016$. An integer $a$ divides an integer $b$ if there exists a unique integer $k$ such that $ak = b$. [b]p4.[/b] The points $A(-16, 256)$ and $B(20, 400)$ lie on the parabola $y = x^2$ . There exists a point $C(a,a^2)$ on the parabola $y = x^2$ such that there exists a point $D$ on the parabola $y = -x^2$ so that $ACBD$ is a parallelogram. Find $a$. [b]p5.[/b] Figure $F_0$ is a unit square. To create figure $F_1$, divide each side of the square into equal fifths and add two new squares with sidelength $\frac15$ to each side, with one of their sides on one of the sides of the larger square. To create figure $F_{k+1}$ from $F_k$ , repeat this same process for each open side of the smallest squares created in $F_n$. Let $A_n$ be the area of $F_n$. Find $\lim_{n\to \infty} A_n$. [img]https://cdn.artofproblemsolving.com/attachments/8/9/85b764acba2a548ecc61e9ffc29aacf24b4647.png[/img] [b]p6.[/b] For a prime $p$, let $S_p$ be the set of nonnegative integers $n$ less than $p$ for which there exists a nonnegative integer $k$ such that $2016^k -n$ is divisible by $p$. Find the sum of all $p$ for which $p$ does not divide the sum of the elements of $S_p$ . [b]p7. [/b] Trapezoid $ABCD$ has $AB \parallel CD$ and $AD = AB = BC$. Unit circles $\gamma$ and $\omega$ are inscribed in the trapezoid such that circle $\gamma$ is tangent to $CD$, $AB$, and $AD$, and circle $\omega$ is tangent to $CD$, $AB$, and $BC$. If circles $\gamma$ and $\omega$ are externally tangent to each other, find $AB$. [b]p8.[/b] Let $x, y, z$ be real numbers such that $(x+y)^2+(y+z)^2+(z+x)^2 = 1$. Over all triples $(x, y, z)$, find the maximum possible value of $y -z$. [b]p9.[/b] Triangle $\vartriangle ABC$ has sidelengths $AB = 13$, $BC = 14$, and $CA = 15$. Let $P$ be a point on segment $BC$ such that $\frac{BP}{CP} = 3$, and let $I_1$ and $I_2$ be the incenters of triangles $\vartriangle ABP$ and $\vartriangle ACP$. Suppose that the circumcircle of $\vartriangle I_1PI_2$ intersects segment $AP$ for a second time at a point $X \ne P$. Find the length of segment $AX$. [b]p10.[/b] For $1 \le i \le 9$, let Ai be the answer to problem i from this section. Let $(i_1,i_2,... ,i_9)$ be a permutation of $(1, 2,... , 9)$ such that $A_{i_1} < A_{i_2} < ... < A_{i_9}$. For each $i_j$ , put the number $i_j$ in the box which is in the $j$th row from the top and the $j$th column from the left of the $9\times 9$ grid in the bonus section of the answer sheet. Then, fill in the rest of the squares with digits $1, 2,... , 9$ such that $\bullet$ each bolded $ 3\times 3$ grid contains exactly one of each digit from $ 1$ to $9$, $\bullet$ each row of the $9\times 9$ grid contains exactly one of each digit from $ 1$ to $9$, and $\bullet$ each column of the $9\times 9$ grid contains exactly one of each digit from $ 1$ to $9$. PS. You had better use hide for answers.

The $U$-tile is made up of $1 \times 1$ squares and has the following shape: [img]https://cdn.artofproblemsolving.com/attachments/8/7/5795ee33444055794119a99e675ef977add483.png[/img] where there are two vertical rows of a squares, one horizontal row of $b$ squares, and also $a \ge 2$ and $b \ge 3$. Notice that there are different types of tile $U$ . For example, some types of $U$ tiles are as follows: [img]https://cdn.artofproblemsolving.com/attachments/0/3/ca340686403739ffbbbb578d73af76e81a630e.png[/img] Prove that for each integer $n \ge 6$, the board of $n\times n$ can be completely covered with $U$-tiles , with no gaps and no overlapping clicks. Clarifications: The $U$-tiles can be rotated. Any amount can be used in the covering of tiles of each type.

A subset of $ n\times n$ table is called even if it contains even elements of each row and each column. Find the minimum $ k$ such that each subset of this table with $ k$ elements contains an even subset

A natural number \(N\) is given. A cube with side length \(2N + 1\) is made up of \((2N + 1)^3\) unit cubes, each of which is either black or white. It turns out that among any $8$ cubes that share a common vertex and form a \(2 \times 2 \times 2\) cube, there are at most $4$ black cubes. What is the maximum number of black cubes that could have been used?

Georg writes a positive integer $a$ on a blackboard. As long as there is a number on the blackboard, he does the following each day: $\bullet$ If the last digit in the number on the blackboard is less than or equal to $5$, he erases that last digit. (If there is only this digit, the blackboard thus becomes empty.) $\bullet$ Otherwise he erases the entire number and writes $9$ times the number. Can Georg choose $a$ in such a way that the blackboard never becomes empty?

We have $1000$ balls in $40$ different colours, $25$ balls of each colour. Determine the smallest $n$ for which the following holds: if you place the $1000$ balls in a circle, in any arbitrary way, then there are always $n$ adjacent balls which have at least $20$ different colours.

A tuple of real numbers $(a_1, a_2, \dots, a_m)$ is called [i]stable [/i]if for each $k \in \{1, 2, \cdots, m-1\}$, $$ \left \vert \frac{a_1+ a_2 + \cdots + a_k}{k} - a_{k+1} \right \vert < 1. $$ Does there exist a stable $n$-tuple $(x_1, x_2, \dots, x_n)$ such that for any real number $x$, the $(n+1)$-tuple $(x, x_1, x_2, \dots, x_n)$ is not stable?

An equilateral triangle $ABC$ has sides of length $n$, a positive integer. Divide the triangle into equilateral triangles of length $ 1$, drawing parallel lines (at distance $ 1$) to all sides of the triangle. A path is a continuous path, starting at the triangle with vertex $A$ and always crossing from one small triangle to another on the side that both triangles share, in such a way that it never passes through a small triangle twice. Find the maximum number of triangles that can be visited.

A panel contains $100$ light bulbs, arranged in a $10$ by $10$ square array. Some of them are on, the others are off. The electrical system is such that when the switch corresponding to a light bulb is pressed, all the light bulbs that are on the same row or column of it (including the bulb linked to the pressed switch) change their state (that is they are turned on or off). [list] [*] From which starting configurations, pressing the right sequence of switches, is it possible to achieve that all bulbs are on at the same time? [*] What is the answer to the previous question if the bulbs are $81$, arranged in a $9$ by $9$ panel?[/list]