OBM 2017

For each real number $r$ between $0$ and $1$ we can represent $r$ as an infinite decimal $r = 0.r_1r_2r_3\dots$ with $0 \leq r_i \leq 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 rational numbers $p$ and $q$ between $0$ and $1$ such that, from their decimal representations $p = 0.p_1p_2p_3\dots$ and $q = 0.q_1q_2q_3\dots$ , it's possible to construct an irrational number $\alpha = 0.a_1a_2a_3\dots$ such that, for each $i = 1, 2, 3, \dots$ , we have $a_i = p_1$ or $a_1 = q_i$ .

b) Show that there's a rational number $s = 0.s_1s_2s_3\dots$ and an irrational number $\beta = 0.b_1b_2b_3\dots$ such that, for all $N \geq 2017$ , the number of indexes $1 \leq i \leq N$ satisfying $s_i \neq b_i$ is less than or equal to $\frac{N}{2017}$ .

Let $n \geq 3$ be an integer. Prove that for all integers $k$ , with $1 \leq k \leq \binom{n}{2}$ , there exists a set $A$ with $n$ distinct positive integer elements such that the set $B = \{\gcd(x, y): x, y \in A, x \neq y \}$ (gotten from the greatest common divisor of all pairs of distinct elements from $A$ ) contains exactly $k$ distinct elements.

A quadrilateral $ABCD$ has the incircle $\omega$ and is such that the semi-lines $AB$ and $DC$ intersect at point $P$ and the semi-lines $AD$ and $BC$ intersect at point $Q$ . The lines $AC$ and $PQ$ intersect at point $R$ . Let $T$ be the point of $\omega$ closest from line $PQ$ . Prove that the line $RT$ passes through the incenter of triangle $PQC$ .

We see, in Figures 1 and 2, examples of lock screens from a cellphone that only works with a password that is not typed but drawn with straight line segments. Those segments form a polygonal line with vertices in a lattice. When drawing the pattern that corresponds to a password, the finger can't lose contact with the screen. Every polygonal line corresponds to a sequence of digits and this sequence is, in fact, the password. The tracing of the polygonal obeys the following rules:

i. The tracing starts at some of the detached points which correspond to the digits from $1$ to $9$ (Figure 3).

ii. Each segment of the pattern must have as one of its extremes (on which we end the tracing of the segment) a point that has not been used yet.

iii. If a segment connects two points and contains a third one (its middle point), then the corresponding digit to this third point is included in the password. That does not happen if this point/digit has already been used.

iv. Every password has at least four digits.

Thus, every polygonal line is associated to a sequence of four or more digits, which appear in the password in the same order that they are visited. In Figure 1, for instance, the password is 218369, if the first point visited was $2$ . Notice how the segment connecting the points associated with $3$ and $9$ includes the points associated to digit $6$ . If the first visited point were the $9$ , then the password would be $963812$ . If the first visited point were the $6$ , then the password would be $693812$ . In this case, the $6$ would be skipped, because it can't be repeated. On the other side, the polygonal line of Figure 2 is associated to a unique password.

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

Attachments:

In triangle $ABC$ , let $r_A$ be the line that passes through the midpoint of $BC$ and is perpendicular to the internal bisector of $\angle{BAC}$ . Define $r_B$ and $r_C$ similarly. Let $H$ and $I$ be the orthocenter and 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$ .

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