The plane is divided into equal squares by parallel lines; i.e., a square net is given. Let $M$ be an arbitrary set of $n$ squares of this net. Prove that it is possible to choose no fewer than $n/4$ squares of $M$ in such a way that no two of them have a common point.

Soma has a tower of $63$ bricks , consisting of $6$ levels. On the $k$-th level from the top, there are $2k-1$ bricks (where $k = 1, 2, 3, 4, 5, 6$), and every brick which is not on the lowest level lies on precisely $2$ smaller bricks (which lie one level below) - see the figure. Soma takes away $7$ bricks from the tower, one by one. He can only remove a brick if there is no brick lying on it. In how many ways can he do this, if the order of removals is considered as well? [img]https://cdn.artofproblemsolving.com/attachments/b/6/4b0ce36df21fba89708dd5897c43a077d86b5e.png[/img]

Decomposition of number $n$ is showing $n$ as a sum of positive integers (not neccessarily distinct). Order of addends is important. For every positive integer $n$ show that number of decompositions is $2^{n-1}$

For a set $S \subseteq \mathbb{N}$, define $f(S) = \{\left\lceil \sqrt{s} \right\rceil \mid s \in S\}$. Find the number of sets $T$ such that $\vert f(T) \vert = 2$ and $f(f(T)) = \{2\}$.

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$.

[i]20 problems for 20 minutes.[/i] [b]p1.[/b] Euclid eats $\frac17$ of a pie in $7$ seconds. Euler eats $\frac15$ of an identical pie in $10$ seconds. Who eats faster? [b]p2.[/b] Given that $\pi = 3.1415926...$ , compute the circumference of a circle of radius 1. Express your answer as a decimal rounded to the nearest hundred thousandth (i.e. $1.234562$ and $1.234567$ would be rounded to $1.23456$ and $1.23457$, respectively). [b]p3.[/b] Alice bikes to Wonderland, which is $6$ miles from her house. Her bicycle has two wheels, and she also keeps a spare tire with her. If each of the three tires must be used for the same number of miles, for how many miles will each tire be used? [b]p4.[/b] Simplify $\frac{2010 \cdot 2010}{2011}$ to a mixed number. (For example, $2\frac12$ is a mixed number while $\frac52$ and $2.5$ are not.) [b]p5.[/b] There are currently $175$ problems submitted for $EMC^2$. Chris has submitted $51$ of them. If nobody else submits any more problems, how many more problems must Chris submit so that he has submitted $\frac13$ of the problems? [b]p6.[/b] As shown in the diagram below, points $D$ and $L$ are located on segment $AK$, with $D$ between $A$ and $L$, such that $\frac{AD}{DK}=\frac{1}{3}$ and $\frac{DL}{LK}=\frac{5}{9}$. What is $\frac{DL}{AK}$? [img]https://cdn.artofproblemsolving.com/attachments/9/a/3f92bd33ffbe52a735158f7ebca79c4c360d30.png[/img] [b]p7.[/b] Find the number of possible ways to order the letters $G, G, e, e, e$ such that two neighboring letters are never $G$ and $e$ in that order. [b]p8.[/b] Find the number of odd composite integers between $0$ and $50$. [b]p9.[/b] Bob tries to remember his $2$-digit extension number. He knows that the number is divisible by $5$ and that the first digit is odd. How many possibilities are there for this number? [b]p10.[/b] Al walks $1$ mile due north, then $2$ miles due east, then $3$ miles due south, and then $4$ miles due west. How far, in miles, is he from his starting position? (Assume that the Earth is flat.) [b]p11.[/b] When n is a positive integer, $n!$ denotes the product of the first $n$ positive integers; that is, $n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$. Given that $7! = 5040$, compute $8! + 9! + 10!$. [b]p12.[/b] Sam's phone company charges him a per-minute charge as well as a connection fee (which is the same for every call) every time he makes a phone call. If Sam was charged $\$4.88$ for an $11$-minute call and $\$6.00$ for a $19$-minute call, how much would he be charged for a $15$-minute call? [b]p13.[/b] For a positive integer $n$, let $s_n$ be the sum of the n smallest primes. Find the least $n$ such that $s_n$ is a perfect square (the square of an integer). [b]p14.[/b] Find the remainder when $2011^{2011}$ is divided by $7$. [b]p15.[/b] Let $a, b, c$, and $d$ be $4$ positive integers, each of which is less than $10$, and let $e$ be their least common multiple. Find the maximum possible value of $e$. [b]p16.[/b] Evaluate $100 - 1 + 99 - 2 + 98 - 3 + ... + 52 - 49 + 51 - 50$. [b]p17.[/b] There are $30$ basketball teams in the Phillips Exeter Dorm Basketball League. In how ways can $4$ teams be chosen for a tournament if the two teams Soule Internationals and Abbot United cannot be chosen at the same time? [b]p18.[/b] The numbers $1, 2, 3, 4, 5, 6$ are randomly written around a circle. What is the probability that there are four neighboring numbers such that the sum of the middle two numbers is less than the sum of the other two? [b]p19.[/b] What is the largest positive $2$-digit factor of $3^{2^{2011}} - 2^{2^{2011}}$? [b]p20.[/b] Rhombus $ABCD$ has vertices $A = (-12,-4)$, $B = (6, b)$, $C = (c,-4)$ and $D = (d,-28)$, where $b$, $c$, and $d$ are integers. Find a constant $m$ such that the line y = $mx$ divides the rhombus into two regions of equal area. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[i]25 problems for 30 minutes[/i] [b]p1.[/b] Today is Saturday, April $25$, $2020$. What is the value of $6 + 4 + 25 + 2020$? [b]p2.[/b] The figure below consists of a $2$ by $3$ grid of squares. How many squares of any size are in the grid? $\begin{tabular}{|l|l|l|} \hline & & \\ \hline & & \\ \hline \end{tabular}$ [b]p3.[/b] James is playing a game. He first rolls a six-sided dice which contains a different number on each side, then randomly picks one of twelve dierent colors, and finally ips a quarter. How many different possible combinations of a number, a color and a flip are there in this game? [b]p4.[/b] What is the sum of the number of diagonals and sides in a regular hexagon? [b]p5.[/b] Mickey Mouse and Minnie Mouse are best friends but they often fight. Each of their fights take up exactly one hour, and they always fight on prime days. For example, they fight on January $2$nd, $3$rd, but not the $4$th. Knowing this, how many total times do Mickey and Minnie fight in the months of April, May and June? [b]p6.[/b] Apple always loved eating watermelons. Normal watermelons have around $13$ black seeds and $25$ brown seeds, whereas strange watermelons had $45$ black seeds and $2$ brown seeds. If Apple bought $14$ normal watermelons and $7$ strange watermelons, then let $a$ be the total number of black seeds and $b$ be the total number of brown seeds. What is $a - b$? [b]p7.[/b] Jerry and Justin both roll a die once. The probability that Jerry's roll is greater than Justin's can be expressed as a fraction in the form $\frac{m}{n}$ in simplified terms. What is $m + n$? [b]p8.[/b] Taylor wants to color the sides of an octagon. What is the minimum number of colors Taylor will need so that no adjacent sides of the octagon will be filled in with the same color? [b]p9.[/b] The point $\frac23$ of the way from ($-6, 8$) to ($-3, 5$) can be expressed as an ordered pair $(a, b)$. What is $|a - b|$? [b]p10.[/b] Mary Price Maddox laughs $7$ times per class. If she teaches $4$ classes a day for the $5$ weekdays every week but doesn't laugh on Wednesdays, then how many times does she laugh after $5$ weeks of teaching? [b]p11.[/b] Let $ABCD$ be a unit square. If $E$ is the midpoint of $AB$ and $F$ lies inside $ABCD$ such that $CFD$ is an equilateral triangle, the positive difference between the area of $CED$ and $CFD$ can be expressed in the form $\frac{a-\sqrt{b}}{c}$ , where $a$, $b$, $c$ are in lowest simplified terms. What is $a + b + c$? [b]p12.[/b] Eddie has musician's syndrome. Whenever a song is a $C$, $A$, or $F$ minor, he begins to cry and his body becomes very stiff. On the other hand, if the song is in $G$ minor, $A$ at major, or $E$ at major, his eyes open wide and he feels like the happiest human being ever alive. There are a total of $24$ keys. How many different possibilities are there in which he cries while playing one song with two distinct keys? [b]p13.[/b] What positive integer must be added to both the numerator and denominator of $\frac{12}{40}$ to make a fraction that is equivalent to $\frac{4}{11}$ ? [b]p14.[/b] The number $0$ is written on the board. Each minute, Gene the genie either multiplies the number on the board by $3$ or $9$, each with equal probability, and then adds either $1$,$2$, or $3$, each with equal probability. Find the expected value of the number after $3$ minutes. [b]p15.[/b] $x$ satisfies $\dfrac{1}{x+ \dfrac{1}{1+\frac{1}{2}}}=\dfrac{1}{2+ \dfrac{1}{1- \dfrac{1}{2+\frac{1}{2}}}}$ Find $x$. [b]p16.[/b] How many different points in a coordinate plane can a bug end up on if the bug starts at the origin and moves one unit to the right, left, up or down every minute for $8$ minutes? [b]p17.[/b] The triplets Addie, Allie, and Annie, are racing against the triplets Bobby, Billy, and Bonnie in a relay race on a track that is $100$ feet long. The first person of each team must run around the entire track twice and tag the second person for the second person to start running. Then, the second person must run once around the entire track and tag the third person, and finally, the third person would only have to run around half the track. Addie and Bob run first, Allie and Billy second, Annie and Bonnie third. Addie, Allie, and Annie run at $50$ feet per minute (ft/m), $25$ ft/m, and $20$ ft/m, respectively. If Bob, Billy, and Bonnie run half as fast as Addie, Allie, and Annie, respectively, then how many minutes will it take Bob, Billy, and Bonnie to finish the race. Assume that everyone runs at a constant rate. [b]p18.[/b] James likes to play with Jane and Jason. If the probability that Jason and Jane play together is $\frac13$, while the probability that James and Jason is $\frac14$ and the probability that James and Jane play together is $\frac15$, then the probability that they all play together is $\frac{\sqrt{p}}{q}$ for positive integers $p$, $q$ where $p$ is not divisible by the square of any prime. Find $p + q$. [b]p19.[/b] Call an integer a near-prime if it is one more than a prime number. Find the sum of all near-primes less than$ 1000$ that are perfect powers. (Note: a perfect power is an integer of the form $n^k$ where $n, k \ge 2$ are integers.) [b]p20.[/b] What is the integer solution to $\sqrt{\frac{2x-6}{x-11}} = \frac{3x-7}{x+6}$ ? [b]p21.[/b] Consider rectangle $ABCD$ with $AB = 12$ and $BC = 4$ with $F$,$G$ trisecting $DC$ so that $F$ is closer to $D$. Then $E$ is on $AB$. We call the intersection of $EF$ and $DB$ $X$, and the intersection of $EG$ and $DB$ is $Y$. If the area of $\vartriangle XY E$ is \frac{8}{15} , then what is the length of $EB$? [b]p22.[/b] The sum $$\sum^{\infty}_{n=2} \frac{1}{4n^2-1}$$ can be expressed as a common fraction $\frac{a}{b}$ in lowest terms. Find $a + b$. [b]p23.[/b] In square $ABCD$, $M$, $N$, $O$, $P$ are points on sides $\overline{AB}$, $\overline{BC}$, $\overline{CD}$ and $\overline{DA}$, respectively. If $AB = 4$, $AM = BM$ and $DP = 3AP$, the least possible value of $MN + NO + OP$ can be expressed as $\sqrt{x}$ forsome integer x. Find x: [b]p24.[/b] Grand-Ovich the ant is at a vertex of a regular hexagon and he moves to one of the adjacent vertices every minute with equal probability. Let the probability that after $8$ minutes he will have returned to the starting vertex at least once be the common fraction $\frac{a}{b}$ in lowest terms. What is $a + b$? [b]p25.[/b] Find the last two non-zero digits at the end of $2020!$ written as a two digit number. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In a board of $2021 \times 2021$ grids, we pick $k$ unit squares such that every picked square shares vertice(s) with at most $1$ other picked square. Determine the maximum of $k$.

Let $A$ and $B$ be sets such that there are exactly $144$ sets which are subsets of either $A$ or $B$. Determine the number of elements $A \cup B$ has.

Some cells of a $11 \times 11$ table are filled with pluses. It is known that the total number of pluses in the given table and in any of its $2 \times 2$ sub-tables is even. Prove that the total number of pluses on the main diagonal of the given table is also even. ($2 \times 2$ sub-table consists of four adjacent cells, four cells around a common vertex).

There are 60 empty boxes $B_1,\ldots,B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game. In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer $k$ with $1\leq k\leq 59$ and splits the boxes into the two groups $B_1,\ldots,B_k$ and $B_{k+1},\ldots,B_{60}$. (b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group. Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning. [i]Czech Republic[/i]

Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1\pmod{4}$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1\pmod{8}$. Show $A$ and $B$ are isomorphic to each other. [i]Linus Hamilton.[/i]

Determine the number of $n$-tuples of integers $(x_1,x_2,\cdots ,x_n)$ such that $|x_i| \le 10$ for each $1\le i \le n$ and $|x_i-x_j| \le 10$ for $1 \le i,j \le n$.

Three grasshoppers $A$, $B$ and $C$ are placed on a line. Grasshopper $B$ sits at the midpoint between $A$ and $C$. Every second, one of the grasshoppers jumps over one of the others to the symmetrical point on the other side (if $X$ jumps over $Y$ to point $X'$, then $XY $= $YX'$). After several jumps it so happened that they returned to the three initial points (but maybe in different order). Prove that in this case $B$ returns to his initial middle position. (AK Kovaldzhy)

Caitlin and Donal play a game called [i]Basketball Shoot-Out[/i]. The game consists of $10$ rounds. In each round, Caitlin and Donal both throw a ball simultaneously at each other's basket. If a player's ball falls into the basket, that player scores one point; otherwise, they score zero points. The scoreboard shows the complete sequence of points scored by each player in each of the $10$ rounds of the game. It turns out that Caitlin has scored at least as many points in total as Donal after every round of the game. Prove the number of possible scoreboards is divisible by $4$ but not by $8$.

You have a large number of congruent equilateral triangular tiles on a table and you want to fit $n$ of them together to ma€ke a convex equiangular hexagon (i.e. one whose interior angles are $120^o$) . Obviously, $n$ cannot be any positive integer. The first three feasible $n$ are $6, 10$ and $13$. Determine if $19$ and $20$ are feasible .

For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

Let $A$ be a set with $1000$ members and $\mathcal F =${$A_1,A_2,\ldots,A_n$} a family of subsets of A such that (a) Each element in $\mathcal F$ consists of 3 members (b) For every five elements in $\mathcal F$, the union of them all will have at least $12$ members Find the largest value of $n$

Let $n$ be a positive integer. On a board consisting of $4n \times 4n$ squares, exactly $4n$ tokens are placed so that each row and each column contains one token. In a step, a token is moved horizontally of vertically to a neighbouring square. Several tokens may occupy the same square at the same time. The tokens are to be moved to occupy all the squares of one of the two diagonals. Determine the smallest number $k(n)$ such that for any initial situation, we can do it in at most $k(n)$ steps.

Let $n$ be a positive integer relatively prime to $6$. We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

A [i]string of parentheses[/i] is any word that can be composed by the following rules. 1) () is a string of parentheses. 2) If $s$ is a string of parentheses then $(s)$ is a string of parentheses. 3) If $s$ and t are strings of parentheses then $st$ is a string of parentheses. The [i]midcode [/i] of a string of parentheses is the tuple of natural numbers obtained by finding, for all pairs of opening and its corresponding closing parenthesis, the number of characters remaining to the left from the medium position between these parentheses, and writing all these numbers in non-decreasing order. For example, the midcode of $(())$ is $(2,2)$ and the midcode of ()() is $(1,3)$. Prove that midcodes of arbitrary two different strings of parentheses are different.

At a party there are eight guests, and each participant can't talk with at most three persons. Prove that we can group the persons in four pairs such that in every pair a conversation can take place.

[b]p1.[/b] (a) Show that for every set of three integers, we can find two of them whose average is also an integer. (b) Show that for every set of $5$ integers, there is a subset of three of them whose average is an integer. [b]p2.[/b] Let $f(x) = x^2 + ax + b$ and $g(x) = x^2 + cx + d$ be two different quadratic polynomials such that $f(7) + f(11) = g(7) + g(11)$. (a) Show that $f(9) = g(9)$. (b) Show that $x = 9$ is the only value of $x$ where $f(x) = g(x)$. [b]p3.[/b] Consider a rectangle $ABCD$ and points $E$ and $F$ on the sides $BC$ and $CD$, respectively, such that the areas of the triangles $ABE$, $ECF$, and $ADF$ are $11$, $3$, and $40$, respectively. Compute the area of rectangle $ABCD$. [img]https://cdn.artofproblemsolving.com/attachments/f/0/2b0bb188a4157894b85deb32d73ab0077cd0b7.png[/img] [b]p4.[/b] How many ways are there to put markers on a $8 \times 8$ checkerboard, with at most one marker per square, such that each of the $8$ rows and each of the $8$ columns contain an odd number of markers? [b]p5.[/b] A robot places a red hat or a blue hat on each person in a room. Each person can see the colors of the hats of everyone in the room except for his own. Each person tries to guess the color of his hat. No communication is allowed between people and each person guesses at the same time (so no timing information can be used, for example). The only information a person has is the color of each other person’s hat. Before receiving the hats, the people are allowed to get together and decide on their strategies. One way to think of this is that each of the $n$ people makes a list of all the possible combinations he could see (there are $2^{n-1}$ such combinations). Next to each combination, he writes what his guess will be for the color of his own hat. When the hats are placed, he looks for the combination on his list and makes the guess that is listed there. (a) Prove that if there are exactly two people in the room, then there is a strategy that guarantees that always at least one person gets the right answer for his hat color. (b) Prove that if you have a group of $2008$ people, then there is a strategy that guarantees that always at least $1004$ people will make a correct guess. (c) Prove that if there are $2009$ people, then there is no strategy that guarantees that always at least $1005$ people will make a correct guess. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let the [i]subbishop[/i] (a bishop is the figure moving only by a diagonal) be a figure moving only by diagonal but only in the next cells (squares) of the chessboard. Find the maximal count of subbishops over a chessboard $n\times n$, no two of which are not attacking. [i]V. Chukanov[/i]

Construct a tetromino by attaching two $2 \times 1$ dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them $S$- and $Z$-tetrominoes, respectively. Assume that a lattice polygon $P$ can be tiled with $S$-tetrominoes. Prove that no matter how we tile $P$ using only $S$- and $Z$-tetrominoes, we always use an even number of $Z$-tetrominoes. [i]Proposed by Tamas Fleiner and Peter Pal Pach, Hungary[/i]