In a certain country there are $n$ cities. Some pairs of cities are connected by highways in such a way that for each two cities there is at most one highway connecting them. Assume that for a certain positive integer $k$, the total number of highways is greater than $\frac{nk}{2}$. Show that there exist $k+2$ distinct cities $C_1, C_2, \dots, C_{k+2}$ such that $C_i$ and $C_{i+1}$ are connected by a highway for $i=1, 2, \dots, k+1$. [i]Proposed by Oriol Solé[/i]

Prove that $$\sum \limits_{0\leq i<j\leq n}(i+j) {{n}\choose{i}}{{n}\choose{j}}=n\left (2^{2n-1}-{{2n-1}\choose{n}} \right )$$

$n > 10$ teams take part in a football tournament. Every team plays exactly once against each other. A win gives two points, a draw a point, and a defeat no point. After the tournament it turns out that each team gets exactly half their points in the games against the bottom $10$ teams has won (in particular, each of these $10$ teams has won the made half their points against the $9$ remaining). Determine all possible values ​​of $n$, and give an example of such a tournament for these values.

[b]p1.[/b] The following number is the product of the divisors of $n$. $$2^63^3$$ What is $n$? [b]p2.[/b] Let a right triangle have the sides $AB =\sqrt3$, $BC =\sqrt2$, and $CA = 1$. Let $D$ be a point such that $AD = BD = 1$. Let $E$ be the point on line $BD$ that is equidistant from $D$ and $A$. Find the angle $\angle AEB$. [b]p3.[/b] There are twelve indistinguishable blackboards that are distributed to eight different schools. There must be at least one board for each school. How many ways are there of distributing the boards? [b]p4.[/b] A Nishop is a chess piece that moves like a knight on its first turn, like a bishop on its second turn, and in general like a knight on odd-numbered turns and like a bishop on even-numbered turns. A Nishop starts in the bottom-left square of a $3\times 3$-chessboard. How many ways can it travel to touch each square of the chessboard exactly once? [b]p5.[/b] Let a Fibonacci Spiral be a spiral constructed by the addition of quarter-circles of radius $n$, where each $n$ is a term of the Fibonacci series: $$1, 1, 2, 3, 5, 8,...$$ (Each term in this series is the sum of the two terms that precede it.) What is the arclength of the maximum Fibonacci spiral that can be enclosed in a rectangle of area $714$, whose side lengths are terms in the Fibonacci series? [b]p6.[/b] Suppose that $a_1 = 1$ and $$a_{n+1} = a_n -\frac{2}{n + 2}+\frac{4}{n + 1}-\frac{2}{n}$$ What is $a_{15}$? [b]p7.[/b] Consider $5$ points in the plane, no three of which are collinear. Let $n$ be the number of circles that can be drawn through at least three of the points. What are the possible values of $n$? [b]p8.[/b] Find the number of positive integers $n$ satisfying $\lfloor n /2014 \rfloor =\lfloor n/2016 \rfloor$. [b]p9.[/b] Let $f$ be a function taking real numbers to real numbers such that for all reals $x \ne 0, 1$, we have $$f(x) + f \left( \frac{1}{1 - x}\right)= (2x - 1)^2 + f\left( 1 -\frac{1}{ x}\right)$$ Compute $f(3)$. [b]p10.[/b] Alice and Bob split $5$ beans into piles. They take turns removing a positive number of beans from a pile of their choice. The player to take the last bean loses. Alice plays first. How many ways are there to split the piles such that Alice has a winning strategy? [b]p11.[/b] Triangle $ABC$ is an equilateral triangle of side length $1$. Let point $M$ be the midpoint of side $AC$. Another equilateral triangle $DEF$, also of side length $1$, is drawn such that the circumcenter of $DEF$ is $M$, point $D$ rests on side $AB$. The length of $AD$ is of the form $\frac{a+\sqrt{b}}{c}$ , where $b$ is square free. What is $a + b + c$? [b]p12.[/b] Consider the function $f(x) = \max \{-11x- 37, x - 1, 9x + 3\}$ defined for all real $x$. Let $p(x)$ be a quadratic polynomial tangent to the graph of $f$ at three distinct points with x values $t_1$, $t_2$ and $t_3$ Compute the maximum value of $t_1 + t_2 + t_3$ over all possible $p$. [b]p13.[/b] Circle $J_1$ of radius $77$ is centered at point $X$ and circle $J_2$ of radius $39$ is centered at point $Y$. Point $A$ lies on $J1$ and on line $XY$ , such that A and Y are on opposite sides of $X$. $\Omega$ is the unique circle simultaneously tangent to the tangent segments from point $A$ to $J_2$ and internally tangent to $J_1$. If $XY = 157$, what is the radius of $\Omega$ ? [b]p14.[/b] Find the smallest positive integer $n$ so that for any integers $a_1, a_2,..., a_{527}$,the number $$\left( \prod^{527}_{j=1} a_j\right) \cdot\left( \sum^{527}_{j=1} a^n_j\right)$$ is divisible by $527$. [b]p15.[/b] A circle $\Omega$ of unit radius is inscribed in the quadrilateral $ABCD$. Let circle $\omega_A$ be the unique circle of radius $r_A$ externally tangent to $\Omega$, and also tangent to segments $AB$ and $DA$. Similarly define circles $\omega_B$, $\omega_C$, and $\omega_D$ and radii $r_B$, $r_C$, and $r_D$. Compute the smallest positive real $\lambda$ so that $r_C < \lambda$ over all such configurations with $r_A > r_B > r_C > r_D$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Students $ A $ and $ B $ play according to the following rules: student $ A $ selects a vector $ \overrightarrow{a_1} $ of length 1 in the plane, then student $ B $ gives the number $ s_1 $, equal to $ 1 $ or $ - $1; then the student $ A $ chooses a vector $ \overrightarrow{a_1} $ of length $ 1 $, and in turn the student $ B $ gives a number $ s_2 $ equal to $ 1 $ or $ -1 $ etc. $ B $ wins if for a certain $ n $ vector $ \sum_{j=1}^n \varepsilon_j \overrightarrow{a_j} $ has a length greater than the number $ R $ determined before the start of the game. Prove that student $B$ can achieve a win in no more than $R^2 + 1$ steps regardless of partner $A$'s actions.

Let $ n, k \in \mathbb{N}$ with $ 1 \leq k \leq \frac {n}{2} - 1.$ There are $ n$ points given on a circle. Arbitrarily we select $ nk + 1$ chords among the points on the circle. Prove that of these chords there are at least $ k + 1$ chords which pairwise do not have a point in common.

A total of $n$ people compete in a mathematical match which contains $15$ problems where $n>12$. For each problem, $1$ point is given for a right answer and $0$ is given for a wrong answer. Analysing each possible situation, we find that if the sum of points every group of $12$ people get is no less than $36$, then there are at least $3$ people that got the right answer of a certain problem, among the $n$ people. Find the least possible $n$.

There are $18$ children in the class. Parents decided to give children from this class a cake. To do this, they first learned from each child the area of ​​the piece he wants to get. After that, they showed a square-shaped cake, the area of ​​which is exactly equal to the sum of $18$ named numbers. However, when they saw the cake, the children wanted their pieces to be squares too. The parents cut the cake with lines parallel to the sides of the cake (cuts do not have to start or end on the side of the cake). For what maximum k the parents are guaranteed to cut out $k$ square pieces from the cake, which you can give to $k$ children so that each of them gets what they want?

we named a $n*n$ table $selfish$ if we number the row and column with $0,1,2,3,...,n-1$.(from left to right an from up to down) for every {$ i,j\in{0,1,2,...,n-1}$} the number of cell $(i,j)$ is equal to the number of number $i$ in the row $j$. for example we have such table for $n=5$ 1 0 3 3 4 1 3 2 1 1 0 1 0 1 0 2 1 0 0 0 1 0 0 0 0 prove that for $n>5$ there is no $selfish$ table

Per and Kari each have $n$ pieces of paper. They both write down the numbers from $1$ to $2n$ in an arbitrary order, one number on each side. Afterwards, they place the pieces of paper on a table showing one side. Prove that they can always place them so that all the numbers from $1$ to $2n$ are visible at once.

A well-known puzzle asks for a partition of a cross into four parts which are to be reassembled into a square. One solution is exhibited on the picture. [img]https://cdn.artofproblemsolving.com/attachments/9/1/3b8990baf5e37270c640e280c479b788d989ba.png[/img] Show that there are infinitely many solutions. (Some solutions split the cross into four equal parts!)

You are playing a game called "Hovse." Initially you have the number $0$ on a blackboard. If at any moment the number $x$ is written on the board, you can either: $\bullet$ replace $x$ with $3x + 1$ $\bullet$ replace $x$ with $9x + 1$ $\bullet$ replace $x$ with $27x + 3$ $\bullet$ or replace $x$ with $\left \lfloor \frac{x}{3} \right \rfloor $. However, you are not allowed to write a number greater than $2017$ on the board. How many positive numbers can you make with the game of "Hovse?"

Find all numbers $n$ for which it is possible to cut a square into $n$ smaller squares.

Prove that any polygon $A_1A_2\dots A_n$ has three vertices $A_i,A_j,A_k$ such that $[A_iA_jA_k]>\frac{1}{4}[A_1A_2\dots A_n]$. [i]Folklore[/i]

In the following, a [i]word[/i] will mean a finite sequence of letters "$a$" and "$b$". The [i]length[/i] of a word will mean the number of the letters of the word. For instance, $abaab$ is a word of length $5$. There exists exactly one word of length $0$, namely the empty word. A word $w$ of length $\ell$ consisting of the letters $x_1$, $x_2$, ..., $x_{\ell}$ in this order is called a [i]palindrome[/i] if and only if $x_j=x_{\ell+1-j}$ holds for every $j$ such that $1\leq j\leq\ell$. For instance, $baaab$ is a palindrome; so is the empty word. For two words $w_1$ and $w_2$, let $w_1w_2$ denote the word formed by writing the word $w_2$ directly after the word $w_1$. For instance, if $w_1=baa$ and $w_2=bb$, then $w_1w_2=baabb$. Let $r$, $s$, $t$ be nonnegative integers satisfying $r + s = t + 2$. Prove that there exist palindromes $A$, $B$, $C$ with lengths $r$, $s$, $t$, respectively, such that $AB=Cab$, if and only if the integers $r + 2$ and $s - 2$ are coprime.

Let $n$ be a positive integer . If $\sigma$ is a permutation of the first $n$ positive integers , let $S(\sigma)$ be the set of all distinct sums of the form $\sum_{i=k}^{l} \sigma(i)$ where $1 \leq k \leq l \leq n$ . [b](a)[/b] Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)|\geq \left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor $. [b](b)[/b] Show that $|S(\sigma)|>\frac{n\sqrt{n}}{4\sqrt{2}}$ for all permutations $\sigma$ of the first $n$ positive integers .

A domino is a $1\times2$ or $2\times 1$ rectangle. Diego wants to completely cover a $6\times 6$ board using $18$ dominoes. Determine the smallest positive integer $k$ for which Diego can place $k$ dominoes on the board (without overlapping) such that what remains of the board can be covered uniquely using the remaining dominoes.

The figure $F$ is the intersection of $N$ circles (they may have different radii). Find the maximal number of curvilinear “sides” which $F$ can have. Curvilinear sides of $F$ are the arcs (of the given circumferences) that constitute the boundary of $F$. (Their ends are the “vertices” of $F$ - the points of intersection of given circumferences that lie on the boundary of $F$.) (N Brodsky)

The Integration Premier League has $n$ teams competing. The tournament follows a round-robin system, that is, where every pair of teams play each other exactly once. So every team plays exactly $n-1$ matches. The top $m \leq n$ temas at the end of the tournament qualify for the playoffs. Assume there are no tied matches. Let $A(m,n)$ be the minimum number of matches a team has to win to gurantee selection for the playoffs, regardless of what their run rate is. For example, $A(n,n) = 0$ (everyone qualifies anyway so no need to win!) and $A(1,n) = n-1$ (even if you lose to just one other team, they might defeat everyone and qualify instead of you). Answer the following: $(A)$ FInd the value of $A(2,4),A(2,6)$ and $A(4,10)$ with proof (explain why a smaller value can still lead to the team not qualifying, and show that the respective values themselves are enough). $(B)$ Show that $A(n-1,n) = \frac{n}{2}$ when $n$ even and $ = \frac{n+1}{2}$ when $n$ odd. $(C)$ For bonus marks, try to find a general pattern for $A(m,n)$.

Define a "ternary sequence" is a sequence that every number is $0,1$ or $2$. ternary sequence $(x_1,x_2,x_3,\cdots,x_n)$, define its difference to be $$(|x_1-x_2|,|x_2-x_3|,\cdots,|x_{n-1}-x_n|)$$ A difference will make the length of the sequence decrease by $1$, so we define the "feature value" of a ternary sequence with length $n$ is the number left after $n-1$ differences. How many ternary sequences has length $2023$ and feature value $0$? [i]Proposed by CSJL[/i]

Fix a set of integers $S$. An integer is [i]clean[/i] if it is the sum of distinct elements of $S$ in exactly one way, and [i]dirty[/i] otherwise. Prove that the set of dirty numbers is either empty or infinite. [i]Note:[/i] We consider the empty sum to equal \(0\). [i]Proposed by Tony Wang and Ethan Tan[/i]

A tribe called Ababab uses only letters $A$ and $B$, and they create words according to the following rules: (1) $A$ is a word; (2) if $w$ is a word, then $ww$ and $w\overline{w}$ are also words, where $\overline{w}$ is obtained from $w$ by replacing all letters $A$ with $B$ and all letters $B$ with $A$ ( $xy$ denotes the concatenation of $x$ and $y$) (3) all words are created by rules (1) and (2). Prove that any two words with the same number of letters differ exactly in half of their letters.

[b]p1.[/b] The oil pipeline passes by three villages $A$, $B$, $C$. In the first village, $30\%$ of the initial amount of oil is drained, in the second - $40\%$ of the amount that will reach village $B$, and in the third - $50\%$ of the amount that will reach village $C$ What percentage of the initial amount of oil reaches the end of the pipeline? [b]p2.[/b] There are several ordinary irreducible fractions (not necessarily proper) with natural numerators and denominators (and the denominators are greater than $1$). The product of all fractions is equal to $10$. All numerators and denominators are increased by $1$. Can the product of the resulting fractions be greater than $10$? [b]p3.[/b] The garland consists of $10$ light bulbs connected in series. Exactly one of the light bulbs has burned out, but it is not known which one. There is a suitable light bulb available to replace a burnt out one. To unscrew a light bulb, you need $10$ seconds, to screw it in - also $10$ seconds (the time for other actions can be neglected). Is it possible to be guaranteed to find a burnt out light bulb: a) in $10$ minutes, b) in $5$ minutes? [b]p4.[/b] When fast and slow athletes run across the stadium in one direction, the fast one overtakes the slow one every $15$ minutes, and when they run towards each other, they meet once every $5$ minutes. How many times is the speed of a fast runner greater than the speed of a slow runner? [b]p5.[/b] Petya was $35$ minutes late for school. Then he decided to run to the kiosk for ice cream. But when he returned, the second lesson had already begun. He immediately ran for ice cream a second time and was gone for the same amount of time. When he returned, it turned out that he was late again, and he had to wait $50$ minutes before the start of the fourth lesson. How long does it take to run from school to the ice cream stand and back if each lesson, including recess after it, lasts $55$ minutes? [b]p6.[/b] In a convex heptagon, draw as many diagonals as possible so that no three of them are sides of the same triangle, the vertices of which are at the vertices of the original heptagon. [b]p7.[/b] In the writing of the antipodes, numbers are also written with the digits $0, ..., 9$, but each of the numbers has different meanings for them and for us. It turned out that the equalities are also true for the antipodes $5 * 8 + 7 + 1 = 48$ $2 * 2 * 6 = 24$ $5* 6 = 30$ a) How will the equality $2^3 = ...$ in the writing of the antipodes be continued? b) What does the number 9 mean among the Antipodes? Clarifications: a) It asks to convert $2^3$ in antipodes language, and write with what number it is equal and find a valid equality in both numerical systems. b) What does the digit $9$ mean among the antipodes, i.e. with which digit is it equal in our number system? [b]p8.[/b] They wrote the numbers $1, 2, 3, 4, ..., 1996, 1997$ in a row. Which digits were used more when writing these numbers - ones or twos? How long? [b]p9.[/b] On the number axis there lives a grasshopper who can jump $1$ and $4$ to the right and left. Can he get from point $1$ to point $2$ of the numerical axis $in 1996$ jumps if he must not get to points with coordinates divisible by $ 4$ (points $0$, $\pm 4$, $\pm 8$, etc.)? [b]p10.[/b] Is there a convex quadrilateral that can be cut along a straight line into two parts of the same size and shape, but neither the diagonal nor the straight line passing through the midpoints of opposite sides divides it into two equal parts? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c2416727_soros_olympiad_in_mathematics]here.[/url]

There are $2005$ players in a chess tournament played a game. Every pair of players played a game against each other. At the end of the tournament, it turned out that if two players $A$ and $B$ drew the game between them, then every other player either lost to $A$ or to $B$. Suppose that there are at least two draws in the tournament. Prove that all players can be lined up in a single file from left to right in the such a way that every play won the game against the person immediately to his right.

There are villager $0$, villager $1$, . . . , villager $2015$ i.e. $2016$ people in the village. You are villager $0$. Each villager is either honest or liar. You don’t know each villager is honest or liar, but you know you are honest and the number of liar is equal or smaller than integer $T$. The villagers became to write one letter without fail from one day. For integers $1 \le n \le 2015$, there are set integers $1 < k_n < 2015$. The letter villager $i$ wrote in day $n$ of the morning is delivered to villager $i + k_n$ if villager $i$ is honest, or villager $i - k_n$ if villager $i$ is liar in day $n$ of the evening. If $i - j$ is divisible by $2016$, villager $i$ and $j$ point same villager. Villagers don’t know $k_n$, but sender is told when letters are received. Villager can write anything on a letter, and each villager receives letters from any villagers a sufficient number of times after enough time. i.e. there are $n$ satisfying $k = k_n$ infinitely for each integer $1 \le k \le 2015$. You want to know the honest persons of this village. You can gather all villagers just once and instruct in one day of noon. The honest person obeys your instruction but the liar person not always obeys and he or she writes on a letter anything possible. One day from your instruction for a while, you could determine all honest persons of this village. Find the maximum value of $T$ such that it is possible to do this if you instruct appropriate regardless of the villagers who are honest or liar.