19
$\begingroup$

... 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.

$\endgroup$
6
  • $\begingroup$ Here's a more general question: Let $m,n$ be positive integers. Count the number of pandigital numbers in base $mn$ allowing lead zeros. Is the number of pandigital base-$mn$ numbers $x$ such that $n\cdot x$ in base-$mn$ is again pandigital equal to $(m!)^n\cdot(n!)^m/n$ ? (OP is when $m=5$ and $n=2$.) $\endgroup$
    – user78949
    Mar 27, 2023 at 11:38
  • $\begingroup$ @EdwardH I'll offer another small bounty if you can write down a clean proof for this generalisation. $\endgroup$
    – loopy walt
    Mar 27, 2023 at 12:38
  • $\begingroup$ Thanks for this generosity. I don't think I can. Perhaps someone else can find a clean proof? $\endgroup$
    – user78949
    Mar 28, 2023 at 7:33
  • $\begingroup$ @EdwardH Have you investigated this? Do you know if it holds when $m$ and $n$ have common factors? (I think my proof generalizes to general coprime $m$ and $n$.) $\endgroup$ Mar 29, 2023 at 17:39
  • 1
    $\begingroup$ @AxiomaticSystem One more comment: As far as I'm aware, there should be no reason to expect that the result to this problem should depend in any way on the number-theoretic properties of $m,n$. There is a purely combinatorial core of the problem that makes this heuristic apparent, even though the number-theoretic mask of PD-ness is making it seem unclear. $\endgroup$
    – user78949
    Mar 29, 2023 at 20:50

7 Answers 7

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I can confirm that there is scope for streamlining this argument ;-) $\endgroup$
    – loopy walt
    Mar 25, 2023 at 2:56
  • 2
    $\begingroup$ If by "4 choose 9" you meant "9 choose 4", that's 126, not 90, but you didn't use that value in your calculations anyway. $\endgroup$ Mar 25, 2023 at 3:44
5
$\begingroup$

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$$

$\endgroup$
4
  • $\begingroup$ This contains many good elements. The derivation of the final formula is, however, not convincing because it is not at all clear how it generalises from the example to an arbitrary PD10 number. $\endgroup$
    – loopy walt
    Mar 24, 2023 at 14:32
  • $\begingroup$ I think it is still true because multiplication is commutative, so it does not matter "when" you take decisions. But I agree that even I would say it is not a rigorous proof. $\endgroup$
    – Qise
    Mar 24, 2023 at 21:26
  • $\begingroup$ That argument doesn't really work. Probabilities or combinatorial frequencies can in general only be multiplied if they are independent. You'd have to organise your decision tree in such a way that the features you count are independent. I encourage you to give it a try. It is the most interesting and rewarding part of solving this puzzle. $\endgroup$
    – loopy walt
    Mar 25, 2023 at 0:36
  • $\begingroup$ I got this answer via a much longer combinatorial argument, which makes me think my approach was overkill. $\endgroup$ Mar 25, 2023 at 2:34
3
$\begingroup$

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

$\endgroup$
3
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's pretty close to what I had in mind and I'm inclined to award the bounty unless something much better comes up. Just one small nitpick: To me it's not obvious that each set of merging instructions yields a valid solution. For example, at the last low digit we cannot do the opposite of the merging instruction of its corresponding high digit if the latter happens to be followed by a high digit. Luckily, that does no harm as one can show that we must then be at the very last position and no-carry is all we need. Still, this seems to illustrate that the scheme is not entirely self evident. $\endgroup$
    – loopy walt
    Mar 26, 2023 at 23:54
2
+500
$\begingroup$

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.

complete_bipartite_graph

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.

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!)

circuit

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is my answer, but it's not quite right. I think xnor has it right, although it would be great to find a dead-simple explanation of why it works. $\endgroup$ Apr 22, 2023 at 1:46
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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