Compute the number of sets $S$ such that every element of $S$ is a nonnegative integer less than 16, and if $x\in S$ then $(2x\bmod{16})\in S$.

Evariste has drawn twelve triangles as follows, so that two consecutive triangles share exactly one edge. [img]https://cdn.artofproblemsolving.com/attachments/6/2/50377e7ad5fb1c40e36725e43c7eeb1e3c2849.png[/img] Sophie colors every triangle side in red, green or blue. Among the $3^{24}$ possible colorings, how many have the property that every triangle has one edge of each color?

The cities of Terra Brasilis are connected by some roads. There are no two cities directly connected by more than one road. It is known that it is possible to go from one city to any other using one or more roads. We call [i]role[/i] any closed road route (ie, it starts in a city and ends in the same city) that does not pass through a city more than once. At Terra Brasilis, all roles go through an odd number of cities. The government of Terra Brasilis decided to close some roles for reform. When you close a role, all it;s roads are closed, so traffic is not allowed on these roads. By doing this, Terra Brasilis was divided into several regions such that from any city in each region it is possible to reach any other in the same region by road, but it is not possible to reach cities in other regions. Prove that the number of regions is odd [hide=original wording]As cidades da Terra Brasilis sao conectadas por algumas estradas. Nao ha duas cidades conectadas diretamente por mais de uma estrada. Sabe-se que, e possivel ir de uma cidade para qualquer outra utilizando uma ou mais estradas. Chamamos de rol^e qualquer rota fechada de estradas (isto e, comeca em uma cidade e termina na mesma cidade) que nao passa por uma cidade mais de uma vez. Na Terra Brasilis, todos os roles passam por quantidades impares de cidades. O governo da Terra Brasilis decidiu fechar alguns roles para reforma. Ao fechar um role, todas as suas estradas sao interditadas, de modo que nao e permitido o trafego nessas estradas. Ao fazer isso, a Terra Brasilis ficou dividida em varias regioes de modo que, de qualquer cidade de cada regiao e possivel hegar a qualquer outra da mesma regiao atraves de estradas, mas nao e possivel hegar a cidades de outras regioes. Prove que o numero de regioes e impar.[/hide]

Exactly one integer is written in each square of an $n$ by $n$ grid, $n \ge 3$. The sum of all of the numbers in any $2 \times 2$ square is even and the sum of all the numbers in any $3 \times 3$ square is even. Find all $n$ for which the sum of all the numbers in the grid is necessarily even.

Vishal starts with $n$ copies of the number $1$ written on the board. Every minute, he takes two numbers $a, b$ and replaces them with either $a+b$ or $\min(a^2, b^2)$. After $n-1$ there is $1$ number on the board. Let the maximal possible value of this number be $f(n)$. Prove $2^{n/3}<f(n)\leq 3^{n/3}$.

The best part of grandma’s $18$ cm $\times 36$ cm rectangle-shaped cake is the chocolate covering on the edges. Her three grandchildren would like to split the cake between each other so that everyone gets the same amount (of the area) of the cake, and they all get the same amount of the delicious perimeter too. a) Can they cut the cake into three convex pieces like that? b) The next time grandma baked this cake, the whole family wanted to try it so they had to cut the cake into six convex pieces this way. Is this possible? c) Soon the entire neighbourhood has heard of the delicious cake. Can the cake be cut into $12$ convex pieces with the same conditions?

Let $ G$ be a connected graph with $ n$ vertices and $ m$ edges such that each edge is contained in at least one triangle. Find the minimum value of $ m$.

On the plane are given $ k\plus{}n$ distinct lines , where $ k>1$ is integer and $ n$ is integer as well.Any three of these lines do not pass through the same point . Among these lines exactly $ k$ are parallel and all the other $ n$ lines intersect each other.All $ k\plus{}n$ lines define on the plane a partition of triangular , polygonic or not bounded regions. Two regions are colled different, if the have not common points or if they have common points only on their boundary.A regions is called ''good'' if it contained in a zone between two parallel lines . If in a such given configuration the minimum number of ''good'' regionrs is $ 176$ and the maximum number of these regions is $ 221$, find $ k$ and $ n$. Babis

Ten points are marked in the plane so that no three of them lie on a line. Each pair of points is connected with a segment. Each of these segments is painted with one of $k$ colors, in such a way that for any $k$ of the ten points, there are $k$ segments each joining two of them and no two being painted with the same color. Determine all integers $k$, $1\leq k\leq 10$, for which this is possible.

[i]25 problems for 30 minutes[/i] [b]p1.[/b] Somya has a football game $4$ days from today. If the day before yesterday was Wednesday, what day of the week is the game? [b]p2.[/b] Sammy writes the following equation: $$\frac{2 + 2}{8 + 8}=\frac{x}{8}.$$ What is the value of $x$ in Sammy's equation? [b]p3.[/b] On $\pi$ day, Peter buys $7$ pies. The pies costed $\$3$, $\$1$, $\$4$, $\$1$, $\$5$, $\$9$, and $\$2$. What was the median price of Peter's $7$ pies in dollars? [b]p4.[/b] Antonio draws a line on the coordinate plane. If the line passes through the points ($1, 3$) and ($-1,-1$), what is slope of the line? [b]p5.[/b] Professor Varun has $25$ students in his science class. He divides his students into the maximum possible number of groups of $4$, but $x$ students are left over. What is $x$? [b]p6.[/b] Evaluate the following: $$4 \times 5 \div 6 \times 3 \div \frac47$$ [b]p7.[/b] Jonny, a geometry expert, draws many rectangles with perimeter $16$. What is the area of the largest possible rectangle he can draw? [b]p8.[/b] David always drives at $60$ miles per hour. Today, he begins his trip to MIT by driving $60$ miles. He stops to take a $20$ minute lunch break and then drives for another $30$ miles to reach the campus. What is the total time in minutes he spends getting to MIT? [b]p9.[/b] Richard has $5$ hats: blue, green, orange, red, and purple. Richard also has 5 shirts of the same colors: blue, green, orange, red, and purple. If Richard needs a shirt and a hat of different colors, how many outts can he wear? [b]p10.[/b] Poonam has $9$ numbers in her bag: $1, 2, 3, 4, 5, 6, 7, 8, 9$. Eric runs by with the number $36$. How many of Poonam's numbers evenly divide Eric's number? [b]p11.[/b] Serena drives at $45$ miles per hour. If her car runs at $6$ miles per gallon, and each gallon of gas costs $2$ dollars, how many dollars does she spend on gas for a $135$ mile trip? [b]p12.[/b] Grace is thinking of two integers. Emmie observes that the sum of the two numbers is $56$ but the difference of the two numbers is $30$. What is the sum of the squares of Grace's two numbers? [b]p13.[/b] Chang stands at the point ($3,-3$). Fang stands at ($-3, 3$). Wang stands in-between Chang and Fang; Wang is twice as close to Fang as to Chang. What is the ordered pair that Wang stands at? [b]p14.[/b] Nithin has a right triangle. The longest side has length $37$ inches. If one of the shorter sides has length $12$ inches, what is the perimeter of the triangle in inches? [b]p15.[/b] Dora has $2$ red socks, $2$ blue socks, $2$ green socks, $2$ purple socks, $3$ black socks, and $4$ gray socks. After a long snowstorm, her family loses electricity. She picks socks one-by-one from the drawer in the dark. How many socks does she have to pick to guarantee a pair of socks that are the same color? [b]p16.[/b] Justin selects a random positive $2$-digit integer. What is the probability that the sum of the two digits of Justin's number equals $11$? [b]p17.[/b] Eddie correctly computes $1! + 2! + .. + 9! + 10!$. What is the remainder when Eddie's sum is divided by $80$? [b]p18.[/b] $\vartriangle PQR$ is drawn such that the distance from $P$ to $\overline{QR}$ is $3$, the distance from $Q$ to $\overline{PR}$ is $4$, and the distance from $R$ to $\overline{PQ}$ is $5$. The angle bisector of $\angle PQR$ and the angle bisector of $\angle PRQ$ intersect at $I$. What is the distance from $I$ to $\overline{PR}$? [b]p19.[/b] Maxwell graphs the quadrilateral $|x - 2| + |y + 2| = 6$. What is the area of the quadrilateral? [b]p20.[/b] Uncle Gowri hits a speed bump on his way to the hospital. At the hospital, patients who get a rare disease are given the option to choose treatment $A$ or treatment $B$. Treatment $A$ will cure the disease $\frac34$ of the time, but since the treatment is more expensive, only $\frac{8}{25}$ of the patients will choose this treatment. Treatment $B$ will only cure the disease $\frac{1}{2}$ of the time, but since it is much more aordable, $\frac{17}{25}$ of the patients will end up selecting this treatment. Given that a patient was cured, what is the probability that the patient selected treatment $A$? [b]p21.[/b] In convex quadrilateral $ABCD$, $AC = 28$ and $BD = 15$. Let $P, Q, R, S$ be the midpoints of $AB$, $BC$, $CD$ and $AD$ respectively. Compute $PR^2 + QS^2$. [b]p22.[/b] Charlotte writes the polynomial $p(x) = x^{24} - 6x + 5$. Let its roots be $r_1$, $r_2$, $...$, $r_{24}$. Compute $r^{24}_1 +r^{24}_2 + r^{24}_3 + ... + r^{24}_24$. [b]p23.[/b] In rectangle $ABCD$, $AB = 6$ and $BC = 4$. Let $E$ be a point on $CD$, and let $F$ be the point on $AB$ which lies on the bisector of $\angle BED$. If $FD^2 + EF^2 = 52$, what is the length of $BE$? [b]p24.[/b] In $\vartriangle ABC$, the measure of $\angle A$ is $60^o$ and the measure of $\angle B$ is $45^o$. Let $O$ be the center of the circle that circumscribes $\vartriangle ABC$. Let $I$ be the center of the circle that is inscribed in $\vartriangle ABC$. Finally, let $H$ be the intersection of the $3$ altitudes of the triangle. What is the angle measure of $\angle OIH$ in degrees? [b]p25.[/b] Kaitlyn fully expands the polynomial $(x^2 + x + 1)^{2018}$. How many of the coecients are not divisible by $3$? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Alberto and Barbara are sitting one next to each other in front of a table onto which they arranged in a line $15$ chocolates. Some of them are milk chocolates, while the others are dark chocolates. Starting from Alberto, they play the following game: during their turn, each player eats a positive number of consecutive chocolates, starting from the leftmost of the remaining ones, so that the number of chocolates eaten that are of the same type as the first one is odd (for example, if after some turns the sequence of the remaining chocolates is $\text{MMDMD},$ where $\text{M}$ stands for $\emph{milk}$ and $\text{D}$ for $\emph{dark},$ the player could either eat the first chocolate, the first $4$ chocolates or all $5$ of them). The player eating the last chocolate wins. Among all $2^{15}$ possible initial sequences of chocolates, how many of them allow Barbara to have a winning strategy?

How many a) bishops b) horses can be positioned on a chessboard at most, so that no one threatens another?

We call a finite plane set $S$ consisting of points with integer coefficients a two-neighbour set, if for each point $(p, q)$ of $S$ exactly two of the points $(p +1, q), (p, q +1), (p-1, q), (p, q-1)$ belong to $S$. For which integers $n$ there exists a two-neighbour set which contains exactly $n$ points?

Inside a square with side lengths $1$ a broken line of length $>1000$ without selfintersection is drawn. Show that there is a line parallel to a side of the square that intersects the broken line in at least $501$ points.

Let $n$ be a positive integer. Lavi Dopes has two boards $n \times n$. On the first board, he writes an integer in each of his $n^2$ squares (the written numbers are not necessarily distinct). On the second board, he writes, on each square, the sum of the numbers corresponding, on the first board, to that square and to all its adjacent squares (that is, those that share a common vertex). For example, if $n = 3$ and if Lavi Dopes writes the numbers on the first board, as shown below, the second board will look like this. Next, Davi Lopes receives only the second board, and from it, he tries to discover the numbers written by Lavi Dopes on the first board. (a) If $n = 4$, is it possible that Davi Lopes always manages to find the numbers written by Lavi Dopes on the first board? (b) If $n = 5$, is it possible that Davi Lopes always manages to find the numbers written by Lavi Dopes on the first board?

How many ways are there to color the vertices of a square with $n$ colors $1,2, .. ., n$. (The colorings must be different so that we can’t get one from the other by a rotation.)

$100$ points are given in space such that no four of them lie in the same plane. Consider those convex polyhedra with five vertices that have all vertices from the given set. Prove that the number of such polyhedra is even.

In an $m\times n$ rectangular chessboard,there is a stone in the lower leftmost square. Two persons A,B move the stone alternately. In each step one can move the stone upward or rightward any number of squares. The one who moves it into the upper rightmost square wins. Find all $(m,n)$ such that the first person has a winning strategy.

All cells of the $m\times n$ table are colored either white or black such that all corner cells of any rectangle containing the cells of this table with sides greater than one cell are not the same color. For values $m = 2, 3, 4,$ find all $n$ such that the mentioned coloring is possible.

In a $3n \times 3n$ grid, each square is either black or red. Each red square not on the edge of the grid has exactly five black squares among its eight neighbor squares.. On every black square that not at the edge of the grid, there are exactly four reds in the adjacent squares box. How many black and how many red squares are in the grid?

The number $10^{2007}$ is written on the blackboard. Anne and Berit play a two player game in which the player in turn performs one of the following operations: 1) replace a number $x$ on the blackboard with two integers $a,b>1$ such that $ab=x$. 2) strike off one or both of two equal numbers on the blackboard. The person who cannot perform any operation loses. Who has the winning strategy if Anne starts?

Each edge of a complete graph with $101$ vertices is marked with $1$ or $-1$. It is known that absolute value of the sum of numbers on all the edges is less than $150$. Prove that the graph contains a path visiting each vertex exactly once such that the sum of numbers on all edges of this path is zero. [i](Y. Caro, A. Hansberg, J. Lauri, C. Zarb)[/i]

In an archery competition of 30 contestants, the target is divided into two zones, zone 1 and zone 2. Each arrow hitting the zone 1 gets 10 points, when hitting zone 2 will get 5 points and no score for miss. Each contestant throws 16 arrows. At the end of the competition, the statistics show that more than 50% of the arrows hit zone 2. The number of arrows that hit zone 1 is equal to the arrows which are missed. Prove than there are two contestants having equal score.

Is it possible to cover a $2003 \times 2003$ chessboard (without overlap) using only horizontal $1 \times 2$ dominoes and only vertical $3 \times 1$ trominoes?

Several distinct real numbers are written on a blackboard. Peter wants to create an algebraic expression such that among its values there would be these and only these numbers. He may use any real numbers, brackets, signs $+, -, \times$ and a special sign $\pm$. Usage of $\pm$ is equivalent to usage of $+$ and $-$ in all possible combinations. For instance, the expression $5 \pm 1$ results in $\{4, 6\}$, while $(2 \pm 0.5) \pm 0.5$ results in $\{1, 2, 3\}$. Can Peter construct an expression if the numbers on the blackboard are : (a) $1, 2, 4$ ? [i]($2$ points)[/i] (b) any $100$ distinct real numbers ? [i]($6$ points)[/i]