Japan Mathematical Olympiad 2018 — Honsen (Final)

gcd operation on blackboard, final number not a square

On a blackboard, the integers from $1$ to $100$ are written, each exactly once. We repeatedly perform the following operation: choose two integers $a,b$ written on the blackboard, erase them, and write the greatest common divisor of $a^2{b}^2+3$ and $a^2+b^2+2$. Show that when only one integer remains on the blackboard, that integer is not a perfect square.

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

gcd operazione sulla lavagna, numero finale non quadrato

Su una lavagna sono scritti i numeri interi da $1$ a $100$, ognuno esattamente una volta. Ripettivamente eseguiamo la seguente operazione: scegliamo due integri $a,b$ scritti sulla lavagna, li cancelliamo e scriviamo il più grande divisore comune di $a^2{b}^2+3$ e $a^2+b^2+2$. Mostrate che quando rimane solo un intero sulla lavagna, quel intero non è un quadrato perfetto.

src_jmo28mq_honsen__Q01

lines BX and CY meet on circumcircle of ADE

Let $ABC$ be a triangle with $AB<AC$. Points $D$ and $E$ lie on sides $AB$ and $AC$ respectively (not at the endpoints) and satisfy $CA=CD$ and $BA=BE$. Let $\omega$ be the circumcircle of triangle $ADE$, and let $P$ be the reflection of $A$ across line $BC$. Let $X$ be the intersection of line $PD$ with $\omega$ other than $D$, and let $Y$ be the intersection of line $PE$ with $\omega$ other than $E$. Show that lines $BX$ and $CY$ meet at a point on $\omega$. (Here $ST$ denotes the length of the segment $ST$.)

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

le linee BX e CY si incontrano sul circolo di ADE

Che $ABC$ sia un triangolo con $AB<AC$. I punti $D$ e $E$ si trovano rispettivamente sui lati $AB$ e $AC$ (non nei punti finali) e soddisfano $CA=CD$ e $BA=BE$. $\omega$ sia il circoncircolo del triangolo $ADE$, e $P$ sia il riflesso di $A$ attraverso la linea $BC$. Il $X$ è l’intersezione della linea $PD$ con $\omega$ diversa da $D$ e il $Y$ è l’intersezione della linea $PE$ con $\omega$ diversa da $E$. Indicare che le linee $BX$ e $CY$ si incontrano in un punto di $\omega$. (Qui $ST$ indica la lunghezza del segmento $ST$.)

src_jmo28mq_honsen__Q02

function on 1..999 with iteration conditions has a fixed point

Let $S=\{1,2,\dots ,999\}$. Let $f$ be a function defined on $S$ taking values in $S$, such that for every element $n\in S$, $f^{n+f(n)+1}(n)=f^{nf(n)}(n)=n$ holds. Show that there exists an element $a\in S$ with $f(a)=a$. (Here $f^k(n)$ denotes $\underset{k}{\underbrace{f(f(\cdots f(n)\cdots ))}}$, the $k$-fold composition of $f$.)

Topic: Insiemi e funzioni, Teoria dei Numeri Metodo: Ricorsione, Congruenze Abilita: Astrazione, Riconoscimento di pattern Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

La funzione * su 1,999 con condizioni di iterazione ha un punto fisso*

Let $S=\{1,2,\dots ,999\}$. $f$ deve essere una funzione definita su $S$, assumendo valori in $S$, in modo tale che per ogni elemento $n\in S$, $f^{n+f(n)+1}(n)=f^{nf(n)}(n)=n$ sia valido. Indicare che esiste un elemento $a\in S$ con $f(a)=a$. (Qui $f^k(n)$ indica $\underset{k}{\underbrace{f(f(\cdots f(n)\cdots ))}}$, la composizione a moltiplicazione di $k$ di $f$.)

src_jmo28mq_honsen__Q03

no labeling of infinite grid with 1,2,3 meets all three conditions

Let $n$ be a positive odd integer. Consider an infinite grid of cells extending without bound in all directions. Show that it is impossible to write one of the numbers $1,2,3$ in each cell so that all of the following conditions are satisfied: \begin{enumerate} \item[(a)] No two cells sharing an edge contain the same number. \item[(b)] In no block of three consecutive cells in a row or column (that is, a $3\times 1$ or $1\times 3$ block of cells) do the numbers read $1,2,3$ in order, whether read from top, bottom, left, or right. \item[(c)] The sum of the numbers written in an $n\times n$ block of cells is the same regardless of the position of the block. \end{enumerate}

Topic: Combinatoria Metodo: Colorazione, Invarianti, Casework Abilita: Casework accurato, Conteggio sistematico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

nessuna etichettatura di griglia infinita con 1,2,3 soddisfa tutte e tre le condizioni

Lasciate che $n$ sia un intero pari positivo. Considerate una griglia infinita di cellule che si estendono senza limite in tutte le direzioni. Mostrare che è impossibile scrivere uno dei numeri $1,2,3$ in ogni cella in modo che tutte le seguenti condizioni siano soddisfatte: \begin{enumerate} \item[(a)) Nessuna delle due celle che condividono un bordo contiene lo stesso numero. \item[(b) In nessun blocco di tre celle consecutive in una riga o colonna (cioè un blocco di celle $3\times 1$ o $1\times 3$) i numeri si leggono $1,2,3$ in ordine, che si legga dall’alto, dal basso, dalla sinistra o dalla destra. \item[(c) La somma dei numeri scritti in un blocco di celle $n\times n$ è la stessa indipendentemente dalla posizione del blocco. \end{enumere}

src_jmo28mq_honsen__Q04

find all functions on pairs with level-set and shift conditions

Let $T$ be a positive integer. Find all functions $f$, defined on ordered pairs of positive integers and taking positive integer values, together with integers $C_0,C_1,\dots ,C_T$, satisfying both of the following: \begin{itemize} \item For every positive integer $n$, there are exactly $n$ ordered pairs $(k,l)$ of positive integers with $f(k,l)=n$. \item For each $t=0,1,\dots ,T$ and every ordered pair $(k,l)$ of positive integers, $f(k+t,l+T-t)-f(k,l)=C_t$. \end{itemize}

Topic: Combinatoria, Teoria dei Numeri Metodo: Doppio conteggio, Estremalità Abilita: Astrazione, Conteggio sistematico, Modellizzazione Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri Fonte: apri PDF

trovare tutte le funzioni su coppie con condizioni di impostazione di livello e di spostamento

$T$ sia un numero intero positivo. Trovare tutte le funzioni $f$, definite su coppie ordinate di integri positivi e assumendo valori di integri positivi, insieme ad integri $C_0,C_1,\dots ,C_T$, soddisfacendo entrambe le seguenti caratteristiche: \begin{itemize} \item Per ogni integro positivo $n$, ci sono esattamente $n$ coppie ordinate $(k,l)$ di integri positivi con $f(k,l)=n$. \item Per ogni $t=0,1,\dots ,T$ e ogni coppia ordinata $(k,l)$ di integri positivi, $f(k+t,l+T-t)-f(k,l)=C_t$. # Finire #

src_jmo28mq_honsen__Q05