Maths Olympiad Prep

Library / /108 of 121

Number theory Difficulty 7.0 National Olympiad Prove it India

Problem:

Define a sequence ann=1\left\langle a_{n}\right\rangle_{n=1}^{\infty} as follows:

an={0, if the number of positive divisors of n is odd 1, if the number of positive divisors of n is even  a_{n}= \begin{cases}0, & \text{ if the number of positive divisors of } n \text{ is odd } \\ 1, & \text{ if the number of positive divisors of } n \text{ is even }\end{cases}

(The positive divisors of nn include 1 as well as nn.) Let x=0.a1a2a3x=0 . a_{1} a_{2} a_{3} \ldots be the real number whose decimal expansion contains ana_{n} in the nn-th place, n1n \geq 1. Determine, with proof, whether xx is rational or irrational.

Solution

Solution:

We show that xx is irrational. Suppose that xx is rational. Then the sequence ann=1\left\langle a_{n}\right\rangle_{n=1}^{\infty} is periodic after some stage; there exist natural numbers k,lk, l such that an=an+la_{n}=a_{n+l} for all nkn \geq k. Choose mm such that mlkm l \geq k and mlm l is a perfect square. Let

m=p1α1p2α2prαr,l=p1β1p2β2prβr m=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{r}^{\alpha_{r}}, \quad l=p_{1}^{\beta_{1}} p_{2}^{\beta_{2}} \ldots p_{r}^{\beta_{r}}

be the prime decompositions of m,lm, l so that αj+βj\alpha_{j}+\beta_{j} is even for 1jr1 \leq j \leq r. Now take a prime pp different from p1,p2,,prp_{1}, p_{2}, \ldots, p_{r}. Consider mlm l and pmlp m l. Since pmlmlp m l-m l is divisible by ll, we have apml=amla_{p m l}=a_{m l}. Hence d(pml)d(p m l) and d(ml)d(m l) have same parity. But d(pml)=2d(ml)d(p m l)=2 d(m l), since gcd(p,ml)=1\operatorname{gcd}(p, m l)=1 and pp is a prime. Since mlm l is a square, d(ml)d(m l) is odd. It follows that d(pml)d(p m l) is even and hence apmlamla_{p m l} \neq a_{m l}. This contradiction implies that xx is irrational.

Alternative Solution:

As earlier, assume that xx is rational and choose natural numbers k,lk, l such that an=an+la_{n}=a_{n+l} for all nkn \geq k. Consider the numbers am+1,am+2,,am+la_{m+1}, a_{m+2}, \ldots, a_{m+l}, where mkm \geq k is any number. This must contain at least one 00. Otherwise an=1a_{n}=1 for all nkn \geq k. But ar=0a_{r}=0 if and only if rr is a square. Hence it follows that there are no squares for n>kn>k, which is absurd. Thus every ll consecutive terms of the sequence an\left\langle a_{n}\right\rangle must contain a 00 after certain stage. Let t=max{k,l}t=\max \{k, l\}, and consider t2t^{2} and (t+1)2(t+1)^{2}. Since there are no squares between t2t^{2} and (t+1)2(t+1)^{2}, we conclude that at2+j=1a_{t^{2}+j}=1 for 1j2t1 \leq j \leq 2 t. But then, we have 2t(>l)2 t(>l) consecutive terms of the sequence an\left\langle a_{n}\right\rangle which miss 00, contradicting our earlier observation.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.