Consider a matrix whose entries are integers. Adding a same integer to all entries on a same row, or on a same column, is called an operation. It is given that, for infinitely many positive integers $n$, one can obtain, through a finite number of operations, a matrix having all entries divisible by $n$. Prove that, through a finite number of operations, one can obtain the null matrix.

At a strange party, each person knew exactly $22$ others. For any pair of people $X$ and $Y$ who knew one another, there was no other person at the party that they both knew. For any pair of people $X$ and $Y$ who did not know each other, there were exactly six other people that they both knew. How many people were at the party?

The partition of $2n$ positive integers into $n$ pairs is called [i]square-free[/i] if the product of numbers in each pair is not a perfect square.Prove that if for $2n$ distinct positive integers, there exists one square-free partition, then there exists at least $n!$ square-free partitions.

Alice and Bob play a game on a strip of $n \ge 3$ squares with two game pieces. At the beginning, Alice’s piece is on the first square while Bob’s piece is on the last square. The figure shows the starting position for a strip of $ n = 7$ squares. [img]https://cdn.artofproblemsolving.com/attachments/1/7/c636115180fd624cbeec0c6adda31b4b89ed60.png[/img] The players alternate. In each move, they advance their own game piece by one or two squares in the direction of the opponent’s piece. The piece has to land on an empty square without jumping over the opponent’s piece. Alice makes the first move with her own piece. If a player cannot move, they lose. For which $n$ can Bob ensure a win no matter how Alice plays? For which $n$ can Alice ensure a win no matter how Bob plays? [i](Karl Czakler)[/i]

Peter has several $100$ ruble notes and no other money. He starts buying books; each book costs a positive integer number of rubles, and he gets change in $1$ ruble coins. Whenever Peter is buying an expensive book for $100$ rubles or higher he uses only $100$ ruble notes in the minimum necessary number. Whenever he is buying a cheap one (for less than $100$ rubles) he uses his coins if he has enough, otherwise using a $100$ ruble note. When the $100$ ruble notes have come to the end, Peter has expended exactly a half of his money. Is it possible that he has expended $5000$ rubles or more? (Tatiana Kazitsina)

Prove that the edges of a simple planar graph can always be oriented such that the outdegree of all vertices is at most three. [i]UK Competition Problem[/i]

We call a permutation of the set of real numbers $\{a_1,\cdots,a_n\}$, $n\in\mathbb{N}$ [i]average increasing[/i] if the arithmetic mean of its first $k$ elements for $k=1,\cdots ,n$ form a strictly increasing sequence. 1) Depending on $n$, determine the smallest number that can be the last term of some average increasing permutation of the numbers $\{1,\cdots,n\}$; 2) Depending on $n$, determine the lowest position (in some general order) that the number $n$ can be achieved in some average increasing permutation of the numbers $\{1,\cdots,n\}.$ [i] Proposed by David Hruska, Czech Republic[/i]

An $8\times 8$ square board is divided into $64$ unit squares. A ’skew-diagonal’ of the board is a set of $8$ unit squares no two of which are in the same row or same column. Checkers are placed in some of the unit squares so that ’each skew-diagonal contains exactly two squares occupied by checkers’. Prove that there exist two rows or two columns which contain all the checkers.

Consider $37$ distinct points in space, all with integer coordinates. Prove that we may find among them three distinct points such that their barycentre has integers coordinates.

Given a matrix $\{a_{ij}\}_{i,j=0}^{9}$, $a_{ij}=10i+j+1$. Andrei is going to cover its entries by $50$ rectangles $1\times 2$ (each such rectangle contains two adjacent entries) so that the sum of $50$ products in these rectangles is minimal possible. Help him. [i]A. Badzyan[/i]

Consider the following layouts of nine triangles with the letters $A, B, C, D, E, F, G, H, I$ in its interior. [asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */ import graph; size(200); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = 1.740000000000003, xmax = 8.400000000000013, ymin = 3.500000000000005, ymax = 9.360000000000012; /* image dimensions */ draw((5.020000000000005,8.820000000000011)--(2.560000000000003,4.580000000000005)--(7.461947712046029,4.569577506690286)--cycle); /* draw figures */ draw((5.020000000000005,8.820000000000011)--(2.560000000000003,4.580000000000005)); draw((2.560000000000003,4.580000000000005)--(7.461947712046029,4.569577506690286)); draw((7.461947712046029,4.569577506690286)--(5.020000000000005,8.820000000000011)); draw((3.382989341689345,5.990838871467448)--(4.193333333333338,4.580000000000005)); draw((4.202511849578174,7.405966442513598)--(5.828619600041468,4.573707435672692)); draw((5.841878190157451,7.408513542990484)--(4.193333333333338,4.580000000000005)); draw((6.656214943659867,5.990342259816768)--(5.828619600041468,4.573707435672692)); draw((4.202511849578174,7.405966442513598)--(5.841878190157451,7.408513542990484)); draw((3.382989341689345,5.990838871467448)--(6.656214943659867,5.990342259816768)); label("\textbf{A}",(4.840000000000007,8.020000000000010),SE*labelscalefactor,fontsize(22)); label("\textbf{B}",(3.980000000000006,6.640000000000009),SE*labelscalefactor,fontsize(22)); label("\textbf{C}",(4.820000000000007,7.000000000000010),SE*labelscalefactor,fontsize(22)); label("\textbf{D}",(5.660000000000008,6.580000000000008),SE*labelscalefactor,fontsize(22)); label("\textbf{E}",(3.160000000000005,5.180000000000006),SE*labelscalefactor,fontsize(22)); label("\textbf{F}",(4.020000000000006,5.600000000000008),SE*labelscalefactor,fontsize(22)); label("\textbf{G}",(4.800000000000007,5.200000000000007),SE*labelscalefactor,fontsize(22)); label("\textbf{H}",(5.680000000000009,5.620000000000007),SE*labelscalefactor,fontsize(22)); label("\textbf{I}",(6.460000000000010,5.140000000000006),SE*labelscalefactor,fontsize(22)); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */[/asy] A sequence of letters, each letter chosen from$ A, B, C, D, E, F, G, H, I$ is said to be [i]triangle-friendly[/i] if the first and last letter of the sequence is $C$, and for every letter except the first letter, the triangle containing this letter shares an edge with the triangle containing the previous letter in the sequence. For example, the letter after $C$ must be either $A, B$, or $D$. For example, $CBF BC$ is triangle-friendly, but $CBF GH$ and $CBBHC$ are not. [list] [*] (a) Determine the number of triangle-friendly sequences with $2012$ letters. [*] (b) Determine the number of triangle-friendly sequences with exactly $2013$ letters.[/list]

A computer is programmed to randomly generate a string of six symbols using only the letters $A,B,C$. What is the probability that the string will not contain three consecutive $A$'s?

A polygon is decomposed into triangles by drawing some non-intersecting interior diagonals in such a way that for every pair of triangles of the triangulation sharing a common side, the sum of the angles opposite to this common side is greater than $180^o$. a) Prove that this polygon is convex. b) Prove that the circumcircle of every triangle used in the decomposition contains the entire polygon. [i]Proposed by Morteza Saghafian - Iran[/i]

Let $n$ be a positive integer. On the table, we have $n^2$ ornaments in $n$ different colours, not necessarily $n$ of each colour. Prove that we can hang the ornaments on $n$ Christmas trees in such a way that there are exactly $n$ ornaments on each tree and the ornaments on every tree are of at most $2$ different colours.

In the cells of a $5 \times 5$ grid there are some lamps. If a lamp is touched, it is turned on and it lights up all of its neighbouring cells, including its own cell. If a cell is lit up and there is a lamp in it, the lamp is also turned on and lights up its neighbouring cells, including its own. What is the smallest number of lamps needed to light up all of the cells with just one touch? [i](Note: Two cells are neighbours if they have a common side or vertex.)[/i]

Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that: \[ a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. \]

There are $n\geq1$ cities on a horizontal line. Each city is guarded by a pair of stationary elephants, one just to the left and one just ot the right of the city, and facing away from it. The $2n$ elephants are of different sizes. If an elephant walks forward, it will knock aside any elephant that it approaches from behind, and in face-to-face meeting, the smaller elephant will be knocked aside. A moving elephant will keep walking in the same direction until it is knocked aside. Show that there is a unique city with the property that if any of the other cities orders its elephants to walk, then that city will not be invaded by an elephant. [url=https://artofproblemsolving.com/community/c6h1268873p6622370]IMO 2015, Shortlist C1[/url], modified by G. Smith

We consider $5 \times 5$ tables containing a real number in each of the $25$ cells. The same number may occur in different cells, but no row or column contains five equal numbers. Such a table is [i]balanced [/i] if the number in the middle cell of every row and column is the average of the numbers in that row or column. A cell is called [i]small [/i] if the number in that cell is strictly smaller than the number in the cell in the very middle of the table. What is the least number of small cells that a balanced table can have?

Initially, the numbers $1$ and $2$ are written on the board. A move consists of choosing a positive real number $x$ and replacing $(a,b)$ on the board by $\left(a+\frac{x}{b},b+\frac{x}{a}\right)$. Is it possible to create in finitely many moves a situation where the numbers on the board are $2$ and $3$?

A museum has the shape of a $n \times n$ square divided into $n^2$ rooms of the shape of a unit square $(n>1)$. Between every two adjacent rooms (i.e. sharing a wall) there is a door. A night guardian wants to organize an inspection journey through the museum according to the following rules. He starts from some room and, whenever he enters a room, he stays there for exactly one minute and then proceeds to another room. He is allowed to enter a room more than once, but at the end of his journey he must have spent exactly $k$ minutes in every room. Find all $n$ and $k$ for which it is possible to organize such a journey.

Ten monkeys have 60 bananas. Each monkey has at least one banana and any two monkeys have different amounts of bananas. Prove that any six monkeys can distribute their bananas between others such that all 4 remaining monkeys have the same amount of bananas. [i]A. Voidelevich[/i]

In each of the different grades of a high school there are an odd number of pupils. Each pupil has a best friend (who possibly is in a different grade). Everyone is the best friend of their best friend. In the upcoming school trip, every pupil goes to either Rome or Paris. Show that the pupils can be distributed over the two destinations in such a way that (i) every student goes to the same destination as their best friend; (ii) for each grade the absolute difference between the number of pupils that are going to Rome and that of those who are going to Paris is equal to $1$.

A table $2 \times 2024$ is filled with positive integers. Specifically, the first row is filled with numbers from the set $\{1, \ldots, 2023\}$. It turned out that for any two columns the difference of numbers from the first row is divisible by the difference of numbers from the second row, while all numbers in the second row are pairwise different. Is it true for sure that the numbers in the first row are equal? Ivan Kukharchuk

On the plane with a rectangular coordinate system, a set of infinitely many rectangles is given. Every rectangle has the origin as one of its vertices. The sides of all rectangles are parallel to the coordinate axes, and all sides have integer lengths. Prove that there are at least two rectangles in the set, one of which completely covers the other.

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 $.