Japan IMO Selection Camp 2017 — Selection Camp

Binary strings game: find minimum whiteboard count for B to win

Let $n$ and $k$ be positive integers with $n>k$. Players A and B play the following game. Find the smallest positive integer $m$ such that B can always win. (B is told the values of $n$ and $k$ at the start of the game.)

• A chooses an $n$-digit binary string $X$, and writes on the blackboard all binary strings that can be obtained from $X$ by flipping exactly $k$ digits.
• B sees the strings on the blackboard, then writes $m$ numbers on the whiteboard.
• B wins if $X$ is among the numbers written on the whiteboard.

Here an $n$-digit binary string is a sequence of $n$ symbols each equal to $0$ or $1$. For example, the $3$-digit binary strings are $000,001,010,011,100,101,110,111$, giving $8$ strings in total.

Topic: Combinatoria Metodo: Casework, Invarianti, Conteggio Abilita: Ragionamento geometrico, Conteggio sistematico, Modellizzazione, Lettura attenta Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Gioco con stringhe binarie: trovare il numero minimo di whiteboard per vincere B

Lasciate che $n$ e $k$ siano integri positivi con $n>k$. I giocatori A e B giocano il seguente gioco. Trova il più piccolo intero positivo $m$ in modo che B possa sempre vincere. (B viene informato dei valori di $n$ e $k$ all’inizio della partita.)

• A sceglie una stringa binaria $n$ a cifre $X$, e scrive sulla lavagna tutte le stringhe binarie che possono essere ottenute da $X$ volando esattamente $k$ cifre. - B vede le stringhe sulla lavagna, poi scrive i numeri $m$ sulla lavagna. - B vince se $X$ è tra i numeri scritti sulla lavagna.

Qui una stringa binaria $n$-cifre è una sequenza di simboli $n$ ognuno uguale a $0$ o $1$. Ad esempio, le stringhe binarie $3$ a cifre sono $000,001,010,011,100,101,110,111$, dando stringhe $8$ in totale.

src_selection_camp_2017__Q01

Circumcircle, incenter, foot of perpendicular: lines XD and AM meet on Gamma

Let triangle $ABC$ satisfy $AB\ne AC$. Let $\Gamma$ be the circumcircle of triangle $ABC$ and let $I$ be its incenter. Let $M$ be the midpoint of side $BC$, and let $D$ be the foot of the perpendicular from $I$ to side $BC$. The line through $I$ perpendicular to line $AI$ meets sides $AB$ and $AC$ at $F$ and $E$, respectively. Let $X$ be the second intersection point (other than $A$) of the circumcircle of triangle $AEF$ with $\Gamma$. Prove that lines $XD$ and $AM$ meet on $\Gamma$.

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

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

Circolo, incentro, piede perpendicolare: linee XD e AM si incontrano su gamma

Il triangolo $ABC$ deve soddisfare $AB\ne AC$. Che $\Gamma$ sia il circoncircolo del triangolo $ABC$ e che $I$ sia il suo incentro. Il $M$ deve essere il punto medio del lato $BC$ e il $D$ deve essere il piede della perpendicolare da $I$ al lato $BC$. La linea che attraversa $I$ perpendicolare alla linea $AI$ incontra i lati $AB$ e $AC$ rispettivamente a $F$ e $E$. Il $X$ deve essere il secondo punto di intersezione (diversi da $A$) del circoncircolo del triangolo $AEF$ con $\Gamma$. Provare che le linee $XD$ e $AM$ si incontrano su $\Gamma$.

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

src_selection_camp_2017__Q02

Find all k such that sum of k-th powers equals (sum)^{r_n} for all n

Let $a_1,a_2,\dots$ and $r_1,r_2,\dots$ be sequences of positive integers. Find all positive integers $k$ such that there exist such sequences satisfying:

• $a_1<a_2<a_3<\cdots$;
• For every positive integer $n$, $a_1^k+a_2^k+\cdots +a_n^k=(a_1+a_2+\cdots +a_n{)}^{r_n}.$

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

Ricerca tutte le k in modo tale che la somma delle potenze k-th sia uguale (somma)^{r_n} per tutte le n

Lasciate che $a_1,a_2,\dots$ e $r_1,r_2,\dots$ siano sequenze di numeri interi positivi. Trova tutti gli integri positivi $k$ in modo tale che esistano sequenze che soddisfano:

• $a_1<a_2<a_3<\cdots$; - Per ogni numero intero positivo $n$, $a_1^k+a_2^k+\cdots +a_n^k=(a_1+a_2+\cdots +a_n{)}^{r_n}.$

src_selection_camp_2017__Q03

Isosceles triangle, incenter, reflection: lies on circumcircle of BDE

Let triangle $ABC$ satisfy $AB=AC\ne BC$, and let $I$ be its incenter. Line $BI$ meets side $AC$ at $D$. The line through $D$ perpendicular to $AC$ meets line $AI$ at $E$. Prove that the reflection of $I$ over line $AC$ lies on the circumcircle of triangle $BDE$.

(Here $XY$ denotes the length of segment $XY$.)

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

Triangolo isosceles, incentro, riflessione: si trova sul circoncircolo di BDE

Il triangolo $ABC$ deve soddisfare $AB=AC\ne BC$ e $I$ deve essere il suo incentro. La linea $BI$ incontra il lato $AC$ a $D$. La linea attraverso $D$ perpendicolare a $AC$ incontra la linea $AI$ a $E$. Prova che il riflesso di $I$ sulla linea $AC$ si trova sul circoncircolo del triangolo $BDE$.

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

src_selection_camp_2017__Q04

Regular n-gon vertices 3-colored odd each color: rainbow isosceles triangle exists

Let $n$ be an integer $\ge 5$ that is coprime to $6$. The vertices of a regular $n$-gon are colored with $3$ colors such that for each color the number of vertices of that color is odd. Prove that one can choose $3$ vertices of the regular $n$-gon forming an isosceles triangle whose three vertices all have different colors.

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

Vertici di n-gon regolari 3 colori unici per colore: esiste un triangolo con arcobaleno e isosceles

$n$ sia un numero intero $\ge 5$ che sia coprimo a $6$. I vertici di un normale $n$-gon sono colorati con $3$ colori in modo tale che per ogni colore il numero di vertici di quel colore sia strano. Prove che si possono scegliere le vertici $3$ del normale $n$-gon formando un triangolo di uguali stelle le cui tre vertici hanno tutti colori diversi.

src_selection_camp_2017__Q05

Find all real-valued functions satisfying a max functional equation

Find all functions $f$ defined on the reals taking real values such that $f(0)\ne 0$ and, for all real numbers $x,y$, $f(x+y{)}^2=2f(x)f(y)+\max \{f(x^2)+f(y^2),f(x^2+y^2)\}.$

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

Ricerca tutte le funzioni a valore reale che soddisfano un’equazione funzionale massima

Trova tutte le funzioni $f$ definite sui reali assumendo valori reali quali $f(0)\ne 0$ e, per tutti i numeri reali $x,y$, $f(x+y{)}^2=2f(x)f(y)+\max \{f(x^2)+f(y^2),f(x^2+y^2)\}.$

src_selection_camp_2017__Q06

Find all positive integer pairs (n,k) with n^4+10n^2+2^k a perfect square

Find all pairs of positive integers $(n,k)$ such that $n^4+10n^2+2^k$ is a perfect square.

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

Trova tutte le coppie di numeri interi positivi (n,k) con n^4+10n^2+2^k un quadrato perfetto

Trova tutte le coppie di integri positivi $(n,k)$ in modo tale che $n^4+10n^2+2^k$ sia un quadrato perfetto.

src_selection_camp_2017__Q07

Positive integer sequence with term exceeding average of next 2016 terms: bounded above

Let $a_1,a_2,\dots$ be a sequence of positive integers satisfying, for every positive integer $n$, $a_n>\frac{a_{n+1}+a_{n+2}+\cdots +a_{2n}}{n+2016}.$ Prove that there exists a positive real constant $C$ such that $a_n<C$ for all positive integers $n$.

Topic: Algebra, Teoria dei Numeri Metodo: Induzione, Telescoping, Estremalità Abilita: Manipolazione algebrica, Stima, Lettura attenta Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

Sequenza di numeri interi positivi con termine superiore alla media dei prossimi termini del 2016: dilimitato sopra

Che $a_1,a_2,\dots$ sia una sequenza di interi positivi che soddisfi, per ogni intero positivo $n$, $a_n>\frac{a_{n+1}+a_{n+2}+\cdots +a_{2n}}{n+2016}.$ Prove che esiste una costante reale positiva $C$ tale che $a_n<C$ per tutti gli interi positivi $n$.

src_selection_camp_2017__Q08

Ferry network on n islands: prove some island eventually connected to all others

Let $n\ge 3$ be an integer. A country has $n$ islands. Initially, IMO Company operates bidirectional ferry routes between some pairs of distinct islands so that any two islands are connected (possibly via intermediate islands). At the beginning of each year, IMO Company updates its ferry routes as follows:

(1) Choose two distinct islands $X$ and $Y$ such that a ferry operated between them in the previous year. (2) Cancel the ferry route between $X$ and $Y$. (3) For each island $Z\ne X,Y$ such that a ferry operated between exactly one of $\{X,Z\}$ and $\{Y,Z\}$ in the previous year, add a new ferry route between $Z$ and the other one of $X,Y$. (4) No other ferry routes are added or cancelled.

The selection of $X$ and $Y$ in step (1) must satisfy the following condition at every point in time:

Condition: For every non-empty subset $\mathcal{S}$ of islands with $|\mathcal{S}|\le n-1$, at least one of $X,Y$ is in $\mathcal{S}$ and the other is not.

Prove that there exist some year and some island such that in that year a ferry operates between that island and every other island.

Topic: Combinatoria Metodo: Invarianti, Grafi, Induzione, Estremalità Abilita: Modellizzazione, Ragionamento geometrico, Astrazione, Lettura attenta Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Rete traghetti su n isole: dimostrare che una delle isole è eventualmente collegata a tutte le altre

$n\ge 3$ sia un numero intero. Un paese ha $n$ isole. Inizialmente, la Società IMO gestisce rotte bidirezionali di traghetti tra alcune coppie di isole distinte in modo che le due isole siano collegate (possibilmente tramite isole intermedi). All’inizio di ogni anno, la Società IMO aggiorna le sue rotte di traghetto come segue:

(1) Scegliere due isole distinte $X$ e $Y$ in modo tale che un traghetto abbia operato tra di loro nell’anno precedente. (2) Cancellare la rotta di traghetto tra $X$ e $Y$. (3) Per ciascuna isola $Z\ne X,Y$ in modo tale che un traghetto abbia operato tra esattamente uno di $\{X,Z\}$ e $\{Y,Z\}$ nell’anno precedente, aggiungere una nuova rotta di traghetto tra $Z$ e l’altro di $X,Y$. (4) Nessuna altra rotta di traghetti viene aggiunta o cancellata.

La selezione di $X$ e $Y$ nella fase (1) deve soddisfare in ogni momento la seguente condizione:

Condizione: per ogni sottoinsieme non vuoto $\mathcal{S}$ di isole con $|\mathcal{S}|\le n-1$, almeno uno di $X,Y$ è in $\mathcal{S}$ e l’altro non lo è.

Prove che esiste un anno e un’isola in modo tale che in quell’anno un traghetto opera tra quell’isola e ogni altra isola.

src_selection_camp_2017__Q09

Find all n>=3: for any 2n reals with |a_k|+|b_k|=1, choose x_k=pm1 bounding two sums

Find all positive integers $n\ge 3$ such that the following holds: for any $2n$ real numbers $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ satisfying $|a_k|+|b_k|=1$ for $k=1,2,\dots ,n$, one can choose real numbers $x_1,x_2,\dots ,x_n$ with $|x_k|=1$ for $k=1,2,\dots ,n$ such that $\left|{\sum }_{k=1}^n{x}_k{a}_k\right|+\left|{\sum }_{k=1}^n{x}_k{b}_k\right|\le 1.$

Topic: Algebra, Combinatoria Metodo: Casework, Estremalità, Simmetria Abilita: Manipolazione algebrica, Casework accurato, Stima, Lettura attenta Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Ricerca tutti n>=3: per qualsiasi 2n reali con ≠a_k=1, scegliere x_k=pm1 limitando due somme

Trovare tutti i numeri interi positivi $n\ge 3$ in modo tale che si verifichi quanto segue: per qualsiasi numero reale $2n$ $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ soddisfacente $|a_k|+|b_k|=1$ per $k=1,2,\dots ,n$, si possono scegliere numeri reali $x_1,x_2,\dots ,x_n$ con $|x_k|=1$ per $k=1,2,\dots ,n$ in modo tale che $\left|{\sum }_{k=1}^n{x}_k{a}_k\right|+\left|{\sum }_{k=1}^n{x}_k{b}_k\right|\le 1.$

src_selection_camp_2017__Q10

Find all f on positive integers with f(m)+f(n)-mn nonzero and ratio integer

Find all functions $f$ defined on the positive integers taking positive integer values such that for any positive integers $m,n$, one has $f(m)+f(n)-mn\ne 0$ and $\frac{mf(m)+nf(n)}{f(m)+f(n)-mn}$ is an integer.

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

Ricerca tutti i f su interi positivi con f(m) + f(n) -mn non zero e numero intero del rapporto

Trova tutte le funzioni $f$ definite sui numeri interi positivi che assumono valori interi positivi in modo tale che per qualsiasi numero intero positivo $m,n$, si abbia $f(m)+f(n)-mn\ne 0$ e $\frac{mf(m)+nf(n)}{f(m)+f(n)-mn}$ è un numero intero.

src_selection_camp_2017__Q11

Convex quadrilateral with equal angles, bisectors, midpoint and circumcircle: PQ perp AC

Let $ABCD$ be a convex quadrilateral with $\angle ABC=\angle ADC<90^{\circ }$. The angle bisectors of $\angle ABC$ and $\angle ADC$ meet line $AC$ at distinct points $E$ and $F$, respectively, and meet each other at point $P$. Let $M$ be the midpoint of segment $AC$, and let $\omega$ be the circumcircle of triangle $BPD$. Line $BM$ meets $\omega$ again at a point $X\ne B$, and line $DM$ meets $\omega$ again at a point $Y\ne D$. If lines $XE$ and $YF$ meet at point $Q$, prove that lines $PQ$ and $AC$ are perpendicular.

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

*Quadrilaterali convex con angoli, bisettori, punto medio e circoncircolo uguali: PQ perp AC *

Il $ABCD$ deve essere un quadrilaterale converso con $\angle ABC=\angle ADC<90^{\circ }$. I bisettori angolari di $\angle ABC$ e $\angle ADC$ incontrano la linea $AC$ rispettivamente in punti distinti $E$ e $F$ e si incontrano a punto $P$. Let $M$ essere il punto medio del segmento $AC$, e let $\omega$ essere il circoncircolo del triangolo $BPD$. La linea $BM$ incontra di nuovo $\omega$ a un punto $X\ne B$ e la linea $DM$ incontra di nuovo $\omega$ a un punto $Y\ne D$. Se le linee $XE$ e $YF$ si incontrano al punto $Q$, dimostrare che le linee $PQ$ e $AC$ sono perpendicolari.

src_selection_camp_2017__Q12