Consider a $3k \times 3k$ square grid (where $k$ is a positive integer), the cells in the grid are coordinated in terms of columns and rows: Cell $(i, j)$ is at the $i^{\text{th}}$ column from left to right and the $j^{\text{th}}$ row from bottom up. We want to place $4k$ marbles in the cells of the grid, with each cell containing at most one marble, such that - Each row and each column has at least one marble - For each marble, there is another marble placed on the same row or column with that marble. a) Assume $k=1$. Determine the number of ways to place the marbles to satisfy the above conditions (Two ways to place marbles are different if there is a cell $(i, j)$ having a marble placed in one way but not in the other way). b) Assume $k \geq 1$. Find the largest positive integer $N$ such that if we mark any $N$ cells on the board, there is always a way to place $4k$ marbles satisfying the above conditions such that none of the marbles are placed on any of the marked cells.

There are two airlines A and B and finitely many airports. For each pair of airports, there is exactly one airline among A and B whose flights operates in both directions. Each airline plans to develop world travel packages which pass each airport exactly once using only its flights. Let $a$ and $b$ be the number of possible packages which belongs to A and B respectively. Prove that $a-b$ is a multiple of $4$. The official statement of the problem has been changed. The above is the form which appeared during the contest. Now the condition 'the number of airports is no less than 4'is attached. Cite the following link. [url]https://artofproblemsolving.com/community/c6h2923697p26140823[/url]

A one player game is played on the triangular board shown on the picture. A token is placed on each circle. Each token is white on one side and black on the other. Initially, the token at one vertex of the triangle has the black side up, while the others have the white sides up. A move consists of removing a token with the black side up and turning over the adjacent tokens (two tokens are adjacent if they are joined by a segment). Is it possible to remove all the tokens by a sequence of moves? [img]https://cdn.artofproblemsolving.com/attachments/d/2/aabf82a0ddd6907482f27e6e0f1e1b56cd931d.png[/img]

A fire that starts in the steppe spreads in all directions at a speed of $1$ km per hour. A grader with a plow arrived on the fire line at the moment when the fire engulfed a circle with a radius of $1$ km. The grader moves at a speed of $14$ km per hour and cuts a strip with a plow that cuts off the fire. Indicate the path along which the grader should move so that the total area of the burnt steppe does not exceed: a) $4 \pi $ km$^2$; b) $3 \pi $ km$^2$. (We can assume that the grader’s path consists of straight segments and circular arcs.)

On the table there are written numbers $673, 674, \cdots, 2018, 2019.$ Nibab chooses arbitrarily three numbers $a,b$ and $c$, erases them and writes the number $\frac{\min(a,b,c)}{3}$, then he continues in an analogous way. After Nibab performed this operation $673$ times, on the table remained a single number $k$. Prove that $k\in(0,1).$

Sugar Station sells $44$ different kinds of candies, packaged one to a box. Each box is priced at a positive integer number of cents, and it costs $\$1.51$ to buy one of every kind. (There is no discount based on the number of candies in a purchase.) Unfortunately, Anna only has $\$0.75$. [list=a] [*] Show that Anna can buy at least $22$ boxes, each containing a different candy. [*] Show that Anna can do even better, buying at least $25$ boxes, each containing a different candy. [/list]

Let $n$ be a positive integer such that there exists a positive integer that is less than $\sqrt{n}$ and does not divide $n$. Let $(a_1, . . . , a_n)$ be an arbitrary permutation of $1, . . . , n$. Let $a_{i1} < . . . < a_{ik}$ be its maximal increasing subsequence and let $a_{j1} > . . . > a_{jl}$ be its maximal decreasing subsequence. Prove that tuples $(a_{i1}, . . . , a_{ik})$ and $(a_{j1}, . . . , a_{jl} )$ altogether contain at least one number that does not divide $n$.

In an $6 \times 6$ grid of lattice points, how many ways are there to choose $ 4$ points that are vertices of a nondegenerate quadrilateral with at least one pair of opposite sides parallel to the sides of the grid?

Barry has a standard die containing the numbers 1-6 on its faces. He rolls the die continuously, keeping track of the sum of the numbers he has rolled so far, starting from 0. Let $E_n$ be the expected number of time he needs to until his recorded sum is at least $n$. It turns out that there exist positive reals $a, b$ such that $$\lim_{n \rightarrow \infty} E_n - (an + b) = 0$$ Find $(a,b)$. [i]Proposed by Dilhan Salgado[/i]

Let $ A = \{ 1, 2, 3, \cdots , 12 \} $. Find the number of one-to-one function $ f :A \to A $ satisfying following condition: for all $ i \in A $, $ f(i)-i $ is not a multiple of $ 3 $.

Let $X=\{1,2,3,...,10\}$. Find the number of pairs of $\{A,B\}$ such that $A\subseteq X, B\subseteq X, A\ne B$ and $A\cap B=\{5,7,8\}$.

Three acute triangles are inscribed in the same circle with their vertices being nine distinct points. Show that one can choose a vertex from each triangle so that the three chosen points determine a triangle each of whose angles is at most $90^\circ$.

In a set of objects, each has one of two colors and one of two shapes. There is at least one object of each color and at least one object of each shape. Prove that there exist two objects in the set that are different both in color and in shape.

Sir Alex plays the following game on a row of 9 cells. Initially, all cells are empty. In each move, Sir Alex is allowed to perform exactly one of the following two operations: [list=1] [*] Choose any number of the form $2^j$, where $j$ is a non-negative integer, and put it into an empty cell. [*] Choose two (not necessarily adjacent) cells with the same number in them; denote that number by $2^j$. Replace the number in one of the cells with $2^{j+1}$ and erase the number in the other cell. [/list] At the end of the game, one cell contains $2^n$, where $n$ is a given positive integer, while the other cells are empty. Determine the maximum number of moves that Sir Alex could have made, in terms of $n$. [i]Proposed by Warut Suksompong, Thailand[/i]

In each side of a regular polygon with $n$ sides, we choose a point different from the vertices and we obtain a new polygon of $n$ sides. For which values of $n$ can we obtain a polygon such that the internal angles are all equal but the polygon isn't regular?

There are $2017$ lines in the plane such that no three of them go through the same point. Turbo the snail sits on a point on exactly one of the lines and starts sliding along the lines in the following fashion: she moves on a given line until she reaches an intersection of two lines. At the intersection, she follows her journey on the other line turning left or right, alternating her choice at each intersection point she reaches. She can only change direction at an intersection point. Can there exist a line segment through which she passes in both directions during her journey?

A triangle has an angle of measure $\theta$. It is dissected into several triangles. Is it possible that all angles of the resulting triangles are less than $\theta$, if (a) $\theta = 70^o$ ? (b) $\theta = 80^o$ ?

Let $n$ be the answer to this problem. Box $B$ initially contains n balls, and Box $A$ contains half as many balls as Box $B$. After $80$ balls are moved from Box $A$ to Box $B$, the ratio of balls in Box $A$ to Box $B$ is now $\frac{p}{q}$ , where $p$, $q$ are positive integers with gcd$(p, q) = 1$. Find $100p + q$.

Find number of terms when we expand $(a+b+c)^{99}$ (in the general case).

On a $999\times 999$ board a [i]limp rook[/i] can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A [i]non-intersecting route[/i] of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called [i]cyclic[/i], if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over. How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit? [i]Proposed by Nikolay Beluhov, Bulgaria[/i]

Some of the towns in a country are connected with bidirectional paths, where each town can be reached by any other by going through these paths. From each town there are at least $n \geq 3$ paths. In the country there is no such route that includes all towns exactly once. Find the least possible number of towns in this country (Answer depends from $n$).

Let $M$ be a set of $n \ge 4$ points in the plane, no three of which are collinear. Initially these points are connected with $n$ segments so that each point in $M$ is the endpoint of exactly two segments. Then, at each step, one may choose two segments $AB$ and $CD$ sharing a common interior point and replace them by the segments $AC$ and $BD$ if none of them is present at this moment. Prove that it is impossible to perform $n^3 /4$ or more such moves. [i]Proposed by Vladislav Volkov, Russia[/i]

each cells in a $9\times 9 $ grid is painted either blue or red.two cells are called [i]diagonal neighbors[/i] if their intersection is exactly a point.show that some cell has exactly two red neighbors,or exactly two blue neighbors, or both.

In a country, there are \( n \) cities. Each pair of cities is connected either by a paved road or a dirt road. It is known that there exists a pair of cities such that it is impossible to travel between them using only paved roads. Show that, in this case, it is possible to travel between any two cities using only dirt roads.

$239$ wise men stand in a circle near an opaque baobab. The king put on the head of each of these wise men a hat og one of $16$ colors. Each wise men does nor know the color of his hat and can only see the two nearest wise men on each side around the circle. Without communicating, these wise men must at the same time make a guess about the color of their hat $($i.e, tell one color$)$. These wise men were allowed to consult in advance, while they are afraid of being too lucky. What is the maximum $k$ for which, in any arrangement of hats, they can certainly ensure that no more than $k$ wise men guess the color of their hats$?$