A cube of dimensions $20 \times 20 \times 20$ is constructed with blocks of $1 \times 2 \times 2$. Prove that there is a line that passes through the cube but not any block.

[u]Round 1 [/u] [b]p1.[/b] Pirate Jim had $8$ boxes with gun powder weighing $1, 2, 3, 4, 5, 6, 7$, and $8$ pounds (the weight is printed on top of every box). Pirate Bob hid a $1$-pound gold bar in one of these boxes. Pirate Jim has a balance scale that he can use, but he cannot open any of the boxes. Help him find the box with the gold bar using two weighings on the balance scale. [b]p2.[/b] James Bond will spend one day at Dr. Evil's mansion to try to determine the answers to two questions: a) Is Dr. Evil at home? b) Does Dr. Evil have an army of ninjas? The parlor in Dr. Evil's mansion has three windows. At noon, Mr. Bond will sneak into the parlor and use open or closed windows to signal his answers. When he enters the parlor, some windows may already be opened, and Mr. Bond will only have time to open or close one window (or leave them all as they are). Help Mr. Bond and Moneypenny design a code that will tell Moneypenny the answers to both questions when she drives by later that night and looks at the windows. Note that Moneypenny will not have any way to know which window Mr. Bond opened or closed. [b]p3.[/b] Suppose that you have a triangle in which all three side lengths and all three heights are integers. Prove that if these six lengths are all different, there cannot be four prime numbers among them. p4. Fred and George have designed the Amazing Maze, a $5\times 5$ grid of rooms, with Adorable Doors in each wall between rooms. If you pass through a door in one direction, you gain a gold coin. If you pass through the same door in the opposite direction, you lose a gold coin. The brothers designed the maze so that if you ever come back to the room in which you started, you will find that your money has not changed. Ron entered the northwest corner of the maze with no money. After walking through the maze for a while, he had $8$ shiny gold coins in his pocket, at which point he magically teleported himself out of the maze. Knowing this, can you determine whether you will gain or lose a coin when you leave the central room through the north door? [b]p5.[/b] Bill and Charlie are playing a game on an infinite strip of graph paper. On Bill’s turn, he marks two empty squares of his choice (not necessarily adjacent) with crosses. Charlie, on his turn, can erase any number of crosses, as long as they are all adjacent to each other. Bill wants to create a line of $2013$ crosses in a row. Can Charlie stop him? [u]Round 2 [/u] [b]p6.[/b] $1000$ non-zero numbers are written around a circle and every other number is underlined. It happens that each underlined number is equal to the sum of its two neighbors and that each non-underlined number is equal to the product of its two neighbors. What could the sum of all the numbers written on the circle be? [b]p7.[/b] A grasshopper is sitting at the edge of a circle of radius $3$ inches. He can hop exactly $4$ inches in any direction, as long as he stays within the circle. Which points inside the circle can the grasshopper reach if he can make as many jumps as he likes? [img]https://cdn.artofproblemsolving.com/attachments/1/d/39b34b2b4afe607c1232f4ce9dec040a34b0c8.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Billy let his herd freely. Enjoying their time the horses started to jump on the squares of a lattice of meadow that is infinite in both directions. Each horse can jump as follows: horizontally or vertically moves three, then turn to left and moves two. Naturally, under the jump a horse don’t touch the ground. The horses are standing on squares that no two can meet by such a jump. How many horses does Billy have if their number is the maximum possible? [i]The figure below shows where a horse can jump to. Notice that there 4 places and not 8 like in chess.[/i] [img]https://cdn.artofproblemsolving.com/attachments/c/6/8b6f9ca4e0aad46a13e133d87bcd4dd4384e7a.png[/img]

Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^m$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2k}(n)=n+k$, and let $k_n$ be the smallest such $k$. Prove that the sequence $k_1,k_2,\ldots $ is unbounded. [i]Proposed by Palmer Mebane, United States[/i]

A set $S$ has $7$ elements. Several $3$-elements subsets of $S$ are listed, such that any $2$ listed subsets have exactly $1$ common element. What is the maximum number of subsets that can be listed?

[b]8.1[/b] $x$ and $y$ are the roots of the equation $t^2-ct-c=0$. Prove that holds the inequality $x^3 + y^3 + (xy)^3 \ge 0.$ [b]8.2.[/b] Two circles touch internally at point $A$ . Through a point $B$ of the inner circle, different from $A$, a tangent to this circle intersecting the outer circle at points C and $D$. Prove that $AB$ is a bisector of angle $CAD$. [img]https://cdn.artofproblemsolving.com/attachments/2/8/3bab4b5c57639f24a6fd737f2386a5e05e6bc7.png[/img] [b]8.3[/b] Prove that $2^{3^{100}} + 1$ is divisible by $3^{101}$. [b]8.4 / 7.5[/b] An entire arc of circle is drawn through the vertices $A$ and $C$ of the rectangle $ABCD$ lying inside the rectangle. Draw a line parallel to $AB$ intersecting $BC$ at point $P$, $AD$ at point $Q$, and the arc $AC$ at point $R$ so that the sum of the areas of the figures $AQR$ and $CPR$ is the smallest. [img]https://cdn.artofproblemsolving.com/attachments/1/4/9b5a594f82a96d7eff750e15ca6801a5fc0bf1.png [/img] [b]8.5[/b] In a certain group of people, everyone has one enemy and one Friend. Prove that these people can be divided into two companies so that in every company there will be neither enemies nor friends. [b]8.6[/b] Numbers $a_1, a_2, . . . , a_{100}$ are such that $$a_1 - 2a_2 + a_3 \le 0$$ $$a_2-2a_3 + a_ 4 \le 0$$ $$...$$ $$a_{98}-2a_{99 }+ a_{100} \le 0$$ and at the same time $a_1 = a_{100}\ge 0$. Prove that all these numbers are non-negative. PS. You should use hide for answers.Collected [url=https://artofproblemsolving.com/community/c3988083_1967_leningrad_math_olympiad]here[/url].

There are $2023$ guinea pigs placed in a circle, from which everyone except one of them, call it $M$, has a mirror that points towards one of the $2022$ other guinea pigs. $M$ has a lantern that will shoot a light beam towards one of the guinea pigs with a mirror and will reflect to the guinea pig that the mirror is pointing and will keep reflecting with every mirror it reaches. Isaías will re-direct some of the mirrors to point to some other of the $2023$ guinea pigs. In the worst case scenario, what is the least number of mirrors that need to be re-directed, such that the light beam hits $M$ no matter the starting point of the light beam?

In Durer’s duck school, there are six rows of doors, as seen on the diagram; both rows are made up of three doors. Dodo duck wishes to enter the school from the street in a way that she uses all six doors exactly once. (On her path, she may go to the street again, or leave the school, so long as she finishes her path in the school.) How many ways can she perform this? [i]Two paths are considered different if Dodo takes the doors in a different order.[/i] [img]https://cdn.artofproblemsolving.com/attachments/5/1/8b722eb2c642e8275928753921fdfbd7495df9.png[/img]

$n$ red and $n$ blue points on a plane are given so that no three of the $2n$ points are collinear. Prove that it is always possible to split up the points into $n$ pairs, with one red and one blue point in each pair, so that no two of the $n$ line segments which connect the two members of a pair intersect.

A chessboard has 64 cells painted black and white in the usual way. A bishop path is a sequence of distinct cells such that two consecutive cells have exactly one common point. At least how many bishop paths can the set of all white cells be divided into?

Let $A_1,A_2,...,A_n$ be $n$ finite subsets of a set $X, n \ge 2$, such that (i) $|A_i| \ge 2, 1 \le i \le n$, (ii) $ |A_i \cap A_j | \ne 1, j \le i < j \le n$. Prove that the elements of $A_1 \cup A_2 \cup ... \cup A_n$ may be colored with $2$ colors so that no $A_i$ is colored by the same color.

The intelligence quotient (IQ) of a country is defined as the average IQ of its entire population. It is assumed that the total population and individual IQs remain constant throughout. (a) (i) A group of people from country $A$ has emigrated to country $B$ . Show that it can happen that as a result , the IQs of both countries have increased. (ii) After this, a group of people from $B$, which may include immigrants from $A$, emigrates to $A$. Can it happen that the IQs of both countries will increase again? (b) A group of people from country $A$ has emigrated to country $B$, and a group of people from $B$ has emigrated to country $C$ . It is known that a s a result , the IQs o f all three countries have increased. After this, a group of people from $C$ emigrates to $B$ and a group of people from $B$ emigrates to $A$. Can it happen that the IQs of all three countries will increase again? (A Kanel, B Begun)

Let $n \ne 0$ be a natural number. A sequence of numbers is briefly called a sequence “$F_n$” if $n$ different numbers $z_1$, $z_2$, $...$, $z_n$ exist so that the following conditions are fulfilled: (1) Each term of the sequence is one of the numbers $z_1$, $z_2$, $...$, $z_n$. (2) Each of the numbers $z_1$, $z_2$, $...$, $z_n$ occurs at least once in the sequence. (3) Any two immediately consecutive members of the sequence are different numbers. (4) No subsequence of the sequence has the form $\{a, b, a, b\}$ with $a \ne b$. Note: A subsequence of a given sequence $\{x_1, x_2, x_3, ...\}$ or $\{x_1, x_2, x_3, ..., x_s\}$ is called any sequence of the form $\{x_{m1}, x_{m2}, x_{m3}, ...\}$ or $\{x_{m1}, x_{m2}, x_{m3}, ..., x_{mt}\}$ with natural numbers $m_1 < m_2 < m_3 < ...$ Answer the following questions: a) Given $n$, are there sequences $F_n$ of arbitrarily long length? b) If question (a) is answered in the negative for an $n$: What is the largest possible number of terms that a sequence $F_n$ can have (given $n$)?

All $ 2n\ge 2 $ squares of a $ 2\times n $ rectangle are colored with three colors. We say that a color has a [i]cut[/i] if there is some column (from all $ n $) that has both squares colored with it. Determine: [b]a)[/b] the number of colorings that have no cuts. [b]b)[/b] the number of colorings that have a single cut.

Let $n$ be an odd positive integer. There is a graph $G$ with $2n$ vertices such that if you partition the vertices into two groups $A$ and $B$ with $n$ vertices each, then the subgraph consisting of only vertices and edges within $A$ is connected and has a closed path containing all of its edges, starting and ending with the same vertex. The same condition is true for $B$ as well. Is $G$ necessarily a clique? [i](Proposed by Ho Janson)[/i]

Given a $19 \times 19$ matrix where each component is either $1$ or $-1$. Let $b_i$ be the product of all components in the $i$-th row, and $k_i$ be the product of all components in the $i$-th column, for all $1 \le i \le 19$. Prove that for any such matrix, $b_1 + k_1 + b_2 + k_2 + \cdots + b_{19} + k_{19} \neq 0$.

An $8\times 8$ chessboard is to be tiled (i.e., completely covered without overlapping) with pieces of the following shapes: [asy] unitsize(.6cm); draw(unitsquare,linewidth(1)); draw(shift(1,0)*unitsquare,linewidth(1)); draw(shift(2,0)*unitsquare,linewidth(1)); label("\footnotesize $1\times 3$ rectangle",(1.5,0),S); draw(shift(8,1)*unitsquare,linewidth(1)); draw(shift(9,1)*unitsquare,linewidth(1)); draw(shift(10,1)*unitsquare,linewidth(1)); draw(shift(9,0)*unitsquare,linewidth(1)); label("\footnotesize T-shaped tetromino",(9.5,0),S); [/asy] The $1\times 3$ rectangle covers exactly three squares of the chessboard, and the T-shaped tetromino covers exactly four squares of the chessboard. [list](a) What is the maximum number of pieces that can be used? (b) How many ways are there to tile the chessboard using this maximum number of pieces?[/list]

In a school there are $1200$ students. Each student is part of exactly $k$ clubs. For any $23$ students, they are part of a common club. Finally, there is no club to which all students belong. Find the smallest possible value of $k$.

We say a positive integer $ n$ is [i]good[/i] if there exists a permutation $ a_1, a_2, \ldots, a_n$ of $ 1, 2, \ldots, n$ such that $ k \plus{} a_k$ is perfect square for all $ 1\le k\le n$. Determine all the good numbers in the set $ \{11, 13, 15, 17, 19\}$.

A white equilateral triangle is split into $n^2$ equal smaller triangles by lines that are parallel to the sides of the triangle. Denote a [i]line of triangles[/i] to be all triangles that are placed between two adjacent parallel lines that forms the grid. In particular, a triangle in a corner is also considered to be a line of triangles. We are to paint all triangles black by a sequence of operations of the following kind: choose a line of triangles that contains at least one white triangle and paint this line black (a possible situation with $n=6$ after four operations is shown in Figure 1; arrows show possible next operations in this situation). Find the smallest and largest possible number of operations.

The king assembled 300 wizards and gave them the following challenge. For this challenge, 25 colors can be used, and they are known to the wizards. Each of the wizards receives a hat of one of those 25 colors. If for each color the number of used hats would be written down then all these number would be different, and the wizards know this. Each wizard sees what hat was given to each other wizard but does not see his own hat. Simultaneously each wizard reports the color of his own hat. Is it possible for the wizards to coordinate their actions beforehand so that at least 150 of them would report correctly?

For $n=2^m$ (m is a positive integer) consider the set $M(n) = \{ 1,2,...,n\}$ of natural numbers. Prove that there exists an order $a_1, a_2, ..., a_n$ of the elements of M(n), so that for all $1\leq i < j < k \leq n$ holds: $a_j - a_i \neq a_k - a_j$.

a) Let $1, 2, 3, 5, 6, 7, 10, .., N$ be all the divisors of $N = 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31$ (the product of primes $2$ to $31$) written in increasing order. Below this series of divisors, write the following series of $1$’s or $-1$’s: write $1$ below any number that factors into an even number of prime factors and below a $1$, write $-1$ below the remaining numbers. Prove that the sum of the series of $1$’s and $-1$’s is equal to $0$. b) Let $1, 2, 3, 5, 6, 7, 10, .., N$ be all the divisors of $N = 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37$ (the product of primes $2$ to $37$) written in increasing order. Below this series of divisors, write the following series of $1$’s or $-1$’s: write $1$ below any number that factors into an even number of prime factors and below a $1$, write $-1$ below the remaining numbers. Prove that the sum of the series of $1$’s and $-1$’s is equal to $0$.

A [i]word[/i] is a sequence of 0 and 1 of length 8. Let $ x$ and $ y$ be two words differing in exactly three places. Prove that the number of words differing from each of $ x$ and $ y$ in at least five places is 188.