Save now! All the digits at half the price

Question

... or double the price depending on where you're coming from

Consider the set $PD10$ of pan-digital ten-digit numbers, i.e. positive whole numbers whose decimal representation has each of the digits 0,1,...,9 occurring exactly once.

For simplicity, we will allow leading $0$s (so there are precisely $10!$ such numbers). The smallest $PD10$ number, $x=0123456789$, has an interesting property: Doubling it will shuffle its digits, in other words, $2x\in PD10$, too: $2x = 0246913578$.

It turns out that a surprisingly large number of numbers $z\in PD10$ have the same property, $2z\in PD10$.

Question: How many?

Please be sure to note the no-computers tag.

Inspired by this meta-ish question.

Answer 1

Let's define some terms:

Each of the 10 digits has a partner modulo 5: 0's partner is 5, 7's is 2, 2's is 7, and so on. A digit and its partner (which form a pair) can double to two different digits, depending on whether they are carried into: 1 and 6 can become 2 or 3, 3 and 8 can become 6 or 7, etcetera. We'll say a number such as 0123456789 has a carry profile describing its carries - we'll include (necessarily zero) carries into the bottom digit and out of the top digit, for convenience.

Now we can begin.

In order for x and 2x to be pandigital, we must have the following:
- For each pair, the outgoing carries must be distinct (else x has duplicate digits)
- For each pair, the incoming carries must be distinct (else 2x has duplicate digits)
This means that if we attach each digit with a tag denoting its incoming and outgoing carries, the tag of any number is the complement of its partner's. (This is why we added two extra carries to the profile.)
Armed with these criteria, we can forget the digit structures of x and 2x and rephrase the problem as follows: How many valid (pair assignment)-(carry profile) pairs are there?

Let's break the problem down now.

How many valid carry profiles are there?
For starters, there are 9 choose 4, or 90 126, ways to assign four zeros to the interior of a carry profile. Every such choice is potentially valid, because every 01 can pair with a 10, and there is such a pair for every block of 1's. There must be a total of 5 0* tags and 5 1* tags, so the remaining tags will form 00-11 pairs.
How many tag assignments does a carry profile admit?
Partnership bijects the 00 tags with the 11 tags, and likewise the 01 tags with the 10 tags. Therefore, a carry profile with p blocks admits p!(5-p)! pair assignments. (As usual, 0! = 1)

Now for the final count!

Each composition (ordered partition, like 5, 212, 1121, or 41) of 5 determines a different "class" of carry profile with that sequence of block lengths. There are 16 classes, and each class' calculation follows the same format: After collapsing each block of 1's and the 0 after it to a single space, we have 5* spaces for our p parts, and thus p choose 5 ways to place them. Each placement admits p!(5-p)! assignments, which conveniently yields 5! per class - so we have 16×120 = 1920 total assignment-profile pairs. The pairs can be placed in an assignment in any order, but the high digit in each pair is fixed by the carry profile, so each of these assignments corresponds to 120 values of x and we get...
230400, as in Qise's answer.
*It seems like we're ignoring the restrictions on the ends of the profile, but the bottom end counts as a degree of freedom because you can pretend it gets absorbed instead of the last block's expected target.

Answer 2

My guess is:

230400

First, observe that the first digit of $x$:

is in $\{0..4\}$, otherwise $2x$ has too much digits

Then, the reasoning goes this way:

Notice that for the $i$-th digit to be odd after the multiplication, we need the digit $i+1$ to be such that $2x_{i+1}>10$. Observe that you can pairs the digits in the following way: $0$ is paired with $5$ because when you multiply them by $2$ then compute the rest of the division by $10$, it gives the same thing: $0$. Consequently, if $2x$ is PD10, it contains a $0$ and a $1$, so exactly one of $\{0,5\}$ was followed by a digit greater than $5$. I will call $\{5..9\}$ the big digits from now on, and small digits the other ones.

I'm not 100% sure of my calculus but this is how I did it:

Look at the structure of $0123456789$. First digit is a small one so 5 choices. Then you decide if it is followed by a big digit or not: 2 choice. Then because it's a small digit, you have only 4 choices, then you remake a decision big/small digit, then 3 choices, etc. So the number of PD10 numbers is $$5 \times 2 \times 4 \times 2 \times 3 \times 2 \times 2 \times 2 \times 1 \times 5 \times 1\times 4 \times 1 \times 3 \times 1 \times 2 \times 1 = 230400$$

Answer 3

Other reasoning, same result:

Of all the 5 pairs {0,5}, {1,6}, {2,7}, {3,8}, {4,9}, exactly one must be before a high number.
That give 5! possibilities to choose such a 'high position' for each pair and 5! possibilities to choose 'low positions' for the other members of each pair.
1 pair contains the leading digit, which must be a low number, fixating this pair.
For the other 4 pairs one can arbitrary swap for 2 possibilities each time.
Total number 5! x 5! x 2^4 = 230400 possibilities

Answer 4

A bit messier than I'd like, but here goes.

As other answers have noted, the doubleable PD10 numbers we want are those where

for each of the five digits pairs $(0,5), (1,6), (2,7), (3,8), (4,9)$, one is followed by a low digit 0 to 4, and the other by a high digit 5 to 9 (which carries when doubled). The last digit is considered to be followed by a low digit, since it doesn't receive a carry.

Let's show that every such number can be specified by:

- the relative order in which the five low digits appear ($5!$ options)
- the relative order in which the five high digits appear ($5!$ options)
- merging instruction, which say for each of the first four high digits ordered as above, whether the digit after is low or high ($2^4$ options)

for an overall number of possibilities

$ 5! \cdot 5! \cdot 2^4$

For example,

the number 4638205179 has the low digits appear in order as 43201 and the high digits as 68579. But, there's many ways to interleave (merge) them, such as 6845732091, not all which way produce a number with the desired property. We can think of a merge as producing the number left to right, each time deciding whether the next digit is low or high and extracting it from its respective list.

The merging instructions say, for each high digit in the ordered high-digit list, whether it's followed by a high digit or a low digit. That lets us recover the number fully: start with the first low digit (a high digit would carry), whenever you're at a high digit use the merge instructions to choose if the next one is high or low, and if you're at a low digit do the opposite of the instructions for its high counterpart.
The only failure mode is that the last digit in the high list must be followed by low (or, be the last digit), since there are no further high digits to take. With that satisfied, we'll always end up taking five low digits and five high digits, exhausting both lists. So, there are $2^4$ valid merging instructions.

Answer 5

JBL on Mathematics Stack Exchange gave a beautiful solution to this problem. Here I will explain JBL's solution in slightly more detail.

Proposition. Assume $m,n$ are positive integers. Consider only the pandigital numbers in base $mn$, allowing lead zeros. The count of such numbers $x$ whose multiple $nx$ is again such a number is equal to $$\frac{(n!)^m\cdot(m!)^n}{n}.$$ In particular when $m=5$ and $n=2$, the count of numbers that the OP had asked for is equal to $230400$.

Proof.

We first draw a complete bipartite directed graph as in the following image, with $m$ vertices on top, $n$ vertices on the bottom, and two-way edges in between every top vertex and every bottom vertex.

Consider a pandigital number $x$ with $nx$ also pandigital. Every digit $d$ of $x$ can be written as $d=am+b$ with $0\le a<n$ and $0\le b<m$ by Euclidean division by $m$, such that $n\cdot d$ in base-$mn$ has $a$ in its $mn$'s digit and $nb$ in its ones digit. We represent $d$ in the above graph by the upward (gray) edge pointing from the node "carry $a$" to the node "$b$ mod $m$". As an example, with $m=3$ and $n=2$, the pandigital base-6 number $012345_6$ can be represented as the following set of edges.

For two consecutive digits $d_1d_2$ of $x$ represented by edges $a_1\to b_1$ and $a_2\to b_2$ respectively, the digit $e_1$ of $nx$ in the same place as $d_1$ must be equal to $nb_1+a_2$ by carrying. So if a digit $e_1$ in $nx$ is written as $e_1=nb_1+a_2$ through Euclidean division by $n$, its corresponding arrow (pointing from "$b_1$ mod $m$" to "carry $a_2$") must join the tip of the arrow representing $d_1$ to the tail of the arrow representing $d_2$. In the previous example, $nx$ is equal to $2\cdot 012345_6=025134_6$, and the digits of $nx$ connects the previous set of arrows as follows: (sorry to those who are colorblind!)

Some observations:

• Since both $x$ and $nx$ are pandigital, every possible directed edge from the complete bipartite graph is visited precisely once.
• By the constraint on the number of digits of $x$ and $nx$, the chain of arrows must start from the node "carry $0$" (first digit of $x$) and end in the node "carry $0$" (last digit of $nx$).
• Therefore every arrow joins precisely two other arrows, and one trip following every arrow completes a tour through every edge in the directed graph, starting and ending at the node "carry $0$".

The last observation describes an Eulerian circuit on the directed graph. Furthermore, it's not hard to be convinced of that the pandigital numbers $x$ of question are in one-to-one correspondence with each Eulerian circuit of the directed graph starting and ending at "carry $0$".

Let $\textrm{pd}$ denote the number of pandigits $x$ such that $nx$ is pandigital, and let $\textrm{ec}$ denote the number of Eulerian circuits on the graph without a specified starting point. Then since each Eulerian circuit must pass through the node "carry $0$" $m$ times, each of which times could be a starting point of a pandigit $x$ of question, we have the identity $$\textrm{pd}=m\cdot\textrm{ec}$$ Now we use the BEST theorem, which states that $$\textrm{ec}=t(K_{m,n})\cdot\prod_{v\in V}(\deg(v)-1)!$$ where $t(K_{m,n})$ is the number of spanning trees of the undirected complete bipartite graph $K_{m,n}$, and $\prod_{v\in V}(\deg(v)-1)!$ is the product over the vertices $v$ of the complete bipartite graph $K_{m,n}$ with $\deg(v)$ being the degree of $v$ in the graph $K_{m,n}$. Easily, $$\prod_{v\in V}(\deg(v)-1)!=(n-1)!^m\cdot(m-1)!^n$$ The value of $t(K_{m,n})$ can be found by using the matrix-tree theorem. Starting from the graph $K_{m,n}$, we find its Laplacian matrix $$L=\left(\vphantom{\begin{matrix}0\\0\\0\\0\\0\end{matrix}}\right.\underbrace{\begin{matrix}n&0&0\\0&n&0\\0&0&n\\-1&-1&-1\\-1&-1&-1\end{matrix}}_{m}\;\;\underbrace{\begin{matrix}-1&-1\\-1&-1\\-1&-1\\m&0\\0&m\end{matrix}}_{n}\left.\vphantom{\begin{matrix}0\\0\\0\\0\\0\end{matrix}}\right)\begin{array}{l}\left.\vphantom{\begin{matrix}0\\0\\0\end{matrix}}\right\}\scriptstyle{m}\\\left.\vphantom{\begin{matrix}0\\0\end{matrix}}\right\}\scriptstyle{n}\end{array}$$ We remove the last row and column of $L$ (to account for the null vector $(1,1,\ldots,1)$) to get the matrix $$L^*=\begin{pmatrix}n&0&0&-1\\0&n&0&-1\\0&0&n&-1\\-1&-1&-1&m\end{pmatrix}$$ Then, the matrix-tree theorem states that $$t(K_{m,n})=\det(L^*)$$ is the determinant of $L^*$.

Finding this determinant involves some fairly routine row and column manipulations which can be seen in for example this online document. In the end, we get $$t(K_{m,n})=m^{n-1}\cdot n^{m-1}$$ Plugging in all the values we attained, we deduce that \begin{align*}\textrm{pd}&=m\cdot\textrm{ec}\\&=m\cdot\left(m^{n-1}\cdot n^{m-1}\right)\cdot\left((n-1)!^m\cdot(m-1)!^n\right)\\&=\frac{(n!)^m\cdot(m!)^n}{n}\end{align*} as desired. $\square$

Answer 6

Sorry if this is repetitive. I solved the problem independently, and wrote an answer without looking at other answers (though I've checked that my answer agrees). I've tried hard to make it as simple as I could.

We have the high digits (5-9), which create carries, and the low digits, which don't. Each mod-5 pair (e.g., 2 and 7) has the same base digit when doubled (4 in this case), so we'll get a pan-digital number exactly when each pair receives exactly one carry.

Note also that a candidate answer must start with a low digit (or else its double will be too long). This also means that the total number of carries created will always be the correct value of 5.

We can freely pick a relative order of the low digits, and separately of the high digits. We place the first low digit in the left-most position, then decide whether its double is going to get a carry. That determines both whether the next digit we choose is from the low list or the high list, and whether its mod-5 partner's double is going to get a carry.

Then repeat…

• insert the known next digit from either the low group or the high group (respecting the previous carry decision)

• make a carry decision if necessary (if the new digit's partner has not yet been placed)

… until you reach the last digit from either the low group or the high group. Here there is no carry decision because we can only fill in the remaining spaces from the other group (in the chosen order). Since we have no more carry decisions, and we know that the total number of carries must come out right, all of the forced placements must have the correct carry values.

Thus an answer can be specified uniquely by:

• Ordering the low digits

• Ordering the high digits

• Deciding carry pairing for all but one of the pairs

Thus 5!*5!*2^4 answers.

Answer 7

The incomplete part of xnor's answer, as pointed out by loopy walt, is:

Does each choice of labels for all but one pair generate a legal answer?

To see that it works, note that, when we are constructing the answer:

each digit tells us how to choose the subsequent digit. As long as we are going to be asking (after the first digit) for 4 low digits and 5 high digits, things have to work. This is going to work out as long as the last digit (which isn't followed by anything) does not ask for a carry. Then the 9 digits that are followed by something have to have exactly five asking for carries.

So there are two cases:

If the last digit is high, we know by construction that it's not asking for a carry.

If the last digit is low, we know we have already used all of the high digits, which means we've already asked for five carries, so the last digit can't be asking for another one.