Japan Mathematical Olympiad 2023 — Honsen (Final)

Max cells covered by at least 1 L-tetromino on 5x5 grid

On a $5\times 5$ grid, L-shaped tetromino tiles (each covering 4 cells in an L-shape, as shown) are placed along the grid lines. Tiles may overlap one another but must not extend outside the grid. For every cell, the number of tiles covering it must be between $0$ and $2$ (inclusive). Find the maximum possible number of cells that are covered by at least $1$ tile.

(Tiles may be rotated and reflected.)

Topic: Combinatoria Metodo: Estremalità, Casework, Conteggio Abilita: Conteggio sistematico, Modellizzazione, Casework accurato, Lettura attenta Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Cellule massime coperte da almeno 1 L di tetromino su una griglia 5x5

Su una griglia $5\times 5$, le piastrelle di tetromino a forma di L (che coprono ciascuna 4 celle a forma di L, come mostrato) sono posizionate lungo le linee della griglia. Le piastrelle possono sovrapporsi tra loro, ma non devono estendersi al di fuori della griglia. Per ogni cella, il numero di piastrelle che la coprono deve essere compreso tra $0$ e $2$ (inclusi). Trovare il numero massimo possibile di celle che sono coperte da almeno $1$ piastrelle.

(Le piastrelle possono essere rotate e riflesse.)

src_jmo33hq_honsen__Q01

In acute triangle, line through F parallel to XY meets DY at P; prove AD perp EP

Let $ABC$ be an acute triangle with $D$, $E$, $F$ the midpoints of sides $BC$, $CA$, $AB$ respectively. Let $X$ and $Y$ be the feet of the perpendiculars from $D$ to lines $AB$ and $AC$ respectively. The line through $F$ parallel to line $XY$ meets line $DY$ at a point $P$. Prove that lines $AD$ and $EP$ are perpendicular.

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

Nel triangolo acuto, la linea attraverso F parallela a XY incontra DY a P; prova AD perp EP

Il $ABC$ deve essere un triangolo acuto con $D$, $E$, $F$ i punti medi dei lati $BC$, $CA$ e $AB$ rispettivamente. I piedi $X$ e $Y$ siano i piedi delle perpendicolari da $D$ alle linee $AB$ e $AC$ rispettivamente. La linea attraverso $F$ parallela alla linea $XY$ incontra la linea $DY$ in un punto $P$. Provare che le linee $AD$ e $EP$ sono perpendicolari.

src_jmo33hq_honsen__Q02

Find all positive-integer sequences where count of i with a_i <= a_{i+1}+c equals c for all n

Let $c$ be a non-negative integer. Find all sequences of positive integers $a_1,a_2,\dots$ such that for any non-negative integer $n$, the number of positive integers $i$ satisfying $a_i\le a_{i+1}+c$ and $i\le n$ is exactly $c$.

(Here, when $n=0$ the count is $0$, so the condition is vacuously satisfied for $n=0$.)

Topic: Combinatoria, Algebra Metodo: Invarianti, Ricorsione, Casework Abilita: Lettura attenta, Riconoscimento di pattern, Modellizzazione, Ragionamento geometrico Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Trova tutte le sequenze di numeri interi positivi dove il conteggio di i con a_i <= a_{i+1}+c è uguale a c per tutte le n

$c$ sia un numero intero non negativo. Trovare tutte le sequenze di interi positivi $a_1,a_2,\dots$ in modo tale che per qualsiasi intero non negativo $n$, il numero di interi positivi $i$ che soddisfano $a_i\le a_{i+1}+c$ e $i\le n$ sia esattamente $c$.

(Quindi, quando $n=0$ il conteggio è $0$, quindi la condizione è soddisfatta a vuoto per $n=0$.)

src_jmo33hq_honsen__Q03

Find all positive integers n for which (phi(n)^phi(n) - 1) / d(n) is not an integer

Find all positive integers $n$ such that $\frac{\phi (n{)}^{\phi (n)}-1}{d(n)}$ is not an integer. Here $\phi (n)$ denotes the number of integers from $1$ to $n$ that are coprime to $n$ (Euler’s totient function), and $d(n)$ denotes the number of positive divisors of $n$.

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

Ricerca tutti gli integri positivi n per i quali (phi(n)^phi(n) - 1) / d(n) non è un intero

Trovare tutti gli integri positivi $n$ in modo che $\frac{\phi (n{)}^{\phi (n)}-1}{d(n)}$ non sia un intero. Qui $\phi (n)$ indica il numero di integri da $1$ a $n$ che sono copriemi a $n$ (funzione totiente di Euler), e $d(n)$ indica il numero di divisori positivi di $n$.

src_jmo33hq_honsen__Q04

S={1,…,3000}; find max X such that for any bijection f, some bijection g makes sum >= X

Let $S=\{1,2,\dots ,3000\}$. Find the maximum integer $X$ such that the following condition holds:

For any bijection $f:S\to S$, there exists a bijection $g:S\to S$ such that ${\sum }_{k=1}^{3000}(\max \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\}-\min \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\})\ge X.$

Here, a bijection from $S$ to $S$ is a function $f:S\to S$ such that for every element $y\in S$ there exists exactly one element $x\in S$ with $f(x)=y$. For positive integers $x_1,x_2,x_3,x_4$, $\max \{x_1,x_2,x_3,x_4\}$ and $\min \{x_1,x_2,x_3,x_4\}$ denote their maximum and minimum respectively.

Topic: Combinatoria, Insiemi e funzioni Metodo: Estremalità, Doppio conteggio, Simmetria, Casework Abilita: Modellizzazione, Conteggio sistematico, Astrazione, Stima, Lettura attenta Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

S={1,…,3000}; trovare il massimo X in modo che per qualsiasi bijezione f, qualche bijezione g faccia la somma >= X

Let $S=\{1,2,\dots ,3000\}$. Trova il numero intero massimo $X$ in modo tale che la seguente condizione sia valida:

Per qualsiasi bizione $f:S\to S$, esiste una bizione $g:S\to S$ tale che ${\sum }_{k=1}^{3000}(\max \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\}-\min \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\})\ge X.$

Qui, una bijezione da $S$ a $S$ è una funzione $f:S\to S$ tale che per ogni elemento $y\in S$ esiste esattamente un elemento $x\in S$ con $f(x)=y$. Per i numeri interi positivi $x_1,x_2,x_3,x_4$, $\max \{x_1,x_2,x_3,x_4\}$ e $\min \{x_1,x_2,x_3,x_4\}$ indicano rispettivamente il loro massimo e il loro minimo.

src_jmo33hq_honsen__Q05