Problem 491: Double Pandigital Number Divisible by 11

Notation

Throughout, a double pandigital number is a 20-digit string $d_1 d_2 \cdots d_{20}$ (with $d_1 \neq 0$) in which every digit $0, 1, \ldots, 9$ appears exactly twice. Positions $1, 3, 5, \ldots, 19$ are called odd positions and positions $2, 4, 6, \ldots, 20$ are called even positions. We write $O = \sum_{i \text{ odd}} d_i$ and $E = \sum_{i \text{ even}} d_i$.

Mathematical Foundation

Theorem 1 (Divisibility rule for 11). An integer $N$ with decimal representation $d_1 d_2 \cdots d_n$ satisfies $11 \mid N$ if and only if $\sum_{i=1}^{n}(-1)^{i+1} d_i \equiv 0 \pmod{11}$.

Proof. Since $10 \equiv -1 \pmod{11}$, we have $10^k \equiv (-1)^k \pmod{11}$ for all $k \geq 0$. Therefore

For $n = 20$ (even), $(-1)^{n-i} = (-1)^{-i} = (-1)^i$, so $N \equiv \sum_{i=1}^{20} (-1)^i d_i = E - O \pmod{11}$. Hence $11 \mid N$ if and only if $O \equiv E \pmod{11}$. $\square$

Lemma 1 (Reduction to a single congruence). The divisibility condition $O \equiv E \pmod{11}$ is equivalent to $O \equiv 1 \pmod{11}$.

Proof. Since every digit $0, 1, \ldots, 9$ appears exactly twice, the total digit sum is $2(0 + 1 + \cdots + 9) = 90$. Thus $O + E = 90$, giving $E = 90 - O$. The condition $O \equiv E \pmod{11}$ becomes $O \equiv 90 - O \pmod{11}$, i.e., $2O \equiv 90 \pmod{11}$. Now $90 = 8 \cdot 11 + 2$, so $90 \equiv 2 \pmod{11}$. Hence $2O \equiv 2 \pmod{11}$. Since $\gcd(2, 11) = 1$, we may divide both sides by $2$ (equivalently, multiply by $2^{-1} \equiv 6 \pmod{11}$) to obtain $O \equiv 1 \pmod{11}$. $\square$

Definition (Assignment vector). An assignment vector is a tuple $\mathbf{c} = (c_0, c_1, \ldots, c_9) \in \{0, 1, 2\}^{10}$ satisfying $\sum_{d=0}^{9} c_d = 10$, where $c_d$ denotes the number of copies of digit $d$ placed at odd positions. The complementary count at even positions is $2 - c_d$.

Lemma 2 (Feasible values of $O$). Under any assignment vector $\mathbf{c}$, the odd-position sum is $O(\mathbf{c}) = \sum_{d=0}^{9} d \cdot c_d$. Since $0 \leq c_d \leq 2$ and $\sum c_d = 10$, we have $0 \leq O \leq 90$. The values satisfying $O \equiv 1 \pmod{11}$ in $[0, 90]$ are exactly

Proof. The minimum of $O$ is $0$ (attained when $c_d = 2$ for $d = 0, 1, 2, 3, 4$ and $c_d = 0$ otherwise) and the maximum is $90$ (attained when $c_d = 2$ for $d = 5, 6, 7, 8, 9$). The integers congruent to $1 \pmod{11}$ in $\{0, 1, \ldots, 90\}$ are $1, 12, 23, 34, 45, 56, 67, 78, 89$. The value $O = 0$ does not satisfy the congruence, nor does $O = 90$. $\square$

Theorem 2 (Counting formula). For a valid assignment vector $\mathbf{c}$ (i.e., $\sum c_d = 10$ and $\sum d \cdot c_d \equiv 1 \pmod{11}$), the number of double pandigital numbers with no leading zero is

Proof. Given $\mathbf{c}$, the 10 odd-position slots receive $c_d$ copies of digit $d$ for each $d \in \{0, \ldots, 9\}$. The number of distinct permutations of these 10 items is the multinomial coefficient $\binom{10}{c_0, c_1, \ldots, c_9} = 10!/\prod c_d!$. Similarly, the 10 even-position slots receive $2 - c_d$ copies of each digit $d$, yielding $10!/\prod (2 - c_d)!$ permutations. Since the choices for odd and even positions are independent, the total number of 20-digit strings (including those with a leading zero) is the product of these two multinomials.

To exclude leading zeros: position 1 is an odd-position slot. A leading zero occurs precisely when digit $0$ occupies position 1. If $c_0 \geq 1$, we can fix one zero at position 1 and permute the remaining $9$ odd-position digits (consisting of $c_0 - 1$ zeros and $c_d$ copies of each $d \geq 1$) in $9!/((c_0-1)! \prod_{d \geq 1} c_d!)$ ways. Multiplying by the even-position count and subtracting yields the formula. If $c_0 = 0$, no odd-position slot contains a zero, so the leading digit is never zero and no subtraction is needed. $\square$

Corollary. The answer is $\displaystyle \sum_{\mathbf{c} \text{ valid}} N(\mathbf{c})$.

Editorial

We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

answer = 0
For each each (c_0, c_1, ..., c_9) in {0,1,2}^10:
    If sum(c_d) != 10 then continue
    O = sum(d * c_d for d = 0..9)
    If O mod 11 != 1 then continue
    odd_perms = 10! / prod(c_d!)
    even_perms = 10! / prod((2 - c_d)!)
    total = odd_perms * even_perms
    If c_0 >= 1 then
        leading_zero = 9! / ((c_0 - 1)! * prod(c_d! for d=1..9)) * even_perms
        total -= leading_zero
    answer += total
Return answer

Complexity Analysis

• Time: $O(3^{10} \cdot 10) = O(590490)$. There are $3^{10} = 59049$ candidate vectors, each processed in $O(10)$ arithmetic operations.
• Space: $O(1)$ auxiliary (beyond the precomputed table of $10! , 9!, \ldots, 0!$).

Answer

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Each digit 0-9 appears exactly twice in a double pandigital number (20 digits).
    // We choose c[d] in {0,1,2} copies of digit d to place at odd positions (10 positions).
    // Sum of c[d] must be 10.
    // Divisibility by 11: O - E ≡ 0 (mod 11) where O = sum of odd-position digits.
    // O + E = 90, so O ≡ 1 (mod 11).

    long long fact[11];
    fact[0] = 1;
    for(int i = 1; i <= 10; i++) fact[i] = fact[i-1] * i;

    // We enumerate choices c[0..9] in {0,1,2}, sum = 10
    // For each valid choice, count = (10! / prod c[d]!) * (10! / prod (2-c[d])!)
    // Then subtract leading-zero cases.

    long long total = 0;
    long long leading_zero = 0;

    // Use recursion or iterative enumeration
    // c[d] in {0,1,2}, 10 digits -> 3^10 = 59049 combos

    int c[10];
    // iterate over all 3^10 combinations
    for(int mask = 0; mask < 59049; mask++){
        int tmp = mask;
        int sum_c = 0;
        int sum_val = 0;
        bool valid = true;
        for(int d = 0; d < 10; d++){
            c[d] = tmp % 3;
            tmp /= 3;
            sum_c += c[d];
            sum_val += d * c[d];
        }
        if(sum_c != 10) continue;
        if(sum_val % 11 != 1) continue;

        // Count permutations for odd positions: 10! / prod(c[d]!)
        long long odd_perms = fact[10];
        for(int d = 0; d < 10; d++) odd_perms /= fact[c[d]];

        // Count permutations for even positions: 10! / prod((2-c[d])!)
        long long even_perms = fact[10];
        for(int d = 0; d < 10; d++) even_perms /= fact[2 - c[d]];

        long long ways = odd_perms * even_perms;
        total += ways;

        // Leading zero: digit 0 is at position 1 (odd position).
        // If c[0] >= 1, fix one 0 at position 1, remaining 9 odd positions
        // have the other digits. The count of such arrangements:
        // (c[0]/10) * odd_perms * even_perms ... but more precisely:
        // Among odd_perms arrangements, fraction c[0]/10 have 0 in the first spot.
        if(c[0] >= 1){
            // Number of odd arrangements with 0 in first position:
            // Fix 0 there. Remaining 9 positions: (9! / ((c[0]-1)! * prod_{d>0} c[d]!))
            long long odd_lz = fact[9];
            odd_lz /= fact[c[0] - 1];
            for(int d = 1; d < 10; d++) odd_lz /= fact[c[d]];
            leading_zero += odd_lz * even_perms;
        }
    }

    cout << total - leading_zero << endl;
    return 0;
}

from math import factorial
from itertools import product

def solve():
    """
    Count double pandigital numbers divisible by 11.

    A 20-digit number using each of 0-9 exactly twice is divisible by 11
    iff the odd-position digit sum O satisfies O = 1 (mod 11).
    We enumerate assignment vectors c in {0,1,2}^10 with sum 10,
    filter on sum(d*c_d) = 1 (mod 11), and count permutations
    minus leading-zero arrangements.
    """
    fact = [factorial(i) for i in range(11)]
    answer = 0

    for combo in product(range(3), repeat=10):
        if sum(combo) != 10:
            continue
        if sum(d * combo[d] for d in range(10)) % 11 != 1:
            continue

        odd_perms = fact[10]
        even_perms = fact[10]
        for d in range(10):
            odd_perms //= fact[combo[d]]
            even_perms //= fact[2 - combo[d]]

        ways = odd_perms * even_perms

        if combo[0] >= 1:
            lz = fact[9] // fact[combo[0] - 1]
            for d in range(1, 10):
                lz //= fact[combo[d]]
            ways -= lz * even_perms

        answer += ways

    print(answer)

solve()