Japan IMO Selection Camp 2022 — Selection Camp

Colorful integers on a circular arrangement; find maximum non-colorful

Let $n$ be an integer with $n\ge 3$. An integer $m\ge n+1$ is called $n$-colorful if there exists a way to write one integer from $\{1,2,\dots ,n\}$ in each of $m$ cells arranged in a circle such that the following condition holds:

For any $n+1$ consecutive cells and for any integer $i$ with $1\le i\le n$, there exists a cell among those $n+1$ cells containing the value $i$.

Prove that there are only finitely many positive integers that are not $n$-colorful, and find the largest such integer.

Topic: Combinatoria Metodo: Invarianti, Estremalità, Casework Abilita: Ragionamento geometrico, Conteggio sistematico, Manipolazione algebrica Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Interi colorati su una disposizione circolare; trovare il massimo non colorato

$n$ sia un numero intero con $n\ge 3$. Un intero $m\ge n+1$ è chiamato $n$-colorful se esiste un modo per scrivere un intero da $\{1,2,\dots ,n\}$ in ciascuna delle celle $m$ disposte in un cerchio in modo tale che la seguente condizione è valida:

Per tutte le celle $n+1$ consecutive e per ogni numero intero $i$ con $1\le i\le n$, esiste una cellula tra le celle $n+1$ contenente il valore $i$.

Prova che ci sono solo finitamente molti interi positivi che non sono $n$-colorati, e trova il più grande tale intero.

src_selection_camp_2022__Q01

Find all real functions satisfying a given functional equation

Find all functions $f:\mathbb{R}\to \mathbb{R}$ such that for all real numbers $x,y$, $f(xf(y)+f(f(y)))+yf(f(x))=f\left((f(f(x))+1)f(y)\right)+xy.$

Topic: Equazioni funzionali Metodo: Casework, Simmetria Abilita: Manipolazione algebrica, Lettura attenta, Ragionamento geometrico Area: Algebra e Analisi Fonte: apri PDF

Ricerca tutte le funzioni reali che soddisfano una determinata equazione funzionale

Trova tutte le funzioni $f:\mathbb{R}\to \mathbb{R}$ in modo che per tutti i numeri reali $x,y$, $f(xf(y)+f(f(y)))+yf(f(x))=f\left((f(f(x))+1)f(y)\right)+xy.$

src_selection_camp_2022__Q02

Sequence of positive integers with divisibility condition implies eventual periodicity

Let $a_1,a_2,\dots$ be a sequence of positive integers such that for any positive integers $n$ and $m$, $a_{n+2m}$ is divisible by $a_n+a_{n+m}$. Prove that there exist positive integers $N$ and $d$ such that $a_n=a_{n+d}$ holds for all integers $n\ge N$.

Topic: Teoria dei Numeri Metodo: Induzione, Congruenze, Invarianti Abilita: Manipolazione algebrica, Riconoscimento di pattern, Lettura attenta Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF

Sequenza di integri positivi con condizione di divisibilità implica una eventuale periodicità

Che $a_1,a_2,\dots$ sia una sequenza di integri positivi tale che per tutti gli integri positivi $n$ e $m$, $a_{n+2m}$ sia divisibile da $a_n+a_{n+m}$. Dimostrare che esistono integri positivi $N$ e $d$ in modo tale che $a_n=a_{n+d}$ sia valido per tutti gli integri $n\ge N$.

src_selection_camp_2022__Q03

Minimum value of sum of floor(a_i/i) over all permutations

Let $n$ be a positive integer. When $a_1,a_2,\dots ,a_n$ is a permutation of $1,2,\dots ,n$, find the minimum possible value of $\lfloor \frac{a_1}{1}\rfloor +\lfloor \frac{a_2}{2}\rfloor +\cdots +\lfloor \frac{a_n}{n}\rfloor .$ Here a permutation of $1,2,\dots ,n$ is a sequence of length $n$ in which each integer from $1$ to $n$ appears exactly once, and $\lfloor r\rfloor$ denotes the greatest integer not exceeding the real number $r$.

Topic: Combinatoria, Teoria dei Numeri Metodo: Estremalità, Casework, Conteggio Abilita: Manipolazione algebrica, Stima, Conteggio sistematico Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri Fonte: apri PDF

*Valuta minima della somma del pavimento a_i/i) su tutte le permutazioni *

$n$ sia un numero intero positivo. Quando $a_1,a_2,\dots ,a_n$ è una permutazione di $1,2,\dots ,n$, trovare il valore minimo possibile di $\lfloor \frac{a_1}{1}\rfloor +\lfloor \frac{a_2}{2}\rfloor +\cdots +\lfloor \frac{a_n}{n}\rfloor .$ Qui una permutazione di $1,2,\dots ,n$ è una sequenza di lunghezza $n$ in cui ogni numero intero da $1$ a $n$ appare esattamente una volta, e $\lfloor r\rfloor$ indica il numero intero più grande non superiore al numero reale $r$.

src_selection_camp_2022__Q04

Bead-moving game on a line with ratio r; find r allowing red bead to reach B in at most 2021 moves

Let $r>1$ be a rational number, and let $B$ and $R$ be two distinct points on a line. Initially, one blue bead is placed at $B$ and one red bead is placed at $R$. Taro repeatedly performs the following operation:

Choose an integer $k$ and a point $X$ at which one of the beads is placed. Let $Y$ be the point where the other bead is placed. On the ray $YX$, choose the point $X^{\prime }$ such that $Y{X}^{\prime }=r^k\cdot YX$. Then move the bead at $X$ to $X^{\prime }$.

Find all values of $r$ such that Taro can move the red bead to $B$ in at most $2021$ operations. Here $PQ$ denotes the length of segment $PQ$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Invarianti, Casework, Congruenze Abilita: Modellizzazione, Ragionamento geometrico, Manipolazione algebrica Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Gioco di movimentazione di perle su una linea con rapporto r; trovare r che consente alla perla rossa di raggiungere B in almeno 2021 mosse

Che $r>1$ sia un numero razionale, e che $B$ e $R$ siano due punti distinti su una linea. Inizialmente, una perla blu è collocata a $B$ e una perla rossa a $R$. Taro esegue ripetutamente la seguente operazione:

Selezionare un numero intero $k$ e un punto $X$ in cui si colloca una delle perle. Il punto in cui si colloca l’altra perla è $Y$. Sul raggio $YX$, scegliere il punto $X^{\prime }$ in modo tale che $Y{X}^{\prime }=r^k\cdot YX$. Poi spostare la perla a $X$ a $X^{\prime }$.

Trovare tutti i valori di $r$ in modo tale che Taro possa spostare il marchio rosso a $B$ in un massimo di $2021$ operazioni. Qui $PQ$ indica la lunghezza del segmento $PQ$.

src_selection_camp_2022__Q05

Three lines AM, PY, QX concur in a circle configuration

Let $\Gamma$ be a circle with diameter $MN$, and let $A$ be a point in the interior of $\Gamma$ (not on $\Gamma$). Let the circle centered at $N$ passing through $A$ meet $\Gamma$ at points $B$ and $C$. Let $P$ and $Q$ be distinct points on segment $BC$ (excluding the endpoints) such that $\angle BAP=\angle QAC$. Among the intersections of line $NP$ with $\Gamma$, let $X$ be the one other than $N$; among the intersections of line $NQ$ with $\Gamma$, let $Y$ be the one other than $N$. Prove that the three lines $AM$, $PY$, and $QX$ are concurrent.

Topic: Geometria piana Metodo: Trigonometria, Coordinate, Simmetria Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria Fonte: apri PDF

Tre linee AM, PY, QX convergono in una configurazione di cerchio

Il $\Gamma$ deve essere un cerchio di diametro $MN$ e $A$ deve essere un punto all’interno di $\Gamma$ (non su $\Gamma$). Il cerchio centrato a $N$ che passa attraverso $A$ deve incontrare $\Gamma$ nei punti $B$ e $C$. Il $P$ e il $Q$ devono essere punti distinti sul segmento $BC$ (esclusi i punti finali) in modo tale che $\angle BAP=\angle QAC$. Tra le intersezioni della linea $NP$ e $\Gamma$, $X$ sia quella diversa da $N$; tra le intersezioni della linea $NQ$ e $\Gamma$, $Y$ sia quella diversa da $N$. Prove che le tre linee $AM$, $PY$ e $QX$ sono simultanee.

src_selection_camp_2022__Q06

Three lines CD, AQ, BR concur in parallelogram configuration with circumcircles

Let $ABCD$ be a parallelogram with $AC=BC$, and let $P$ be a point on the extension of side $AB$ beyond $B$. The circumcircle of triangle $ACD$ meets segment $PD$ at a point $Q$ other than $D$, and the circumcircle of triangle $APQ$ meets segment $PC$ at a point $R$ other than $P$. Prove that the three lines $CD$, $AQ$, and $BR$ are concurrent. Here $XY$ denotes the length of segment $XY$.

Topic: Geometria piana Metodo: Trigonometria, Simmetria, Coordinate Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria Fonte: apri PDF

Tre linee CD, AQ, BR convergono in configurazione parallela con circoncircoli

$ABCD$ sia un parallelo con $AC=BC$ e $P$ sia un punto nell’estensione laterale $AB$ oltre $B$. Il circoncircolo del triangolo $ACD$ incontra il segmento $PD$ in un punto $Q$ diverso da $D$, e il circoncircolo del triangolo $APQ$ incontra il segmento $PC$ in un punto $R$ diverso da $P$. Prove che le tre linee $CD$, $AQ$ e $BR$ sono simultanee. Qui $XY$ indica la lunghezza del segmento $XY$.

src_selection_camp_2022__Q07

Minimum operations for chairman to achieve majority preference ordering

Let $m$ be an odd integer with $m\ge 3$, and let $n$ be an integer with $n\ge 3$. For each integer $i$ with $1\le i\le m$, let $a_{i,1},a_{i,2},\dots ,a_{i,n}$ be a permutation of $1,2,\dots ,n$.

A chairman and $m$ delegates (delegate $1$, delegate $2$, $\dots$, delegate $m$) are holding a meeting to select problems for this year’s IMO. There are $n$ candidate problems (problem $1$, problem $2$, $\dots$, problem $n$). Each delegate has a preference score for each problem, which is an integer from $1$ to $n$; the initial preference score of delegate $i$ for problem $j$ is $a_{i,j}$. The chairman can repeatedly perform the following operation:

Choose integers $i,j,k$ with $1\le i\le m$ and $1\le j,k\le n$ such that the difference between delegate $i$‘s preference scores for problem $j$ and problem $k$ is exactly $1$, and swap those two preference scores of delegate $i$.

Regardless of the values of the $mn$ integers $a_{i,j}$ ($1\le i\le m$, $1\le j\le n$), find the minimum non-negative integer $L$ such that the chairman can achieve the following condition by performing the operation at most $L$ times:

For any two distinct integers $x,y$ with $1\le x,y\le n$, there exist an integer $s\ge 2$ and a sequence $p_1,p_2,\dots ,p_s$ of integers from $1$ to $n$ with $p_1=x$ and $p_s=y$, such that for every integer $t$ with $1\le t\le s-1$, at least $\frac{m+1}{2}$ delegates have a strictly higher preference score for problem $p_{t+1}$ than for problem $p_t$.

Topic: Combinatoria Metodo: Estremalità, Invarianti, Casework, Conteggio Abilita: Modellizzazione, Conteggio sistematico, Ragionamento geometrico, Manipolazione algebrica Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Minimum di operazioni per il presidente per ottenere l’ordine di preferenza di maggioranza

Lasciate che $m$ sia un numero intero parente con $m\ge 3$, e lasciate che $n$ sia un numero intero con $n\ge 3$. Per ogni numero intero $i$ con $1\le i\le m$, $a_{i,1},a_{i,2},\dots ,a_{i,n}$ deve essere una permutazione di $1,2,\dots ,n$.

Un presidente e i delegati $m$ (delegato $1$, delegato $2$, $\dots$, delegato $m$) stanno tenendo una riunione per selezionare i problemi per l’IMO di quest’anno. Esistono problemi di candidato $n$ (problema $1$, problema $2$, $\dots$, problema $n$). Ogni delegato ha un punteggio di preferenza **** per ogni problema, che è un numero intero da $1$ a $n$; il punteggio di preferenza iniziale del delegato $i$ per il problema $j$ è $a_{i,j}$. Il presidente può eseguire ripetutamente la seguente operazione:

Scegliere i numeri interi $i,j,k$ con $1\le i\le m$ e $1\le j,k\le n$ in modo tale che la differenza tra i punteggi preferenziali del delegato $i$ per il problema $j$ e il problema $k$ sia esattamente $1$, e scambiare quei due punteggi preferenziali del delegato $i$.

Indipendentemente dai valori degli integri $mn$ $a_{i,j}$ ($1\le i\le m$, $1\le j\le n$), trovare il numero intero minimo non negativo $L$ in modo tale che il presidente possa ottenere la seguente condizione eseguendo l’operazione al massimo $L$ volte:

Per due numeri interi distinti $x,y$ con $1\le x,y\le n$, esiste un numero intero $s\ge 2$ e una sequenza $p_1,p_2,\dots ,p_s$ di numeri interi da $1$ a $n$ con $p_1=x$ e $p_s=y$, in modo tale che per ogni numero intero $t$ con $1\le t\le s-1$, almeno $\frac{m+1}{2}$ i delegati hanno un punteggio di preferenza strettamente superiore per il problema $p_{t+1}$ rispetto al problema $p_t$.

src_selection_camp_2022__Q08

Find all real functions with f(-1)=-1 satisfying a functional equation

Find all functions $f:\mathbb{R}\to \mathbb{R}$ such that for all real numbers $x,y$, $f(x)f(y)-f(x+y)=yf(x)-f(x+f(y))$ and $f(-1)=-1$.

Topic: Equazioni funzionali Metodo: Casework, Simmetria Abilita: Manipolazione algebrica, Lettura attenta, Riconoscimento di pattern Area: Algebra e Analisi Fonte: apri PDF

Ricerca tutte le funzioni reali con f(-1)=-1 che soddisfano un’equazione funzionale

Trova tutte le funzioni $f:\mathbb{R}\to \mathbb{R}$ in modo tale che per tutti i numeri reali $x,y$, $f(x)f(y)-f(x+y)=yf(x)-f(x+f(y))$ e $f(-1)=-1$.

src_selection_camp_2022__Q09

Find all n such that divisors can be arranged with all partial sums perfect squares

Let $n$ be a positive integer and let $d(n)$ denote the number of positive divisors of $n$. Find all positive integers $n$ for which there exists a sequence $a_1,a_2,\dots ,a_{d(n)}$ consisting of all distinct positive divisors of $n$ such that for every positive integer $i\le d(n)$, $a_1+a_2+\cdots +a_i$ is a perfect square.

Topic: Teoria dei Numeri, Combinatoria Metodo: Congruenze, Casework, Estremalità Abilita: Manipolazione algebrica, Conteggio sistematico, Riconoscimento di pattern Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Trova tutte le n in modo che i divisori possano essere disposti con tutte le somme parziali squadrati perfetti

$n$ sia un intero positivo e $d(n)$ indichi il numero di divisori positivi di $n$. Trova tutti gli integri positivi $n$ per i quali esiste una sequenza $a_1,a_2,\dots ,a_{d(n)}$ composta da tutti i divisiori positivi distinti di $n$ in modo tale che per ogni intero positivo $i\le d(n)$, $a_1+a_2+\cdots +a_i$ sia un quadrato perfetto.

src_selection_camp_2022__Q10

Three lines AC, DT, BK concur in a cyclic quadrilateral configuration

Let $ABCD$ be a quadrilateral inscribed in a circle $\Omega$. The tangent to $\Omega$ at $D$ meets the rays $BA$ and $BC$ at points $E$ and $F$, respectively. Let $T$ be a point in the interior of triangle $ABC$ (not on its boundary) such that $TE\parallel CD$ and $TF\parallel AD$. Furthermore, let $K$ be a point on segment $DF$ other than $D$ such that $TD=TK$. Prove that the three lines $AC$, $DT$, and $BK$ are concurrent. Here $XY$ denotes the length of segment $XY$.

Topic: Geometria piana Metodo: Trigonometria, Coordinate, Simmetria Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria Fonte: apri PDF

Tre linee AC, DT, BK convergono in una configurazione quadrilaterale ciclica

$ABCD$ sia un quadrilaterale inciso in un cerchio $\Omega$. La tangente di $\Omega$ a $D$ incontra i raggi $BA$ e $BC$ rispettivamente ai punti $E$ e $F$. Il $T$ deve essere un punto all’interno del triangolo $ABC$ (non al suo confine) tale che $TE\parallel CD$ e $TF\parallel AD$. Inoltre, $K$ deve essere un punto del segmento $DF$ diverso da $D$ in modo tale che $TD=TK$. Prove che le tre linee $AC$, $DT$ e $BK$ sono simultanee. Qui $XY$ indica la lunghezza del segmento $XY$.

src_selection_camp_2022__Q11

Hunter-rabbit game on infinite grid; can rabbit avoid being located?

A hunter and an invisible rabbit play a game on an infinite grid. First, the hunter chooses a positive integer $k$ and assigns one integer from $\{1,2,\dots ,k\}$ to each cell of the grid, then tells the assignment to the rabbit. Next, the rabbit chooses a cell to hide in. After that, the rabbit repeatedly performs the following actions in order:

(i) The rabbit tells the hunter the integer assigned to the cell it is currently in.

(ii) The rabbit moves to an unvisited cell sharing a side with its current cell. If no such unvisited cell exists, the game ends.

At any point during the game, if the hunter can uniquely identify the cell where the rabbit first hid, using only the integers reported so far, then the game ends at that point.

Is it possible for the rabbit to choose its starting cell and continue playing without the game ending, regardless of how the hunter chooses $k$ and the assignment of integers?

Topic: Combinatoria Metodo: Invarianti, Colorazione, Casework, Induzione Abilita: Modellizzazione, Ragionamento geometrico, Riconoscimento di pattern, Astrazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Giocatore di coniglio su una griglia infinita. Il coniglio può evitare di essere localizzato?

Un cacciatore e un coniglio invisibile giocano a un gioco su una griglia infinita. In primo luogo, il cacciatore sceglie un intero positivo $k$ e assegna un intero da $\{1,2,\dots ,k\}$ a ogni cella della griglia, quindi informa l’assegnazione al coniglio. Successivamente, il coniglio sceglie una cella in cui nascondersi. In seguito, il coniglio esegue ripetutamente le seguenti azioni:

(i) Il coniglio dice al cacciatore il numero intero assegnato alla cella in cui si trova attualmente.

(ii) Il coniglio si sposta in una cella non visitata che condivide un lato con la sua cella corrente. Se non esiste una cellula non visitata, il gioco finisce.

In qualsiasi momento del gioco, se il cacciatore riesce a identificare in modo unico la cella in cui il coniglio si è nascosto per la prima volta, utilizzando solo i numeri interi segnalati finora, allora il gioco finisce a quel punto.

È possibile che il coniglio scelga la sua cella di partenza e continui a giocare senza che il gioco finisca, indipendentemente dal modo in cui il cacciatore sceglie $k$ e l’assegnazione di numeri interi?

src_selection_camp_2022__Q12