如何寻找最大的和与最小正差？

Question

使用数字9、8、7、6、5和4，每个数字只能使用一次，找出以下内容：

a) 最大可能的和

有多个解可以得到最大可能的和吗？如何确定这是最大可能的和？

b) 最小可能（正）差异

是否存在多个解？如何知道这是最小可能的差异？

这些数字必须是3位数。例如，965 + 784或879-654。

- user2856199

---

不需要电脑就能解决这个问题。尝试在http://math.stackexchange.com上发布。 - GOTO 0

有时顺序并不重要。例如：975 + 864 = 1839，同时964 + 875 = 1839也是成立的。在这种情况下，由于两个数字对称且都是三位数，唯一需要做的就是将最高优先级的数字均匀分配在这两个数字之间，这样你就完成了，至少针对最大的和部分是如此。最小正差异有点棘手，我承认。 - Shashank

这个问题似乎不适合讨论，因为它涉及到数学而非软件开发。 - AakashM

Answer 1

嗯，有意思。

区别：

如果你总是取元组 (a_1,b_1),(a_2,b_2),(a_3,b_3) 作为 a_1a_2a_3-b_1b_2b_3 的输入，那么它们的差就是：

100*(a_1-b_1)+10*(a_2-b_2)+(a_1-b_1)

因此，对于最小的差异，我猜想应该满足：-(a_2-b_2) > -(a_3-b_3) > (a_1-b_1)：

(a_2-b_2) = 4-9 = -5 = d_2
(a_3-b_3) = 5-8 = -3 = d_3
(a_1-b_1) = 7-6 =  1 = d_1

给你 745-698 = 47，这是唯一最小的，因为在所有其他情况下，d_2 要么更大，要么 d_3 更大，甚至 d_1 更大。

此外，它是唯一的解决方案，因为它是在正差之后被要求的，所以你不能交换数字。

总和：

所以对于总和，我们得到：

100*(a_1+b_1) + 10*(a_2+b_2) + (a_2+b_2)

现在是这样的：(a_1+b_1)>(a_2+b_2)>(a_3+b_3)：这里涉及到IT技术。

a_1+b_1 = 8+9 = 17
a_2+b_2 = 7+6 = 13
a_3+b_3 = 4+5 = 9

因此，它是 964+875 = 975+864 = 1839，它不是唯一的，但仍然是最大的。你可以改变 b_i 和 a_i，你有 2^3 种可能性来构建这个总和。

- mjb4

Answer 2

既然你要求算法，这里提供一个Python的暴力解决方案：

In [1]: from itertools import permutations
In [2]: def gen_pairs():
   ...:     for p in permutations('987654'):
   ...:         yield int(''.join(p[:3])), int(''.join(p[3:]))
In [3]: '%i = %i + %i' % max((a+b, a, b) for a,b in gen_pairs())
Out[3]: '1839 = 975 + 864'
In [4]: '%i = %i - %i' % min((a-b, a, b) for a,b in gen_pairs() if a>b)
Out[4]: '47 = 745 - 698'

这只是提供了最小值和最大值。要检查唯一性：

In [4]: [(a,b) for (a,b) in gen_pairs() if a+b == 1839]
Out[4]: 
[(975, 864),
 (974, 865),
 (965, 874),
 (964, 875),
 (875, 964),
 (874, 965),
 (865, 974),
 (864, 975)]

请注意，如果不计算交换的答案，这只是4种解决方案。

In [5]: [(a,b) for (a,b) in gen_pairs() if a-b == 47]
Out[6]: [(745, 698)]

因此，差异具有唯一解。

我认为通过逻辑推理来解决这个问题更加优雅，正如其他人所展示的那样。这只是证明了他们是正确的。

- Bas Swinckels

Answer 3

确保尝试所有组合并记住最佳解决方案。但当你聪明时，可以通过以下方式避免：

1. 最大和为975 + 864 = 1839

   • 或任何将更大的数字均匀分配到更高位数位置的组合
   • 就像Shashank Gupta在评论中写的那样

2. 最小正差异类似于745 - 698 = 47

   • 第二个数字（不包括第一位）必须尽可能大
   • 第一个数字（不包括第一位）必须尽可能小
   • 第一位数字只能相差1
   • 经过一些思考，您应该得出相同的结果

- Spektre