A $100 \times 100 \times 100$ cube is divided into a million unit cubes and in each small cube there is a light bulb. Three faces $100 \times 100$ of the large cube having a common vertex are painted: one in red, one in blue and the other in green. Call a $\textit{column}$ a set of $100$ cubes forming a block $1 \times 1 \times 100$. Each of the $30 000$ columns have one painted end cell, on which there is a switch. After pressing a switch, the states of all light bulbs of this column are changed. Petya pressed several switches, getting a situation with exactly $k$ lamps on. Prove that Vasya can press several switches so that all lamps are off, but by using no more than $\frac {k} {100}$ switches on the red face.

Let $P(n)$ be the number of ways to split a natural number $n$ to the sum of powers of two, when the order does not matter. For example $P(5) = 4$, as $5=4+1=2+2+1=2+1+1+1=1+1+1+1+1$. Prove that for any natural the identity $P(n) + (-1)^{a_1} P(n-1) + (-1)^{a_2} P(n-2) + \ldots + (-1)^{a_{n-1}} P(1) + (-1)^{a_n} = 0,$ is true, where $a_k$ is the number of units in the binary number record $k$ . [url=http://matol.kz/comments/2720/show]source[/url]

Some cells of a $2n\times2n$ board are marked so that each cell has an even number of neighboring (i.e. sharing a side) marked cells. Find the number of such markings.

For positive integers $m, n$ ($m>n$), $a_{n+1}, a_{n+2}, ..., a_m$ are non-negative integers that satisfy the following inequality. $$ 2> \frac{a_{n+1}}{n+1} \ge \frac{a_{n+2}}{n+2} \ge \cdots \ge \frac{a_m}{m}$$ Find the number of pair $(a_{n+1}, a_{n+2}, \cdots, a_m)$.

Let $n \in N$. The land of Draconis has more than $2^n$ dungeons. Between two different Dungeons have exactly one path, but each path is a one-way street. Total $n$ Dragon cults share the territory; each path is controlled by exactly one cult. It is said that a dragon cult $K$ has established itself in a dungeon $D$ if there is both one a path beginning in $D$ and one a path ending in $D$, both of which are controlled by $K$ . Prove that there is a cult $K$, which has at least one dungeon controlled.

Let $n$ be a positive integer. Find the number of permutations $a_1$, $a_2$, $\dots a_n$ of the sequence $1$, $2$, $\dots$ , $n$ satisfying $$a_1 \le 2a_2\le 3a_3 \le \dots \le na_n$$. Proposed by United Kingdom

Let $p$ be a positive integer, $p>1.$ Find the number of $m\times n$ matrices with entries in the set $\left\{ 1,2,\dots,p\right\} $ and such that the sum of elements on each row and each column is not divisible by $p.$

Let $n$ be a positive integer. Each square of a $(2n-1) \times (2n - 1)$ square board contains an arrow, either pointing up, down,to the left, or to the right. A beetle sits in one of the cells. Each year it creeps from one square in the direction of the arrow in that square, either reaching another square or leaving the board. Each time the beetle moves, the arrow in the square it leaves turns $\frac{\pi}{2}$ clockwise. Prove that the beetle leaves the board in at most $2^{3n-1}(n-1)!-4$ years after it first moves.

Ten points are marked in the plane so that no three of them lie on the same straight line. All points are connected with segments.Each of these segments is painted one of the $k$ colors. For what positive integer $k$ ($1 \le k \le 5$) is it possible to paint the segments so that for any $k$ of the given $10$ points there are $k$ segments with the ends at these $k$ points, all of these segments being painted $k$ different colors ? (E. Barabanov)

Proctors Andy and Kristin have a PUMaC team of eight students labelled $s_1, s_2, ... , s_8$ (the PUMaC staff being awful with names). The following occurs: $1$. Andy tells the students to arrange themselves in a line in arbitrary order. $2$. Kristin tells each student $s_i$ to move to the current spot of student $s_j$ , where $j \equiv 3i + 1$ (mod $8$). $3$. Andy tells each student $s_i$ to move to the current spot of the student who was in the $i$th position of the line after step $1$. How many possible orders can the students be in now?

$n \ge 4$ real numbers are arranged in a circle. It turned out that for any four consecutive numbers $a, b, c, d$, that lie on the circle in this order, holds $a+d = b+c$. For which $n$ does it follow that all numbers on the circle are equal? [i]Proposed by Oleksiy Masalitin[/i]

[b]p1.[/b] What is $20\times 19 + 20 \div (2 - 7)$? [b]p2.[/b] Will has three spinners. The first has three equally sized sections numbered $1$, $2$, $3$; the second has four equally sized sections numbered $1$, $2$, $3$, $4$; and the third has five equally sized sections numbered $1$, $2$, $3$, $4$, $5$. When Will spins all three spinners, the probability that the same number appears on all three spinners is $p$. Compute $\frac{1}{p}$. [b]p3.[/b] Three girls and five boys are seated randomly in a row of eight desks. Let $p$ be the probability that the students at the ends of the row are both boys. If $p$ can be expressed in the form $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$, compute $m + n$. [b]p4.[/b] Jaron either hits a home run or strikes out every time he bats. Last week, his batting average was $.300$. (Jaron's batting average is the number of home runs he has hit divided by the number of times he has batted.) After hitting $10$ home runs and striking out zero times in the last week, Jaron has now raised his batting average to $.310$. How many home runs has Jaron now hit? [b]p5.[/b] Suppose that the sum $$\frac{1}{1 \cdot 4} +\frac{1}{4 \cdot 7}+ ...+\frac{1}{97 \cdot 100}$$ is expressible as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$. Compute $m + n$. [b]p6.[/b] Let $ABCD$ be a unit square with center $O$, and $\vartriangle OEF$ be an equilateral triangle with center $A$. Suppose that $M$ is the area of the region inside the square but outside the triangle and $N$ is the area of the region inside the triangle but outside the square, and let $x = |M -N|$ be the positive difference between $M$ and $N$. If $$x =\frac1 8(p -\sqrt{q})$$ for positive integers $p$ and $q$, find $p + q$. [b]p7.[/b] Find the number of seven-digit numbers such that the sum of any two consecutive digits is divisible by $3$. For example, the number $1212121$ satisfies this property. [b]p8.[/b] There is a unique positive integer $x$ such that $x^x$ has $703$ positive factors. What is $x$? [b]p9.[/b] Let $x$ be the number of digits in $2^{2019}$ and let $y$ be the number of digits in $5^{2019}$. Compute $x + y$. [b]p10.[/b] Let $ABC$ be an isosceles triangle with $AB = AC = 13$ and $BC = 10$. Consider the set of all points $D$ in three-dimensional space such that $BCD$ is an equilateral triangle. This set of points forms a circle $\omega$. Let $E$ and $F$ be points on $\omega$ such that $AE$ and $AF$ are tangent to $\omega$. If $EF^2$ can be expressed in the form $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers, determine $m + n$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A finite set of points $X$ and an equilateral triangle $T$ are given on a plane. Suppose that every subset $X'$ of $X$ with no more than $9$ elements can be covered by two images of $T$ under translations. Prove that the whole set $X$ can be covered by two images of $T$ under translations.

A fair coin is repeatedly flipped until $2019$ consecutive coin flips are the same. Compute the probability that the first and last flips of the coin come up differently.

[b]8.1 / 7.4[/b] What number needs to be put in place * so that the next the problem had a unique solution: “There are n straight lines on the plane, intersecting at * points. Find n.” ? [b]8.2 / 7.3[/b] Prove that for any natural number $n$ the number $ n(2n+1)(3n+1)...(1966n + 1) $ is divisible by every prime number less than $1966$. [b]8.3 / 7.6[/b] There are $n$ points on the plane so that any triangle with vertices at these points has an area less than $1$. Prove that all these points can be enclosed in a triangle of area $4$. [b]8.4[/b] Prove that the sum of all divisors of the number $n^2$ is odd. [b]8.5[/b] A quadrilateral has three obtuse angles. Prove that the larger of its two diagonals emerges from the vertex of an acute angle. [b]8.6[/b] Numbers $x_1, x_2, . . . $ are constructed according to the following rule: $$x_1 = 2, x_2 = (x^5_1 + 1)/5x_1, x_3 = (x^5_2 + 1)/5x_2, ...$$ Prove that no matter how much we continued this construction, all the resulting numbers will be no less $1/5$ and no more than $2$. PS. You should use hide for answers.Collected [url=https://artofproblemsolving.com/community/c3988082_1966_leningrad_math_olympiad]here[/url].

Let $\mathcal{P}_0=A_0A_1\ldots A_{n-1}$ be a convex polygon such that $A_iA_{i+1}=2^{[i/2]}$ for $i=0, 1,\ldots ,n-1$ (where $A_n=A_0$). Define the sequence of polygons $\mathcal{P}_k=A_0^kA_1^k\ldots A_{n-1}^k$ as follows: $A_i^1$ is symmetric to $A_i$ with respect to $A_0$, $A_i^2$ is symmetric to $A_i^1$ with respect to $A_1^1$, $A_i^3$ is symmetric to $A_i^2$ with respect to $A_2^2$ and so on. Find the values of $n$ for which infinitely many polygons $\mathcal{P}_k$ coincide with $\mathcal{P}_0$.

Let $n$ be even positive integer. There are $n$ real positive numbers written on the blackboard. In every step, we choose two numbers, erase them, and replace [i]each[/i] of then by their product. Show that for any initial $n$-tuple it is possible to obtain $n$ equal numbers on the blackboard after a finite number of steps. [i]Proposed by Peter Novotný[/i]

On the control board of a nuclear station, there are $n$ electric switches ($n > 0$), all in one row. Each switch has two possible positions: up and down. The switches are connected to each other in such a way that, whenever a switch moves down from its upper position, its right neighbour (if it exists) automatically changes position. At the beginning, all switches are down. The operator of the board first changes the position of the leftmost switch once, then the position of the second leftmost switch twice etc., until eventually he changes the position of the rightmost switch n times. How many switches are up after all these operations?

Let $ k > 1$ be an integer, and consider the infinite array given by the integer lattice in the first quadrant of the plane, filled with real numbers. The array is said to be constant if all its elements are equal in value. The array is said to be $ k$-balanced if it is non-constant, and the sums of the elements of any $ k\times k$ sub-square have a constant value $ v_k$. An array which is both $ p$-balanced and $ q$-balanced will be said to be $ (p, q)$-balanced, or just doubly-balanced, if there is no confusion as to which $ p$ and $ q$ are meant. If $p, q$ are relatively prime, the array is said to be co-prime. We will call $ (M\times N)$-seed a $ M \times N$ array, anchored with its lower left corner in the origin of the plane, which extended through periodicity in both dimensions in the plane results into a $ (p, q)$-balanced array; more precisely, if we denote the numbers in the array by $ a_{ij}$ , where $ i, j$ are the coordinates of the lower left corner of the unit square they lie in, we have, for all non-negative integers $ i, j$ \[ a_{i \plus{} M,j} \equal{} a_{i,j} \equal{} a_{i,j \plus{} N}\] (a) Prove that $ q^2v_p \equal{} p^2v_q$ for a $ (p, q)$-balanced array. (b) Prove that more than two different values are used in a co-prime $ (p,q)$-balanced array. Show that this is no longer true if $ (p, q) > 1$. (c) Prove that any co-prime $ (p, q)$-balanced array originates from a seed. (d) Show there exist $ (p, q)$-balanced arrays (using only three different values) for arbitrary values $ p, q$. (e) Show that neither a $ k$-balanced array, nor a $ (p, q)$-balanced array if $ (p, q) > 1$, need originate from a seed. (f) Determine the minimal possible value $ T$ for a square $ (T\times T)$-seed resulting in a co-prime $ (p, q)$-balanced array, when $p,q$ are both prime. (g) Show that for any relatively prime $ p, q$ there must exist a co-prime $ (p, q)$-balanced array originating from a square $ (T\times T)$-seed, with no lesser $ (M\times N)$-seed available ($ M\leq T, N\leq T$ and $MN< T^2$). [i]Dan Schwarz[/i]

In lawn-tennis the player who scores at least four points, while his opponent scores at least two points less, wins a game. The player who wins at least six games, while his opponent wins at least two games less, wins a set. What minimum percentage of all points does the winner have to score in a set?

A group of $100$ kids has a deck of $101$ cards numbered by $0, 1, 2,\dots, 100$. The first kid takes the deck, shuffles it, and then takes the cards one by one; when he takes a card (not the last one in the deck), he computes the average of the numbers on the cards he took up to that moment, and writes down this average on the blackboard. Thus, he writes down $100$ numbers, the first of which is the number on the first taken card. Then he passes the deck to the second kid which shuffles the deck and then performs the same procedure, and so on. This way, each of $100$ kids writes down $100$ numbers. Prove that there are two equal numbers among the $10000$ numbers on the blackboard.

Let $n\ge 3$ be an integer. In a country there are $n$ airports and $n$ airlines operating two-way flights. For each airline, there is an odd integer $m\ge 3$, and $m$ distinct airports $c_1, \dots, c_m$, where the flights offered by the airline are exactly those between the following pairs of airports: $c_1$ and $c_2$; $c_2$ and $c_3$; $\dots$ ; $c_{m-1}$ and $c_m$; $c_m$ and $c_1$. Prove that there is a closed route consisting of an odd number of flights where no two flights are operated by the same airline.

There are ten congruent segments on a plane. Each intersection point divides every segment passing through it in the ratio $3:4$. Find the maximum number of intersection points.

Eva draws an equilateral triangle and its altitudes. In a first step she draws the center triangle of the equilateral triangle, in a second step the center triangle of this center triangle and so on. After each step Eva counts all triangles whose sides lie completely on drawn lines. What is the minimum number of center triangles she must have drawn so that the figure contains more than 2022 such triangles?

There are $ 63$ points arbitrarily on the circle $ \mathcal{C}$ with its diameter being $ 20$. Let $ S$ denote the number of triangles whose vertices are three of the $ 63$ points and the length of its sides is no less than $ 9$. Fine the maximum of $ S$.