Japan Mathematical Olympiad 2016 — Honsen (Final)

Sum of counts of divisors of kp+1 in [k,p) over k=1..p-1

Let $p$ be a prime number. For each integer $k$ with $1\le k\le p-1$, let $a_k$ be the number of divisors of $kp+1$ that are greater than or equal to $k$ and less than $p$. Find the value of $a_1+a_2+\cdots +a_{p-1}$.

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

Summa dei conti dei divisori di kp+1 in [k,p) su k=1..p-1

$p$ sia un numero primo. Per ogni numero intero $k$ con $1\le k\le p-1$, $a_k$ è il numero di divisori di $kp+1$ che sono superiori o uguali a $k$ e inferiori a $p$. Trova il valore di $a_1+a_2+\cdots +a_{p-1}$.

src_jmo26mq_honsen__Q01

Cyclic quadrilateral: angle bisectors, midpoints, parallel line

A cyclic quadrilateral $ABCD$ is inscribed in a circle, satisfying $AB:AD=CD:CB$. Let $X$ be the intersection of diagonals $AC$ and $BD$, and let $Y$ be the intersection of lines $AB$ and $CD$. Let $E$, $F$, $G$, $H$ be the midpoints of $AB$, $BC$, $CD$, $DA$ respectively. Let $S$ be the intersection of the angle bisector of $\angle AXB$ with segment $EG$, and let $T$ be the intersection of the angle bisector of $\angle AYD$ with segment $FH$. Prove that line $ST$ is parallel to diagonal $BD$.

(Here, $UV$ denotes the length of segment $UV$.)

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

Quadrilaterali ciclici: bisettori angolari, punti di mezzo, linea parallela

Un quadrilaterale ciclico $ABCD$ è inserito in un cerchio, soddisfacendo $AB:AD=CD:CB$. Il $X$ è l’intersezione delle diagonali $AC$ e $BD$, e il $Y$ è l’intersezione delle linee $AB$ e $CD$. $E$, $F$, $G$, $H$ siano rispettivamente i punti intermedi di $AB$, $BC$, $CD$ e $DA$. $S$ sia l’intersezione del bisettore angolare di $\angle AXB$ con il segmento $EG$, e $T$ sia l’intersezione del bisettore angolare di $\angle AYD$ con il segmento $FH$. Prova che la linea $ST$ è parallela alla diagonale $BD$.

(Qui $UV$ indica la lunghezza del segmento $UV$.)

src_jmo26mq_honsen__Q02

JMO Kingdom coin micro-taxation: find minimum total coins S

Let $n$ be a positive integer. In the JMO Kingdom there are $2^n$ citizens and one king. The currency consists of $2^a$-yen coins for $a=0,1,2,\dots ,n-1$ (i.e., $1$-yen, $2$-yen, $4$-yen, $\dots$, $2^{n-1}$-yen coins). Every citizen holds many of each denomination. The total number of coins held by all citizens is $S$.

Starting from some day, the JMO Kingdom carries out the following operation, called a “micro-taxation,” every day:

• Every citizen selects a finite subset (possibly empty) of the coins they currently hold, and that night hands over all selected coins to other citizens (distributing them among the other citizens however they wish).
• After this step, for every citizen, the total amount they gave away is made strictly more than $1$ yen greater than the total amount they received.

It is said that micro-taxation can be continued indefinitely in the JMO Kingdom. Find the minimum value of $S$ for which this is achievable.

Topic: Combinatoria, Teoria dei Numeri Metodo: Invarianti, Induzione, Estremalità Abilita: Modellizzazione, Astrazione, Conteggio sistematico, Lettura attenta Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri Fonte: apri PDF

JMO Microtassazione delle monete del Regno: trovare monete totali minime S

$n$ sia un numero intero positivo. Nel Regno dell’OMS ci sono cittadini $2^n$ e un re. La moneta è costituita da monete $2^a$-yen per $a=0,1,2,\dots ,n-1$ (cioè monete $1$-yen, $2$-yen, $4$-yen, $\dots$, $2^{n-1}$-yen). Ogni cittadino possiede molte denominazioni. Il numero totale di monete detenute da tutti i cittadini è $S$.

A partire da qualche giorno, il Regno JMO svolge ogni giorno la seguente operazione, chiamata “micro-tassazione”:

• Ogni cittadino seleziona un sottoinsieme finito (possibilmente vuoto) delle monete che detiene attualmente e quella notte consegna tutte le monete selezionate ad altri cittadini (distribuendole tra gli altri cittadini come desiderano). - Dopo questo passaggio, per ogni cittadino, l’importo totale che ha donato è rigorosamente superiore a $1$ yen superiore all’importo totale che ha ricevuto.

Si dice che la micro-tassazione possa continuare a tempo indeterminato nel Regno dell’OMM. Trova il valore minimo di $S$ per il quale questo è raggiungibile.

src_jmo26mq_honsen__Q03

Find all real functions satisfying f(yf(x)-x)=f(x)f(y)+2x

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

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

Ricerca tutte le funzioni reali che soddisfano f(yf(x) -x) = f(x) f(y) +2x

Trovare tutte le funzioni $f:\mathbb{R}\to \mathbb{R}$ definite su tutti i numeri reali in modo tale che per tutti i numeri reali $x,y$, $f(yf(x)-x)=f(x)f(y)+2x$ si mantenga.

src_jmo26mq_honsen__Q04

Partition m cities into two groups so each city has at most 1 highway

Let $m,n$ be positive integers with $m\ge 2$ and $n<\frac{3}{2}(m-1)$. A country has $m$ cities and $n$ roads, where each road connects two distinct cities (there may be multiple roads between the same pair of cities).

The cities are to be divided into two groups $\alpha$ and $\beta$, and every road connecting a city in group $\alpha$ to a city in group $\beta$ is designated a highway. Prove that there exists such a partition satisfying both of the following conditions:

• Each group contains at least one city.
• For every city, the number of highways incident to that city is at most $1$.

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

Partire le città in due gruppi in modo che ciascuna città abbia al massimo 1 autostrada

$m,n$ siano integri positivi con $m\ge 2$ e $n<\frac{3}{2}(m-1)$. Un paese ha città $m$ e strade $n$, dove ciascuna strada collega due città distinte (potrebbero esserci più strade tra la stessa coppia di città).

Le città devono essere suddivise in due gruppi $\alpha$ e $\beta$ e ogni strada che collega una città del gruppo $\alpha$ a una città del gruppo $\beta$ è designata autostrada. Dimostrare l’esistenza di una tale partizione che soddisfa entrambe le seguenti condizioni:

• Ogni gruppo contiene almeno una città. - Per ogni città, il numero di incidenti sulle autostrade in quella città è massimo $1$.

src_jmo26mq_honsen__Q05