Show that a path on a rectangular grid which starts at the northwest corner, goes through each point on the grid exactly once, and ends at the southeast corner divides the grid into two equal halves: (a) those regions opening north or east; and (b) those regions opening south or west. [img]https://cdn.artofproblemsolving.com/attachments/b/e/aa20c9f9bc44bd1e5a9b9e86d49debf0f821b7.png[/img] (The figure above shows a path meeting the conditions of the problem on a $5 \times 8$ grid. The shaded regions are those opening north or east while the rest open south or west.)

Initially, the number $1$ is written on the blackboard. At each step, the number on the blackboard is erased and another is written, which is obtained by applying any of the following operations: Operation A: Multiply the number on the board with $\frac12$. Operation B: Subtract the number on the board from $1$. For example, if the number $\frac38$ is on the board, it can be replaced by $\frac12 \frac38=\frac{3}{16}$ or by $1-\frac38=\frac58$ . Give a sequence of steps after which the number on the board is $\frac{2009}{2^{20009}}$ .

On a circle, Alina draws $2019$ chords, the endpoints of which are all different. A point is considered [i]marked[/i] if it is either $\text{(i)}$ one of the $4038$ endpoints of a chord; or $\text{(ii)}$ an intersection point of at least two chords. Alina labels each marked point. Of the $4038$ points meeting criterion $\text{(i)}$, Alina labels $2019$ points with a $0$ and the other $2019$ points with a $1$. She labels each point meeting criterion $\text{(ii)}$ with an arbitrary integer (not necessarily positive). Along each chord, Alina considers the segments connecting two consecutive marked points. (A chord with $k$ marked points has $k-1$ such segments.) She labels each such segment in yellow with the sum of the labels of its two endpoints and in blue with the absolute value of their difference. Alina finds that the $N + 1$ yellow labels take each value $0, 1, . . . , N$ exactly once. Show that at least one blue label is a multiple of $3$. (A chord is a line segment joining two different points on a circle.)

Let $n$ be a positive integer. There is a collection of cards that meets the following properties: $\bullet$Each card has a number written in the form $m!$, where $m$ is a positive integer. $\bullet$For every positive integer $t\le n!$, it is possible to choose one or more cards from the collection in such a way $\text{ }$that the sum of the numbers of those cards is $t$. Determine, based on $n$, the smallest number of cards that this collection can have.

A table tennis club hosts a series of doubles matches following several rules: (i) each player belongs to two pairs at most; (ii) every two distinct pairs play one game against each other at most; (iii) players in the same pair do not play against each other when they pair with others respectively. Every player plays a certain number of games in this series. All these distinct numbers make up a set called the “[i]set of games[/i]”. Consider a set $A=\{a_1,a_2,\ldots ,a_k\}$ of positive integers such that every element in $A$ is divisible by $6$. Determine the minimum number of players needed to participate in this series so that a schedule for which the corresponding [i]set of games [/i] is equal to set $A$ exists.

Let $n\geq 3$ be an integer. Let also $P_1,P_2,...,P_n$ be different two-element-subsets of $M=\{1,2,...,n\}$, such that when for $i,j \in M , i\neq j$ the sets $P_i,P_j$ are not totally disjoint, then there is a $k \in M$ with $P_k = \{ i,j\}$. Prove that every element of $M$ occurse in exactly $2$ of these subsets.

Two symbols $A$ and $B$ obey the rule $ABBB = B$. Given a word $x_1x_2\ldots x_{3n+1}$ consisting of $n$ letters $A$ and $2n+1$ letters $B$, show that there is a unique cyclic permutation of this word which reduces to $B$.

Around a circular table an even number of persons have a discussion. After a break they sit again around the circular table in a different order. Prove that there are at least two people such that the number of participants sitting between them before and after a break is the same.

[i]Alice[/i], who works for the [i]Graph County Electric Works[/i], is commissioned to wire the newly erected utility poles in $k$ days. Each day she either chooses a pole and runs wires from it to as many poles as she wishes, or chooses at most $17$ pairs of poles and runs wires between each pair. [i]Bob[/i], who works for the [i]Graph County Paint Works[/i], claims that, no matter how many poles there are and how [i]Alice[/i] connects them, all the poles can be painted using not more than $2009$ colors in such a way that no pair of poles connected by a wire is the same color. Determine the greatest value of $k$ for which [i]Bob[/i]'s claim is valid.

On an infinite square grid we place finitely many [i]cars[/i], which each occupy a single cell and face in one of the four cardinal directions. Cars may never occupy the same cell. It is given that the cell immediately in front of each car is empty, and moreover no two cars face towards each other (no right-facing car is to the left of a left-facing car within a row, etc.). In a [i]move[/i], one chooses a car and shifts it one cell forward to a vacant cell. Prove that there exists an infinite sequence of valid moves using each car infinitely many times. [i]Nikolai Beluhov[/i]

Let $\mathcal{F}$ be a finite family of subsets of some set $X{}$. It is known that for any two elements $x,y\in X$ there exists a permutation $\pi$ of the set $X$ such that $\pi(x)=y$, and for any $A\in\mathcal{F}$ \[\pi(A):=\{\pi(a):a\in A\}\in\mathcal{F}.\]A bear and crocodile play a game. At a move, a player paints one or more elements of the set $X$ in his own color: brown for the bear, green for the crocodile. The first player to fully paint one of the sets in $\mathcal{F}$ in his own color loses. If this does not happen and all the elements of $X$ have been painted, it is a draw. The bear goes first. Prove that he doesn't have a winning strategy.

[b]p1.[/b] The following figure represents a rectangular piece of paper $ABCD$ whose dimensions are $4$ inches by $3$ inches. When the paper is folded along the line segment $EF$, the corners $A$ and $C$ coincide. (a) Find the length of segment $EF$. (b) Extend $AD$ and $EF$ so they meet at $G$. Find the area of the triangle $\vartriangle AEG$. [img]https://cdn.artofproblemsolving.com/attachments/d/4/e8844fd37b3b8163f62fcda1300c8d63221f51.png[/img] [b]p2.[/b] (a) Let $p$ be a prime number. If $a, b, c$, and $d$ are distinct integers such that the equation $(x -a)(x - b)(x - c)(x - d) - p^2 = 0$ has an integer solution $r$, show that $(r - a) + (r - b) + (r - c) + (r - d) = 0$. (b) Show that $r$ must be a double root of the equation $(x - a)(x - b)(x - c)(x - d) - p^2 = 0$. [b]p3.[/b] If $\sin x + \sin y + \sin z = 0$ and $\cos x + \cos y + \cos z = 0$, prove the following statements. (a) $\cos (x - y) = -\frac12$ (b) $\cos (\theta - x) + \cos(\theta - y) + \cos (\theta - z) = 0$, for any angle $\theta$. (c) $\sin^2 x + \sin^2 y + \sin^2 z =\frac32$ [b]p4.[/b] Let $|A|$ denote the number of elements in the set $A$. (a) Construct an infinite collection $\{A_i\}$ of infinite subsets of the set of natural numbers such that $|A_i \cap A_j | = 0$ for $i \ne j$. (b) Construct an infinite collection $\{B_i\}$ of infinite subsets of the set of natural numbers such that $|B_i \cap B_j |$ gives a distinct integer for every pair of $i$ and $j$, $i \ne j$. [b]p5.[/b] Consider the equation $x^4 + y^4 = z^5$. (a) Show that the equation has a solution where $x, y$, and $z$ are positive integers. (b) Show that the equation has infinitely many solutions where $x, y$, and $z$ are positive integers. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A pawn is placed on a square of a $ n \times n$ board. There are two types of legal moves: (a) the pawn can be moved to a neighbouring square, which shares a common side with the current square; or (b) the pawn can be moved to a neighbouring square, which shares a common vertex, but not a common side with the current square. Any two consecutive moves must be of different type. Find all integers $ n \ge 2$, for which it is possible to choose an initial square and a sequence of moves such that the pawn visits each square exactly once (it is not required that the pawn returns to the initial square).

A row of $1000$ numbers is written on the blackboard. We write a new row, below the first according to the rule: We write under every number $a$ the natural number, indicating how many times the number $a$ is encountered in the first line. Then we write down the third line: under every number $b$ -- the natural number, indicating how many times the number $b$ is encountered in the second line, and so on. a) Prove that there is a line that coincides with the preceding one. b) Prove that the eleventh line coincides with the twelfth. c) Give an example of the initial line such, that the tenth row differs from the eleventh.

On the plane are given a convex $n$-gon $P_1P_2....P_n$ and a point $Q$ inside it, not lying on any of its diagonals. Prove that if $n$ is even, then the number of triangles $P_iP_jP_k$ containing the point $Q$ is even.

Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$. Prove that Sisyphus cannot reach the aim in less than \[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \] turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )

Let $a_1, a_2, ....., a_{2003}$ be sequence of reals number. Call $a_k$ $leading$ element, if at least one of expression $a_k; a_k+a_{k+1}; a_k+a_{k+1}+a_{k+2}; ....; a_k+a{k+1}+a_{k+2}+....+a_{2003}$ is positive. Prove, that if exist at least one $leading$ element, then sum of all $leading$'s elements is positive. Official solution [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=125&t=365714&p=2011659#p2011659]here[/url]

Let $n\ge 4$ be a positive integer. Megavan and Minivan are playing a game, where Megavan secretly chooses a real number $x$ in $[0, 1]$. At the start of the game, the only information Minivan has about $x$ is $x$ in $[0, 1]$. He needs to now learn about $x$ based on the following protocols: at each turn of his, Minivan chooses a number $y$ and submits to Megavan, where Megavan replies immediately with one of $y > x$, $y < x$, or $y\simeq x$, subject to two rules: $\bullet$ The answers in the form of $y > x$ and $y < x$ must be truthful; $\bullet$ Define the score of a round, known only to Megavan, as follows: $0$ if the answer is in the form $y > x$ and $y < x$, and $|x - y|$ if in the form $y\simeq x$. Then for every positive integer $k$ and every $k$ consecutive rounds, at least one round has score no more than $\frac{1}{k + 1}$. Minivan's goal is to produce numbers $a, b$ such that $a\le x\le b$ and $b - a\le \frac 1n$. Let $f(n)$ be the minimum number of queries that Minivan needs in order to guarantee success, regardless of Megavan's strategy. Prove that $$n\le f(n) \le 4n$$ [i]Proposed by Anzo Teh Zhao Yang[/i]

Albrecht fills in each cell of an $8 \times 8$ table with a $0$ or a $1$. Then at the end of each row and column he writes down the sum of the $8$ digits in that row or column, and then he erases the original digits in the table. Afterwards, he claims to Berthold that given only the sums, it is possible to restore the $64$ digits in the table uniquely. Show that the $8 \times 8$ table contained either a row full of $0$’s or a column full of $1$’s

Let $a_1, . . . , a_n$ be positive integers satisfying the inequality $\sum_{i=1}^{n}\frac{1}{a_n}\le \frac{1}{2}$. Every year, the government of Optimistica publishes its Annual Report with n economic indicators. For each $i = 1, . . . , n$,the possible values of the $i-th$ indicator are $1, 2, . . . , a_i$. The Annual Report is said to be optimistic if at least $n - 1$ indicators have higher values than in the previous report. Prove that the government can publish optimistic Annual Reports in an infinitely long sequence.

The Wonder Island is inhabited by Hedgehogs. Each Hedgehog consists of three segments of unit length having a common endpoint, with all three angles between them $120^{\circ}$. Given that all Hedgehogs are lying flat on the island and no two of them touch each other, prove that there is a finite number of Hedgehogs on Wonder Island.

$ n\geq 2$ cars are participating in a rally. The cars leave the start line at different times and arrive at the finish line at different times. During the entire rally each car takes over any other car at most once , the number of cars taken over by each car is different and each car is taken over by the same number of cars. Find all possible values of $ n$

Rishabh has $2024$ pairs of socks in a drawer. He draws socks from the drawer uniformly at random, without replacement, until he has drawn a pair of identical socks. Compute the expected number of unpaired socks he has drawn when he stops.

Suppose a box contains $28$ balls: $1$ red, $2$ blue, $3$ yellow, $4$ orange, $5$ purple, $6$ green, and $7$ pink. One by one, each ball is removed uniformly at random and without replacement until all $28$ balls have been removed. Determine the probability that the most likely “scenario of exhaustion” occurs; that is, determine the probability that the first color to have all such balls removed from the box is red, that the second is blue, the third is yellow, the fourth is orange, the fifth is purple, the sixth is green, and the seventh is pink.

Three piles of stones are given, initially containing 2000, 4000, and 4899 stones respectively. Ali and Baba play the following game, taking turns, with Ali starting first. In one move, a player can choose two piles and transfer some stones from one pile to the other, provided that at the end of the move, the pile from which the stones are moved has no fewer stones than the pile to which the stones are moved. The player who cannot make a move loses. Does either player have a winning strategy, and if so, who?