IMO 2022 (LXIII International Mathematical Olympiad)

Coin chain sorting process, same-type final coins

The Bank of Oslo issues two types of coin: aluminium (denoted $A$) and bronze (denoted $B$). Marianne has $n$ aluminium coins and $n$ bronze coins, arranged in a row in some arbitrary initial order. A chain is any subsequence of consecutive coins of the same type. Given a fixed positive integer $k\le 2n$, Marianne repeatedly performs the following operation: she identifies the longest chain containing the $k^{\text{th}}$ coin from the left, and moves all coins in that chain to the left end of the row. For example, if $n=4$ and $k=4$, the process starting from the ordering $AABBBABA$ would be $AABBBABA\to BBBAAABA\to AAABBBBA\to BBBBAAAA\to AAAABBBB\to BBBBAAAA\to \cdots$ Find all pairs $(n,k)$ with $1\le k\le 2n$ such that, starting from any initial ordering, at some moment during the process, the remaining $n$ coins will all be of the same type.

Topic: Combinatoria Metodo: Invarianti, Casework Abilita: Riconoscimento di pattern, Lettura attenta, Ragionamento geometrico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

This is the total amount of coins denominated in the currency of the Union.

The Bank of Oslo issues two types of coin: aluminium (denoted $A$) and bronze (denoted $B$). Marianne has $n$ aluminium coins and $n$ bronze coins, arranged in a row in some arbitrary initial order. A chain is any subsequence of consecutive coins of the same type. Given a fixed positive integer $k\le 2n$, Marianne repeatedly performs the following operation: she identifies the longest chain containing the $k^{\text{th}}$ coin from the left, and moves all coins in that chain to the left end of the row. For example, if $n=4$ and $k=4$, the process starting from the ordering $AABBBABA$ would be $AABBBABA\to BBBAAABA\to AAABBBBA\to BBBBAAAA\to AAAABBBB\to BBBBAAAA\to \cdots$ Find all pairs $(n,k)$ with $1\le k\le 2n$ such that, starting from any initial ordering, at some point during the process, the remaining $n$ coins will all be of the same type.

src_imho_2022__Q01

Find all functions f: R+ -> R+ with xf(y)+yf(x)≤2

Let ${\mathbb{R}}^{+}$ denote the set of positive real numbers. Find all functions $f:{\mathbb{R}}^{+}\to {\mathbb{R}}^{+}$ such that for each $x\in {\mathbb{R}}^{+}$, there is exactly one $y\in {\mathbb{R}}^{+}$ satisfying $xf(y)+yf(x)\le 2.$

Topic: Equazioni funzionali, Algebra Metodo: Estremalità, Casework Abilita: Manipolazione algebrica, Lettura attenta, Astrazione Area: Algebra e Analisi Fonte: apri PDF p.1

Find all functions f: R+ -> R+ with xf(y) +yf(x) ≤2

Let ${\mathbb{R}}^{+}$ denotes the set of positive real numbers. Find all functions $f:{\mathbb{R}}^{+}\to {\mathbb{R}}^{+}$ such that for each $x\in {\mathbb{R}}^{+}$, there is exactly one $y\in {\mathbb{R}}^{+}$ satisfying $xf(y)+yf(x)\le 2.$

src_imho_2022__Q02

Odd prime set on circle, neighbours product form x²+x+k

Let $k$ be a positive integer and let $S$ be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of $S$ around a circle such that the product of any two neighbours is of the form $x^2+x+k$ for some positive integer $x$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Grafi, Congruenze Abilita: Ragionamento geometrico, Modellizzazione, Manipolazione algebrica Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

Odd prime set on circle, neighbours product form x2+x+k

Let $k$ be a positive integer and let $S$ be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of $S$ around a circle such that the product of any two neighbors is of the form $x^2+x+k$ for some positive integer $x$.

src_imho_2022__Q03

Convex pentagon ABCDE with BC=DE, show P,S,Q,R concyclic

Let $ABCDE$ be a convex pentagon such that $BC=DE$. Assume that there is a point $T$ inside $ABCDE$ with $TB=TD$, $TC=TE$ and $\angle ABT=\angle TEA$. Let line $AB$ intersect lines $CD$ and $CT$ at points $P$ and $Q$, respectively. Let line $AE$ intersect lines $CD$ and $DT$ at points $R$ and $S$, respectively. Assume that the points $P$, $Q$, $A$, $S$ occur on their line in that order. Prove that the points $P$, $S$, $Q$, $R$ lie on a circle.

Topic: Geometria piana Metodo: Trigonometria, Coordinate Abilita: Ragionamento geometrico, Lettura attenta, Modellizzazione Area: Geometria Fonte: apri PDF p.1

Convex pentagon ABCDE with BC=DE, show P,S,Q,R concyclic

Let $ABCDE$ be a convex pentagon such that $BC=DE$. Assume that there is a point $T$ inside $ABCDE$ with $TB=TD$, $TC=TE$ and $\angle ABT=\angle TEA$. Let line $AB$ intersect lines $CD$ and $CT$ at points $P$ and $Q$, respectively. Let line $AE$ intersect lines $CD$ and $DT$ at points $R$ and $S$, respectively. Assumes that the points $P$, $Q$, $A$, $S$ occur on their line in that order. Prove that the points$P$,$S$,$Q$,$R$ lie on a circle.

src_imho_2022__Q04

Find all triples (a,b,p) positive integers, p prime, a^b+b=p^a

Find all triples $(a,b,p)$ of positive integers with $p$ prime and $a^b+b=p^a.$

Topic: Teoria dei Numeri Metodo: Congruenze, Casework, Fattorizzazione Abilita: Manipolazione algebrica, Casework accurato, Lettura attenta Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF p.1

Find all triples (a,b,p) positive integers, p prime, a^b+b=p

Find all triples $(a,b,p)$ of positive integers with $p$ prime and $a^b+b=p^a.$

src_imho_2022__Q05

Nordic square uphill paths: find minimum total as function of n

Let $n$ be a positive integer. A Nordic square is an $n\times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that: (i) the first cell in the sequence is a valley, (ii) each subsequent cell in the sequence is adjacent to the previous cell, and (iii) the numbers written in the cells in the sequence are in increasing order. Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

Topic: Combinatoria Metodo: Conteggio, Estremalità, Induzione Abilita: Conteggio sistematico, Riconoscimento di pattern, Modellizzazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

Nordic square uphill paths: find minimum total as function of n

Let $n$ be a positive integer. A Nordic square is a $n\times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that: (i) the first cell in the sequence is a valley, (ii) each subsequent cell in the sequence is adjacent to the previous cell, and (iii) the numbers written in the cells in the sequence are in increasing order. Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

src_imho_2022__Q06