Consider a checkered $3m\times 3m$ square, where $m$ is an integer greater than $1.$ A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F.$ The frog can hop from any cell to either the next cell to the right or the next cell upwards. Some cells can be [i]sticky[/i], and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called [i]blocking[/i] if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is [i] minimal[/i] if it does not contain a smaller blocking set.[list=a][*]Prove that there exists a minimal blocking set containing at least $3m^2-3m$ cells. [*]Prove that every minimal blocking set containing at most $3m^2$ cells.

[b]p1.[/b] Archimedes, Euclid, Fermat, and Gauss had a math competition. Archimedes said, “I did not finish $1$st or $4$th.” Euclid said, “I did not finish $4$th.” Fermat said, “I finished 1st.” Gauss said, “I finished $4$th.” There were no ties in the competition, and exactly three of the mathematicians told the truth. Who finished first and who finished last? Justify your answers. [b]p2.[/b] Find the area of the set in the xy-plane defined by $x^2 - 2|x| + y^2 \le 0$. Justify your answer. [b]p3.[/b] There is a collection of $2004$ circular discs (not necessarily of the same radius) in the plane. The total area covered by the discs is $1$ square meter. Show that there is a subcollection $S$ of discs such that the discs in S are non-overlapping and the total area of the discs in $S$ is at least $1/9$ square meter. [b]p4.[/b] Let $S$ be the set of all $2004$-digit integers (in base $10$) all of whose digits lie in the set $\{1, 2, 3, 4\}$. (For example, $12341234...1234$ is in $S$.) Let $n_0$ be the number of $s \in S$ such that $s$ is a multiple of $3$, let $n_1$ be the number of $s \in S$ such that $s$ is one more than a multiple of $3$, and let $n_2$ be the number of $s \in S$ such that $s$ is two more than a multiple of $3$. Determine which of $n_0$, $n_1$, $n_2$ is largest and which is smallest (and if there are any equalities). Justify your answers. [b]p5.[/b] There are $6$ members on the Math Competition Committee. The problems are kept in a safe. There are $\ell$ locks on the safe and there are $k$ keys, several for each lock. The safe does not open unless all of the locks are unlocked, and each key works on exactly one lock. The keys should be distributed to the $6$ members of the committee so that each group of $4$ members has enough keys to open all of the $\ell$ locks. However, no group of $3$ members should be able to open all of the $\ell$ locks. (a) Show that this is possible with $\ell = 20$ locks and $k = 60$ keys. That is, it is possible to use $20$ locks and to choose and distribute 60 keys in such a way that every group of $4$ can open the safe, but no group of $3$ can open the safe. (b) Show that we always must have $\ell \ge 20$ and $k\ge60$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Two players are writting in turn natural numbers not exceeding $p$. The rules forbid to write the divisors of the numbers already having been written. Those who cannot make his move looses. a) Who, and how, can win if $p=10$? b) Who wins if $p=1000$?

The kingdom of Anisotropy consists of $n$ cities. For every two cities there exists exactly one direct one-way road between them. We say that a [i]path from $X$ to $Y$[/i] is a sequence of roads such that one can move from $X$ to $Y$ along this sequence without returning to an already visited city. A collection of paths is called [i]diverse[/i] if no road belongs to two or more paths in the collection. Let $A$ and $B$ be two distinct cities in Anisotropy. Let $N_{AB}$ denote the maximal number of paths in a diverse collection of paths from $A$ to $B$. Similarly, let $N_{BA}$ denote the maximal number of paths in a diverse collection of paths from $B$ to $A$. Prove that the equality $N_{AB} = N_{BA}$ holds if and only if the number of roads going out from $A$ is the same as the number of roads going out from $B$. [i]Proposed by Warut Suksompong, Thailand[/i]

$7$ pupils has been given $20$ candies, $5$ candies of $4$ different kinds, so that each pupil has no more then one candy of each kind. Prove that there are two pupils that have three or more pairs of candies of the same kind.

There are $n\leq 99$ people around a circular table. At every moment everyone can either be truthful (always says the truth) or a liar (always lies). Initially some of people (possibly none) are truthful and the rest are liars. At every minute everyone answers at the same time the question "Is your left neighbour truthful or a liar?" and then becomes the same type of person as his answer. Determine the largest $n$ for which, no matter who are the truthful people in the beginning, at some point everyone will become truthful forever.

In a simple graph, there are two disjoint set of vertices $A$ and $B$ where $A$ has $k$ and $B$ has $2016$ vertices. Four numbers are written to each vertex using the colors red, green, blue and black. There is no any edge at the beginning. For each vertex in $A$, we first choose a color and then draw all edges from this vertex to the vertices in $B$ having a larger number with the chosen color. It is known that for each vertex in $B$, the set of vertices in $A$ connected to this vertex are different. Find the minimal possible value of $k$.

Jacob and Laban take turns playing a game. Each of them starts with the list of square numbers $1, 4, 9, \dots, 2021^2$, and there is a whiteboard in front of them with the number $0$ on it. Jacob chooses a number $x^2$ from his list, removes it from his list, and replaces the number $W$ on the whiteboard with $W + x^2$. Laban then does the same with a number from his list, and the repeat back and forth until both of them have no more numbers in their list. Now every time that the number on the whiteboard is divisible by $4$ after a player has taken his turn, Jacob gets a sheep. Jacob wants to have as many sheep as possible. What is the greatest number $K$ such that Jacob can guarantee to get at least $K$ sheep by the end of the game, no matter how Laban plays?

There are $n$($\ge 2$) clubs $A_1,A_2,...A_n$ in Korean Mathematical Society. Prove that there exist $n-1$ sets $B_1,B_2,...B_{n-1}$ that satisfy the condition below. (1) $A_1\cup A_2\cup \cdots A_n=B_1\cup B_2\cup \cdots B_{n-1}$ (2) for any $1\le i<j\le n-1$, $B_i\cap B_j=\emptyset, -1\le\left\vert B_i \right\vert -\left\vert B_j \right\vert\le 1$ (3) for any $1\le i \le n-1$, there exist $A_k,A_j $($1\le k\le j\le n$)such that $B_i\subseteq A_k\cup A_j$

Describe all the ways to color each natural number as one of three colors so that the following condition is satisfied: if the numbers $a$, $b$ and $c$ (not necessarily different) satisfy the condition $2000(a + b) = c$, then they either all the same color or three different colors

Let $m$ and $n$ be natural numbers with $mn$ even. Jetze is going to cover an $m \times n$ board (consisting of $m$ rows and $n$ columns) with dominoes, so that every domino covers exactly two squares, dominos do not protrude or overlap, and all squares are covered by a domino. Merlin then moves all the dominoe color red or blue on the board. Find the smallest non-negative integer $V$ (in terms of $m$ and $n$) so that Merlin can always ensure that in each row the number squares covered by a red domino and the number of squares covered by a blue one dominoes are not more than $V$, no matter how Jetze covers the board.

assume that k,n are two positive integer $k\leq n$count the number of permutation $\{\ 1,\dots ,n\}\ $ st for any $1\leq i,j\leq k$and any positive integer m we have $f^m(i)\neq j$ ($f^m$ meas iterarte function,)

Let $a$ and $b$ be positive integers, and let $A$ and $B$ be finite sets of integers satisfying (i) $A$ and $B$ are disjoint; (ii) if an integer $i$ belongs to either to $A$ or to $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$. Prove that $a\left\lvert A \right\rvert = b \left\lvert B \right\rvert$. (Here $\left\lvert X \right\rvert$ denotes the number of elements in the set $X$.)

Find the number of all 6-digits numbers having exactly three odd and three even digits.

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?

[hide=R stands for Ramanujan , P stands for Pascal]they had two problem sets under those two names[/hide] [u]Set 4[/u] [b]R4.16 / P1.4[/b] Adam and Becky are building a house. Becky works twice as fast as Adam does, and they both work at constant speeds for the same amount of time each day. They plan to finish building in $6$ days. However, after $2$ days, their friend Charlie also helps with building the house. Because of this, they finish building in just $5$ days. What fraction of the house did Adam build? [b]R4.17[/b] A bag with $10$ items contains both pencils and pens. Kanye randomly chooses two items from the bag, with replacement. Suppose the probability that he chooses $1$ pen and $1$ pencil is $\frac{21}{50}$ . What are all possible values for the number of pens in the bag? [b]R4.18 / P2.8[/b] In cyclic quadrilateral $ABCD$, $\angle ABD = 40^o$, and $\angle DAC = 40^o$. Compute the measure of $\angle ADC$ in degrees. (In cyclic quadrilaterals, opposite angles sum up to $180^o$.) [b]R4.19 / P2.6[/b] There is a strange random number generator which always returns a positive integer between $1$ and $7500$, inclusive. Half of the time, it returns a uniformly random positive integer multiple of $25$, and the other half of the time, it returns a uniformly random positive integer that isn’t a multiple of $25$. What is the probability that a number returned from the generator is a multiple of $30$? [b]R4.20 / P2.7[/b] Julia is shopping for clothes. She finds $T$ different tops and $S$ different skirts that she likes, where $T \ge S > 0$. Julia can either get one top and one skirt, just one top, or just one skirt. If there are $50$ ways in which she can make her choice, what is $T - S$? [u]Set 5[/u] [b]R5.21[/b] A $5 \times 5 \times 5$ cube’s surface is completely painted blue. The cube is then completely split into $ 1 \times 1 \times 1$ cubes. What is the average number of blue faces on each $ 1 \times 1 \times 1$ cube? [b]R5.22 / P2.10[/b] Find the number of values of $n$ such that a regular $n$-gon has interior angles with integer degree measures. [b]R5.23[/b] $4$ positive integers form an geometric sequence. The sum of the $4$ numbers is $255$, and the average of the second and the fourth number is $102$. What is the smallest number in the sequence? [b]R5.24[/b] Let $S$ be the set of all positive integers which have three digits when written in base $2016$ and two digits when written in base $2017$. Find the size of $S$. [b]R5.25 / P3.12[/b] In square $ABCD$ with side length $13$, point $E$ lies on segment $CD$. Segment $AE$ divides $ABCD$ into triangle $ADE$ and quadrilateral $ABCE$. If the ratio of the area of $ADE$ to the area of $ABCE$ is $4 : 11$, what is the ratio of the perimeter of $ADE$ to the perimeter of $ABCE$? [u]Set 6[/u] [b]R6.26 / P6.25[/b] Submit a decimal n to the nearest thousandth between $0$ and $200$. Your score will be $\min (12, S)$, where $S$ is the non-negative difference between $n$ and the largest number less than or equal to $n$ chosen by another team (if you choose the smallest number, $S = n$). For example, 1.414 is an acceptable answer, while $\sqrt2$ and $1.4142$ are not. [b]R6.27 / P6.27[/b] Guang is going hard on his YNA project. From $1:00$ AM Saturday to $1:00$ AM Sunday, the probability that he is not finished with his project $x$ hours after $1:00$ AM on Saturday is $\frac{1}{x+1}$ . If Guang does not finish by 1:00 AM on Sunday, he will stop procrastinating and finish the project immediately. Find the expected number of minutes $A$ it will take for him to finish his project. An estimate of $E$ will earn $12 \cdot 2^{-|E-A|/60}$ points. [b]R6.28 / P6.28[/b] All the diagonals of a regular $100$-gon (a regular polygon with $100$ sides) are drawn. Let $A$ be the number of distinct intersection points between all the diagonals. Find $A$. An estimate of $E$ will earn $12 \cdot \left(16 \log_{10}\left(\max \left(\frac{E}{A},\frac{A}{E}\right)\right)+ 1\right)^{-\frac12}$ or $0$ points if this expression is undefined. [b]R6.29 / P6.29 [/b]Find the smallest positive integer $A$ such that the following is true: if every integer $1, 2, ..., A$ is colored either red or blue, then no matter how they are colored, there are always 6 integers among them forming an increasing arithmetic progression that are all colored the same color. An estimate of $E$ will earn $12 min \left(\frac{E}{A},\frac{A}{E}\right)$ points or $0$ points if this expression is undefined. [b]R6.30 / P6.30[/b] For all integers $n \ge 2$, let $f(n)$ denote the smallest prime factor of $n$. Find $A =\sum^{10^6}_{n=2}f(n)$. In other words, take the smallest prime factor of every integer from $2$ to $10^6$ and sum them all up to get $A$. You may find the following values helpful: there are $78498$ primes below $10^6$, $9592$ primes below $10^5$, $1229$ primes below $10^4$, and $168$ primes below $10^3$. An estimate of $E$ will earn $\max \left(0, 12-4 \log_{10}(max \left(\frac{E}{A},\frac{A}{E}\right)\right)$ or $0$ points if this expression is undefined. PS. You should use hide for answers. R1-15 /P1-5 have been posted [url=https://artofproblemsolving.com/community/c3h2786721p24495629]here[/url], and P11-25 [url=https://artofproblemsolving.com/community/c3h2786880p24497350]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[b]carpeting[/b] suppose that $S$ is a figure in the plane such that it's border doesn't contain any lattice points. suppose that $x,y$ are two lattice points with the distance $1$ (we call a point lattice point if it's coordinates are integers). suppose that we can cover the plane with copies of $S$ such that $x,y$ always go on lattice points ( you can rotate or reverse copies of $S$). prove that the area of $S$ is equal to lattice points inside it. time allowed for this question was 1 hour.

We have $n$ keys, each of them belonging to exactly one of $n$ locked chests. Our goal is to decide which key opens which chest. In one try we may choose a key and a chest, and check whether the chest can be opened with the key. Find the minimal number $p(n)$ with the property that using $p(n)$ tries, we can surely discover which key belongs to which chest.

Natural numbers from $1$ to $200$ were divided into $50$ sets. Prove that one of them contains three numbers that are the lengths of the sides of some triangle

At the start of the Mighty Mathematicians Football Team's first game of the season, their coach noticed that the jersey numbers of the 22 players on the field were all the numbers from 1 to 22. At halftime, the coach substituted her goal-keeper, with jersey number 1, for a reserve player. No other substitutions were made by either team at or before halftime. The coach noticed that after the substitution, no two players on the field had the same jersey number and that the sums of the jersey numbers of each of the teams were exactly equal. Determine * the greatest possible jersey number of the reserve player, * the smallest possible (positive) jersey number of the reserve player.

The cells of the $200 \times 200$ table are painted black and white so that there are $404$ more black cells than white ones. Prove that there is a $2 \times 2$ square in which the number of white cells is odd.

There are $10000$ cities in country, and roads between some cities. Every city has $<100$ roads. Every cycle route with odd number of road consists of $\geq 101 $ roads. Prove that we can divide all cities in $100$ groups with $100$ cities, such that every road leads from one group to other.

Let $n$ be a positive integer. In how many ways can an $n \times n$ table be filled with integers from $0$ to $5$ such that a) the sum of each row is divisible by $2$ and the sum of each column is divisible by $3$ b) the sum of each row is divisible by $2$, the sum of each column is divisible by $3$ and the sum of each of the two diagonals is divisible by $6$?

In how many ways can we construct a square with dimensions $4\times 4$ using $4$ white, $4$ green , $4$ red and 4 $blue$ squares of dimensions $1\times 1$, such that in every horizontal and in every certical line, squares have different colours .

A box contains $p$ white balls and $q$ black balls. Beside the box there is a pile of black balls. Two balls are taken out of the box. If they have the same color, a black ball from the pile is put into the box. If they have different colors, the white ball is put back into the box. This procedure is repeated until the last two balls are removed from the box and one last ball is put in. What is the probability that this last ball is white?