In a horizontal strip $1 \times n$ made of $n$ unit squares the vertices of all squares are marked. The strip is partitioned into parts by segments connecting marked points and not lying on the sides of the strip. The segments can not have common inner points; the upper end of each segment must be either above the lower end or further to the right. Prove that the number of all partitions is divisible by $2^n$. (The partition where no segments are drawn, is counted too.) [i](E. Robeva, M. Sun)[/i]

A [i]tile[/i] $T$ is a union of finitely many pairwise disjoint arcs of a unit circle $K$. The [i]size[/i] of $T$, denoted by $|T|$, is the sum of the lengths of the arcs $T$ consists of, divided by $2\pi$. A [i]copy[/i] of $T$ is a tile $T'$ obtained by rotating $T$ about the centre of $K$ through some angle. Given a positive real number $\varepsilon < 1$, does there exist an infinite sequence of tiles $T_1,T_2,\ldots,T_n,\ldots$ satisfying the following two conditions simultaneously: 1) $|T_n| > 1 - \varepsilon$ for all $n$; 2) The union of all $T_n'$ (as $n$ runs through the positive integers) is a proper subset of $K$ for any choice of the copies $T_1'$, $T_2'$, $\ldots$, $T_n', \ldots$? [hide=Note] In the extralist the problem statement had the clause "three conditions" rather than two, but only two are presented, the ones you see. I am quite confident this is a typo or that the problem might have been reformulated after submission.[/hide]

Simple graph $G$ has $19998$ vertices. For any subgraph $\bar G$ of $G$ with $9999$ vertices, $\bar G$ has at least $9999$ edges. Find the minimum number of edges in $G$

Place a pebble at each [i]non-positive[/i] integer point on the real line, and let $n$ be a fixed positive integer. At each step we choose some n consecutive integer points, remove one of the pebbles located at these points and rearrange all others arbitrarily within these points (placing at most one pebble at each point). Determine whether there exists a positive integer $n$ such that for any given $N > 0$ we can place a pebble at a point with coordinate greater than $N$ in a finite number of steps described above.

The figure shows a game board with $16$ squares. At the start of the game, two cars are placed in different squares. Two players $A$ and $B$ alternately take turns, and A starts. In each turn, the player chooses one of the cars and moves it one or more squares to the right. The left-most car may never overtake or land on the same square as the right-most car. The first player which is unable to move loses. [img]https://cdn.artofproblemsolving.com/attachments/1/b/8d6f40fac4983d6aa9bd076392c91a6d200f6a.png[/img] (a) Prove that A can win regardless of how $B$ plays, if the two cars start as shown in the figure. (b) Determine all starting positions in which $B$ can win regardless of how $A$ plays.

There are $n \ge 6$ green points in the plane, such that no $3$ of them are collinear. Suppose further that $6$ of these points are the vertices of a convex hexagon. Prove that there are $5$ green points that form a pentagon that does not contain any other green point inside.

Alicia and Bob take turns writing words on a blackboard. The rules are as follows: a) Any word that has been written cannot be rewritten. b) A player can only write a permutation of the previous word, or can simply simply remove one letter (whatever you want) from the previous word. c) The first person who cannot write another word loses. If Alice starts by typing the word ''Olympics" and Bob's next turn, who, do you think, has a winning strategy and what is it?

[b]2.[/b] Let $n \geq 3$ be an integer. Prove that for all integers $k$, with $1 \leq k \leq \binom{n}{2}$, there exists a set $A$ with $n$ distinct positive integer elements such that the set $B = \{\gcd(x, y): x, y \in A, x \neq y \}$ (gotten from the greatest common divisor of all pairs of distinct elements from $A$) contains exactly $k$ distinct elements.

How many 6-digit numbers are there such that-: a)The digits of each number are all from the set $ \{1,2,3,4,5\}$ b)any digit that appears in the number appears at least twice ? (Example: $ 225252$ is valid while $ 222133$ is not) [b][weightage 17/100][/b]

There are $n \ge 2$ points in a square side $1$. Show that one can label the points $P_1, P_2, ... , P_n$ such that $\sum_{i=1}^n |P_{i-1} - P_i|^2 \le 4$, where we use cyclic subscripts, so that $P_0$ means $P_n$.

Let $n$ be a positive integer. Alice and Bob play the following game. First, Alice picks $n + 1$ subsets $A_1,...,A_{n+1}$ of $\{1,... ,2^n\}$ each of size $2^{n-1}$. Second, Bob picks $n + 1$ arbitrary integers $a_1,...,a_{n+1}$. Finally, Alice picks an integer $t$. Bob wins if there exists an integer $1 \le i \le n + 1$ and $s \in A_i$ such that $s + a_i \equiv t$ (mod $2^n$). Otherwise, Alice wins. Find all values of $n$ where Alice has a winning strategy.

What is the largest number of horses that you can put on a chessboard without there being two horses that can beat each other? a. Describe an arrangement with that maximum number. b. Prove that a larger number is not possible. (A chessboard consists of $8 \times 8$ spaces and a horse jumps from one field to another field according to the line "two squares vertically and one squared horizontally" or "one square vertically and two squares horizontally") [asy] unitsize (0.5 cm); int i, j; for (i = 0; i <= 7; ++i) { for (j = 0; j <= 7; ++j) { if ((i + j) % 2 == 0) { if ((i - 2)^2 + (j - 3)^2 == 5) { fill(shift((i,j))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red); } else { fill(shift((i,j))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), gray(0.8)); } } }} for (i = 0; i <= 8; ++i) { draw((i,0)--(i,8)); draw((0,i)--(8,i)); } label("$a$", (0.5,-0.5), fontsize(10)); label("$b$", (1.5,-0.5), fontsize(10)); label("$c$", (2.5,-0.5), fontsize(10)); label("$d$", (3.5,-0.5), fontsize(10)); label("$e$", (4.5,-0.5), fontsize(10)); label("$f$", (5.5,-0.5), fontsize(10)); label("$g$", (6.5,-0.5), fontsize(10)); label("$h$", (7.5,-0.5), fontsize(10)); label("$1$", (-0.5,0.5), fontsize(10)); label("$2$", (-0.5,1.5), fontsize(10)); label("$3$", (-0.5,2.5), fontsize(10)); label("$4$", (-0.5,3.5), fontsize(10)); label("$5$", (-0.5,4.5), fontsize(10)); label("$6$", (-0.5,5.5), fontsize(10)); label("$7$", (-0.5,6.5), fontsize(10)); label("$8$", (-0.5,7.5), fontsize(10)); label("$P$", (2.5,3.5), fontsize(10)); [/asy]

Show that there do not exist more than $27$ half-lines (or rays) emanating from the origin in the $3$-dimensional space, such that the angle between each pair of rays is $\geq \frac{\pi}{4}$.

Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers, and let $b_1, b_2, \ldots, b_m$ be $m$ positive integers such that $a_1 a_2 \cdots a_n = b_1 b_2 \cdots b_m$. Prove that a rectangular table with $n$ rows and $m$ columns can be filled with positive integer entries in such a way that * the product of the entries in the $i$-th row is $a_i$ (for each $i \in \left\{1,2,\ldots,n\right\}$); * the product of the entries in the $j$-th row is $b_j$ (for each $i \in \left\{1,2,\ldots,m\right\}$).

There is a deck of cards placed at every points $A_1, A_2, \ldots , A_n$ and $O$, where $n \geq 3$. We can do one of the following two operations at each step: $1)$ If there are more than 2 cards at some points $A_i$, we can withdraw three cards from that deck and place one each at $A_{i-1}, A_{i+1}$ and $O$. (Here $A_0=A_n$ and $A_{n+1}=A_1$); $2)$ If there are more than or equal to $n$ cards at point $O$, we can withdraw $n$ cards from that deck and place one each at $A_1, A_2, \ldots , A_n$. Show that if the total number of cards is more than or equal to $n^2+3n+1$, we can make the number of cards at every points more than or equal to $n+1$ after finitely many steps.

$234$ viewers came to the cinema. Determine for which$ n \ge 4$ the viewers could be can be arranged in $n$ rows so that every viewer in $i$-th row gets to know just $j$ viewers in $j$-th row for any $i, j \in \{1, 2,... , n\}, i\ne j$. (The relationship of acquaintance is mutual.) (Tomáš Jurík)

Two players play a game on an $8$ by $8$ chessboard according to the following rules. The first player places a knight on the board. Then each player in turn moves the knight , but cannot place it on a square where it has been before. The player who has no move loses. Who wins in an errorless game , the first player or the second one? (The knight moves are the normal ones. ) (V . Zudilin , year 12 student , Beltsy (Moldova))

[b]a)[/b] Among $9$ apparently identical coins, one is false and lighter than the others. How can you discover the fake coin by making $2$ weighing in a two-course balance? [b]b)[/b] Find the least necessary number of weighing that must be done to cover a false currency between $27$ coins if all the others are true.

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with exactly $n$ occurrences of each of the letters $a, b,$ and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$ , there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.

Let $ABCD$ be a square with side $20$ and $T_1, T_2, ..., T_{2000}$ are points in $ABCD$ such that no $3$ points in the set $S = \{A, B, C, D, T_1, T_2, ..., T_{2000}\}$ are collinear. Prove that there exists a triangle with vertices in $S$, such that the area is less than $1/10$.

[b]p1.[/b] Compute $1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55$. [b]p2.[/b] Given that $a$, $b$, and $c$ are positive integers such that $a+b = 9$ and $bc = 30$, find the minimum possible value of $a + c$. [b]p3.[/b] Points $X$ and $Y$ lie outside regular pentagon $ABCDE$ such that $ABX$ and $DEY$ are equilateral triangles. Find the degree measure of $\angle XCY$ . [b]p4.[/b] Let $N$ be the product of the positive integer divisors of $8!$, including itself. The largest integer power of $2$ that divides $N$ is $2^k$. Compute $k$. [b]p5.[/b] Let $A=(-20, 22)$, $B = (k, 0)$, and $C = (202, 2)$ be points on the coordinate plane. Given that $\angle ABC = 90^o$, find the sum of all possible values of $k$. [b]p6.[/b] Tej is typing a string of $L$s and $O$s that consists of exactly $7$ $L$s and $4$ $O$s. How many different strings can he type that do not contain the substring ‘$LOL$’ anywhere? A substring is a sequence of consecutive letters contained within the original string. [b]p7.[/b] How many ordered triples of integers $(a, b, c)$ satisfy both $a+b-c = 12$ and $a^2+b^2-c^2 = 24$? [b]p8.[/b] For how many three-digit base-$7$ numbers $\overline{ABC}_7$ does $\overline{ABC}_7$ divide $\overline{ABC}_{10}$? (Note: $\overline{ABC}_D$ refers to the number whose digits in base $D$ are, from left to right, $A$, $B$, and $C$; for example, $\overline{123}_4$ equals $27$ in base ten). [b]p9.[/b] Natasha is sitting on one of the $35$ squares of a $5$-by-$7$ grid of squares. Wanda wants to walk through every square on the board exactly once except the one Natasha is on, starting and ending on any $2$ squares she chooses, such that from any square she can only go to an adjacent square (two squares are adjacent if they share an edge). How many squares can Natasha choose to sit on such that Wanda cannot go on her walk? [b]p10.[/b] In triangle $ABC$, $AB = 13$, $BC = 14$, and $CA = 15$. Point $P$ lies inside $ABC$ and points $D,E$, and $F$ lie on sides $BC$, $CA$, and $AB$, respectively, so that $PD \perp BC$, $PE \perp CA$, and $PF \perp AB$. Given that $PD$, $PE$, and $PF$ are all integers, find the sum of all possible distinct values of $PD \cdot PE \cdot PF$. [b]p11.[/b] A palindrome is a positive integer which is the same when read forwards or backwards. Find the sum of the two smallest palindromes that are multiples of $137$. [b]p12.[/b] Let $P(x) = x^2+px+q$ be a quadratic polynomial with positive integer coefficients. Compute the least possible value of p such that 220 divides p and the equation $P(x^3) = P(x)$ has at least four distinct integer solutions. [b]p13.[/b] Everyone at a math club is either a truth-teller, a liar, or a piggybacker. A truth-teller always tells the truth, a liar always lies, and a piggybacker will answer in the style of the previous person who spoke (i.e., if the person before told the truth, they will tell the truth, and if the person before lied, then they will lie). If a piggybacker is the first one to talk, they will randomly either tell the truth or lie. Four seniors in the math club were interviewed and here was their conversation: Neil: There are two liars among us. Lucy: Neil is a piggybacker. Kevin: Excluding me, there are more truth-tellers than liars here. Neil: Actually, there are more liars than truth-tellers if we exclude Kevin. Jacob: One plus one equals three. Define the base-$4$ number $M = \overline{NLKJ}_4$, where each digit is $1$ for a truth-teller, $2$ for a piggybacker, and $3$ for a liar ($N$ corresponds to Neil, $L$ to Lucy, $K$ corresponds to Kevin, and $J$ corresponds to Jacob). What is the sum of all possible values of $M$, expressed in base $10$? [b]p14.[/b] An equilateral triangle of side length $8$ is tiled by $64$ equilateral triangles of unit side length to form a triangular grid. Initially, each triangular cell is either living or dead. The grid evolves over time under the following rule: every minute, if a dead cell is edge-adjacent to at least two living cells, then that cell becomes living, and any living cell remains living. Given that every cell in the grid eventually evolves to be living, what is the minimum possible number of living cells in the initial grid? [b]p15.[/b] In triangle $ABC$, $AB = 7$, $BC = 11$, and $CA = 13$. Let $\Gamma$ be the circumcircle of $ABC$ and let $M$, $N$, and $P$ be the midpoints of minor arcs $BC$ , $CA$, and $AB$ of $\Gamma$, respectively. Given that $K$ denotes the area of $ABC$ and $L$ denotes the area of the intersection of $ABC$ and $MNP$, the ratio $L/K$ can be written as $a/b$ , where $a$ and $b$ are relatively prime positive integers. Compute $a + b$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In each cell of a table $8\times 8$ lives a knight or a liar. By the tradition, the knights always say the truth and the liars always lie. All the inhabitants of the table say the following statement "The number of liars in my column is (strictly) greater than the number of liars in my row". Determine how many possible configurations are compatible with the statement.

Let $x$ and $n$ be integers such that $1\le x\le n$. We have $x+1$ separate boxes and $n-x$ identical balls. Define $f(n,x)$ as the number of ways that the $n-x$ balls can be distributed into the $x+1$ boxes. Let $p$ be a prime number. Find the integers $n$ greater than $1$ such that the prime number $p$ is a divisor of $f(n,x)$ for all $x\in\{1,2,\ldots ,n-1\}$.

There are 20 people at a party. Each person holds some number of coins. Every minute, each person who has at least 19 coins simultaneously gives one coin to every other person at the party. (So, it is possible that $A$ gives $B$ a coin and $B$ gives $A$ a coin at the same time.) Suppose that this process continues indefinitely. That is, for any positive integer $n$, there exists a person who will give away coins during the $n$th minute. What is the smallest number of coins that could be at the party? [i]Proposed by Ray Li[/i]

For how many paths comsisting of a sequence of horizontal and/or vertical line segments, with each segment connecting a pair of adjacent letters in the diagram below, is the word $\textup{OLYMPIADS}$ spelled out as the path is traversed from beginning to end? $\begin{tabular}{ccccccccccccccccc}& & & & & & & & O & & & & & & & &\\ & & & & & & & O & L & O & & & & & & &\\ & & & & & & O & L & Y & L & O & & & & & &\\ & & & & & O & L & Y & M & Y & L & O & & & & &\\ & & & & O & L & Y & M & P & M & Y & L & O & & & &\\ & & & O & L & Y & M & P & I & P & M & Y & L & O & & &\\ & & O & L & Y & M & P & I & A & I & P & M & Y & L & O & &\\ & O & L & Y & M & P & I & A & D & A & I & P & M & Y & L & O &\\ O & L & Y & M & P & I & A & D & S & D & A & I & P & M & Y & L & O \end{tabular}$