a) Prove that there exists a sequence of digits $\{c_n\}_{n\geq 1}$ such that or each $n\geq 1$ no matter how we interlace $k_n$ digits, $1\leq k_n\leq 9$, between $c_n$ and $c_{n+1}$, the infinite sequence thus obtained does not represent the fractional part of a rational number. b) Prove that for $1\leq k_n\leq 10$ there is no such sequence $\{c_n\}_{n\geq 1}$. Dan Schwartz
Problem
Source: Romanian IMO TST 2005 - day 4, problem 4
Tags: modular arithmetic, number theory proposed, number theory
23.04.2005 19:48
Sorry, I can't understand it.
23.04.2005 20:02
At a) you have to find a sequence of digits $c_1,c_2,\ldots$ such that no matter how we put 1 or 2 or 3 or ... or 9 digits between $c_1$ and $c_2$, then between $c_2$ and $c_3$, etc. the resulting number ${0.c_1 \ a_1a_2\ldots a_{k_1}} \ c_2 \ b_1b_2\ldots b_{k_2} \ c_3 \ \ldots$ is not rational. At b) you must prove that if we allow to include 10 digits between each two consecutive terms of $\{c_n\}_n$ we can create a rational number.
23.04.2005 20:55
For a. It is quite clear. Take, for example, $c_n=s_k\pmod{10}$ for all $10^{k!}<n\leq 10^{(k+1)!}$, where $s_k$ is a sequence s.t. for each ordered pair of digits $(a,b)$ there are infinitely many $i$ s.t. $s_i=a$ and $s_i=b$. Suppose we can construct a rational number $r$ from it. The choice of $c_n$ guaratees that part of each digit in representation of $r$ is at least $\frac{1}{10}$. It follows that each digit 0,..., 9 meets exactly 10% of times in the period of $r$. Moreover it is clear we should have $r_n=r_{n+10}$, i.e. period is $d_1d_2...d_10$, where $\{d_1,...,d_10\}=\{0,1,2,...,9\}$. On the other hand it is an impossible. Indeed, suppose $c_n=d_1$ and $c_{n+1}=d_2$ (remember, there are infinitely many such $n$), then we should insert at least 10 numbers between them! Contradiction.
23.04.2005 20:59
Myth wrote: For a. It is quite clear. This appears to be the most difficult problem on the test, as far as the results go
23.04.2005 21:08
For b. Indeed, I am dumb. We can always provide a period $0123456789$.
23.04.2005 23:22
Also for (a) (terribly sorry if this is the same as Myth's solution). Given the first few digits $c_1,c_2,\ldots,c_k$ and a rational, partition the decimal representation of the rational in groups of $9$ digits. From each such group, at least one digit is missing, and in each group we must have at least one of the $c_i$'s. Pick a digit $a$ which is missing from a group of $9$ which appears infinitely many times (which is part of the period, for example). If $t$ is large enough and $c_{k+1},c_{k+2},\ldots,c_{k+t}$ are all equal to $a$, then this rational cannot be formed by the procedure described in the problem. We now enumerate the rationals, and, at each step, we construct more of our sequence in the manner described above. I hope it's Ok.