r****y
发帖数: 1437 | 1 Friend asked me this question and I have no clue how to do it
A set of numbers, sqrt(1), sqrt(2), ..., sqrt(50)
You divide these 50 numbers into two group, the sum of the
first group is sum1, the sum of the second group is sum2, let
dsum = abs(sum1 - sum2)
question, how you divide these 50 numbers to make dsum as small as
possible?
The gut is dsum could be very small, -> 0. But no idea how to prove
and how to find those two sets. Hehe.
| H****h
发帖数: 1037 | 2 Let a_k=sqrt(2k)-sqrt(2k-1) for k=1,...,25.
Define S_n=\sum_1^n p_ka_k, where p_k=1 or -1 are determined by
p_1=1, and p_n=-sign(S_{n-1}) for n>1.
In this way, we can make sure |S_{25}|
This method can be improved.
Let b_0=a_{25}, and b_k=a_{2k-1}-a_{2k} for k=1,...,12.
Define T_n=\sum_0^n q_kb_k, where q_k=1 or -1 are determined by
q_0=1, and q_n=-sign(T_{n-1}) for n>0.
We have |d_{12}| ~=0.0014.
In fact, by observing the values of b_0,...,b_12 directly, we find that
b_1+b_2+b_3+b
【在 r****y 的大作中提到】
: Friend asked me this question and I have no clue how to do it
: A set of numbers, sqrt(1), sqrt(2), ..., sqrt(50)
: You divide these 50 numbers into two group, the sum of the
: first group is sum1, the sum of the second group is sum2, let
: dsum = abs(sum1 - sum2)
: question, how you divide these 50 numbers to make dsum as small as
: possible?
: The gut is dsum could be very small, -> 0. But no idea how to prove
: and how to find those two sets. Hehe.
:
| r****y
发帖数: 1437 | 3 My simulation can get result as small as 1e-8, yet its impossible
to go over all the permutation. Maybe there is case even < 1e-8.
This is an interview question on wall street, and they need an
answer in 15 minutes.
【在 H****h 的大作中提到】
: Let a_k=sqrt(2k)-sqrt(2k-1) for k=1,...,25.
: Define S_n=\sum_1^n p_ka_k, where p_k=1 or -1 are determined by
: p_1=1, and p_n=-sign(S_{n-1}) for n>1.
: In this way, we can make sure |S_{25}|: This method can be improved.
: Let b_0=a_{25}, and b_k=a_{2k-1}-a_{2k} for k=1,...,12.
: Define T_n=\sum_0^n q_kb_k, where q_k=1 or -1 are determined by
: q_0=1, and q_n=-sign(T_{n-1}) for n>0.
: We have |d_{12}| ~=0.0014.
: In fact, by observing the values of b_0,...,b_12 directly, we find that
| H****h
发帖数: 1037 | 4 手里若有个Excel，可以估算得更好一些。我刚才试到8e-5.
【在 r****y 的大作中提到】
: My simulation can get result as small as 1e-8, yet its impossible
: to go over all the permutation. Maybe there is case even < 1e-8.
: This is an interview question on wall street, and they need an
: answer in 15 minutes.
| r****y
发帖数: 1437 | 5 It seems they need an analytical solution for this. Hehe.
【在 H****h 的大作中提到】
: 手里若有个Excel，可以估算得更好一些。我刚才试到8e-5.
| e********g
发帖数: 2524 | 6 Just a hint FYI:
abs(sqrt(n)-sqrt(n-1)) > abs(sqrt(n+1)-sqrt(n))
prove
【在 r****y 的大作中提到】
: It seems they need an analytical solution for this. Hehe.
| r****y
发帖数: 1437 | 7 give us the full proof, a hint is not enough.
【在 e********g 的大作中提到】
: Just a hint FYI:
: abs(sqrt(n)-sqrt(n-1)) > abs(sqrt(n+1)-sqrt(n))
:
: prove
| x********g
发帖数: 595 | 8 0.0000311064
One group can be 2,3,5,7,8,10,11,12,14,15,16,17,19,21,23,24,28,31,35,36,37,
38,42,43,44,46
several other groups can also give the same result 0.0000311064. Don't know
if there is a smaller value or not.
prove
【在 r****y 的大作中提到】
: give us the full proof, a hint is not enough.
| x********g
发帖数: 595 | 9 Assume that the values lies randomly between [Max,-Max]. The smallest one is
roughly
239.03 * 2^(-50) = 2.1236*10^(-13)
prove
【在 r****y 的大作中提到】
: give us the full proof, a hint is not enough.
|
|
