Japan IMO Selection Camp 2018 — Selection Camp

Convex pentagon with equal sides and angles, perpendicular from E to BC meets AC and BD at one point

Let $ABCDE$ be a convex pentagon satisfying $AB=BC=CD$, $\angle EAB=\angle BCD$, and $\angle EDC=\angle CBA$. Prove that the perpendicular dropped from $E$ to line $BC$, and the lines $AC$ and $BD$, all meet at a single point.

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

Pentagono converso con lati e angoli uguali, perpendicolare da E a BC, che incontra AC e BD in un punto

Il $ABCDE$ deve essere un pentagono convexo che soddisfa $AB=BC=CD$, $\angle EAB=\angle BCD$ e $\angle EDC=\angle CBA$. Provare che la perpendicolare è scesa da $E$ alla linea $BC$, e che le linee $AC$ e $BD$ si incontrano tutti in un unico punto.

src_selection_camp_2018__Q01

Self-map on {1,…,n}: unique g satisfying f(g(f(m)))=g(f(g(m))) implies f and f∘f have same image

Let $n$ be a positive integer. Let $S=\{1,2,\dots ,n\}$, and let $\mathcal{A}$ be the set of all functions from $S$ to $S$. Let $f$ be a function in $\mathcal{A}$. Suppose that the only function $g\in \mathcal{A}$ satisfying $f(g(f(m)))=g(f(g(m))),m=1,2,\dots ,n$ is $g=f$ itself. Prove that $\{f(m)\mid m=1,2,\dots ,n\}=\{f(f(m))\mid m=1,2,\dots ,n\}.$

Topic: Insiemi e funzioni, Combinatoria Metodo: Invarianti, Backward Abilita: Manipolazione algebrica, Astrazione, Lettura attenta Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Self-map su {1,…,n}: unica g soddisfacente f(g(f(m)))=g(f(g(m))) implica che f e ff hanno la stessa immagine

$n$ sia un numero intero positivo. Let $S=\{1,2,\dots ,n\}$, e let $\mathcal{A}$ essere l’insieme di tutte le funzioni da $S$ a $S$. Let $f$ essere una funzione in $\mathcal{A}$. Supponiamo che l’unica funzione $g\in \mathcal{A}$ che soddisfa $f(g(f(m)))=g(f(g(m))),m=1,2,\dots ,n$ sia la stessa $g=f$. Provare che $\{f(m)\mid m=1,2,\dots ,n\}=\{f(f(m))\mid m=1,2,\dots ,n\}.$

src_selection_camp_2018__Q02

Find all prime pairs (p,q) with p>q such that a given expression is an integer

Find all pairs of primes $(p,q)$ with $p>q$ such that $\frac{(p+q{)}^{p+q}(p-q{)}^{p-q}-1}{(p+q{)}^{p-q}(p-q{)}^{p+q}-1}$ is an integer.

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

Ricerca tutte le coppie prime (p,q) con p>q in modo tale che un’espressione data sia un intero

Trova tutte le coppie di prime $(p,q)$ con $p>q$ in modo tale che $\frac{(p+q{)}^{p+q}(p-q{)}^{p-q}-1}{(p+q{)}^{p-q}(p-q{)}^{p+q}-1}$ sia un numero intero.

src_selection_camp_2018__Q03

Minimum total separation number over all lines through n points in general position

Let $n\ge 3$ be an integer. Consider a set $S$ of $n$ points in the plane such that no three points are collinear. Let $L$ be the set of all lines passing through two distinct points of $S$. For a line $\ell \in L$, define its separation number as the product of the number of points of $S$ in each of the two open half-planes determined by $\ell$. Find the minimum possible value of the sum of the separation numbers over all lines in $L$.

Topic: Combinatoria, Geometria piana Metodo: Estremalità, Conteggio, Doppio conteggio Abilita: Conteggio sistematico, Ragionamento geometrico, Modellizzazione Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF

Numero minimo di separazione totale su tutte le linee attraverso n punti in posizione generale

$n\ge 3$ sia un numero intero. Considera un insieme $S$ di punti $n$ nel piano in modo tale che nessun punto sia collineare. $L$ è l’insieme di tutte le linee che attraversano due punti distinti di $S$. Per una linea $\ell \in L$, definire il suo numero di separazione come il prodotto del numero di punti di $S$ in ciascuno dei due semipiani aperti determinati da $\ell$. Trova il valore minimo possibile della somma dei numeri di separazione su tutte le linee in $L$.

src_selection_camp_2018__Q04

Only finitely many subsets S of {1,…,n} with |S|≥√n+1 and all products xy being perfect powers

Prove that there are only finitely many positive integers $n$ for which there exists a subset $S\subseteq \{1,2,\dots ,n\}$ satisfying the following two conditions: \begin{itemize} \item The number of elements of $S$ is at least $[\sqrt{n}]+1$. \item For any two elements $x,y\in S$, the product $xy$ is a perfect power, i.e., an integer that can be expressed as $a^b$ for some positive integer $a$ and integer $b\ge 2$. \end{itemize} Here, for a real number $r$, $[r]$ denotes the greatest integer not exceeding $r$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Estremalità, Fattorizzazione, Induzione Abilita: Astrazione, Riconoscimento di pattern, Manipolazione algebrica Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Solo finitamente molti sottoinsiemi S di {1,…,n} con S ≥ √n+1 e tutti i prodotti xy sono potenze perfette

Prove che ci sono solo finitamente molti interi positivi $n$ per i quali esiste un sottoinsieme $S\subseteq \{1,2,\dots ,n\}$ che soddisfa le seguenti due condizioni: \begin{itemize} \item Il numero di elementi di $S$ è almeno $[\sqrt{n}]+1$. \item Per due elementi $x,y\in S$, il prodotto $xy$ è una potenza perfetta, cioè un intero che può essere espresso come $a^b$ per un intero positivo $a$ e un intero $b\ge 2$. \end{itemize} Qui, per un numero reale $r$, $[r]$ indica il numero intero più grande non superiore a $r$.

src_selection_camp_2018__Q05

Integer sequence with positive integer parameters: one of a_{2017}, a_{2018} is at least 2017

Let $a_0,a_1,a_2,\dots$ be a sequence of integers and $b_0,b_1,b_2,\dots$ be a sequence of positive integers. Suppose $a_0=0$, $a_1=1$, and for $n=1,2,\dots$, $a_{n+1}=\{\begin{array}{ll}{a}_n{b}_n+a_{n-1}& \text{if }{b}_{n-1}=1,\\ a_n{b}_n-a_{n-1}& \text{if }{b}_{n-1}>1.\end{array}$ Prove that at least one of $a_{2017}$ and $a_{2018}$ is greater than or equal to $2017$.

Topic: Algebra, Teoria dei Numeri Metodo: Induzione, Invarianti, Ricorsione Abilita: Manipolazione algebrica, Riconoscimento di pattern, Stima Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

Sequenza di numeri interi con parametri interi positivi: uno di a_{2017}, a_{2018} è almeno 2017

Che $a_0,a_1,a_2,\dots$ sia una sequenza di enti interi e $b_0,b_1,b_2,\dots$ sia una sequenza di enti interi positivi. Supponiamo $a_0=0$, $a_1=1$, e per $n=1,2,\dots$, $a_{n+1}=\{\begin{array}{ll}{a}_n{b}_n+a_{n-1}& \text{if }{b}_{n-1}=1,\\ a_n{b}_n-a_{n-1}& \text{if }{b}_{n-1}>1.\end{array}$ Prove che almeno uno dei $a_{2017}$ e $a_{2018}$ sia maggiore o uguale a $2017$.

src_selection_camp_2018__Q06

Two-player game on {0,…,p-1} building a base-10 number: first player has winning strategy mod p

Let $p$ be a prime. Two players alternately perform the following action:

Action: Choose a number $i$ from $\{0,1,\dots ,p-1\}$ that has not been chosen before, then choose an integer between $0$ and $9$ (inclusive) to assign to $i$.

The game ends when all elements of $\{0,1,\dots ,p-1\}$ have been chosen. Let $a_i$ be the integer assigned to $i$, and set $M=a_0+a_1\cdot 10+\cdots +a_{p-1}\cdot 10^{p-1}$. If $M$ is divisible by $p$, the first player wins; otherwise the second player wins. Prove that the first player has a winning strategy.

Topic: Teoria dei Numeri, Combinatoria Metodo: Invarianti, Casework, Congruenze Abilita: Astrazione, Ragionamento geometrico, Lettura attenta, Modellizzazione Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Gioco a due giocatori su {0,…,p-1} costruendo un numero base-10: il primo giocatore ha la strategia vincente mod p

Lasciate che $p$ sia un primo. Due giocatori eseguono alternativamente la seguente azione:

Azione: scegli un numero $i$ da $\{0,1,\dots ,p-1\}$ che non è stato scelto prima, quindi scegli un numero intero tra $0$ e $9$ (inclusivo) per assegnare a $i$.

Il gioco termina quando tutti gli elementi di $\{0,1,\dots ,p-1\}$ sono stati scelti. $a_i$ sia il numero intero assegnato a $i$ e imposta $M=a_0+a_1\cdot 10+\cdots +a_{p-1}\cdot 10^{p-1}$. Se $M$ è divisibile per $p$, vince il primo giocatore; altrimenti vince il secondo giocatore. Prove che il primo giocatore ha una strategia vincente.

src_selection_camp_2018__Q07

Convex quadrilateral with incircle; incenters of two triangles and common external tangent point are concyclic with I

Let $ABCD$ be a convex quadrilateral that has an inscribed circle with center $I$. Let $I_a$ and $I_c$ be the incenters of triangles $DAB$ and $BCD$ respectively. Suppose the common external tangent (other than sides of the quadrilateral) of the circumcircles of triangles $B{I}_a{I}_c$ and $D{I}_a{I}_c$ meets at a point $X$. Prove that the four points $X$, $I$, $I_a$, $I_c$ are concyclic.

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

Quadrilatero converso con incircolo; gli incentri di due triangoli e il punto tangente esterno comune sono conciclici con I

$ABCD$ sia un quadrilaterale convex che abbia un cerchio inciso con il centro $I$. I centri di incendio dei triangoli $I_a$ e $I_c$ siano rispettivamente $DAB$ e $BCD$. Supponiamo che la tangente esterna comune (diversi dai lati del quadrilaterale) dei circoncircoli dei triangoli $B{I}_a{I}_c$ e $D{I}_a{I}_c$ si incontrino a un punto $X$. Prova che i quattro punti $X$, $I$, $I_a$, $I_c$ sono conciclici.

src_selection_camp_2018__Q08

Operation * on finite sets of positive integers; AB=BA implies iterated star associativity

For finite sets $X$ and $Y$ of positive integers, let $f_X(k)$ denote the $k$-th smallest positive integer not in $X$. Define $X\ast Y=X\cup \{f_X(y)\mid y\in Y\}.$ Let $a,b$ be positive integers. Let $A$ be a set of $a$ positive integers and $B$ be a set of $b$ positive integers. Suppose $A\ast B=B\ast A$. Prove that $\underset{A\text{ appears }b\text{ times}}{\underbrace{A\ast (A\ast \cdots \ast (A\ast (A\ast A))\cdots )}}=\underset{B\text{ appears }a\text{ times}}{\underbrace{B\ast (B\ast \cdots \ast (B\ast (B\ast B))\cdots )}}.$

Topic: Combinatoria, Insiemi e funzioni Metodo: Induzione, Invarianti, Biiezione Abilita: Astrazione, Manipolazione algebrica, Lettura attenta Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

L’operazione * su gruppi finiti di integri positivi; AB=BA implica l’associazione stellare iterata

Per i set finiti $X$ e $Y$ di enti interi positivi, $f_X(k)$ indica il $k$-minimo intero positivo non in $X$. Definire $X\ast Y=X\cup \{f_X(y)\mid y\in Y\}.$ Lasciate che $a,b$ siano numeri interi positivi. Che $A$ sia un insieme di enti interi positivi $a$ e $B$ sia un insieme di enti interi positivi $b$. Supponiamo $A\ast B=B\ast A$. Provare che $\underset{A\text{ appears }b\text{ times}}{\underbrace{A\ast (A\ast \cdots \ast (A\ast (A\ast A))\cdots )}}=\underset{B\text{ appears }a\text{ times}}{\underbrace{B\ast (B\ast \cdots \ast (B\ast (B\ast B))\cdots )}}.$

src_selection_camp_2018__Q09

Positive integer conditions on a_i imply polynomial M(x+1)^k - product has no positive real roots

Let $a_1,a_2,\dots ,a_n,k,M$ be positive integers satisfying $\frac{1}{a_1}+\frac{1}{a_2}+\cdots +\frac{1}{a_n}=k,a_1{a}_2\cdots a_n=M.$ Assume $M>1$. Prove that the equation in $x$ $M(x+1{)}^k-(x+a_1)(x+a_2)\cdots (x+a_n)=0$ has no positive real solutions.

Topic: Algebra, Disuguaglianze Metodo: Disuguaglianze, Estremalità Abilita: Manipolazione algebrica, Stima, Lettura attenta Area: Algebra e Analisi Fonte: apri PDF

Le condizioni di un numero intero positivo su a_i implicano polinomi M(x+1)^k - il prodotto non ha radici reali positive

Lasciate che $a_1,a_2,\dots ,a_n,k,M$ siano integri positivi che soddisfino $\frac{1}{a_1}+\frac{1}{a_2}+\cdots +\frac{1}{a_n}=k,a_1{a}_2\cdots a_n=M.$ Supponiamo $M>1$. Prove che l’equazione $x$ $M(x+1{)}^k-(x+a_1)(x+a_2)\cdots (x+a_n)=0$ non ha soluzioni reali positive.

src_selection_camp_2018__Q10

n×n×n cube colored with unit cubes: maximize colors such that every n×n×1 slab has the same color multiset

Let $n\ge 2$ be an integer. Consider an $n\times n\times n$ large cube made up of $n^3$ unit cubes, each painted in one color. For each of the $3n$ slabs of dimensions $n\times n\times 1$ (in any of the three orientations), consider the set of colors appearing in that slab (counting each color only once). When these $3n$ sets are divided into three groups according to orientation, it turns out that every set in one group also appears in each of the other two groups. Find the maximum possible number of colors that can appear in the large cube.

Topic: Combinatoria Metodo: Casework, Conteggio, Doppio conteggio Abilita: Conteggio sistematico, Modellizzazione, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

n×n×n cubo colorato con cubetti unitari: massimizzare i colori in modo che ogni lastra n×n×1 abbia lo stesso color multiset

$n\ge 2$ sia un numero intero. Considerate un grande cubo $n\times n\times n$ composto da cubi unitari $n^3$, ognuno dipinto in un colore. Per ciascuna delle lastre $3n$ di dimensioni $n\times n\times 1$ (in uno dei tre orientamenti), si deve considerare l’insieme dei colori presenti in tale lastra (conteggiando ogni colore solo una volta). Quando questi set $3n$ sono divisi in tre gruppi in base all’orientamento, si scopre che ogni set in un gruppo appare anche in ciascuno degli altri due gruppi. Trova il massimo numero possibile di colori che possono apparire nel grande cubo.

src_selection_camp_2018__Q11

Convex hexagon with AB=BC; reflections of A,B,C across line l; circumcircles meet at E; BB1 and DE meet on circumcircle

Let $ABC{C}_1{B}_1{A}_1$ be a convex hexagon satisfying $AB=BC$. Let $A_1$, $B_1$, $C_1$ be the reflections of $A$, $B$, $C$ respectively across a line $\ell$. Let $D$ be the intersection of segments $A{C}_1$ and $A_{1}C$, and let $\omega$ be the circumcircle of triangle $ABC$. Suppose $\omega$ and the circumcircle of triangle $A_{1}B{C}_1$ meet at a point $E$ other than $B$. Prove that line $B{B}_1$ and line $DE$ meet on $\omega$.

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

Esagono converso con AB=BC; riflessi di A,B,C attraverso la linea l; circoncircoli si incontrano a E; BB1 e DE si incontrano su circoncircolo

Che $ABC{C}_1{B}_1{A}_1$ sia un esagono convexo che soddisfi $AB=BC$. $A_1$, $B_1$, $C_1$ siano rispettivamente i riflessi di $A$, $B$, $C$ su una linea $\ell$. Il $D$ è l’intersezione dei segmenti $A{C}_1$ e $A_{1}C$, e il $\omega$ è il circoncircolo del triangolo $ABC$. Supponiamo che $\omega$ e il circoncircolo del triangolo $A_{1}B{C}_1$ si incontrino in un punto $E$ diverso da $B$. Provare che la riga $B{B}_1$ e la riga $DE$ si incontrano su $\omega$.

src_selection_camp_2018__Q12