Library / /19 of 24

, 2018

Number theory Difficulty 5.7 AIME, harder Prove it United States

Problem:
Let $m > 1$ be a fixed positive integer. For a nonempty string of base-ten digits $S$ , let $c(S)$ be the number of ways to split $S$ into contiguous nonempty strings of digits such that the base-ten number represented by each string is divisible by $m$ . These strings are allowed to have leading zeroes.
In terms of $m$ , what are the possible values that $c(S)$ can take?
For example, if $m = 2$ , then $c(1234) = 2$ as the splits $1234$ and $12 \mid 34$ are valid, while the other six splits are invalid.

Solution

Solution:
Answer: $0$ and $2^{n}$ for all nonnegative integer $n$

First, we note that $c(1) = 0$ and $c(00 \ldots 0) = 2^{n-1}$ if there are $n$ zeroes in the string. Now we show that these are the only possibilities. Note that a split can be added if and only if the string before this split (ignoring all other splits) represents a multiple of $m$ (if there is a split before it, then removing the digits before this preceding split is equivalent to subtracting the removed number times a power of $10$ , which will also be a multiple of $m$ , so the remaining number between the two splits remains a multiple of $m$ ). Thus, whether we can add a split or not depends only on the string itself and no other splits, so $c(S)$ is $0$ if the number is not divisible by $m$ and a power of two otherwise.

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.