Problem 154: Exploring Pascal’s Triangle

Mathematical Foundation

Theorem 1 (Legendre’s Formula). For a prime $p$ and non-negative integer $n$:

where $v_p$ denotes the $p$-adic valuation.

Proof. Each integer $k \in \{1, \ldots, n\}$ contributes $v_p(k)$ to $v_p(n!)$. We have $v_p(k) = \sum_{m=1}^{\infty} \mathbb{1}[p^m \mid k]$. Swapping summation: $v_p(n!) = \sum_{m=1}^{\infty} |\{k \le n : p^m \mid k\}| = \sum_{m=1}^{\infty} \lfloor n/p^m \rfloor$. $\square$

Theorem 2 (Trinomial Valuation). For the trinomial coefficient $\binom{n}{i,j,k}$ with $i + j + k = n$:

This equals the total number of carries when adding $i$, $j$, $k$ in base $p$ (Kummer’s theorem generalization).

Proof. Direct from $\binom{n}{i,j,k} = n! / (i!\,j!\,k!)$ and the additive property of $v_p$. $\square$

Lemma 1 (Divisibility Condition). $10^{12} \mid \binom{n}{i,j,k}$ if and only if $v_2\!\left(\binom{n}{i,j,k}\right) \ge 12$ and $v_5\!\left(\binom{n}{i,j,k}\right) \ge 12$.

Proof. Since $10^{12} = 2^{12} \cdot 5^{12}$ and $\gcd(2^{12}, 5^{12}) = 1$, the divisibility holds iff both prime-power conditions hold. $\square$

Lemma 2 (Symmetry Reduction). The number of ordered triples $(i,j,k)$ with $i + j + k = n$ satisfying the divisibility condition can be computed by iterating over $i \le j \le k$ and applying symmetry multipliers:

• $6$ if $i < j < k$ (all distinct),
• $3$ if exactly two of $i, j, k$ are equal,
• $1$ if $i = j = k$.

Proof. The trinomial coefficient is symmetric in $(i,j,k)$. The multinomial coefficient for the number of distinct permutations of $(i,j,k)$ gives the multiplier. $\square$

Editorial

the trinomial coefficient IS divisible by 10^12. v_p(C(n; i,j,k)) = v_p(n!) - v_p(i!) - v_p(j!) - v_p(k!) We need v_2 >= 12 AND v_5 >= 12. Note: This Python solution is slow for N=200000 (O(N^2) iterations). For the actual answer, use the C++ version. This serves as a reference. We precompute p-adic valuations of factorials. We then precompute target valuations. Finally, check v_2 condition.

Pseudocode

Precompute p-adic valuations of factorials
Precompute target valuations
Check v_2 condition
Check v_5 condition
Count with symmetry
else

Complexity Analysis

• Time: $O(n)$ for precomputation of $f_2$ and $f_5$. The main loop iterates over $O(n^2 / 6)$ triples, each in $O(1)$. Total: $O(n^2)$ where $n = 200000$, giving approximately $6.67 \times 10^9$ operations. (In practice, the inner loop often terminates early.)
• Space: $O(n)$ for the precomputed valuation arrays.

Answer

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

/*
 * Problem 154: Count triples (i,j,k) with i+j+k=200000 where
 * the trinomial coefficient IS divisible by 10^12.
 *
 * v_p(binom(n; i,j,k)) = v_p(n!) - v_p(i!) - v_p(j!) - v_p(k!)
 * Need v_2 >= 12 AND v_5 >= 12.
 */

int main() {
    const int N = 200000;
    const int TARGET = 12;

    // Precompute v_p(m!) for p = 2 and p = 5
    vector<int> v2(N + 1), v5(N + 1);
    v2[0] = v5[0] = 0;
    for (int m = 1; m <= N; m++) {
        int x = m, c2 = 0, c5 = 0;
        while (x % 2 == 0) { c2++; x /= 2; }
        x = m;
        while (x % 5 == 0) { c5++; x /= 5; }
        v2[m] = v2[m - 1] + c2;
        v5[m] = v5[m - 1] + c5;
    }

    int V2N = v2[N];
    int V5N = v5[N];

    long long count = 0;

    // Iterate i <= j <= k, i+j+k = N
    // So i <= N/3, j >= i, k = N-i-j >= j => j <= (N-i)/2
    for (int i = 0; i <= N / 3; i++) {
        // For v_p: need V_pN - v_p[i] - v_p[j] - v_p[N-i-j] < TARGET
        int r2i = V2N - v2[i]; // v2 of binom without j,k parts
        int r5i = V5N - v5[i];

        for (int j = i; j <= (N - i) / 2; j++) {
            int k = N - i - j;
            int val2 = r2i - v2[j] - v2[k];
            int val5 = r5i - v5[j] - v5[k];

            if (val2 >= TARGET && val5 >= TARGET) {
                // Count with multiplicity
                if (i == j && j == k) count += 1;
                else if (i == j || j == k) count += 3;
                else count += 6;
            }
        }
    }

    printf("%lld\n", count);
    return 0;
}

"""
Problem 154: Count triples (i,j,k) with i+j+k=200000 where
the trinomial coefficient IS divisible by 10^12.

v_p(C(n; i,j,k)) = v_p(n!) - v_p(i!) - v_p(j!) - v_p(k!)
We need v_2 >= 12 AND v_5 >= 12.

Note: This Python solution is slow for N=200000 (O(N^2) iterations).
For the actual answer, use the C++ version. This serves as a reference.
"""

def solve():
    N = 200000
    TARGET = 12

    # Precompute v_p(m!) for p=2 and p=5
    v2 = [0] * (N + 1)
    v5 = [0] * (N + 1)
    for m in range(1, N + 1):
        x = m
        c2 = 0
        while x % 2 == 0:
            c2 += 1
            x //= 2
        x = m
        c5 = 0
        while x % 5 == 0:
            c5 += 1
            x //= 5
        v2[m] = v2[m - 1] + c2
        v5[m] = v5[m - 1] + c5

    V2N = v2[N]
    V5N = v5[N]

    count = 0

    for i in range(N // 3 + 1):
        r2i = V2N - v2[i]
        r5i = V5N - v5[i]

        for j in range(i, (N - i) // 2 + 1):
            k = N - i - j
            val2 = r2i - v2[j] - v2[k]
            val5 = r5i - v5[j] - v5[k]

            if val2 >= TARGET and val5 >= TARGET:
                if i == j == k:
                    count += 1
                elif i == j or j == k:
                    count += 3
                else:
                    count += 6

    print(count)

solve()