Let $n$ to be a positive integer. Given a set $\{ a_1, a_2, \ldots, a_n \} $ of integers, where $a_i \in \{ 0, 1, 2, 3, \ldots, 2^n -1 \},$ $\forall i$, we associate to each of its subsets the sum of its elements; particularly, the empty subset has sum of its elements equal to $0$. If all of these sums have different remainders when divided by $2^n$, we say that $\{ a_1, a_2, \ldots, a_n \} $ is [i]$n$-complete[/i]. For each $n$, find the number of [i]$n$-complete[/i] sets.

There are $N{}$ friends and a round pizza. It is allowed to make no more than $100{}$ straight cuts without shifting the slices until all cuts are done; then the resulting slices are distributed among all the friends so that each of them gets a share off pizza having the same total area. Is there a cutting which gives the above result if a) $N=201$ and b) $N=400$?

A large pond contains infinitely many lily pads labelled $1$, $2$, $3$,$ ... $, placed in a line, where for each $k$, lily pad $k + 1$ is one unit to the right of lily pad $k$. A frog starts at lily pad $100$. Each minute, if the frog is at lily pad $n$, it hops to lily pad $n + 1$ with probability $\frac{n-1}{n}$ , and hops all the way back to lily pad $1$ with probability $\frac{1}{n}$. Let $N$ be the position of the frog after $1000$ minutes. What is the expected value of $N$?

Let $n$ be a positive integer. There are $n$ islands with $n-1$ bridges connecting them such that one can travel from any island to another. One afternoon, a fire breaks out in one of the islands. Every morning, it spreads to all neighbouring islands. (Two islands are neighbours if they are connected by a bridge.) To control the spread, one bridge is destroyed every night until the fire has nowhere to spread the next day. Let $X$ be the minimum possible number of bridges one has to destroy before the fire stops spreading. Find the maximum possible value of $X$ over all possible configurations of bridges and island where the fire starts at.

Julia is learning how to write the letter C. She has $6$ differently-colored crayons, and wants to write Cc Cc Cc Cc Cc. In how many ways can she write the ten Cs, in such a way that each upper case C is a different color, each lower case C is a different color, and in each pair the upper case C and lower case C are different colors?

How many distinct sets are there such that each set contains only non-negative powers of $2$ or $3$ and sum of its elements is $2014$? $ \textbf{(A)}\ 64 \qquad\textbf{(B)}\ 60 \qquad\textbf{(C)}\ 54 \qquad\textbf{(D)}\ 48 \qquad\textbf{(E)}\ \text{None of the preceding} $

Number $ 0$ is written on the board. Two players alternate writing signs and numbers to the right, where the first player always writes either $ \plus{}$ or $ \minus{}$ sign, while the second player writes one of the numbers $ 1, 2, ... , 1993$,writing each of these numbers exactly once. The game ends after $ 1993$ moves. Then the second player wins the score equal to the absolute value of the expression obtained thereby on the board. What largest score can he always win?

There is a simple graph which chromatic number is equal to $k$. We painted all of the edges of graph using two colors. Prove that there exist a monochromatic tree with $k$ vertices

There is a number written in each square of a $13\times13$ board such that any two numbers in squares with a common side differ by exactly $1$. Each of the numbers $2$ and $24$ is written twice. How many times is the number $13$ written? Find all possibilities.

There are n boys and m girls at Daehan Mathematical High School. Let $d(B)$ a number of girls who know Boy $B$ each other, and let $d(G)$ a number of boys who know Girl $G$ each other. Each girl knows at least one boy each other. Prove that there exist Boy $B$ and Girl $G$ who knows each other in condition that $\frac{d(B)}{d(G)}\ge\frac{m}{n}$.

A right $100$-gon $P$ is given, which has $x$ vertices coloured in white and all other in black. If among some vertices of a right polygon, all the vertices of which are also vertices of $P$, there is exactly one white vertex, then you are allowed to colour this vertex in black. Find all positive integers $x \leq 100$ for which for all initial colourings it is not possible to make all vertices black. [i]A. Vaidzelevich,M. Shutro[/i]

In Middle-Earth, nine cities form a $3$ by $3$ grid. The top left city is the capital of Gondor and the bottom right city is the capital of Mordor. How many ways can the remaining cities be divided among the two nations such that all cities in a country can be reached from its capital via the grid-lines without passing through a city of the other country?

Anna wants to form a four-digit number with four different digits from the digits $1, 2, 3, 4, 5, 6, 7, 8, 9$. She wants the first digit of that number to be bigger than the sum of the other three digits. How many such numbers can she form?

There are five dots arranged in a line from left to right. Each of the dots is colored from one of five colors so that no $3$ consecutive dots are all the same color. How many ways are there to color the dots?

[b]p1.[/b] Consider a parallelogram $ABCD$ with sides of length $a$ and $b$, where $a \ne b$. The four points of intersection of the bisectors of the interior angles of the parallelogram form a rectangle $EFGH$. A possible configuration is given below. Show that $$\frac{Area(ABCD)}{Area(EFGH)}=\frac{2ab}{(a - b)^2}$$ [img]https://cdn.artofproblemsolving.com/attachments/e/a/afaf345f2ef7c8ecf4388918756f0b56ff20ef.png[/img] [b]p2.[/b] A metal wire of length $4\ell$ inches (where $\ell$ is a positive integer) is used as edges to make a cardboard rectangular box with surface area $32$ square inches and volume $8$ cubic inches. Suppose that the whole wire is used. (i) Find the dimension of the box if $\ell= 9$, i.e., find the length, the width, and the height of the box without distinguishing the different orders of the numbers. Justify your answer. (ii) Show that it is impossible to construct such a box if $\ell = 10$. [b]p3.[/b] A Pythagorean n-tuple is an ordered collection of counting numbers $(x_1, x_2,..., x_{n-1}, x_n)$ satisfying the equation $$x^2_1+ x^2_2+ ...+ x^2_{n-1} = x^2_{n}.$$ For example, $(3, 4, 5)$ is an ordinary Pythagorean $3$-tuple (triple) and $(1, 2, 2, 3)$ is a Pythagorean $4$-tuple. (a) Given a Pythagorean triple $(a, b, c)$ show that the $4$-tuple $(a^2, ab, bc, c^2)$ is Pythagorean. (b) Extending part (a) or using any other method, come up with a procedure that generates Pythagorean $5$-tuples from Pythagorean $3$- and/or $4$-tuples. Few numerical examples will not suffice. You have to find a method that will generate infinitely many such $5$-tuples. (c) Find a procedure to generate Pythagorean $6$-tuples from Pythagorean $3$- and/or $4$- and/or $5$-tuples. Note. You can assume without proof that there are infinitely many Pythagorean triples. [b]p4.[/b] Consider the recursive sequence defined by $x_1 = a$, $x_2 = b$ and $$x_{n+2} =\frac{x_{n+1} + x_n - 1}{x_n - 1}, n \ge 1 .$$ We call the pair $(a, b)$ the seed for this sequence. If both $a$ and $b$ are integers, we will call it an integer seed. (a) Start with the integer seed $(2, 2019)$ and find $x_7$. (b) Show that there are infinitely many integer seeds for which $x_{2020} = 2020$. (c) Show that there are no integer seeds for which $x_{2019} = 2019$. [b]p5.[/b] Suppose there are eight people at a party. Each person has a certain amount of money. The eight people decide to play a game. Let $A_i$, for $i = 1$ to $8$, be the amount of money person $i$ has in his/her pocket at the beginning of the game. A computer picks a person at random. The chosen person is eliminated from the game and their money is put into a pot. Also magically the amount of money in the pockets of the remaining players goes up by the dollar amount in the chosen person's pocket. We continue this process and at the end of the seventh stage emerges a single person and a pot containing $M$ dollars. What is the expected value of $M$? The remaining player gets the pot and the money in his/her pocket. What is the expected value of what he/she takes home? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

The [i]binary sudoku[/i] is a puzzle in which a table should be filled with digits $0$ and $1$ such that in each row and column, the number of 0s is equal to the number of $1$s. Furthermore, there cannot exist three adjacent cells in a row or in a column such that they have the same digit written in them. Solving the given binary sudoku, what is the sum of the numbers in the two diagonals? [img]https://cdn.artofproblemsolving.com/attachments/a/8/be7de94ce02a90b3cabf1b9795b94ec7ec677f.png[/img]

The pieces in a game are squares of side $1$ with their sides colored with $4$ colors: blue, red, yellow and green, so that each piece has one side of each color. There are pieces in every possible color arrangement, and the game has a million pieces of each kind. With the pieces, rectangular puzzles are assembled, without gaps or overlaps, so that two pieces that share a side have that side of the same color. Determine if with this procedure you can make a rectangle of $99\times 2007$ with one side of each color. And $100\times 2008$? And $99\times 2008$?

There are $2019$ coins on a table. Some are placed with head up and others tail up. A group of $2019$ persons perform the following operations: the first person chooses any one coin and then turns it over, the second person choses any two coins and turns them over and so on and the $2019$-th person turns over all the coins. Prove that no matter which sides the coins are up initially, the $2019$ persons can come up with a procedure for turning the coins such that all the coins have smae side up at the end of the operations.

There are $N$ cities in a country. Any two of them are connected either by a road or by an airway. A tourist wants to visit every city exactly once and return to the city at which he started the trip. Prove that he can choose a starting city and make a path, changing means of transportation at most once.

Each field of the $n \times n$ array has been colored either red or blue, with the following conditions met: $\bullet$ if a row and a column contain the same number of red fields, the field at their intersection is red; $\bullet$ if a row and a column contain different numbers of red cells, the field at their intersection is blue. Prove that the total number of blue cells is even.

[b]p1.[/b] (a) Find three positive integers $a, b, c$ whose sum is $407$, and whose product (when written in base $10$) ends in six $0$'s. (b) Prove that there do NOT exist positive integers $a, b, c$ whose sum is $407$ and whose product ends in seven $0$'s. [b]p2.[/b] Three circles, each of radius $r$, are placed on a plane so that the center of each circle lies on a point of intersection of the other two circles. The region $R$ consists of all points inside or on at least one of these three circles. Find the area of $R$. [b]p3.[/b] Let $f_1(x) = a_1x^2+b_1x+c_1$, $f_2(x) = a_2x^2+b_2x+c_2$ and $f_3(x) = a_3x^2+b_3x+c_3$ be the equations of three parabolas such that $a_1 > a_2 > a-3$. Prove that if each pair of parabolas intersects in exactly one point, then all three parabolas intersect in a common point. [b]p4.[/b] Gigafirm is a large corporation with many employees. (a) Show that the number of employees with an odd number of acquaintances is even. (b) Suppose that each employee with an even number of acquaintances sends a letter to each of these acquaintances. Each employee with an odd number of acquaintances sends a letter to each non-acquaintance. So far, Leslie has received $99$ letters. Prove that Leslie will receive at least one more letter. (Notes: "acquaintance" and "non-acquaintance" refer to employees of Gigaform. If $A$ is acquainted with $B$, then $B$ is acquainted with $A$. However, no one is acquainted with himself.) [b]p5.[/b] (a) Prove that for every positive integer $N$, if $A$ is a subset of the numbers $\{1, 2, ...,N\}$ and $A$ has size at least $2N/3 + 1$, then $A$ contains a three-term arithmetic progression (i.e., there are positive integers $a$ and $b$ so that all three of the numbers $a$,$a + b$, and $a + 2b$ are elements of $A$). (b) Show that if $A$ is a subset of $\{1, 2, ..., 3500\}$ and $A$ has size at least $2003$, then $A$ contains a three-term arithmetic progression. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A graup of pirates had an argument and not each of them holds some other two at gunpoint.All the pirates are called one by one in some order.If the called pirate is still alive , he shoots both pirates he is aiming at ( some of whom might already be dead .) All shorts are immediatcly lethal . After all the pirates have been called , it turns out the exactly $28$ pirates got killed . Prove that if the pirates were called in whatever other order , at least $10$ pirates would have been killed anyway.

Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n + 1$ smaller rectangles. [i]Proposed by Serbia[/i]

A fractional number $x$ is called [i][b]pretty[/b][/i] if it has finite expression in base$-b$ numeral system, $b$ is a positive integer in $[2;2022]$. Prove that there exists finite positive integers $n\geq 4$ that with every $m$ in $(\frac{2n}{3}; n)$ then there is at least one pretty number between $\frac{m}{n-m}$ and $\frac{n-m}{m}$

A token is placed in one square of a $m\times n$ board, and is moved according to the following rules: [list] [*]In each turn, the token can be moved to a square sharing a side with the one currently occupied. [*]The token cannot be placed in a square that has already been occupied. [*]Any two consecutive moves cannot have the same direction.[/list] The game ends when the token cannot be moved. Determine the values of $m$ and $n$ for which, by placing the token in some square, all the squares of the board will have been occupied in the end of the game.