p*****r
发帖数: 525 | 1 有10个数， 每个数是两个digits.
也就是说 10-99 都可以。
证明一定可以找到一种方法，把10 个数分成两组。
似它们的的SUM 相同。
比如， N1 N2， N3~ N10。
N1+N2 = SUM(N3-N10)
怎么证明？
多谢了。 |
C***m
发帖数: 120 | 2 我可能理解错题意了。
比如 九个10 一个11，怎么分
【在 p*****r 的大作中提到】
: 有10个数， 每个数是两个digits.
: 也就是说 10-99 都可以。
: 证明一定可以找到一种方法，把10 个数分成两组。
: 似它们的的SUM 相同。
: 比如， N1 N2， N3~ N10。
: N1+N2 = SUM(N3-N10)
: 怎么证明？
: 多谢了。
|
s***o
发帖数: 60 | 3 subset sum problem 主要用dynamic programming解吧 naive的方法要O(N*2^N)
exponential time肯定要
【在 p*****r 的大作中提到】
: 有10个数， 每个数是两个digits.
: 也就是说 10-99 都可以。
: 证明一定可以找到一种方法，把10 个数分成两组。
: 似它们的的SUM 相同。
: 比如， N1 N2， N3~ N10。
: N1+N2 = SUM(N3-N10)
: 怎么证明？
: 多谢了。
|
f**********i
发帖数: 45 | 4 不对吧？要是所有数的和是个奇数怎么办……
【在 p*****r 的大作中提到】
: 有10个数， 每个数是两个digits.
: 也就是说 10-99 都可以。
: 证明一定可以找到一种方法，把10 个数分成两组。
: 似它们的的SUM 相同。
: 比如， N1 N2， N3~ N10。
: N1+N2 = SUM(N3-N10)
: 怎么证明？
: 多谢了。
|
s**********6
发帖数: 873 | 5 RE. 题目记错了吧？再回忆下？
【在 f**********i 的大作中提到】
: 不对吧？要是所有数的和是个奇数怎么办……
|
p*****r
发帖数: 525 | 6 这十个数是必须不同的十个数。就是说从10~ 99 取不同的十个数。
嗯， 对啊， 我想想
10 个不同的两位数，加起来可能会是奇数， 那就没法分了。
我再问问出题目的人。
多谢！ |
R**T
发帖数: 784 | 7 9个偶数1个奇数，这和不就是奇数么
【在 p*****r 的大作中提到】
: 这十个数是必须不同的十个数。就是说从10~ 99 取不同的十个数。
: 嗯， 对啊， 我想想
: 10 个不同的两位数，加起来可能会是奇数， 那就没法分了。
: 我再问问出题目的人。
: 多谢！
|
k*****a
发帖数: 5 | 8 Let N be an arbitrary set of ten distinct two-digit numbers.
Let X be the set of all subsets of N.
For any S \in X, let sigma(S) be the sum of numbers in S.
|X| = 2^10
| { sigma(S) : S \in X } | <= (90+99)*10/2 < 2^10
Therefore, there must be two distinct S1, S2 \in X such that sigma(S1) =
sigma(S2). Subtract away from S1 and S2 their intersection, respectively:
this gives us the required two subsets. |
p*****r
发帖数: 525 | 9 Thanks, admire 啊！
krishna 真是牛人。 |
A**u
发帖数: 2458 | |
