Inside a square with sides of length $1$ unit several non-overlapping smaller squares with sides parallel to the sides of the large square are placed (the small squares may differ in size). Draw a diagonal of the large square and consider all of the small squares intersecting it. Can the sum of their perimeters be greater than $1993$? (AN Vblmogorov)

Let $ g(n,k)$ denote the number of strongly connected, $ \textit{simple}$ directed graphs with $ n$ vertices and $ k$ edges. ($ \textit{Simple}$ means no loops or multiple edges.) Show that \[ \sum_{k=n}^{n^2-n}(-1)^kg(n,k)=(n-1)!.\] [i]A. A. Schrijver[/i]

Joe and Penny play a game. Initially there are $5000$ stones in a pile, and the two players remove stones from the pile by making a sequence of moves. On the $k$-th move, any number of stones between $1$ and $k$ inclusive may be removed. Joe makes the odd-numbered moves and Penny makes the even-numbered moves. The player who removes the very last stone is the winner. Who wins if both players play perfectly?

[b]p1.[/b] Martin’s car insurance costed $\$6000$ before he switched to Geico, when he saved $15\%$ on car insurance. When Mayhem switched to Allstate, he, a safe driver, saved $40\%$ on car insurance. If Mayhem and Martin are now paying the same amount for car insurance, how much was Mayhem paying before he switched to Allstate? [b]p2.[/b] The $7$-digit number $N$ can be written as $\underline{A} \,\, \underline{2} \,\,\underline{0} \,\,\underline{B} \,\,\underline{2} \,\, \underline{1} \,\,\underline{5}$. How many values of $N$ are divisible by $9$? [b]p3.[/b] The solutions to the equation $x^2-18x-115 = 0$ can be represented as $a$ and $b$. What is $a^2+2ab+b^2$? [b]p4.[/b] The exterior angles of a regular polygon measure to $4$ degrees. What is a third of the number of sides of this polygon? [b]p5.[/b] Charlie Brown is having a thanksgiving party. $\bullet$ He wants one turkey, with three different sizes to choose from. $\bullet$ He wants to have two or three vegetable dishes, when he can pick from Mashed Potatoes, Saut´eed Brussels Sprouts, Roasted Butternut Squash, Buttery Green Beans, and Sweet Yams; $\bullet$ He wants two desserts out of Pumpkin Pie, Apple Pie, Carrot Cake, and Cheesecake. How many different combinations of menus are there? [b]p6.[/b] In the diagram below, $\overline{AD} \cong \overline{CD}$ and $\vartriangle DAB$ is a right triangle with $\angle DAB = 90^o$. Given that the radius of the circle is $6$ and $m \angle ADC = 30^o$, if the length of minor arc $AB$ is written as $a\pi$, what is $a$? [img]https://cdn.artofproblemsolving.com/attachments/d/9/ea57032a30c16f4402886af086064261d6828b.png[/img] [b]p7.[/b] This Halloween, Owen and his two friends dressed up as guards from Squid Game. They needed to make three masks, which were black circles with a white equilateral triangle, circle, or square inscribed in their upper halves. Resourcefully, they used black paper circles with a radius of $5$ inches and white tape to create these masks. Ignoring the width of the tape, how much tape did they use? If the length can be expressed $a\sqrt{b}+c\sqrt{d}+ \frac{e}{f} \pi$ such that $b$ and $d$ are not divisible by the square of any prime, and $e$ and $f$ are relatively prime, find $a + b + c + d + e + f$. [img]https://cdn.artofproblemsolving.com/attachments/0/c/bafe3f9939bd5767ba5cf77a51031dd32bbbec.png[/img] [b]p8.[/b] Given $LCM (10^8, 8^{10}, n) = 20^{15}$, where $n$ is a positive integer, find the total number of possible values of $n$. [b]p9.[/b] If one can represent the infinite progression $\frac{1}{11} + \frac{2}{13} + \frac{3}{121} + \frac{4}{169} + \frac{5}{1331} + \frac{6}{2197}+ ...$ as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers, what is $a$? [b]p10.[/b] Consider a tiled $3\times 3$ square without a center tile. How many ways are there to color the squares such that no two colored squares are adjacent (vertically or horizontally)? Consider rotations of an configuration to be the same, and consider the no-color configuration to be a coloring. [b]p11.[/b] Let $ABC$ be a triangle with $AB = 4$ and $AC = 7$. Let $AD$ be an angle bisector of triangle $ABC$. Point $M$ is on $AC$ such that $AD$ intersects $BM$ at point $P$, and $AP : PD = 3 : 1$. If the ratio $AM : MC$ can be expressed as $\frac{a}{b}$ such that $a$, $b$ are relatively prime positive integers, find $a + b$. [b]p12.[/b] For a positive integer $n$, define $f(n)$ as the number of positive integers less than or equal to $n$ that are coprime with $n$. For example, $f(9) = 6$ because $9$ does not have any common divisors with $1$, $2$, $4$, $5$, $7$, or $8$. Calculate: $$\sum^{100}_{i=2} \left( 29^{f(i)}\,\,\, mod \,\,i \right).$$ [b]p13.[/b] Let $ABC$ be an equilateral triangle. Let $P$ be a randomly selected point in the incircle of $ABC$. Find $a+b+c+d$ if the probability that $\angle BPC$ is acute can be expressed as $\frac{a\sqrt{b} -c\pi}{d\pi }$ for positive integers $a$, $b$, $c$, $d$ where $gcd(a, c, d) = 1$ and $b$ is not divisible by the square of any prime. [b]p14.[/b] When the following expression is simplified by expanding then combining like terms, how many terms are in the resulting expression? $$(a + b + c + d)^{100} + (a + b - c - d)^{100}$$ [b]p15.[/b] Jerry has a rectangular box with integral side lengths. If $3$ units are added to each side of the box, the volume of the box is tripled. What is the largest possible volume of this box? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Given $2015$ points in the plane, show that if every four of them form a convex quadrilateral then the points are the vertices of a convex $2015-$sided polygon.

[u]Round 5[/u] [b]p13.[/b] You have a $26 \times 26$ grid of squares. Color each randomly with red, yellow, or blue. What is the expected number (to the nearest integer) of $2 \times 2$ squares that are entirely red? [b]p14.[/b] Four snakes are boarding a plane with four seats. Each snake has been assigned to a different seat. The first snake sits in the wrong seat. Any subsequent snake will sit in their assigned seat if vacant, if not, they will choose a random seat that is available. What is the expected number of snakes who sit in their correct seats? [b]p15.[/b] Let $n \ge 1$ be an integer and $a > 0$ a real number. In terms of n, find the number of solutions $(x_1, ..., x_n)$ of the equation $\sum^n_{i=1}(x^2_i + (a - x_i)^2) = na^2$ such that $x_i$ belongs to the interval $[0, a]$ , for $i = 1, 2, . . . , n$. [u]Round 6 [/u] [b]p16.[/b] All roots of $$\prod^{25}_{n=1} \prod^{2n}_{k=0}(-1)^k \cdot x^k = 0$$ are written in the form $r(\cos \phi + i\sin \phi)$ for $i^2 = -1$, $r > 0$, and $0 \le \phi < 2\pi$. What is the smallest positive value of $\phi$ in radians? [b]p17.[/b] Find the sum of the distinct real roots of the equation $$\sqrt[3]{x^2 - 2x + 1} + \sqrt[3]{x^2 - x - 6} = \sqrt[3]{2x^2 - 3x - 5}.$$ [b]p18.[/b] If $a$ and $b$ satisfy the property that $a2^n + b$ is a square for all positive integers $n$, find all possible value(s) of $a$. [u]Round 7 [/u] [b]p19.[/b] Compute $(1 - \cot 19^o)(1 - \cot 26^o)$. [b]p20.[/b] Consider triangle $ABC$ with $AB = 3$, $BC = 5$, and $\angle ABC = 120^o$. Let point $E$ be any point inside $ABC$. The minimum of the sum of the squares of the distances from $E$ to the three sides of $ABC$ can be written in the form $a/b$ , where a and b are natural numbers such that the greatest common divisor of $a$ and $b$ is $1$. Find $a + b$. [b]p21.[/b] Let $m \ne 1$ be a square-free number (an integer – possibly negative – such that no square divides $m$). We denote $Q(\sqrt{m})$ to be the set of all $a + b\sqrt{m}$ where $a$ and $b$ are rational numbers. Now for a fixed $m$, let $S$ be the set of all numbers $x$ in $Q(\sqrt{m})$ such that x is a solution to a polynomial of the form: $x^n + a_1x^{n-1} + .... + a_n = 0$, where $a_0$, $...$, $a_n$ are integers. For many integers m, $S = Z[\frac{m}] = \{a + b\sqrt{m}\}$ where $a$ and $b$ are integers. Give a classification of the integers for which this is not true. (Hint: It is true for $ m = -1$ and $2$.) PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c4h2782002p24434611]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

There are $n$ positive integers on the board. We can add only positive integers $c=\frac{a+b}{a-b}$, where $a$ and $b$ are numbers already writted on the board. $a)$ Find minimal value of $n$, such that with adding numbers with described method, we can get any positive integer number written on the board $b)$ For such $n$, find numbers written on the board at the beginning

Prove that for arbitary integer $ n > 16$, there exists the set $ S$ that contains $ n$ positive integers and has the following property:if the subset $ A$ of $ S$ satisfies for arbitary $ a,a'\in A, a\neq a', a \plus{} a'\notin S$ holds, then $ |A|\leq4\sqrt n.$

Can a paper circle be cut into pieces and then rearranged into a square of the same area, if only a finite number of cuts is allowed and they must be along segments of straight lines or circular arcs? (A Belov)

A student had $18$ papers. He seleced some of these papers, then he cut each of them in $18$ pieces.He took these pieces and selected some of them, which he again cut in $18$ pieces each.The student took this procedure untill he got tired .After a time he counted the pieces and got $2012$ pieces .Prove that the student was wrong during the counting.

During the $2005$ iTest, you will be introduced to Joe and Kathryn, two high school seniors. If $J$ is the number of distinct permutations of $JOE$, and $K$ is the number of distinct permutations of $KATHRYN$, find $K -J$.

This problem is generalization of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=5918]this one[/url]. Suppose $G$ is a graph and $S\subset V(G)$. Suppose we have arbitrarily assign real numbers to each element of $S$. Prove that we can assign numbers to each vertex in $G\backslash S$ that for each $v\in G\backslash S$ number assigned to $v$ is average of its neighbors.

Let $n$ be a positive integer, let $f_1(x),\ldots,f_n(x)$ be $n$ bounded real functions, and let $a_1,\ldots,a_n$ be $n$ distinct reals. Show that there exists a real number $x$ such that $\sum^n_{i=1}f_i(x)-\sum^n_{i=1}f_i(x-a_i)<1$.

Let $2001$ given points on a circle be coloured either red or green. In one step all points are recoloured simultaneously in the following way: If both direct neighbours of a point $P$ have the same colour as $P$, then the colour of $P$ remains unchanged, otherwise $P$ obtains the other colour. Starting with the first colouring $F_1$, we obtain the colourings $F_2,F_3 ,\ldots .$ after several recolouring steps. Prove that there is a number $n_0\le 1000$ such that $F_{n_0}=F_{n_0 +2}$. Is the assertion also true if $1000$ is replaced by $999$?

Four numbers are written on the board: $1, 3, 6, 10.$ Each time two arbitrary numbers, $a$ and $b$ are deleted, and numbers $a + b$ and $ab$ are written in their place. Is it possible to get numbers $2015, 2016, 2017, 2018$ on the board after several such operations?

A set $S$ is called perfect if it has the following two properties: a) $S$ has exactly four elements b) for every element $x$ of $S$, at least one of the numbers $x - 1$ or $x+1$ belongs to $S$. Find the number of all perfect subsets of the set $\{1,2,... ,n\}$

Let $r>1$ be a rational number. Alice plays a solitaire game on a number line. Initially there is a red bead at $0$ and a blue bead at $1$. In a move, Alice chooses one of the beads and an integer $k \in \mathbb{Z}$. If the chosen bead is at $x$, and the other bead is at $y$, then the bead at $x$ is moved to the point $x'$ satisfying $x'-y=r^k(x-y)$. Find all $r$ for which Alice can move the red bead to $1$ in at most $2021$ moves.

[b]p1.[/b] For what integers $x$ is it possible to find an integer $y$ such that $$x(x + 1) (x + 2) (x + 3) + 1 = y^2 ?$$ [b]p2.[/b] Two tangents to a circle are parallel and touch the circle at points $A$ and $B$, respectively. A tangent to the circle at any point $X$, other than $A$ or $B$, meets the first tangent at $Y$ and the second tangent at $Z$. Prove $AY \cdot BZ$ is independent of the position of $X$. [b]p3.[/b] If $a, b, c$ are positive real numbers, prove that $$8abc \le (b + c) (c + a) (a + b)$$ by first verifying the relation in the special case when $c = b$. [b]p4.[/b] Solve the equation $$\frac{x^2}{3}+\frac{48}{x^2}=10 \left( \frac{x}{3}-\frac{4}{x}\right)$$ [b]p5.[/b] Tom and Bill live on the same street. Each boy has a package to deliver to the other boy’s house. The two boys start simultaneously from their own homes and meet $600$ yards from Bill's house. The boys continue on their errand and they meet again $700$ yards from Tom's house. How far apart do the boy's live? [b]p6.[/b] A standard set of dominoes consists of $28$ blocks of size $1$ by $2$. Each block contains two numbers from the set $0,1,2,...,6$. We can denote the block containing $2$ and $3$ by $[2, 3]$, which is the same block as $[3, 2]$. The blocks $[0, 0]$, $[1, 1]$,..., $[6, 6]$ are in the set but there are no duplicate blocks. a) Show that it is possible to arrange the twenty-eight dominoes in a line, end-to-end, with adjacent ends matching, e. g., $... [3, 1]$ $[1, 1]$ $[1, 0]$ $[0, 6] ...$ . b) Consider the set of dominoes which do not contain $0$. Show that it is impossible to arrange this set in such a line. c) Generalize the problem and prove your generalization. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Suppose there are three empty buckets and $n \ge 3$ marbles. Ani and Budi play a game. For the first turn, Ani distributes all the marbles into the buckets so that each bucket has at least one marble. Then Budi and Ani alternate turns, starting with Budi. On a turn, the current player may choose a bucket and take 1, 2, or 3 marbles from it. The player that takes the last marble wins. Find all $n$ such that Ani has a winning strategy, including what Ani's first move (distributing the marbles) should be for these $n$.

There are $6$ computers(power off) and $3$ printers. Between a printer and a computer, they are connected with a wire or not. Printer can be only activated if and only if at least one of the connected computer's power is on. Your goal is to connect wires in such a way that, no matter how you choose three computers to turn on among the six, you can activate all $3$ printers. What is the minimum number of wires required to make this possible?

There are 1997 pieces of medicine. Three bottles $A, B, C$ can contain at most 1997, 97, 19 pieces of medicine respectively. At first, all 1997 pieces are placed in bottle $A$, and the three bottles are closed. Each piece of medicine can be split into 100 part. When a bottle is opened, all pieces of medicine in that bottle lose a part each. A man wishes to consume all the medicine. However, he can only open each of the bottles at most once each day, consume one piece of medicine, move some pieces between the bottles, and close them. At least how many parts will be lost by the time he finishes consuming all the medicine?

Let $m>1$ be a fixed positive integer. For a nonempty string of base-ten digits $S$, let $c(S)$ be the number of ways to split $S$ into contiguous nonempty strings of digits such that the base-ten number represented by each string is divisible by $m$. These strings are allowed to have leading zeroes. In terms of $m$, what are the possible values that $c(S)$ can take? For example, if $m=2$, then $c(1234)=2$ as the splits $1234$ and $12|34$ are valid, while the other six splits are invalid.

[u]Round 5[/u] [b]p13.[/b] Simplify $\frac11+\frac13+\frac16+\frac{1}{10}+\frac{1}{15}+\frac{1}{21}$. [b]p14.[/b] Given that $x + y = 7$ and $x^2 + y^2 = 29$, what is the sum of the reciprocals of $x$ and $y$? [b]p15.[/b] Consider a rectangle $ABCD$ with side lengths $AB = 3$ and $BC = 4$. If circles are inscribeδ in triangles $ABC$ and $BCD$, how far are the centers of the circles from each other? [u]Round 6[/u] [b]p16.[/b] Evaluate $\frac{2!}{1!} +\frac{3!}{2!} +\frac{4!}{3!} + ... +\frac{99!}{98!}+\frac{100!}{99!}$ . [b]p17.[/b] Let $ABCD$ be a square of side length $2$. A semicircle is drawn with diameter $\overline{AC}$ that passes through point $B$. Find the area of the region inside the semicircle but outside the square. [b]p18.[/b] For how many positive integer values of $k$ is $\frac{37k - 30}{k}$ a positive integer? [u]Round 7[/u] [b]p19.[/b] Two parallel planar slices across a sphere of radius $25$ create cross sections of area $576\pi$ and $225\pi$. What is the maximum possible distance between the two slices? [b]p20.[/b] How many positive integers cannot be expressed in the form $3\ell + 4m + 5t$, where $\ell$, $m$, and $t$ are nonnegative integers? [b]p21.[/b] In April, a fool is someone who is fooled by a classmate. In a class of $30$ students, $14$ people were fooled by someone else and $29$ people fooled someone else. What is the largest positive integer $n$ for which we can guarantee that at least one person was fooled by at least $n$ other people? [u]Round 8[/u] [b]p22.[/b] Let $$S = 4 + \dfrac{12}{4 +\dfrac{ 12}{4 +\dfrac{ 12}{4+ ...}}}.$$ Evaluate $4 +\frac{ 12}{S}.$ [b]p23.[/b] Jonathan is buying bananagram sets for $\$11$ each and flip-flops for $\$17$ each. If he spends $\$227$ on purchases for bananagram sets and flip-flops, what is the total number of bananagram sets and flip-flops he bought? [b]p24.[/b] Alan has a $3 \times 3$ array of squares. He starts removing the squares one at a time such that each time he removes one square, all remaining squares share a side with at least two other remaining squares. What is the maximum number of squares Alan can remove? PS. You should use hide for answers. Rounds 1-4 are [url=https://artofproblemsolving.com/community/c3h2952214p26434209]here[/url] and 9-12 [url=https://artofproblemsolving.com/community/c3h3134133p28400917]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $k>1$ be a fixed positive integer. Prove that if $n$ is a sufficiently large positive integer, there exists a sequence of integers with the following properties: [list=disc] [*]Each element of the sequence is between $1$ and $n$, inclusive. [*]For any two different contiguous subsequence of the sequence with length between $2$ and $k$ inclusive, the multisets of values in those two subsequences is not the same. [*]The sequence has length at least $0.499n^2$ [/list]

The positive integers from 1 to 100 are painted into three colors: 50 integers are red, 25 integers are yellow and 25 integers are green. The red and yellow integers can be divided into 25 triples such that each triple includes two red integers and one yellow integer which is greater than one of the red integers and smaller than another one. The same assertion is valid for the red and green integers. Is it necessarily possible to divide all the 100 integers into 25 quadruples so that each quadruple includes two red integers, one yellow integer and one green integer such that the yellow and the green integer lie between the red ones? [i]Alexandr Gribalko[/i]