Olimpíada Brasileira de Matemática 2017 — Nível 3 — Fase 3

Decimal digits of two rationals combined into an irrational; index-counting bound

For each real number $r$ between $0$ and $1$ we can represent $r$ with the infinite decimal $r=0,r_1{r}_2{r}_3\dots$ with $0\le r_i\le 9$. For example, $\frac{1}{4}=0,25000\dots$, $\frac{1}{3}=0,333\dots$ and $\frac{1}{\sqrt{2}}=0,707106\dots$

a) Show that we can choose two rationals $p$ and $q$ between $0$ and $1$ so that, starting from their decimal representations $p=0,p_1{p}_2{p}_3\dots$ and $q=0,q_1{q}_2{q}_3\dots$, it is possible to construct an irrational number $\alpha =0,a_1{a}_2{a}_3\dots$ such that for each $i=1,2,3,\dots$ we have $a_i=p_i$ or $a_i=q_i$.

b) Show that there exist a rational $s=0,s_1{s}_2{s}_3\dots$ and an irrational $\beta =0,b_1{b}_2{b}_3\dots$ such that for all $N\ge 2017$ the number of indices $1\le i\le N$ for which $s_i\ne b_i$ is less than or equal to $\frac{N}{2017}$.

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

Cifri decimali di due numeri razionali combinati in un limite di conteggio dell’indice irrazionale

Per ogni numero reale $r$ tra $0$ e $1$ possiamo rappresentare $r$ con la decima infinita $r=0,r_1{r}_2{r}_3\dots$ con $0\le r_i\le 9$. Ad esempio, $\frac{1}{4}=0,25000\dots$, $\frac{1}{3}=0,333\dots$ e $\frac{1}{\sqrt{2}}=0,707106\dots$

a) Mostrare che possiamo scegliere due razionali $p$ e $q$ tra $0$ e $1$ in modo che, partendo dalle loro rappresentazioni decimali $p=0,p_1{p}_2{p}_3\dots$ e $q=0,q_1{q}_2{q}_3\dots$, sia possibile costruire un numero irrazionale $\alpha =0,a_1{a}_2{a}_3\dots$ tale che per ogni $i=1,2,3,\dots$ abbiamo $a_i=p_i$ o $a_i=q_i$.

b) dimostrare che esiste un $s=0,s_1{s}_2{s}_3\dots$ razionale e un $\beta =0,b_1{b}_2{b}_3\dots$ irrazionale tale che per tutti $N\ge 2017$ il numero degli indici $1\le i\le N$ per i quali $s_i\ne b_i$ è inferiore o uguale a $\frac{N}{2017}$.

src_obm_2017_n3_f3__Q01

Set of n positive integers whose pairwise GCDs form a set of exactly k elements

Let $n\ge 3$ be an integer. Prove that for every integer $k$ with $1\le k\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$, there exists a set $A$ of $n$ distinct positive integers such that the set $B=\{\gcd (x,y):x,y\in A,x\ne y\}$ (obtained from the greatest common divisors of all pairs of distinct elements of $A$) contains exactly $k$ distinct elements.

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

insieme di n integri positivi i cui GCD in coppia formano un insieme di elementi esattamente k

$n\ge 3$ sia un numero intero. Prova che per ogni intero $k$ con $1\le k\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ esiste un insieme $A$ di $n$ diversi interi positivi in modo tale che l’insieme $B=\{\gcd (x,y):x,y\in A,x\ne y\}$ (ottenuto dai più grandi divisori comuni di tutte le coppie di elementi distinti di $A$) contiene esattamente $k$ elementi distinti.

src_obm_2017_n3_f3__Q02

Tangential quadrilateral with inscribed circle; line RT passes through incenter of triangle PQC

A quadrilateral $ABCD$ has an inscribed circle $\omega$ and is such that the rays $AB$ and $DC$ meet at a point $P$ and the rays $AD$ and $BC$ meet at a point $Q$. The lines $AC$ and $PQ$ meet at a point $R$. Let $T$ be the point of $\omega$ closest to the line $PQ$. Prove that the line $RT$ passes through the incenter of triangle $PQC$.

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

Quadrilatero tangenziale con un cerchio inciso; linea RT passa attraverso l’incentro del triangolo PQC

Un quadrilaterale $ABCD$ ha un cerchio inciso $\omega$ ed è tale che i raggi $AB$ e $DC$ si incontrino in un punto $P$ e i raggi $AD$ e $BC$ si incontrino in un punto $Q$. Le linee $AC$ e $PQ$ si incontrano in un punto $R$. $T$ deve essere il punto di $\omega$ più vicino alla linea $PQ$. Prova che la linea $RT$ passa attraverso l’incentro del triangolo $PQC$.

src_obm_2017_n3_f3__Q03

Phone unlock pattern on a 3x3 grid: find smallest n so any n-subset of digits admits a valid path

In Figures 1 and 2 below we see examples of unlocking a cell-phone screen with a password that is not typed but drawn with line segments. These segments form a polygonal line whose vertices lie on a grid. While drawing the pattern corresponding to the password, the finger must stay in contact with the screen the whole time. The whole polygonal line corresponds to a sequence of digits, and this sequence is in fact the password. The drawing of the polygonal lines obeys the following rules:

i. The drawing starts at one of the highlighted points, which correspond to the digits $1$ to $9$ (Figure 3).

ii. Each segment of the pattern must have, as one of its endpoints (the one where we finish drawing the segment), a point that has not yet been used.

iii. If a segment joins two points and contains a third point (its midpoint), then the digit corresponding to that third point is included in the password. This does not happen when that point/digit has already been used.

iv. Every password has at least four digits.

Thus, every polygonal line is associated with a sequence of four or more digits, which appear in the password in the same order in which they are visited. In Figure 1 above, for example, the password is $218369$, in the case where the first point visited was $2$. Note that the segment joining the points associated with the digits $3$ and $9$ includes the point associated with the digit $6$. If the first point visited were $9$, then the password would be $963812$. If the first point visited were $6$, then the password would be $693812$. Note that $6$ would be skipped, since it could not be repeated. On the other hand, the polygonal line of Figure 2 is associated with a single password.

Determine the smallest $n$ ($n\ge 4$) such that, given any subset of $n$ digits from $1$ to $9$, it is possible to elaborate a password that involves exactly those digits in some order.

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

Modello di sblocco del telefono su una griglia 3x3: trovare il più piccolo n in modo che qualsiasi n-sottoinsieme di cifre ammetta un percorso valido

Nelle figure 1 e 2 di seguito vediamo esempi di sblocco di uno schermo del cellulare con una password che non viene digitata ma disegnata con segmenti di linea. Questi segmenti formano una linea poligonale le cui vertici si trovano su una griglia. Durante il disegno del modello corrispondente alla password, il dito deve rimanere in contatto con lo schermo per tutto il tempo. L’intera linea poligonale corrisponde a una sequenza di cifre, e questa sequenza è in realtà la password. Il disegno delle linee poligonali è conforme alle seguenti regole:

i. Il disegno inizia ad uno dei punti evidenziati, che corrispondono alle cifre $1$ a $9$ (figura 3).

ii. Ogni segmento del modello deve avere, come uno dei suoi punti finali (quello in cui si finisce il segmento), un punto che non è ancora stato utilizzato.

iii. Se un segmento unisce due punti e contiene un terzo punto (il suo punto medio), allora la cifra corrispondente a tale terzo punto è inclusa nella password. Questo non avviene quando tale punto/cifre è già stato utilizzato.

iv. Ogni password ha almeno quattro cifre.

Pertanto, ogni linea poligonale è associata a una sequenza di quattro o più cifre, che appaiono nella password nello stesso ordine in cui vengono visitate. Nella figura 1 sopra, ad esempio, la password è $218369$, nel caso in cui il primo punto visitato è stato $2$. Si noti che il segmento che unisce i punti associati ai numeri $3$ e $9$ include il punto associato al numero $6$. Se il primo punto visitato fosse $9$, la password sarebbe $963812$. Se il primo punto visitato fosse $6$, la password sarebbe $693812$. Si noti che $6$ sarebbe saltato, poiché non poteva essere ripetuto. D’altra parte, la linea poligonale della figura 2 è associata a una singola password.

Determinare la minima $n$ ($n\ge 4$) in modo tale che, data qualsiasi sottoinsieme di cifre $n$ da $1$ a $9$, sia possibile elaborare una password che coinvolga esattamente quelle cifre in un certo ordine.

src_obm_2017_n3_f3__Q04

Lines through midpoints perpendicular to internal bisectors; circumcenter of resulting triangle is midpoint of HI

In triangle $ABC$, let $r_A$ be the line passing through the midpoint of $BC$ and perpendicular to the internal bisector of $\angle BAC$. Define $r_B$ and $r_C$ in the same way. Let $H$ and $I$ be the orthocenter and the incenter of $ABC$, respectively. Suppose that the three lines $r_A$, $r_B$, $r_C$ define a triangle. Prove that the circumcenter of this triangle is the midpoint of $HI$.

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

Line attraverso i punti di metà perpendicolari ai bisetti interni; il centro circoncentrale del triangolo risultante è il punto medio di HI

Nel triangolo $ABC$, $r_A$ sia la linea che attraversa il punto medio di $BC$ e che sia perpendicolare al bisettore interno di $\angle BAC$. Definire $r_B$ e $r_C$ nello stesso modo. Che $H$ e $I$ siano rispettivamente l’ortocentro e l’incentro di $ABC$. Supponiamo che le tre linee $r_A$, $r_B$, $r_C$ definiscano un triangolo. Prova che il centro circoncentrale di questo triangolo è il punto medio di $HI$.

src_obm_2017_n3_f3__Q05

Prime divisor p of a^3-3a+1 with p not 3 has the form 9k+1 or 9k-1

Let $a$ be a positive integer and $p$ a prime divisor of $a^3-3a+1$ with $p\ne 3$. Prove that $p$ is of the form $9k+1$ or $9k-1$, with $k$ an integer.

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

Il primo divisore p di a^3-3a+1 con p non 3 ha la forma 9k+1 o 9k-1

Che $a$ sia un intero positivo e $p$ un primo divisore di $a^3-3a+1$ con $p\ne 3$. Provare che $p$ è di forma $9k+1$ o $9k-1$, con $k$ un numero intero.

src_obm_2017_n3_f3__Q06