5
$\begingroup$

The following is an interesting problem a friend of mine told me.

Let $\mathbb{N}^*=\mathbb{N}\setminus\{0\}$ and $U\subset \mathbb{N}^*$ be the set of positive integers whose base $10$ representation contains only $0$s and $1$s.

Show that for all $x\in\mathbb{N}^*$ there is some $y\in\mathbb{N}^*$ with $xy\in U$.

I have managed to solve it, but the solution is rather inelegant. Moreover, it uses Euler's theorem (on the totient function), and my friend implied that there should be a 'basic solution' -- that this problem should be solvable by an undergrad in an introductory course to real analysis.

I am interested to see what different solutions people can come up with. I can also post my own answer, but I figured I'd let you guys try your own hand at it before introducing some 'bias'.

$\endgroup$
  • $\begingroup$ I do not know how to solve that, but do you know are there an infinite number of such y for every x? $\endgroup$ – user480281 Oct 15 '17 at 6:10
  • $\begingroup$ @AntoinedePaladin Yes, there are. $\endgroup$ – Fimpellizieri Oct 15 '17 at 6:18
  • $\begingroup$ OK, so we can assign to every $x_i$ an $\infty $-tuple $(y_{1i},y_{2i},...,y_{ki},...)$. If $x_i \neq x_j$ will then intersection of $(y_{1i},y_{2i},...,y_{ki},...)$ with $(y_{1j},y_{2j},...,y_{kj},...)$ when viewed as sets be a finite set always? $\endgroup$ – user480281 Oct 15 '17 at 6:24
4
$\begingroup$

Consider the following sequence

$$a_i = \sum_{j=0}^i 10^j=\overbrace{1\ldots1}^{i+1}$$

where $i$ takes value from $0$ to $x$.

That is $a_0=1, a_1=11$,$a_2=111$, and so on, where $a_x=\overbrace{1\ldots1}^{x+1}$.

By pigeonhole principle, when we take modulo $x$, two of them will share the same remainder, $r$. Let these two indices be $i$ and $j$, $t<s$, hence $a_t < a_s$.

$$a_t = xp + r$$

$$a_s=xq+r$$

$$a_s-a_t=x(q-p)$$

Notice that $a_s-a_t$ consists of only $0$ and $1$ and it is positive.

That is $a_s-a_t \in U$ and we can pick $y=q-p$.

$\endgroup$
  • 2
    $\begingroup$ This fits very well my criteria of 'basic'. One of these situation where I'm left feeling stupid. Good job! $\endgroup$ – Fimpellizieri Oct 15 '17 at 6:21
  • $\begingroup$ It can also be easily generalized, changing the $1$ in '$0$s and $1$s' to any other digit. Pretty awesome. $\endgroup$ – Fimpellizieri Oct 15 '17 at 6:23
  • $\begingroup$ yup, or we can solve it for $1$ and $0$ and just multiply that number by the digit that you are interested. $\endgroup$ – Siong Thye Goh Oct 15 '17 at 6:28
  • $\begingroup$ Yeah, after this comment, I'm pretty sure it's about time I went to bed. $\endgroup$ – Fimpellizieri Oct 15 '17 at 6:30
2
$\begingroup$

Well, since Siong very quickly provided an awesome answer, I will show my own (rather shameful) answer for those that are curious.


Fix $x \in\mathbb{N}^*$. Notice that we may assume without loss of generality that $(x,10)=1$.

Let $X=x\cdot\mathbb{N}^*$ and $U_0=U$. Observe that the problem is equivalent to showing that $X\cap U_0$ is nonempty.

Choose some $k_1,n_1\in\mathbb{N}$ with the property that $xn_1+k_1=u_0\in U_0$. It's easy to see that one can always pick $k_1<x$, although it's not necessary.
Now, let $U_1\subset\mathbb{N}^*$ be the set obtained by adjoining $k_1$ to the left of each $u\in U$, in base $10$ notation.
Suppose that $X\cap U_1$ is nonempty, so that for some $a\in\mathbb{N}$ one may write

$$x\cdot a=k_1\,\square$$

where $k_1\,\square$ is a number whose base $10$ representation has $k_1$ to the left, and $\square$ denotes the rest of its base $10$ representation, which consists solely of $0$s and $1$s.

If there are $d$ digits in $\square$, we may write $k_1\,\square=k_1\cdot 10^d+v$ for some $v<10^d$ in $U$. In this case:

\begin{align} x\cdot (a+n_1\cdot10^d) &=xa+xn_1\cdot10^d\\ &=\left(k_1\cdot10^d+v\right)+xn_1\cdot10^d\\ &=(xn_1+k_1)\cdot10^d+v\\ &=u_0\cdot10^d+v \end{align}

In other words, $x\cdot (a+n_1\cdot10^d) \in U_0$.
This means that the problem is equivalent to showing that $X\cap (U_0\cup U_1)$ is nonempty.


Now, suppose that we do not yet know whether $X\cap U_1$ is nonempty. We can repeat the process as follows.

Choose $k_2,n_2\in\mathbb{N}$ with the property that $xn_2+k_2=u_1\in U_1$ and let $U_2\subset\mathbb{N}^*$ be the set obtained by adjoining $k_2$ to the left of each $u\in U$, in base $10$ notation.
If $X\cap U_2$ is nonempty, one may write $x\cdot a =k_2\cdot 10^d+v$ for some $a,d\in\mathbb{N}$ and $v<10^d$ in $U$.

Proceeding as above, we will find that $x\cdot(a+n_2\cdot 10^d)=u_1\cdot10^d+v\in U_1$, which means that, like before, the problem is equivalent to showing that $X\cap(U_0\cup U_1 \cup U_2)$ is nonempty.


At this point, I believe the induction is clear.

Lemma: For each $j\geq1$, we may choose $k_j$ so that $k_j\equiv jk_1\pmod x$.

The lemma show that in at most $x$ steps we will have $u_{x-1}=xn_x+k_x\equiv 0\pmod x$, that is, $u_{x-1}\in X\cap U_{x-1}$, which completes the proof.

Proof of Lemma: Since $x$ and $10$ are coprime, by Euler's theorem we have that

$$10^{\varphi(x)}\equiv 1 \pmod x.$$

In particular, there are arbitrarily high powers of $10$ equivalent to $1$ modulo $x$.

We define the $k_j$ via induction. The base case $j=1$ is obvious, and remember it entails the existence of $n_1\in\mathbb{N}$ and $u_0\in U_0$ with $xn_1+k_1=u_0$.
For the inductive step, suppose $k_j$ has been defined so that $k_j\equiv jk_1\pmod x$. Choose some $d\in\mathbb{N}$ with $10^d\equiv 1 \pmod x$ and $u_0<10^d$. Then:

$$k_j\cdot 10^d+u_0=k_j\cdot 10^d+xn_1+k_1=xn_1+\left(k_j\cdot 10^d+k_1\right).$$

Notice that $\left(k_j\cdot 10^d+u_0\right)\in U_{j}$ and that $k_j\cdot 10^d+k_1\equiv k_j+k_1\equiv (j+1)k_1\pmod x$.
It follows that we may take $n_{j+1}=n_1$ and $k_{j+1}=k_j\cdot 10^d+k_1$. $\square$

$\endgroup$
1
$\begingroup$

This is only a part of the answer. Consider this as a hint.

Basically, after you choose $x$, what you have to do is, look at the decimal expansion of $\frac 1x$. Since ${x}$ is natural, ${\frac 1x} $ will be either a terminating or recurring decimal. If it is terminating, then $x$ must be a multiplication of powers of 2 and 5. Then you are done.

Now consider $x$ to be a prime other than 2, 3, 5. Then $\frac 1x$ will be a recurring decimal. For example take $x=7$. Then $$1/7=0.\bar{abcdefg} =\frac {abcdefg} {999999}$$ So $7×abcdefg=999999$.

$abcdefg$ is obviously divisible by 9. So just divide it by 9 to get suitable $y$.

For $x=3$, you have $y=37$ whose multiplication gives $111$.
I guess you can elaborate after this?

$\endgroup$
  • $\begingroup$ This is an interesting approach. One of my other friends whom my first friend showed this problem to ran into some trouble with $x$'s containing factors of $3$.$${}$$ We may assume $x$ is coprime to $10$ $($and hence contains no factors of $2$ and $5)$. I must confess I'm not entirely sure how to proceed if, say, $x=3^a\cdot b$. That said, this method works beautifully whenever $x$ is coprime to $3$. $\endgroup$ – Fimpellizieri Oct 15 '17 at 6:48
  • $\begingroup$ Well, simply by divisibility criterion of $3^a$, $1_{a}$ is a multiple. As for $3^a×b$, where $b$ is any number, you just have to put suitable number of $0's$ between the $1_{a} $ and multiply to suit your answer. $\endgroup$ – Abhishek Bakshi Oct 15 '17 at 6:57
  • $\begingroup$ For example, let's say $x=63=3^2×7 $. We have $3^2×p=111111111$ and $7×q=111111$. So just take $y=(10^6+1)pq$. You see what I did there? $\endgroup$ – Abhishek Bakshi Oct 15 '17 at 7:03
  • $\begingroup$ What divisibility criterion for powers of $3$? $\endgroup$ – Fimpellizieri Oct 15 '17 at 7:15
  • $\begingroup$ By the way, here we have $p=12345679$ and $q=15873$. This should give $y=195963158729962767$, but $63y=12345678999987654321$. While certainly it has an interesting structure, it does not solve our problem. $\endgroup$ – Fimpellizieri Oct 15 '17 at 7:57
1
$\begingroup$

Siong Thye Goh has a pretty cool solution but I have some kind of weird procedure that works too.

First, express $x=5^a\cdot2^b\cdot x'$. Since we can always multiply $x$ by $2^a\cdot 5^b$ to get $10^{a+b}x'$ and this is in $U$ precisely when $x'\in U$, we may assume that $\gcd(x,10)=1$ and just solve the problem.

Given $x\in \mathbb N^*$, are just looking for a positive integer $N=\sum_{i=0}^ka_i10^i$ with $a_i=0$ or $1$ such that $$\sum_{i=0}^ka_i10^i \equiv 0\pmod x. $$ (Once we find this, the $y$ in the problem will just be $N/x$.)

First write out the decimal expansion $x=\sum_{i=0}^d b_i10^i$ with $0\leq b_i\leq 9$. It is trivially true that $$\sum_{i=0}^d b_i10^i=x\equiv 0 \pmod x $$

Now we are going to find a number of the desired form (only has 0 and 1 in it's decimal expansion) congruent to this number.

Write each term $b_i 10^i$ as a sum of $b_i$ copies of $10^i$. Namely, $\overbrace{10^i+\cdots +10^i}^{b_i}$.

Since $(10,x)=1$, by Euler's theorem $(10^i)^{m\varphi(x)+1}=10^i$ for every non-negative integer $m$. Now we can replace all the $\sum_{i=0}^d b_i$ many powers of $10$ with distinct large powers of $10$. So when we take their sum, this will have only $0$s and $1$s in their decimal expansion because we are adding distinct powers of $10$.

The last two sentences also show that there are infinitely many "non boring" solutions, i.e. solutions that do not just differ from each other by multiplication by a power of $10$.

$\endgroup$
  • 1
    $\begingroup$ This is a great, creative solution! You can assume $x$ is coprime to $10$ without loss of generality. First, write $x=x^*\cdot2^a5^b$ where $x^*$ contains no factors of $2$ or $5$. Then, solve the problem for $x^*$, obtaining $y^*$ with $x^*y^*=u\in U$. Finally, take $y=y^*\cdot2^b5^a$, so that $xy=x^*y^*\cdot 10^{a+b}=u\cdot10^{a+b}\in U$. $\endgroup$ – Fimpellizieri Oct 15 '17 at 7:04
  • 1
    $\begingroup$ @Fimpellizieri Aha, I was just making that update. I couldn't sleep without fixing this. :D $\endgroup$ – Ravi Oct 15 '17 at 7:09
  • $\begingroup$ =) Great job! ${}$ $\endgroup$ – Fimpellizieri Oct 15 '17 at 7:10
0
$\begingroup$

Here's a method which is similar to Siong Thye Goh's but for some $x$ yields a smaller result.

If $x=2^s5^t$, we may take $xy=10^{\max(s, t)}.$

Otherwise, let $b_i=10^i\bmod x$. By the pigeonhole principle there will be some $t$ and $s>t$ where $b_s=x-b_t$. One may then take $xy=10^s+10^t$.

For example if $x=7$, $(b_0,\dots)=(1, 3, 2, 6, 4, 5, 1,\dots)$ so we may take $t=0, s=3, xy=1001$.

$\endgroup$
  • $\begingroup$ It is rather obvious that $7\cdot 1001$ does not result in a number that contains only $0$s and $1$s. $\endgroup$ – Fimpellizieri Oct 15 '17 at 20:14
  • $\begingroup$ @Fimpellizieri OK, typo corrected. $\endgroup$ – Rosie F Oct 16 '17 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.