免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

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

姑且分类为数论吧

题:取一个或若干个数,用加号及减号把它们连起来,能够表示从1至1000范围内的任何一个整数,问这样的数最少需要几个?并写出这个些数来。
snap.png
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

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

TOP

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

TOP

回复 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` 等?

还有,怎么证明这样取就最少?

TOP

回复 4# kuing

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

TOP

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

TOP

回复 5# kuing

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

TOP

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


犀利

TOP

回复 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,则取法是否唯一?

TOP

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

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

TOP

返回列表 回复 发帖