Japan IMO Selection Camp 2023 — Selection Camp

Largest n with distinct-gcd arithmetic progression of divisors

Let $n$ be a positive integer with at least $4$ positive divisors. Let $d(n)$ denote the number of positive divisors of $n$. Find all $n$ for which there exist $d(n)-1$ positive integers $a_1,a_2,\dots ,a_{d(n)-1}$ forming an arithmetic progression and satisfying the following condition:

For any integers $i,j$ with $1\le i<j\le d(n)-1$, we have $\gcd (a_i,n)\ne \gcd (a_j,n)$.

Here, for positive integers $x,y$, $\gcd (x,y)$ denotes the greatest common divisor of $x$ and $y$.

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

N più piccolo con progressione aritmetica di divisori distinta-gcd

Che $n$ sia un intero positivo con almeno $4$ divisori positivi. $d(n)$ indica il numero di divisori positivi di $n$. Trova tutti i $n$ per i quali esistono $d(n)-1$ integri positivi $a_1,a_2,\dots ,a_{d(n)-1}$ che formano una progressione aritmetica e soddisfano la seguente condizione:

Per tutti gli integri $i,j$ con $1\le i<j\le d(n)-1$, abbiamo $\gcd (a_i,n)\ne \gcd (a_j,n)$.

Qui, per i numeri interi positivi $x,y$, $\gcd (x,y)$ indica il più grande divisore comune di $x$ e $y$.

src_selection_camp_2023__Q01

Max number of L-shaped 2023-cell tiles on 2023x2023 board

Consider the L-shaped tile shown in the figure, consisting of $2023$ cells (a vertical arm of $1012$ cells and a horizontal arm of $1012$ cells sharing one corner cell). On a $2023\times 2023$ grid, place copies of this tile along the grid cells so that no two tiles overlap. Find the maximum number of tiles that can be placed.

Here, tiles may be rotated, but must not extend beyond the grid.

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

Nombre massimo di piastrelle a celle a forma di L di 2023 sulla lavagna 2023x2023

Considerate la piastrella a forma di L mostrata nella figura, costituita da celle $2023$ (un braccio verticale di celle $1012$ e un braccio orizzontale di celle $1012$ che condividono una cella angolare). Su una griglia $2023\times 2023$, posizionare copie di questa piastrella lungo le celle della griglia in modo che due piastrelle non si sovrappongano. Trova il numero massimo di piastrelle che puoi posizionare.

Qui, le piastrelle possono essere ruotate, ma non devono estendersi oltre la griglia.

src_selection_camp_2023__Q02

Largest n with real sequence whose differences realize powers of r

Let $n$ be an integer with $n\ge 2$. Find the largest possible value of $n$ for which there exist $n$ real numbers $a_1,a_2,\dots ,a_n$ and a positive real number $r\ne 1$ satisfying the following condition:

For every integer $k$ with $1\le k\le \frac{n(n-1)}{2}$, there exist integers $i,j$ with $1\le i<j\le n$ such that $a_j-a_i=r^k$.

Topic: Algebra, Combinatoria Metodo: Estremalità, Casework Abilita: Astrazione, Manipolazione algebrica, Riconoscimento di pattern Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

N più grande con sequenza reale le cui differenze realizzano potenze di r

$n$ sia un numero intero con $n\ge 2$. Trova il valore più grande possibile di $n$ per il quale esistono $n$ numeri reali $a_1,a_2,\dots ,a_n$ e un numero reale positivo $r\ne 1$ che soddisfa la seguente condizione:

Per ogni intero $k$ con $1\le k\le \frac{n(n-1)}{2}$, esistono interi $i,j$ con $1\le i<j\le n$ tali che $a_j-a_i=r^k$.

src_selection_camp_2023__Q03

Four points concyclic via tangent-circle construction on altitude foot

Let $ABC$ be an acute triangle, and let $F$ be the foot of the perpendicular from $A$ to side $BC$. Take a point $P$ on segment $AF$ (excluding the endpoints), and let $D,E$ be the intersections with line $BC$ of the lines through $P$ parallel to lines $AC,AB$ respectively. Let $X,Y$ be points, each different from all of $A,B,C$, lying on the circumcircles of triangles $ABD,ACE$ respectively, such that $DA=DX$ and $EA=EY$. Prove that the four points $B,C,X,Y$ lie on a common circle.

Here, $XY$ denotes the length of segment $XY$.

Topic: Geometria piana Metodo: Trigonometria Abilita: Ragionamento geometrico Area: Geometria Fonte: apri PDF

Quattro punti conciclici tramite costruzione di cerchio tangente a piedi d’altitudine

Il $ABC$ è un triangolo acuto e il $F$ è il piede della perpendicolare da $A$ a lato $BC$. Prendi un punto $P$ sul segmento $AF$ (esclusi i punti terminali) e lasci che $D,E$ siano rispettivamente le intersezioni con la linea $BC$ delle linee attraverso $P$ parallele alle linee $AC,AB$. $X,Y$ siano punti, ognuno diverso da tutti $A,B,C$, che si trovano rispettivamente sui circoncircoli dei triangoli $ABD,ACE$, in modo tale che $DA=DX$ e $EA=EY$. Prove che i quattro punti $B,C,X,Y$ si trovano su un cerchio comune.

Qui $XY$ indica la lunghezza del segmento $XY$.

src_selection_camp_2023__Q04

Find rationals q realized by f(x+f(y))=f(x)+f(y) with f(z)=qz

Call a function $f$ defined on the real numbers and taking real values a good function if, for all real numbers $x,y$, $f(x+f(y))=f(x)+f(y).$ Find all rational numbers $q$ satisfying the following condition: there exists a good function $f$ and a real number $z$ such that $f(z)=qz$.

Topic: Equazioni funzionali Abilita: Manipolazione algebrica, Astrazione Area: Algebra e Analisi Fonte: apri PDF

Ricerca i razionali q realizzati da f(x+f(y))=f(x)+f(y) con f(z)=qz

Chiamare una funzione $f$ definita sui numeri reali e assumendo i valori reali una buona funzione se, per tutti i numeri reali $x,y$, $f(x+f(y))=f(x)+f(y).$ Trovare tutti i numeri razionali $q$ che soddisfano la seguente condizione: esiste una buona funzione $f$ e un numero reale $z$ tale che $f(z)=qz$.

src_selection_camp_2023__Q05

Infinitely many T whose digit-count multiset of 1829-multiples has 2 values

For a positive integer $T$ and an integer $i$ with $1\le i\le 9$, let $d_i(T)$ denote the number of occurrences of the digit $i$ when all multiples of $1829$ from $1$ to $T$ are written in base ten. For example, the multiples of $1829$ from $1$ to $4000$ are $1829$ and $3658$, so $d_8(4000)=2$.

Prove that there exist infinitely many positive integers $T$ such that $\{d_1(T),d_2(T),\dots ,d_9(T)\}$ is a set consisting of exactly two elements.

Here, $\{d_1(T),d_2(T),\dots ,d_9(T)\}$ consisting of two elements means that both of the following conditions hold:

• There exist integers $i,j$ with $1\le i,j\le 9$ such that $d_i(T)\ne d_j(T)$.
• There exist two integers $x,y$ such that for every integer $i$ with $1\le i\le 9$, either $d_i(T)=x$ or $d_i(T)=y$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Conteggio, Casework Abilita: Conteggio sistematico, Stima, Riconoscimento di pattern Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Infinitamente molte T il cui multiset di numeri numerici di 1829-moltipli ha 2 valori

Per un intero positivo $T$ e un intero $i$ con $1\le i\le 9$, $d_i(T)$ indichi il numero di occasioni della cifra $i$ quando tutti i multipli di $1829$ da $1$ a $T$ sono scritti nella base dieci. Ad esempio, i multipli di $1829$ da $1$ a $4000$ sono $1829$ e $3658$, quindi $d_8(4000)=2$.

Prove che esistono infiniti interi positivi $T$ in modo tale che $\{d_1(T),d_2(T),\dots ,d_9(T)\}$ sia un insieme composto da esattamente due elementi.

Qui, $\{d_1(T),d_2(T),\dots ,d_9(T)\}$ costituito da due elementi significa che entrambe le seguenti condizioni sono valide:

• Esistono integri $i,j$ con $1\le i,j\le 9$ tali da $d_i(T)\ne d_j(T)$. - Esistono due enti $x,y$ in modo che per ogni intero $i$ con $1\le i\le 9$, sia $d_i(T)=x$ che $d_i(T)=y$.

src_selection_camp_2023__Q06

Max C with bounded partial sums of good +-1 sequence of length 2022

Call a sequence of $2022$ terms, each of which is $1$ or $-1$, a good sequence. Find the largest integer $C$ satisfying the following condition for every good sequence $a_1,a_2,\dots ,a_{2022}$:

There exist an integer $k\ge 2$ and integers $t_1,t_2,\dots ,t_k$ with $1\le t_1<t_2<\cdots <t_k\le 2022$ such that $t_{i+1}-t_i\le 2$ for every integer $i$ with $1\le i\le k-1$, and moreover $\left|{\sum }_{i=1}^k{a}_{t_i}\right|\ge C$.

Topic: Combinatoria, Algebra Metodo: Estremalità, Casework Abilita: Conteggio sistematico, Stima, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Max C con somme parziali limitate di una buona sequenza +-1 di lunghezza 2022

Chiamare una sequenza di termini $2022$, ognuno dei quali è $1$ o $-1$, una buona sequenza. Trova il numero intero più grande $C$ che soddisfa la seguente condizione per ogni buona sequenza $a_1,a_2,\dots ,a_{2022}$:

Esistono un intero $k\ge 2$ e un intero $t_1,t_2,\dots ,t_k$ con $1\le t_1<t_2<\cdots <t_k\le 2022$ in modo tale che $t_{i+1}-t_i\le 2$ per ogni intero $i$ con $1\le i\le k-1$, e inoltre $\left|{\sum }_{i=1}^k{a}_{t_i}\right|\ge C$.

src_selection_camp_2023__Q07

Blackboard mod-p game: largest x for which B can block A

Players A and B play a game using a blackboard. Initially a positive real number $x$ is fixed.

First, A chooses a prime $p\ge 7$. Next, B chooses real numbers $r_1,r_2\ge 0$. Then A chooses integers $s,t$ satisfying $r_1<s<r_1+xp$ and $r_2<t<r_2+xp$, and writes on the blackboard $0,s,t,st$, each reduced modulo $p$, in this order. After that, A repeatedly performs, as many times as desired, any one of the following three operations:

• Fix an integer $m$ with $1\le m\le p-1$; replace each of the four numbers on the blackboard by that number plus $m$, reduced modulo $p$.
• Fix an integer $n$ with $2\le n\le p-1$; replace each of the four numbers on the blackboard by that number times $n$, reduced modulo $p$.
• Replace each of the four numbers on the blackboard by its $(p-2)$-th power, reduced modulo $p$. However, this operation may not be performed when at least one of the four numbers is $0$.

A’s goal is to make the numbers on the blackboard become $0,2,3,6$ in order. Note that if there do not exist integers $s,t$ satisfying $r_1<s<r_1+xp$ and $r_2<t<r_2+xp$, then A is considered unable to achieve the goal.

Find the largest possible value of $x$ for which B can always prevent A from achieving the goal, regardless of A’s actions.

Topic: Teoria dei Numeri, Combinatoria Metodo: Congruenze, Casework, Estremalità Abilita: Astrazione, Casework accurato, Modellizzazione Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Gioco mod-p da tavolo nero: più grande x per il quale B può bloccare A

I giocatori A e B giocano con una lavagna. Inizialmente viene fissato un numero reale positivo $x$.

In primo luogo, A sceglie un primo $p\ge 7$. Successivamente, B sceglie i numeri reali $r_1,r_2\ge 0$. Poi A sceglie gli integri $s,t$ soddisfa $r_1<s<r_1+xp$ e $r_2<t<r_2+xp$, e scrive sulla lavagna $0,s,t,st$, ciascun modulo ridotto $p$, in questo ordine. Dopo di che, A esegue ripetutamente, quante volte si desidera, una delle seguenti tre operazioni:

• Fixare un numero intero $m$ con $1\le m\le p-1$; sostituire ciascuno dei quattro numeri della lavagna con quel numero più $m$, modulo ridotto $p$. - Fixare un numero intero $n$ con $2\le n\le p-1$; sostituire ciascuno dei quattro numeri sulla lavagna con quel numero volte $n$, modulo ridotto $p$. - sostituire ciascuno dei quattro numeri della lavagna con la sua potenza $(p-2)$-th, modulo ridotto $p$. Tuttavia, questa operazione non può essere eseguita quando almeno uno dei quattro numeri è $0$.

L’obiettivo di A è rendere i numeri sulla lavagna $0,2,3,6$ in ordine. Si noti che se non esistono numeri interi $s,t$ che soddisfano $r_1<s<r_1+xp$ e $r_2<t<r_2+xp$, A è considerato incapace di raggiungere l’obiettivo.

Trova il più grande valore possibile di $x$ per il quale B può sempre impedire a A di raggiungere l’obiettivo, indipendentemente dalle azioni di A.

src_selection_camp_2023__Q08

Fixed point X lies on line PQ independent of P

Let $ABC$ be an acute triangle, and let $H$ be the foot of the perpendicular from $A$ to side $BC$. Choose a point $P$ not on line $BC$ such that the bisector $k$ of $\angle PBC$ and the bisector $l$ of $\angle PCB$ meet on segment $AH$ (excluding its endpoints). Let $E$ be the intersection of $k$ with line $AC$, let $F$ be the intersection of $l$ with line $AB$, and let $Q$ be the intersection of line $EF$ with line $AH$. Prove that there exists a point $X$ such that, independently of the choice of $P$, $X$ lies on line $PQ$.

Topic: Geometria piana Metodo: Trigonometria Abilita: Ragionamento geometrico, Astrazione Area: Geometria Fonte: apri PDF

Il punto fisso X si trova sulla linea PQ indipendente da P

Il $ABC$ è un triangolo acuto e il $H$ è il piede della perpendicolare da $A$ a lato $BC$. Selezionare un punto $P$ non sulla linea $BC$ in modo tale che il bisettore $k$ di $\angle PBC$ e il bisettore $l$ di $\angle PCB$ si incontrino sul segmento $AH$ (esclusi i suoi punti terminali). $E$ sia l’intersezione di $k$ con la linea $AC$, $F$ sia l’intersezione di $l$ con la linea $AB$ e $Q$ sia l’intersezione di $EF$ con la linea $AH$. Prove che esiste un punto $X$ tale che, indipendentemente dalla scelta di $P$, $X$ si trova sulla linea $PQ$.

src_selection_camp_2023__Q09

Min size of set where each element is sum of k others

Let $k$ be an integer with $k\ge 2$. A set $S$ of at least $k+1$ distinct real numbers satisfies the following condition:

For every element $x$ of $S$, there exist $k$ distinct elements of $S$, all different from $x$, whose sum is $x$.

Find the smallest possible value of the number of elements of $S$.

Topic: Combinatoria, Algebra, Insiemi e funzioni Metodo: Estremalità, Casework Abilita: Conteggio sistematico, Astrazione, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Min dimensione di set in cui ogni elemento è la somma di k altri

$k$ sia un numero intero con $k\ge 2$. Un insieme $S$ di almeno $k+1$ numeri reali distinti soddisfa la seguente condizione:

Per ogni elemento $x$ di $S$, esistono $k$ elementi distinti di $S$, tutti diversi da $x$, la cui somma è $x$.

Trova il minimo valore possibile del numero di elementi di $S$.

src_selection_camp_2023__Q10

Three circumcircles share a common point

Let $P$ be a point in the interior (excluding the boundary) of an acute triangle $ABC$ such that line $AP$ and line $BC$ are not perpendicular. Let $X,Y$ be the reflections of $P$ in lines $AB,AC$ respectively, and let $\omega$ be the circumcircle of triangle $AXY$. Suppose a point $Q$ in the interior (excluding the boundary) of triangle $ABC$ satisfies $\angle QBC=\angle CAP$ and $\angle QCB=\angle BAP$, and suppose line $AQ$ and $\omega$ meet at a point $R$ different from $A$ and $Q$. Prove that the circumcircle of triangle $ABC$, the circumcircle of triangle $PQR$, and $\omega$ share a common point.

Topic: Geometria piana Metodo: Simmetria, Trigonometria Abilita: Ragionamento geometrico Area: Geometria Fonte: apri PDF

Tre circoncircoli condividono un punto comune

Il $P$ deve essere un punto all’interno (escluso il confine) di un triangolo acuto $ABC$ in modo tale che la linea $AP$ e la linea $BC$ non siano perpendicolari. $X,Y$ siano rispettivamente i riflessi di $P$ nelle linee $AB,AC$, e $\omega$ sia il circoncircolo del triangolo $AXY$. Supponiamo che un punto $Q$ all’interno (escluso il confine) del triangolo $ABC$ soddisfi $\angle QBC=\angle CAP$ e $\angle QCB=\angle BAP$, e supponiamo che le linee $AQ$ e $\omega$ si incontrino in un punto $R$ diverso da $A$ e $Q$. Prova che il circoncircolo del triangolo $ABC$, il circoncircolo del triangolo $PQR$ e $\omega$ condividono un punto comune.

src_selection_camp_2023__Q11

Second-largest count of good pairs of cities in tunnel network

The kingdom of Mogura consists of $2023$ cities, with several tunnels each connecting two distinct cities. Each tunnel is two-way passable, and between any two distinct cities there is at most one tunnel directly connecting them. Moreover, any two distinct cities can reach each other through some sequence of tunnels.

A pair $\{A,B\}$ of distinct cities is called good if it satisfies the following condition for every city $C$ different from $A$ and $B$:

Let $d_{C,A}$ be the minimum possible number of tunnels used when traveling from $C$ to $A$, and let $d_{C,B}$ be the minimum possible number of tunnels used when traveling from $C$ to $B$. Then it is possible to choose a path $X$ from $C$ to $A$ using $d_{C,A}$ tunnels and a path $Y$ from $C$ to $B$ using $d_{C,B}$ tunnels so that $X$ and $Y$ share no common tunnel.

Find the second-largest possible value of the number of good pairs of cities. Here, $\{A,B\}$ and $\{B,A\}$ are regarded as the same pair.

Topic: Combinatoria Metodo: Grafi, Estremalità, Casework Abilita: Conteggio sistematico, Modellizzazione, Astrazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Seconda più grande conteggio di buone coppie di città in rete di tunnel

Il regno di Mogura è costituito da città $2023$, con diversi tunnel che collegano ciascuna due città distinte. Ogni tunnel è attraversato in due direzioni e tra due città distinte esiste almeno un tunnel che li collega direttamente. Inoltre, due città distinte possono raggiungere l’una l’altra attraverso una sequenza di tunnel.

Una coppia $\{A,B\}$ di città distinte è definita buona se soddisfa la seguente condizione per ogni città $C$ diversa da $A$ e $B$:

Il $d_{C,A}$ deve essere il numero minimo possibile di tunnel utilizzati durante il viaggio da $C$ a $A$ e il $d_{C,B}$ deve essere il numero minimo possibile di tunnel utilizzati durante il viaggio da $C$ a $B$. È quindi possibile scegliere un percorso $X$ da $C$ a $A$ utilizzando tunnel $d_{C,A}$ e un percorso $Y$ da $C$ a $B$ utilizzando tunnel $d_{C,B}$ in modo che $X$ e $Y$ non condividano tunnel comune.

Trova il secondo valore possibile del numero di buone coppie di città. Qui $\{A,B\}$ e $\{B,A\}$ sono considerati come la stessa coppia.

src_selection_camp_2023__Q12