返回题库

安全代码

Safe Codes

专题
Discrete Math / 离散数学
难度
L3

题目详情

电子保险箱有一个三位数代码。关于保险箱密码,你会收到两个提示:

  • 所有数字都不为零
  • 各位数字之和不超过十

有多少可能的三位数条目满足这两个要求?

An electronic safe has a three digit code. You are given two hints regarding the code to the safe:

  • None of the digits are zero
  • The sum of the digits does not exceed ten

How many possible three digit entries satisfy these two requirements?

解析

让我们以第一位数字为条件来确定代码的数量。

如果我们的第一个数字是 99,则有 00 可能的代码(因为总和将超过非零数字的 1010

如果我们的第一位数字是88,那么剩下的数字之和只能是22。完成此操作的唯一方法是剩余数字为 11

如果第一位数字是 77,则剩余的和可以是 22332233 的求和方式有多种(1+2 或 2+1),并且我们已经统计了与 22 求和的方式,如果我们的第一个数字是 77,则总共有 33 不同的组合

如果第一个数字是 66,我们只需要找到与 44 相加的有多少种方法,并将其与我们之前看到的 2233 的组合相加。 33 有多种方法可以与 44 求和。现在,我们应该注意到一个模式。

如果我们的第一个数字是55,就会有1+2+3+41+2+3+4不同的组合。本质上,我们只是对前一个 88 三角数求和。 Total=1+3+6+10+15+21+28+36=120\begin{equation*} Total = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = \boxed{120} \end{equation*}

codes = []
for i in range(1, 10):
    for j in range(1, 10):
        for k in range(1, 10):
            codes.append([i, j, k])

valid_codes = [code for code in codes if sum(code) <= 10]
print(len(valid_codes))

Original Explanation

Let's condition the number of codes on the first digit.

If our first digit is 99, there are 00 possible codes (as sum will exceed 1010 with non-zero digits)

If our first digit is 88, the remaining digits can only sum to 22. The only way to accomplish this is if the remaining digits are 11.

If the first digit is 77, the remaining sum can be 22 or 33. There are 22 ways to sum to 33 (1+2 or 2+1) and we have already counted the ways to sum to 22, resulting in a total of 33 different combinations if our first digit is 77

If the first digit is 66 we only need to find how many ways to sum to 44 and add that with the combinations for 22 and 33 we've seen previously. There are 33 ways to sum to 44. By now, we should notice a pattern.

If our first digit is 55, there will be 1+2+3+41+2+3+4 different combinations. Essentially, we are just summing the first 88 triangular numbers.

Total=1+3+6+10+15+21+28+36=120\begin{equation*} Total = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = \boxed{120} \end{equation*}
codes = []
for i in range(1, 10):
    for j in range(1, 10):
        for k in range(1, 10):
            codes.append([i, j, k])

valid_codes = [code for code in codes if sum(code) <= 10]
print(len(valid_codes))