取若干数 用加号及减号 表示1000内的整数

isee

姑且分类为数论吧

题：取一个或若干个数,用加号及减号把它们连起来,能够表示从1至1000范围内的任何一个整数，问这样的数最少需要几个？并写出这个些数来。

wwdwwd117

不可能吧，假如现在已经表示出1，那么任意改变其中任何一个运算符号，都是增加或减少一个偶数，所以无论改变多少个符号，都是得到奇数。

wwdwwd117

如果题意是一堆数，可用可不用，那应该是三进制。

kuing

回复 3# wwdwwd117

他第一句有“一个或”这三个字，一个都行表明就是可用可不用的意思。

你所说的三进制是这样吗？：设取的数堆为 `\{a_0, a_1,\ldots, a_k\}`，则能表示的数集为
\[\left\{\sum_{i=0}^k p_i a_i \Biggm| p_i\in\{-1, 0, 1\}\right\},\]
记 `S=a_0+a_1+\cdots+a_k`，上式化为
\[\left\{-S+\sum_{i=0}^k q_i a_i \Biggm| q_i\in\{0, 1, 2\}\right\},\]
于是取 `a_i` 为 `3` 的若干次幂？可是具体取多少次幂才能使数目最少呢？毕竟前面还有个 `-S`。

噢，不过也可以先取一个数为 `S` 抵消掉前面的 `-S`，然后其他的就取 `3^0`, `3^1`, `3^2` 等？

还有，怎么证明这样取就最少？

kuing

回复 4# kuing

按照取 S 及 3 的幂的方法，取的数堆可以是 `\{1093, 1, 3, 3^2, 3^3, 3^4, 3^5, 3^6\}`，其中 `1093` 就是后面几个数的和。

wwdwwd117

对，我的意思就是1,3,9...这样。根据乘法原理，n个数码，每个数码前乘以-1，0，1所以共有3^n情形，即使不考虑结果重复，最多也只能表示3^n个和数。对于这题，6个数最多729个结果，无论如何是不够的，所以至少需要7个数，而7个3进制数可以验证确实可行。现在的问题是还存不存在其它7个数来表示？

kuing

回复 5# kuing

噢，我5#错了，这个1093 根本不需要，因为 1000 太小，`(1111111)_3` 就已经大于 1000……

isee

对，我的意思就是1,3,9...这样。根据乘法原理，n个数码，每个数码前乘以-1，0，1所以共有3^n情形，即使不考 ...
wwdwwd117 发表于 2018-10-31 18:14

犀利

kuing

回复 6# wwdwwd117

取法一般是不唯一的，比如 `\{1,3,3^2,3^3,3^4,3^5,m\}` 其中 `m\in\{636,637,\ldots,3^6\}` 都是可以的。

而且还不止这些，比如 `\{1,3,3^2,3^3,3^4,3^5-1,3^6-2\}`、`\{1,3,3^2,3^3,3^4-1,3^5-2,3^6-6\}` 也可以。

这是因为 1000 是随便取的，不处于特殊位置，所以有重复也可以。

倒是可以想想：如果 1000 改为 1093，则取法是否唯一？

kuing

原题由于是从 1 开始，所以直接全部取 3 的幂肯定能覆盖我补 S 的法子，但如果不是从 1 开始的话，情况就不一样了。

比如改为表示 1500 至 2000，这时就应该先补一个中间数，再取 3 的幂，比如 `\{1750,1,3,3^2,3^3,3^4,3^5\}`，说白了其实就是平移。另外，由于 1500 和 2000 也是随便取的，所以 1750 也可以左右移一点。