A wobbly number is a positive integer whose digits are alternately zero and non-zero with the last digit non-zero (for example, 201). Find all positive integers which do not divide any wobbly number.
Problem
Source: IMO Shortlist 1994, N7
Tags: number theory, decimal representation, IMO Shortlist, Divisibility
23.10.2005 10:47
All non-multiples of both $25$ and $10$ should work, I think. First of all, notice that $25$ cannot divide a wobbly number, since it divides the difference between the wobbly number and its unit digit, which is non-zero. It's also clear that $10$ cannot divide a wobbly number. Now we prove that for any $t\ge 0$, there is a wobbly number with $2t+1$ digits, divisible by $2^{2t+3}$. The base step is clear, and if we assume we've shown it for $t$, we construct a wobbly umber with $2t+3$ digits divisible by $2^{2t+5}$ as follows: if the previous one was also divisible by $2^{2t+5}$, we just add $8\cdot 10^{2t+2}$ to it, if it was divisible by $2^{2t+4}$ but not $2^{2t+5}$, we add $4\cdot 10^{2t+2}$, and, finally, if it was divisible by $2^{2t+3}$ but not $2^{2t+4}$, we add either $2\cdot 10^{2t+2}$ or $6\cdot 10^{2t+2}$ to it, according to whether its quotient when divided by $2^{2t+3}$ was of the form $4k+3$ or $4k+1$ respectively. This shows, in particular, that for any $t$ there is a wobbly number divisible by $2^t$. Given any number $n$ which is neither a multiple of $25$ nor of $10$, there are two possibilities: it can be of the form $2^tm,\ (m,10)=1$, or $5m,\ (m,10)=1$. Take a wobbly number $w$ divisible by $2^t$ in the first case and $5$ in the second. If it has $a$ digits, since $(10^{a+1},m)=1$, we can find a $j$ s.t. $10^{j(a+1)}+\ldots+10^{a+1}+1$ is divisible by $m$, and then $w(10^{j(a+1)}+\ldots+10^{a+1}+1)$ will be a wobbly number divisible by $n$.
06.06.2018 16:15
grobber wrote: Take a wobbly number $w$ divisible by $2^t$ in the first case and $5$ in the second. If it has $a$ digits, since $(10^{a+1},m)=1$, we can find a $j$ s.t. $10^{j(a+1)}+\ldots+10^{a+1}+1$ is divisible by $m$, and then $w(10^{j(a+1)}+\ldots+10^{a+1}+1)$ will be a wobbly number divisible by $n$. But, isn't it violating the condition that there are no consecutive squares? Also, can't we use euler's theorem here? I think it would be pretty neat...
06.06.2018 21:43
yes, grober is right. A multiple of !0 doesnot divide any woobly number. and 25 also works. Let us now prove that the others don't work. Let n be odd and not divisible by 5. for any $k>0$ there exists $x$ such that $(10^k -1)n$ divides $10^x -11$, and thus also divides ${10}^{kx} -1$. Consequently, $v_k$=$\frac{10^{kx}-1}{10^k-1}$ is divisible by n, and it is woobly when k=2. If n is divisible by 5, one can $5v_2$ then. let n be a power of $2$. We prove by induction on m that ${2}^{2m+1}$ has a woobly multiple $z_m$ with exactly m non-zero digits. For m=1, take $z_1=8$. suppose that for some $m>0$ there is a woobly $z_m = {2}^{2m+1}d_m$. then the numbers $a.10^{2m} + z_m$ are woobly and divisible by $2^{2m+1}$ when a is an element of ${2,4,6,8}$. Moreover, one of these numbers is divisible by $2^{2m+3}$. It suffices to choose a such that $\frac{a}{2} +d_m$ is divisible by 4. this proves the indutive step. Let $n=r2^m$ where m is a natural number and r is odd. 5 does not divide r. Then $v_{2m}z_{m}$ is woobly and divisible by both $2^r$ and $r$.
07.06.2018 07:18
Doesn't it also contain consecutive zeroes ?!?? I'm probably messing up somewhere... lemme check
29.07.2020 05:27
We claim that all numbers that aren't multiples of $10$ or multiples of $25$ can divide at least one wobbly number. We will first prove that multiples of $10$ and multiples of $25$ will not divide any wobbly number. Since the last digit of the wobbly number is always non-zero, $10$ cannot divide any wobbly number. Also notice the only times that $25$ divides any number is when the number ends in $00, 25, 50,$ or $75$ but since a wobbly number cannot end in any of these four possible combinations, $25$ doesn't divide any wobbly number. Now we will prove that all other numbers divide at least one wobbly number and we have three cases. Case 1: odd numbers $a$ such that $5 \nmid a$ and gcd$(a,10)=1$ Since gcd$(a,10)=1$, gcd$(a(10^k-1),10)=1$ It follows that there exists a $b$ such that $10^b \equiv 1$ mod $(a(10^k-1))$ so $10^{kb} \equiv 1$ mod $(a(10^k-1))$ $10^{kb} -1 = (10^k-1)(10^{k(b-1)} + 10^{k(b-2)} + ... + 10^k + 1)$ then $a \vert (10^{k(b-1)} + 10^{k(b-2)} + ... + 10^k + 1)$ so when $k=2$, $(10^{k(b-1)} + 10^{k(b-2)} + ... + 10^k + 1) = (10^{2(b-1)} + 10^{2(b-2)} + ... + 10^2 + 1)$ which is a wobbly number Case 2: powers of $2$ or numbers in the form $2^a$ where $a\geq1$ We will do a proof by induction on $a$ that $2^{2a+1}$ divides a wobbly number with $2a-1$ digits, let the wobbly number be with $2a-1$ digits be written as $w_a$ Base case: if $a=1$ then $w_1 = 8$ $n+1$ case: suppose there does exist a $w_a$ for all $a\geq1$ then let $w_a = 2^{2a+1}b$ for some $b$ and let $w_{a+1} = 10^{2a}c + w_a$ for $c \in \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ clearly $w_{a+1}$ is wobbly and has $2a+1$ digits so $w_{a+1} = 2^{2a}(5^{2a}c+2b)$ and $2^{2a+3} \vert w_{a+1}$ if $5^{2a}c+2b \equiv 0$ mod $8$ or if $c \equiv 6b$ mod $8$ so if $c \in \{2,4,6,8\}$ then the congruence is satisfied and the induction is complete Case 3: numbers in the form $2^ab$ where $b>1$, $b$ is odd, $a\geq1,$ and gcd$(b,10)=1$ we proved earlier that there exists a $w_a$ that divides $2^a$ and we proved that if $b$ is odd and gcd$(b,10)=1$ then $b \vert (10^{k(c-1)} + 10^{k(c-2)} + ... + 10^k + 1)$ let $f_k = (10^{k(c-1)} + 10^{k(c-2)} + ... + 10^k + 1)$ then numbers in the form $2^ab$ have a wobbly multiple which is $w_af_{2b}$ so the only numbers that don't divide at least one wobbly number are multiples of $10$ and multiples of $25.$ $\blacksquare$