For any polynomial $P(x)=a_0+a_1x+\ldots+a_kx^k$ with integer coefficients, the number of odd coefficients is denoted by $o(P)$. For $i-0,1,2,\ldots$ let $Q_i(x)=(1+x)^i$. Prove that if $i_1,i_2,\ldots,i_n$ are integers satisfying $0\le i_1<i_2<\ldots<i_n$, then: \[ o(Q_{i_{1}}+Q_{i_{2}}+\ldots+Q_{i_{n}})\ge o(Q_{i_{1}}). \]

There is an empty table with $2^{100}$ rows and $100$ columns. Alice and Eva take turns filling the empty cells of the first row of the table, Alice plays first. In each move, Alice chooses an empty cell and puts a cross in it; Eva in each move chooses an empty cell and puts a zero. When no empty cells remain in the first row, the players move on to the second row, and so on (in each new row Alice plays first). The game ends when all the rows are filled. Alice wants to make as many different rows in the table as possible, while Eva wants to make as few as possible. How many different rows will be there in the table if both follow their best strategies? Proposed by Denis Afrizonov

Determine the smallest integer $n \ge 2012$ for which it is possible to have $16$ consecutive integers on a $4 \times 4$ board so that, if we select $4$ elements of which there are not two in the same row or in the same column, the sum of them is always equal to $n$. For the $n$ found, show how to fill the board.

Chandler the Octopus is at a tentacle party! At this party, there is $1$ creature with $2$ tentacles, $2$ creatures with $3$ tentacles, $3$ creatures with $4$ tentacles, all the way up to $14$ creatures with $15$ tentacles. Each tentacle is distinguishable from all other tentacles. For some $2\le m < n \le 15$, a creature with m tentacles “meets” a creature with n tentacles; “meeting” another creature consists of shaking exactly 1 tentacle with each other. Find the number of ways there are to pick distinct $m < n$ between $2$ and $15$, inclusive, and then to pick a creature with $m$ tentacles to “meet” a selected creature with $n$ tentacles. [i]Proposed by Armaan Tipirneni, Richard Chen, and Denise the Octopus[/i]

There is an ant on every vertex of a unit cube. At the time zero, ants start to move across the edges with the velocity of one unit per minute. If an ant reaches a vertex, it alternatively turns right and left (for the first time it will turn in a random direction). If two or more ants meet anywhere on the cube, they die! We know an ant survives after three minutes. Prove that there exists an ant that never dies!

Ten points are marked in the plane so that no three of them lie on the same straight line. All points are connected with segments.Each of these segments is painted one of the $k$ colors. For what positive integer $k$ ($1 \le k \le 5$) is it possible to paint the segments so that for any $k$ of the given $10$ points there are $k$ segments with the ends at these $k$ points, all of these segments being painted $k$ different colors ? (E. Barabanov)

Let it \(k\) be a fixed positive integer. Alberto and Beralto play the following game: Given an initial number \(N_0\) and starting with Alberto, they alternately do the following operation: change the number \(n\) for a number \(m\) such that \(m < n\) and \(m\) and \(n\) differ, in its base-2 representation, in exactly \(l\) consecutive digits for some \(l\) such that \(1 \leq l \leq k\). If someone can't play, he loses. We say a non-negative integer \(t\) is a [i]winner[/i] number when the gamer who receives the number \(t\) has a winning strategy, that is, he can choose the next numbers in order to guarrantee his own victory, regardless the options of the other player. Else, we call it [i]loser[/i]. Prove that, for every positive integer \(N\), the total of non-negative loser integers lesser than \(2^N\) is \(2^{N-\lfloor \frac{log(min\{N,k\})}{log 2} \rfloor}\)

Let $M$ be a finite sum of numbers, such that among any three of its elements there are two whose sum belongs to $M$. Find the greatest possible number of elements of $M$.

For what positive integers $n$ is it possible to tile an equilateral triangle of side $n$ with trapezoids each of which has sides $1, 1, 1, 2$? (NB Vassiliev)

A polyhedron has an even number of edges. Show that we can place an arrow on each edge so that each vertex has an even number of arrows pointing towards it (on adjacent edges).

A mathematician is walking through a library with twenty-six shelves, one for each letter of the alphabet. As he walks, the mathematician will take at most one book off each shelf. He likes symmetry, so if the letter of a shelf has at least one line of symmetry (e.g., M works, L does not), he will pick a book with probability $\frac12$. Otherwise he has a $\frac14$ probability of taking a book. What is the expected number of books that the mathematician will take?

Newton and Leibniz are playing a game with a coin that comes up heads with probability $p$. They take turns flipping the coin until one of them wins with Newton going first. Newton wins if he flips a heads and Leibniz wins if he flips a tails. Given that Newton and Leibniz each win the game half of the time, what is the probability $p$?

Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).

Among the $5$-sided polygons, as many vertices as possible collinear , that is, belonging to a single line, is three, as shown below. What is the largest number of collinear vertices a $12$-sided polygon can have? [img]https://cdn.artofproblemsolving.com/attachments/1/1/53d419efa4fc4110730a857ae6988fc923eb13.png[/img] Attention: In addition to drawing a $12$-sided polygon with the maximum number of vertices collinear , remember to show that there is no other $12$-sided polygon with more vertices collinear than this one.

Let $G$ be a simple graph with $3n^2$ vertices ($n\geq 2$). It is known that the degree of each vertex of $G$ is not greater than $4n$, there exists at least a vertex of degree one, and between any two vertices, there is a path of length $\leq 3$. Prove that the minimum number of edges that $G$ might have is equal to $\frac{(7n^2- 3n)}{2}$.

Suppose that $p(n)$ is the number of partitions of a natural number $n$. Prove that there exists $c>0$ such that $P(n)\ge n^{c \cdot \log n}$. [i]proposed by Mohammad Mansouri[/i]

Let $n>2$ be an integer. In a country there are $n$ cities and every two of them are connected by a direct road. Each road is assigned an integer from the set $\{1, 2,\ldots ,m\}$ (different roads may be assigned the same number). The [i]priority[/i] of a city is the sum of the numbers assigned to roads which lead to it. Find the smallest $m$ for which it is possible that all cities have a different priority.

You start with a single piece of chalk of length $1$. Every second, you choose a piece of chalk that you have uniformly at random and break it in half. You continue this until you have $8$ pieces of chalk. What is the probability that they all have length $\frac18$ ?

A positive integer $n$ is called $omopeiro$ if there exists $n$ non-zero integers that are not necessarily distinct such that $2021$ is the sum of the squares of those $n$ integers. For example, the number $2$ is not an $omopeiro$, because $2021$ is not a sum of two non-zero squares, but $2021$ is an $omopeiro$, because $2021=1^2+1^2+ \dots +1^2$, which is a sum of $2021$ squares of the number $1$. Prove that there exist more than 1500 $omopeiro$ numbers. Note: proving that there exist at least 500 $omopeiro$ numbers is worth 2 points.

[b]p1.[/b] Find the area of a right triangle with legs of lengths $20$ and $18$. [b]p2.[/b] How many $4$-digit numbers (without leading zeros) contain only $2,0,1,8$ as digits? Digits can be used more than once. [b]p3.[/b] A rectangle has perimeter $24$. Compute the largest possible area of the rectangle. [b]p4.[/b] Find the smallest positive integer with $12$ positive factors, including one and itself. [b]p5.[/b] Sammy can buy $3$ pencils and $6$ shoes for $9$ dollars, and Ben can buy $4$ pencils and $4$ shoes for $10$ dollars at the same store. How much more money does a pencil cost than a shoe? [b]p6.[/b] What is the radius of the circle inscribed in a right triangle with legs of length $3$ and $4$? [b]p7.[/b] Find the angle between the minute and hour hands of a clock at $12 : 30$. [b]p8.[/b] Three distinct numbers are selected at random fromthe set $\{1,2,3, ... ,101\}$. Find the probability that $20$ and $18$ are two of those numbers. [b]p9.[/b] If it takes $6$ builders $4$ days to build $6$ houses, find the number of houses $8$ builders can build in $9$ days. [b]p10.[/b] A six sided die is rolled three times. Find the probability that each consecutive roll is less than the roll before it. [b]p11.[/b] Find the positive integer $n$ so that $\frac{8-6\sqrt{n}}{n}$ is the reciprocal of $\frac{80+6\sqrt{n}}{n}$. [b]p12.[/b] Find the number of all positive integers less than $511$ whose binary representations differ from that of $511$ in exactly two places. [b]p13.[/b] Find the largest number of diagonals that can be drawn within a regular $2018$-gon so that no two intersect. [b]p14.[/b] Let $a$ and $b$ be positive real numbers with $a > b $ such that $ab = a +b = 2018$. Find $\lfloor 1000a \rfloor$. Here $\lfloor x \rfloor$ is equal to the greatest integer less than or equal to $x$. [b]p15.[/b] Let $r_1$ and $r_2$ be the roots of $x^2 +4x +5 = 0$. Find $r^2_1+r^2_2$ . [b]p16.[/b] Let $\vartriangle ABC$ with $AB = 5$, $BC = 4$, $C A = 3$ be inscribed in a circle $\Omega$. Let the tangent to $\Omega$ at $A$ intersect $BC$ at $D$ and let the tangent to $\Omega$ at $B$ intersect $AC$ at $E$. Let $AB$ intersect $DE$ at $F$. Find the length $BF$. [b]p17.[/b] A standard $6$-sided die and a $4$-sided die numbered $1, 2, 3$, and $4$ are rolled and summed. What is the probability that the sum is $5$? [b]p18.[/b] Let $A$ and $B$ be the points $(2,0)$ and $(4,1)$ respectively. The point $P$ is on the line $y = 2x +1$ such that $AP +BP$ is minimized. Find the coordinates of $P$. [b]p19.[/b] Rectangle $ABCD$ has points $E$ and $F$ on sides $AB$ and $BC$, respectively. Given that $\frac{AE}{BE}=\frac{BF}{FC}= \frac12$, $\angle ADE = 30^o$, and $[DEF] = 25$, find the area of rectangle $ABCD$. [b]p20.[/b] Find the sum of the coefficients in the expansion of $(x^2 -x +1)^{2018}$. [b]p21.[/b] If $p,q$ and $r$ are primes with $pqr = 19(p+q+r)$, find $p +q +r$ . [b]p22.[/b] Let $\vartriangle ABC$ be the triangle such that $\angle B$ is acute and $AB < AC$. Let $D$ be the foot of altitude from $A$ to $BC$ and $F$ be the foot of altitude from $E$, the midpoint of $BC$, to $AB$. If $AD = 16$, $BD = 12$, $AF = 5$, find the value of $AC^2$. [b]p23.[/b] Let $a,b,c$ be positive real numbers such that (i) $c > a$ (ii) $10c = 7a +4b +2024$ (iii) $2024 = \frac{(a+c)^2}{a}+ \frac{(c+a)^2}{b}$. Find $a +b +c$. [b]p24.[/b] Let $f^1(x) = x^2 -2x +2$, and for $n > 1$ define $f^n(x) = f ( f^{n-1}(x))$. Find the greatest prime factor of $f^{2018}(2019)-1$. [b]p25.[/b] Let $I$ be the incenter of $\vartriangle ABC$ and $D$ be the intersection of line that passes through $I$ that is perpendicular to $AI$ and $BC$. If $AB = 60$, $C A =120$, and $CD = 100$, find the length of $BC$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Ten sportsmen have taken part in a table-tennis tournament (each pair has met once only, no draws). Let $xi$ be the number of $i$-th player victories, $yi$ -- losses. Prove that $$x_1^2 + ... + x_{10}^2 = y_1^2 + ... + y_{10}^2$$

Let $n\ge3$ be a positive integer. Each edge of a complete graph $K_n$ is assigned a real number satisfying the following conditions: $(i)$ For any three vertices, the numbers assigned to two of the edges among them are equal, and the number on the third edge is strictly greater. $(ii) $ The weight of a vertex is defined as the sum of the numbers assigned to the edges emanating from that vertex. The weights of all vertices are equal. Find all possible values of $n$.

How many five-card hands from a standard deck of $52$ cards are full houses? A full house consists of $3$ cards of one rank and $2$ cards of another rank.

Let $A = \{1,2,3, . . . ,11\}$. How many subsets $B$ of $A$ are there, such that for each $n\in \{1,2, . . . ,8\}$, if $n$ and $n+2$ are in $B$ then at least one of the numbers $ n+1$ and $n+3$ is also in $B$?

Two people play a game as follows: At the beginning both of them have one point and in every move, one of them can double it's points, or when the other have more point than him, subtract to him his points. Can the two competitors have 2009 and 2002 points respectively? What about 2009 and 2003? Generally which couples of points can they have?