For an integer $n$ with $b$ digits, let a subdivisor of $n$ be a positive number which divides a number obtained by removing the $r$ leftmost digits and the $l$ rightmost digits of $n$ for nonnegative integers $r,l$ with $r+l<b$ (For example, the subdivisors of $143$ are $1$, $2$, $3$, $4$, $7$, $11$, $13$, $14$, $43$, and $143$). For an integer $d$, let $A_d$ be the set of numbers that don't have $d$ as a subdivisor. Find all $d$, such that $A_d$ is finite.
Problem
Source: Turkey TST 2019 Day 2 P4
Tags: number theory
26.03.2019 21:27
The answer is all $d$ with $(d,10)=1$. If $2\mid d$, then any number with all odd digits is in $A_d$, so it can't be finite. If $5\mid d$, then any number with digits not equal to $0$ or $5$ is in $A_d$, so it can't be finite. Take $d$ with $(d,10)=1$. I will prove that for necessarily large $N$, any number with $N$ or more digits will have $d$ as a subdivisor. Let $a_1, a_2, \ldots, a_d$ be consequent digits in a $k\geq N$ digit number. Take numbers $a_d, \overline{a_{d-1}a_d},\ldots, \overline{a_1a_2\ldots a_d}$. If any of these is divisible by $d$, then it follows that $d$ is a subdivisor. Assume otherwise, then two of these must have the same reminder modulo $d$, thus the difference of these is is some number $\overline{a_1\ldots a_i000}$ which is divisible by $d$. Lastly, because we have $(d,10)=1$, it follows that $d$ divides $\overline{a_1\ldots a_i}$, and the conclusion follows.
29.03.2019 19:37
I think this question is based from a very well-known idea and not beautiful or original enough for Turkey TST...
07.03.2020 13:29
for $(d,10)=1$ let $t= ord _d(10)$ we will prove that $d$ is a subdivisor for $(a_na_{n-1}......a_{1})_{10}$ lemma: let $b_1 ,b_2 .....b_n,d$ natural numbers then there's $i,j$ such that $d|S(i,j)=b_i+b_{i+1}.....+b{j}$ for any large enough $n$ proof: suppose the contrary and let $b_i \equiv r_i mod (d)$ just take the $S(1,1),S(1,2).....S(1,d+1)$ there's $i,j$ such that $S(1,i) \equiv S(1,j) mod d $then $S(i,j) \equiv 0 mod (d)$ Now let $n=kt+r$ first remove ${a_1,a_2...a_r}$ and let $b_i$ the block of $t$ from $a's$ and just apply the lemma for $(d,10)>1$ just consider $n=(111..11111)_{10}$ and we win