Olympiad problems

2021 Moldova EGMO TST, 4

Tags: combinatorics

On a board there are $4$ positive integers $a, b, c$ and $d$. Dan chooses three of them and writes their product on a paper. Then he substracts $1$ from the other number. He does this until $0$ appears on the board. What are the possible values of the sum of the numbers written on the paper?

2017 Bundeswettbewerb Mathematik, 2

Tags: combinatorics , polygon , coloring , isosceles

In a convex regular $35$-gon $15$ vertices are colored in red. Are there always three red vertices that make an isosceles triangle?

2019 Regional Olympiad of Mexico Northwest, 1

Tags: combinatorics , winning strategy

Jose and Maria play the following game: Maria writes $2019$ positive integers different on the blackboard. Jose deletes some of them (possibly none, but not all) and write to the left of each of the remaining numbers a sign $+$or a sign $-$. Then the sum written on the board is calculated. If the result is a multiple of $2019$, Jose wins the game, if not, Maria wins. Determine which of the two has a winning strategy.

2013 China Western Mathematical Olympiad, 4

Tags: floor function , combinatorics

There are $n$ coins in a row, $n\geq 2$. If one of the coins is head, select an odd number of consecutive coins (or even 1 coin) with the one in head on the leftmost, and then flip all the selected coins upside down simultaneously. This is a $move$. No move is allowed if all $n$ coins are tails. Suppose $m-1$ coins are heads at the initial stage, determine if there is a way to carry out $ \lfloor\frac {2^m}{3}\rfloor $ moves

2018 OMMock - Mexico National Olympiad Mock Exam, 6

Tags: combinatorics , elements of set

Let $A$ be a finite set of positive integers, and for each positive integer $n$ we define \[S_n = \{x_1 + x_2 + \cdots + x_n \;\vert\; x_i \in A \text{ for } i = 1, 2, \dots, n\}\] That is, $S_n$ is the set of all positive integers which can be expressed as sum of exactly $n$ elements of $A$, not necessarily different. Prove that there exist positive integers $N$ and $k$ such that $$\left\vert S_{n + 1} \right\vert = \left\vert S_n \right\vert + k \text{ for all } n\geq N.$$ [i]Proposed by Ariel García[/i]

2016 Saudi Arabia BMO TST, 4

Tags: combinatorics , coloring

How many ways are there to color the vertices of a square with $n$ colors $1,2, .. ., n$. (The colorings must be different so that we can’t get one from the other by a rotation.)

2022 Centroamerican and Caribbean Math Olympiad, 5

Tags: combinatorics , magic

Esteban the alchemist have $8088$ copper pieces, $6066$ bronze pieces, $4044$ silver pieces and $2022$ gold pieces. He can take two pieces of different metals and use a magic hammer to turn them into two pieces of different metals that he take and different each other. Find the largest number of gold pieces that Esteban can obtain after using the magic hammer a finite number of times. $\textbf{Note:}$ [i]If Esteban takes a copper and bronze pieces, then he turn them into a silver and a gold pieces.[/i]

2024 Macedonian Balkan MO TST, Problem 1

Tags: combinatorics , graph theory

In a given group of people $\mathcal{F}$, each member has at least two acquaintances from $\mathcal{F}$. Moreover, for each cycle $A_{1} \leftrightarrow A_{2} \leftrightarrow ... \leftrightarrow A_{n} \leftrightarrow A_{1}$ in $\mathcal{F}$ (here '$X \leftrightarrow Y$' means that $X$ and $Y$ are acquaintances), each $A_i$ knows exactly two other members $A_j$ of the cycle. Prove that there exist $X, Y \in \mathcal{F}$ such that each of them has exactly two acquaintances in $\mathcal{F}$, and $X, Y$ have at least one common acquaintance in the group. [i]Authored by Mirko Petrusevski[/i]

2020 SG Originals, Q1

Tags: combinatorics

Given a regular $(6n+3)$-gon, $3n$ of its vertices are used to form $n$ acute triangles with distinct vertices. Prove that the other $3n+3$ vertices can be used to form $n+1$ acute triangles with distinct vertices. [i]Lim Jeck[/i]

ICMC 5, 2

Tags: number theory , combinatorics , table

Find all integers $n$ for which there exists a table with $n$ rows, $2022$ columns, and integer entries, such that subtracting any two rows entry-wise leaves every remainder modulo $2022$. [i]Proposed by Tony Wang[/i]

2019 Ecuador NMO (OMEC), 4

Tags: combinatorics , game theory , sum of roots , strategy

Let $n> 1$ be a positive integer. Danielle chooses a number $N$ of $n$ digits but does not tell her students and they must find the sum of the digits of $N$. To achieve this, each student chooses and says once a number of $n$ digits to Danielle and she tells how many digits are in the correct location compared with $N$. Find the minimum number of students that must be in the class to ensure that students have a strategy to correctly find the sum of the digits of $N$ in any case and show a strategy in that case.

2021/2022 Tournament of Towns, P2

Tags: board , chess rook , combinatorics

There was a rook at some square of a $10 \times 10{}$ chessboard. At each turn it moved to a square adjacent by side. It visited each square exactly once. Prove that for each main diagonal (the diagonal between the corners of the board) the following statement is true: in the rook’s path there were two consecutive steps at which the rook first stepped away from the diagonal and then returned back to the diagonal. [i]Alexandr Gribalko[/i]

2009 Singapore Junior Math Olympiad, 2

Tags: combinatorics , number theory

The set of $2000$-digit integers are divided into two sets: the set $M$ consisting all integers each of which can be represented as the product of two $1000$-digit integers, and the set $N$ which contains the other integers. Which of the sets $M$ and $N$ contains more elements?

2015 QEDMO 14th, 12

Tags: combinatorics , probability

Steve stands in the middle of a field of an infinitely large chessboard, all of which are fields square and one square meter. Every second it randomly wanders into the middle one of the four neighboring fields, each of which has the same probability. How high is the probability that after $2015$ steps, he will have taken exactly five meters way from his starting square?

2025 Euler Olympiad, Round 2, 6

Tags: number theory , combinatorics , graph theory , iteration , algebra

For any subset $S \subseteq \mathbb{Z}^+$, a function $f : S \to S$ is called [i]interesting[/i] if the following two conditions hold: [b]1.[/b] There is no element $a \in S$ such that $f(a) = a$. [b]2.[/b] For every $a \in S$, we have $f^{f(a) + 1}(a) = a$ (where $f^{k}$ denotes the $k$-th iteration of $f$). Prove that: [b]a) [/b]There exist infinitely many interesting functions $f : \mathbb{Z}^+ \to \mathbb{Z}^+$. [b]b) [/b]There exist infinitely many positive integers $n$ for which there is no interesting function $$ f : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}. $$ [i]Proposed by Giorgi Kekenadze, Georgia[/i]

2014 Dutch IMO TST, 5

Tags: combinatorics

On each of the $2014^2$ squares of a $2014 \times 2014$-board a light bulb is put. Light bulbs can be either on or off. In the starting situation a number of the light bulbs is on. A move consists of choosing a row or column in which at least $1007$ light bulbs are on and changing the state of all $2014$ light bulbs in this row or column (from on to off or from off to on). Find the smallest non-negative integer $k$ such that from each starting situation there is a finite sequence of moves to a situation in which at most $k$ light bulbs are on.

2003 Gheorghe Vranceanu, 4

Tags: surjectivity , equivalence relation , combinatorics , function

Find the number of functions $ f:\mathbb{N}\longrightarrow\mathbb{N} $ having the property that $ (f\circ f\circ f)(n)=n+3, $ for any natural numbers $ n. $

2022 Czech and Slovak Olympiad III A, 6

Tags: combinatorics , graph theory

Consider any graph with $50$ vertices and $225$ edges. We say that a triplet of its (mutually distinct) vertices is [i]connected[/i] if the three vertices determine at least two edges. Determine the smallest and the largest possible number of connected triples. [i](Jan Mazak, Josef Tkadlec)[/i]

2015 Denmark MO - Mohr Contest, 5

Tags: combinatorics

For which numbers $n$ is it possible to put marks on a stick such that all distances $1$ cm, $2$ cm, . . . , $n$ cm each appear exactly once as the distance between two of the marks, and no other distance appears as such a distance?

2016 Argentina National Olympiad, 3

Tags: game , winning strategy , game strategy , combinatorics

Agustín and Lucas, by turns, each time mark a box that has not yet been marked on a $101\times 101$ grid board. Augustine starts the game. You cannot check a box that already has two checked boxes in its row or column. The one who can't make his move loses. Decide which of the two players has a winning strategy.

2011 Canada National Olympiad, 3

Tags: combinatorics , rectangle , geometry

Amy has divided a square into finitely many white and red rectangles, each with sides parallel to the sides of the square. Within each white rectangle, she writes down its width divided by its height. Within each red rectangle, she writes down its height divided by its width. Finally, she calculates $x$, the sum of these numbers. If the total area of white equals the total area of red, determine the minimum of $x$.

2024 Korea Junior Math Olympiad, 7

Tags: inequalities , combinatorics

Let $A_k$ be the number of pairs $(a_1, a_2, ..., a_{2k})$ for $k\leq 50$, where $a_1, a_2, ..., a_{2k}$ are all different positive integers that satisfy the following. [b]$\cdot$[/b] $a_1, a_2, ..., a_{2k} \leq 100$ [b]$\cdot$[/b] For an odd number less or equal than $2k-1$, we have $a_i > a_{i+1}$ [b]$\cdot$[/b] For an even number less or equal than $2k-2$, we have $a_i < a_{i+1}$ Prove that $A_1 \leq A_2 \leq \cdots \leq A_{49}$.

1989 Tournament Of Towns, (206) 4

Tags: combinatorics , combinatorial geometry , geometry , 3d geometry

Can one draw , on the surface of a Rubik's cube , a closed path which crosses each little square exactly once and does not pass through any vertex of a square? (S . Fomin, Leningrad)

1990 IMO Longlists, 60

Tags: analytic geometry , combinatorics , euler , 3d geometry , geometry

Unit cubes are made into beads by drilling a hole through them along a diagonal. The beads are put on a string in such a way that they can move freely in space under the restriction that the vertices of two neighboring cubes are touching. Let $ A$ be the beginning vertex and $ B$ be the end vertex. Let there be $ p \times q \times r$ cubes on the string $ (p, q, r \geq 1).$ [i](a)[/i] Determine for which values of $ p, q,$ and $ r$ it is possible to build a block with dimensions $ p, q,$ and $ r.$ Give reasons for your answers. [i](b)[/i] The same question as (a) with the extra condition that $ A \equal{} B.$

2009 Junior Balkan Team Selection Test, 2

Tags: combinatorics

From the set $ \{1,2,3,\ldots,2009\}$ we choose $ 1005$ numbers, such that sum of any $ 2$ numbers isn't neither $ 2009$ nor $ 2010$. Find all ways on we can choose these $ 1005$ numbers.