免费智力题困难

Find The Units Digit

考察公司Citadel

Write every whole number from $0$ to $10^{100}-1$ as a 100-digit string, padding with leading zeros. For each string, multiply its nonzero digits together (the all-zero string counts as $1$ ). Add up all $10^{100}$ of these products. What is the last digit of the total?

For example, the ten 1-digit strings $0$ to $9$ give $1+1+2+3+\dots+9 = 46$ .

解析

先自己试一试，卡住了再打开提示。

提示 1

Ignoring a zero in a product is the same as multiplying by $1$ . Give each digit a weight: $w(0)=1$ , and $w(d)=d$ for $d=1,\dots,9$ .

提示 2

Each string's product is the product of its digits' weights. Can you write the sum over all strings as one product of 100 identical brackets?

查看解析

Method 1: one expansion

Step 1: Turn "ignore the zeros" into a weight. Multiplying by $1$ changes nothing, so ignoring a zero is the same as counting it as $1$ . Define

w(0)=1,\qquad w(d)=d \text{ for } d=1,\dots,9.

The product of the nonzero digits of a string $d_1d_2\dots d_{100}$ is then $w(d_1)\,w(d_2)\cdots w(d_{100})$ . This also handles the all-zero string, whose product is $1$ .

Step 2: The whole sum is one expansion. Look at

\big(w(0)+w(1)+\dots+w(9)\big)^{100}.

Expanding it means picking one digit from each of the 100 brackets and multiplying their weights. Every 100-digit string gets picked exactly once, and its term is exactly its product of nonzero digits. So this expansion is the sum we want.

Step 3: Evaluate. Each bracket is $1 + (1+2+\dots+9) = 1 + 45 = 46$ , so

\text{Sum} = 46^{100}.

Method 2: build the strings one digit at a time

Let $S(n)$ be the sum of the products over all $n$ -digit strings (leading zeros allowed, the all-zero string counting as $1$ ). We want $S(100)$ .

Start: $n = 1$ . The strings $0, 1, \dots, 9$ have products $1, 1, 2, \dots, 9$ , so

S(1) = 1 + (1 + 2 + \dots + 9) = 1 + 45 = 46.

From 1 digit to 2 digits, worked out. Every 2-digit string is a 1-digit string with one more digit stuck on the end. Group the $100$ strings by that last digit:

Last digit $0$ : $00, 10, 20, \dots, 90$ . The extra $0$ changes no product, so these give $1 + 1 + 2 + \dots + 9 = S(1) = 46$ .
Last digit $3$ (for example): $03, 13, 23, \dots, 93$ . The extra $3$ multiplies every product by $3$ : $3 \cdot 1,\ 3 \cdot 1,\ 3 \cdot 2,\ \dots,\ 3 \cdot 9$ . These give $3 \cdot S(1) = 138$ .
Last digit $k$ , for each $k = 1, \dots, 9$ : the same argument gives $k \cdot S(1)$ .

Adding the ten groups:

S(2) = S(1) + (1 + 2 + \dots + 9)\,S(1) = (1 + 45)\,S(1) = 46 \cdot 46 = 2116.

The general step. Nothing above used the fact that the front part had just one digit. Adding a last digit to every $n$ -digit string gives

S(n+1) = \underbrace{S(n)}_{\text{last digit } 0} + \underbrace{1 \cdot S(n) + 2 \cdot S(n) + \dots + 9 \cdot S(n)}_{\text{last digit } 1, \dots, 9} = 46\,S(n).

Unroll it.

S(1) = 46,\quad S(2) = 46^2,\quad S(3) = 46^3,\quad \dots,\quad S(100) = 46^{100}.

Both methods give the same total: Method 1 multiplies all 100 factors of $46$ at once, Method 2 adds them one digit at a time.

Last digit

$6 \times 6 = 36$ ends in $6$ , so every power of $46$ ends in $6$ : $46, 2116, 97336, \dots$

Answer: $6$ .

题目

解析

Method 1: one expansion

Method 2: build the strings one digit at a time

Last digit