Olympiad problems

2021 Nigerian Senior MO Round 2, 2

Tags: combinatorics

$N$ boxes are arranged in a circle and are numbered $1,2,3,.....N$ In a clockwise direction. A ball is assigned a number from${1,2,3,....N}$ and is placed in one of the boxes.A round consist of the following; if the current number on the ball is $n$, the ball is moved $n$ boxes in the clockwise direction and the number on the ball is changed to $n+1$ if $n<N$ and to $1$ if $n=N$. Is it possible to choose $N$, the initial number on the ball, and the first position of the ball in such a way that the ball gets back to the same box with the same number on it for the first time after exactly $2020$ rounds

2002 Tuymaada Olympiad, 1

Tags: modular arithmetic , combinatorics

Each of the points $G$ and $H$ lying from different sides of the plane of hexagon $ABCDEF$ is connected with all vertices of the hexagon. Is it possible to mark 18 segments thus formed by the numbers $1, 2, 3, \ldots, 18$ and arrange some real numbers at points $A, B, C, D, E, F, G, H$ so that each segment is marked with the difference of the numbers at its ends? [i]Proposed by A. Golovanov[/i]

2017 China Team Selection Test, 3

Tags: combinatorics

For a rational point (x,y), if xy is an integer that divided by 2 but not 3, color (x,y) red, if xy is an integer that divided by 3 but not 2, color (x,y) blue. Determine whether there is a line segment in the plane such that it contains exactly 2017 blue points and 58 red points.

2023 LMT Fall, 10

Tags: combinatorics

Aidan and Andrew independently select distinct cells in a $4 $ by $4$ grid, as well as a direction (either up, down, left, or right), both at random. Every second, each of them will travel $1$ cell in their chosen direction. Find the probability that Aidan and Andrew willmeet (be in the same cell at the same time) before either one of them hits an edge of the grid. (If Aidan and Andrew cross paths by switching cells, it doesn’t count as meeting.)

2018 Iran Team Selection Test, 6

Tags: graph theory , combinatorics

A simple graph is called "divisibility", if it's possible to put distinct numbers on its vertices such that there is an edge between two vertices if and only if number of one of its vertices is divisible by another one. A simple graph is called "permutationary", if it's possible to put numbers $1,2,...,n$ on its vertices and there is a permutation $ \pi $ such that there is an edge between vertices $i,j$ if and only if $i>j$ and $\pi(i)< \pi(j)$ (it's not directed!) Prove that a simple graph is permutationary if and only if its complement and itself are divisibility. [i]Proposed by Morteza Saghafian[/i] .

2012 German National Olympiad, 2

Tags: graph theory , combinatorics

Find the maximal number of edges a connected graph $G$ with $n$ vertices may have, so that after deleting an arbitrary cycle, $G$ is not connected anymore.

2008 Princeton University Math Competition, A5/B7

Tags: combinatorics

In how many ways can Alice, Bob, Charlie, David, and Eve split $18$ marbles among themselves so that no two of them have the same number of marbles?

1999 China National Olympiad, 3

Tags: combinatorics

There are $99$ space stations. Each pair of space stations is connected by a tunnel. There are $99$ two-way main tunnels, and all the other tunnels are strictly one-way tunnels. A group of $4$ space stations is called [i]connected[/i] if one can reach each station in the group from every other station in the group without using any tunnels other than the $6$ tunnels which connect them. Determine the maximum number of connected groups.

1997 Iran MO (3rd Round), 3

Tags: combinatorics

There are $30$ bags and there are $100$ similar coins in each bag (coins in each bag are similar, coins of different bags can be different). The weight of each coin is an one digit number in grams. We have a digital scale which can weigh at most $999$ grams in each weighing. Using this scale, we want to find the weight of coins of each bag. [b](a)[/b] Show that this operation is possible by $10$ times of weighing, and [b](b)[/b] It's not possible by $9$ times of weighing.

2023 Durer Math Competition Finals, 2

Tags: combinatorics , number theory

Timi was born in $1999$. Ever since her birth how many times has it happened that you could write that day’s date using only the digits $0$, $1$ and $2$? For example, $2022.02.21$. is such a date.

2001 German National Olympiad, 2

Tags: geometry , rectangle , pigeonhole principle , combinatorics

Determine the maximum possible number of points you can place in a rectangle with lengths $14$ and $28$ such that any two of those points are more than $10$ apart from each other.

1974 Kurschak Competition, 1

Tags: combinatorics

A library has one exit and one entrance and a blackboard at each. Only one person enters or leaves at a time. As he does so he records the number of people found/remaining in the library on the blackboard. Prove that at the end of the day exactly the same numbers will be found on the two blackboards (possibly in a different order).

2014 Brazil Team Selection Test, 2

Tags: additive combinatorics , combinatorics , algorithm

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

2012 Iran MO (3rd Round), 2

Tags: geometry , inequalities , combinatorics

Suppose $S$ is a convex figure in plane with area $10$. Consider a chord of length $3$ in $S$ and let $A$ and $B$ be two points on this chord which divide it into three equal parts. For a variable point $X$ in $S-\{A,B\}$, let $A'$ and $B'$ be the intersection points of rays $AX$ and $BX$ with the boundary of $S$. Let $S'$ be those points $X$ for which $AA'>\frac{1}{3} BB'$. Prove that the area of $S'$ is at least $6$. [i]Proposed by Ali Khezeli[/i]

2010 Contests, 2

Tags: geometry , counting question , combinatorics

There are $n$ points in the page such that no three of them are collinear.Prove that number of triangles that vertices of them are chosen from these $n$ points and area of them is 1,is not greater than $\frac23(n^2-n)$.

1993 Spain Mathematical Olympiad, 5

Tags: grid , combinatorics , square grid

Given a 4×4 grid of points, the points at two opposite corners are denoted $A$ and $D$. We need to choose two other points $ B$ and $C$ such that the six pairwise distances of these four points are all distinct. (a) How many such quadruples of points are there? (b) How many such quadruples of points are non-congruent? (c) If each point is assigned a pair of coordinates $(x_i,y_i)$, prove that the sum of the expressions $|x_i-x_j |+|y_i-y_j|$ over all six pairs of points in a quadruple is constant.

1957 Moscow Mathematical Olympiad, 349

Tags: rectangle table , table , sum , combinatorics , geometry

For any column and any row in a rectangular numerical table, the product of the sum of the numbers in a column by the sum of the numbers in a row is equal to the number at the intersection of the column and the row. Prove that either the sum of all the numbers in the table is equal to $1$ or all the numbers are equal to $0$.

2006 Germany Team Selection Test, 1

Tags: combinatorics

A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off. [i]Proposed by Australia[/i]

2007 All-Russian Olympiad, 5

Tags: function , combinatorics , induction , algebra , polynomial

Two numbers are written on each vertex of a convex $100$-gon. Prove that it is possible to remove a number from each vertex so that the remaining numbers on any two adjacent vertices are different. [i]F. Petrov [/i]

2009 All-Russian Olympiad, 1

Tags: polynomial , combinatorics , algebra

Find all value of $ n$ for which there are nonzero real numbers $ a, b, c, d$ such that after expanding and collecting similar terms, the polynomial $ (ax \plus{} b)^{100} \minus{} (cx \plus{} d)^{100}$ has exactly $ n$ nonzero coefficients.

2002 Estonia National Olympiad, 5

Tags: combinatorics

There is a lottery at Juku’s birthday party with a number of identical prizes, where each guest can win at most one prize. It is known that if there was one prize less, then the number of possible distributions of the prizes among the guests would be $50\%$ less than it actually is, while if there was one prize more, then the number of possible distributions of the prizes would be $50\%$ more than it actually is. Find the number of possible distributions of the prizes.

1988 Tournament Of Towns, (181) 4

Tags: game strategy , combinatorics , game

There is a set of cards with numbers from $1$ to $30$ (which may be repeated) . Each student takes one such card. The teacher can perform the following operation: He reads a list of such numbers (possibly only one) and then asks the students to raise an arm if their number was in this list. How many times must he perform such an operation in order to determine the number on each student 's card? (Indicate the number of operations and prove that it is minimal . Note that there are not necessarily 30 students.)

2024 Czech and Slovak Olympiad III A, 3

Tags: tiling , tiles , combinatorics

Find the largest natural number $n$ such that any set of $n$ tetraminoes, each of which is one of the four shapes in the picture, can be placed without overlapping in a $20 \times 20$ table (no tetramino extends beyond the borders of the table), such that each tetramino covers exactly 4 cells of the 20x20 table. An individual tetramino is allowed to turn and flip at will. [img]https://cdn.artofproblemsolving.com/attachments/b/9/0dddb25c2aa07536b711ded8363679e47972d6.png[/img]

2023 Harvard-MIT Mathematics Tournament, 7

Tags: combinatorics

Svitlana writes the number $147$ on a blackboard. Then, at any point, if the number on the blackboard is $n$, she can perform one of the following three operations: $\bullet$ if $n$ is even, she can replace $n$ with $\frac{n}{2}$ $\bullet$ if $n$ is odd, she can replace $n$ with $\frac{n+255}{2}$ and $\bullet$ if $n \ge 64$, she can replace $n$ with $n - 64$. Compute the number of possible values that Svitlana can obtain by doing zero or more operations.

1997 Brazil Team Selection Test, Problem 5

Tags: combinatorics

Consider an infinite strip, divided into unit squares. A finite number of nuts is placed in some of these squares. In a step, we choose a square $A$ which has more than one nut and take one of them and put it on the square on the right, take another nut (from $A$) and put it on the square on the left. The procedure ends when all squares has at most one nut. Prove that, given the initial configuration, any procedure one takes will end after the same number of steps and with the same final configuration.