首先,我们可以将数组 b 排序,因为这不会改变答案。让我们尝试从 a 到 a1 中选择 a 的值。有多少种方式可以选择 ai 的值呢?新的 ai 必须满足 ai>bi。但是,一些候选值已经被某些 j>i 的值选择为 aj。然而,由于 aj>bj≥bi,我们知道已经有 (n-i) 个候选值被所有 j>i 的值选择。证明
时间: 2024-03-31 11:35:11 浏览: 44
假设我们已经在 a 中选择了 i 个值,且这些值已经按照降序排列。现在我们需要选择第 i+1 个值,满足 ai+1>bi+1,并且不能选择已经被选过的值。
考虑从 a(i+1) 到 a(n) 中选择 ai+1 的值。我们可以发现,已经有 n-i 个候选值被所有 j>i 的值选择了。因为这些候选值都比 bi+1 大,所以它们也满足 ai+1>bi+1 的条件。因此,我们有 n-i 个合法的候选值可供选择。
综上所述,对于每个 i,我们都有 n-i 个合法的候选值可供选择。因此,在选择 a 的值的过程中,总共有 ∑(n-i) = n(n+1)/2 - ∑i 个合法的候选值可供选择。因此,不难得出,选择 a 的值的方案数为:
n(n+1)/2 - ∑i
其中,∑i 表示从 1 到 n 的所有正整数之和,即:
∑i = 1+2+...+n = n(n+1)/2
将其代入上式,得到:
n(n+1)/2 - n(n+1)/2 = 0
因此,选择 a 的值的方案数为 0。这意味着,无论如何选择 a 的值,都不能使得 ai>bi 的数量大于 0。因此,根据反证法,原命题得证。