D**u
发帖数: 204 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: DuGu (火工头陀), 信区: Mathematics
标 题: 来一道题
发信站: BBS 未名空间站 (Thu Oct 22 11:18:45 2009, 美东)
Let {x_1,...,x_n} be n distinct positive real numbers;
{y_1,...,y_n} be n distinct positive real numbers;
and x_i*x_j is not equal to y_k*y_l for any i,j,k,l.
Question:
(1) you can reorder x_i to z_1,...,z_n, such that
(z_i*_z_j - y_i*y_j)(z_i-z_j)(y_i-y_j) > 0 for any distinct i and j.
(2) Is the reordering in (1) unique | a**m
发帖数: 102 | 2 Don't I understand your problem correctly? I think there is an easy counter
example when n=2...
【在 D**u 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: DuGu (火工头陀), 信区: Mathematics
: 标 题: 来一道题
: 发信站: BBS 未名空间站 (Thu Oct 22 11:18:45 2009, 美东)
: Let {x_1,...,x_n} be n distinct positive real numbers;
: {y_1,...,y_n} be n distinct positive real numbers;
: and x_i*x_j is not equal to y_k*y_l for any i,j,k,l.
: Question:
: (1) you can reorder x_i to z_1,...,z_n, such that
: (z_i*_z_j - y_i*y_j)(z_i-z_j)(y_i-y_j) > 0 for any distinct i and j.
| p*****k
发帖数: 318 | 3 attm, it's (z_i-z_j), not (z_i-y_i). i don't see a counter example for n=2. | D**u
发帖数: 204 | 4 z_1,...z_n is a reordering of x_1,...x_n.
Namely there is a permutation f, such that
z_i = x_f(i).
counter
【在 a**m 的大作中提到】
: Don't I understand your problem correctly? I think there is an easy counter
: example when n=2...
| b***e
发帖数: 1419 | 5 1. By a divide and conquer construction:
* Without losing generality, assume X is sorted ascendingly and Y is sorted
descendingly.
* Find i, such that x_{i-1} * x_n < y_i * y_{i-1} < x_i * x_n
* let z_i = x_n
* Solve the following two sub-problems:
- X = {x_1, ..., x_{i-1}}, Y = {y_1, ..., y_{i-1}}
- X = {x_{i+1}, ..., x_n}, Y = {y_{i+1}, ..., y_n}
2. I didn't prove it in details, but my impression is the division is
unique, as a result, the construction is unique. | D**u
发帖数: 204 | 6 I think in the 2nd sub_problem, you mean
"-X = {x_{i}, ..., x_{n-1}}, Y = {y_{i+1}, ..., y_n}"
It is not obvious to me that this construction will guaranty
that for any ki,
z_k*z_m < y_k*y_m.
sorted
【在 b***e 的大作中提到】
: 1. By a divide and conquer construction:
: * Without losing generality, assume X is sorted ascendingly and Y is sorted
: descendingly.
: * Find i, such that x_{i-1} * x_n < y_i * y_{i-1} < x_i * x_n
: * let z_i = x_n
: * Solve the following two sub-problems:
: - X = {x_1, ..., x_{i-1}}, Y = {y_1, ..., y_{i-1}}
: - X = {x_{i+1}, ..., x_n}, Y = {y_{i+1}, ..., y_n}
: 2. I didn't prove it in details, but my impression is the division is
: unique, as a result, the construction is unique.
| p*****k
发帖数: 318 | 7 i guess it's induction then, instead of "divide and conquer". you throw away x_n and y_i, and end up with the same problem but n-1 numbers in each set. | b***e
发帖数: 1419 | 8 Essentially, I am applying the process recursively like psacnik
suggested, for the smaller problem of size n-1 . But it occurs that after
the division by putting x_n to z_i, nothing to the left of z_i could ever
cross the ith position (to z_i's right) anymore. So doing {z_1, ...,
z_{i-1}} is equivalent to doing {z_1, ..., z_{i-1}, z_{i+1}, ..., z_n}.
【在 D**u 的大作中提到】
: I think in the 2nd sub_problem, you mean
: "-X = {x_{i}, ..., x_{n-1}}, Y = {y_{i+1}, ..., y_n}"
: It is not obvious to me that this construction will guaranty
: that for any ki,
: z_k*z_m < y_k*y_m.
:
: sorted
| D**u
发帖数: 204 | 9 If you do {x_1, ... x_{i-1}} for {z_1, ..., z_{i-1}}, then
(z_k - z_m)<0 for any k
(z_k*z_m - y_k*z_m)<0 for k
(z_k*z_m - y_k*z_m)*((z_k - z_m)*(y_k -y_m) > 0.
【在 b***e 的大作中提到】
: Essentially, I am applying the process recursively like psacnik
: suggested, for the smaller problem of size n-1 . But it occurs that after
: the division by putting x_n to z_i, nothing to the left of z_i could ever
: cross the ith position (to z_i's right) anymore. So doing {z_1, ...,
: z_{i-1}} is equivalent to doing {z_1, ..., z_{i-1}, z_{i+1}, ..., z_n}.
| b***e
发帖数: 1419 | 10 Here is what I mean:
* First I find the mapping for the largest x_n and map it to z_i. So
my new sequence Z is:
- z_k = x_k for k in [0..i-1]
- z_i = x_n
- z_k = x_{k-1} for k in [i+1..n]
* Now I can ignore x_n and y_i and reapply the algorithm on:
- Z' = {z_k where k != i}. Note that Z' is sorted in ascending
order.
- Y' = {y_k where y != i}
where the problem size is 1 shorter than the original problem.
Semantically, in this second pass, I am trying to locate the second
| | | p*****k
发帖数: 318 | 11 blaze, sorry about backpedaling, but let's consider:
x={5.1, 7.1, 8} and y={7, 6, 5},
if i understand your approach correctly, one should start by putting "8" at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had something else in mind?
i also found that the ordering is not unique. consider:
{7.1, 6.1, 5.1} with {7, 6, 5},
which is good. but another ordering:
{5.1, 7.1, 6.1} with {7, 6, 5}
also works... | D**u
发帖数: 204 | 12 right, the ordering is not unique. So only the existense part is left.
at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that
either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had
something else in mind?
【在 p*****k 的大作中提到】
: blaze, sorry about backpedaling, but let's consider:
: x={5.1, 7.1, 8} and y={7, 6, 5},
: if i understand your approach correctly, one should start by putting "8" at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had something else in mind?
: i also found that the ordering is not unique. consider:
: {7.1, 6.1, 5.1} with {7, 6, 5},
: which is good. but another ordering:
: {5.1, 7.1, 6.1} with {7, 6, 5}
: also works...
| b***e
发帖数: 1419 | 13 Sharp! Thanks.
I see where my reasoning was flawed: using your example, after
locating 8, I got:
... 5.1, 8, 7.1, ...
... 7, 6, 5, ...
I was thinking, if 8 needs to travel to 6 to beat the corresponding
position in Y, 7.1 will certainly travel more (to cross 6) simply due
to the fact that 7.1 is smaller than 8. But the problem is that on
the border case, 8 is beating 6*7, while 7.1 is beating 5*7 (because 6
is ignored in the sub-problem). So yes, in this case, 7.1 does travel
across 8 to t | D**u
发帖数: 204 | 14 答案:
Let Z = (z_1,...z_n) and
f(Z) = \sum (z_k-y_k)/(z_k+y_k).
If for some k < m that
(z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m) < 0,
then we swap z_i and z_j in Z to define
Z' = (z1,... z_m,...z_k,...z_n).
We have
f(Z') - f(Z) = (z_m-y_k)/(z_m+y_k)+(z_k-y_m)/(z_k+y_m)
- (z_k-y_k)/(z_k+y_k) - (z_m-y_m)/(z_m+y_m)
= -1/2*(z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m)/(zk+yk)(zm+ym)(zk+ym)(zm+yk)
> 0.
So f(Z') is bigger than f(Z). Notice that f(Z) can only take finite number
of different values (since only finite
【在 D**u 的大作中提到】
: right, the ordering is not unique. So only the existense part is left.
:
: at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that
: either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had
: something else in mind?
| b***e
发帖数: 1419 | 15 I see. I was going the algorithmic approach by trying to find an
effective way to compute the mapping, which is not necessary for the
proof.
【在 D**u 的大作中提到】
: 答案:
: Let Z = (z_1,...z_n) and
: f(Z) = \sum (z_k-y_k)/(z_k+y_k).
: If for some k < m that
: (z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m) < 0,
: then we swap z_i and z_j in Z to define
: Z' = (z1,... z_m,...z_k,...z_n).
: We have
: f(Z') - f(Z) = (z_m-y_k)/(z_m+y_k)+(z_k-y_m)/(z_k+y_m)
: - (z_k-y_k)/(z_k+y_k) - (z_m-y_m)/(z_m+y_m)
| D**u
发帖数: 204 | 16 The proof I gave is not a good construction proof. We only know the swapping
process will eventually stop, but don't know when it will stop.
The problem is designed when I tried to solve
\max(\sum(zk-yk)/(zk+yk)), so the problem is proved by "cheating".
【在 b***e 的大作中提到】
: I see. I was going the algorithmic approach by trying to find an
: effective way to compute the mapping, which is not necessary for the
: proof.
| b***e
发帖数: 1419 | 17 This is interesting. Do you have an instance of practical use which needs
such a mapping to be constructed? | D**u
发帖数: 204 | 18 Here is an interpretation.
Suppose you have n chess players (x1,...xn) to play n 1-1 matches with
another n players (y1,...yn). Assume if player x_i matches up with y_j,
he has x_i/(x_i+y_j) chance to win.
The question is: In order to maximize the expected number of wins of your
players, how do you want to order your players to match the other team.
This is equivalent to maximize \sum(z_i/(z_i+y_i)),
or \sum((z_i-y_i)/(z_i+y_i))
【在 b***e 的大作中提到】
: This is interesting. Do you have an instance of practical use which needs
: such a mapping to be constructed?
| b***e
发帖数: 1419 | 19 This's cool, so there is an application.
In that case, you do need an effective algorithm to computer the mapping,
right? How are you currently doing it? The naive brute-force is n!. It
is hard to estimate the algorithm directly derived from your proof,
because the converge rate is hard to understand...
your
【在 D**u 的大作中提到】
: Here is an interpretation.
: Suppose you have n chess players (x1,...xn) to play n 1-1 matches with
: another n players (y1,...yn). Assume if player x_i matches up with y_j,
: he has x_i/(x_i+y_j) chance to win.
: The question is: In order to maximize the expected number of wins of your
: players, how do you want to order your players to match the other team.
: This is equivalent to maximize \sum(z_i/(z_i+y_i)),
: or \sum((z_i-y_i)/(z_i+y_i))
| p*****k
发帖数: 318 | 20 DuGu, nice problem. my little grumble however is that the problem was inspired by the "solution" and you could have given us some hint...
btw, blaze, i am not sure from your later post whether your approach is fixable? | | | b***e
发帖数: 1419 | 21 这个就是田忌赛马的推广。
It would be very interesting to have a generic solution/effective
algorithm for it.
mapping,
It
【在 b***e 的大作中提到】
: This's cool, so there is an application.
: In that case, you do need an effective algorithm to computer the mapping,
: right? How are you currently doing it? The naive brute-force is n!. It
: is hard to estimate the algorithm directly derived from your proof,
: because the converge rate is hard to understand...
:
: your
| D**u
发帖数: 204 | 22 For the max problem, it will be good (but not always a must) to find a way
to compute the mapping. If the mapping is hard to construct, a necessary/
sufficient characterization of max(f(Z)) is also good.
Currently I haven't made more progress beyond
(z_k*z_m-y_k*y_m)(z_k-z_m)(y_k-y_m) > 0.
My "proof" only converge to a "local" maximum of f(Z), not the global
maximum. So I guess we need a new way to construct max(f(Z)).
【在 b***e 的大作中提到】
: This's cool, so there is an application.
: In that case, you do need an effective algorithm to computer the mapping,
: right? How are you currently doing it? The naive brute-force is n!. It
: is hard to estimate the algorithm directly derived from your proof,
: because the converge rate is hard to understand...
:
: your
| D**u
发帖数: 204 | 23 the expected # of wins.
The problem was to maximize "the expected number of wins of individual games
", which is different from "the expected chance of TEAM wins (like a NBA
playoff 7-game series)". Under this interpretation, you have z_k/(z_k+y_k)
chance to win
the k-th game, so your expected number of wins for the k-th game is also
z_k/(z_k+y_k). Add them up over k, it is the expected number of wins of
individual games.
+y2)]
btw, the above formula for n=2 is the same as x_i/(x_i+y_1) + x_j/(x | p*****k
发帖数: 318 | 24 ah, of course, you are right. silly me.
here is another thought regarding the new maximum problem:
consider function: f(t)=1/(1+t), set t(i)=y(i)/z(i), so one has
t(1)*...*t(n)=[y(1)*...*y(n)]/[x(1)*...*x(n)] which is fixed. i wonder whether the continuous case: to maximize the sum of f[t(i)] s.t. the product of t(i)=const. might help. (so instead of pairwise swap, i am thinking of adjusting all n elements with some constraints)
unfortunately f is neither log-concave or log-convex, so the conv | D**u
发帖数: 204 | 25 Let's think about the case of n=2.
To maximize \sum(f(t(i))
(1) if t(1)*t(2) > 1, you want t(1) and t(2) to be as apart as possible.
(2) if t(1)*t(2) < 1, you want t(1)=t(2) (or as close as possible when there
are constraints)
(3) if t(1)*t(2) = 1, then it doesn't matter because f(t)+f(1/t)=1.
This is mainly due to the convexity of function g(x)=1/(1+e^x), which is
convex when x>1, but concave when x<1. This inconsistancy in convexity makes it hard even to conjecture
what the final t(i) might be
【在 p*****k 的大作中提到】
: ah, of course, you are right. silly me.
: here is another thought regarding the new maximum problem:
: consider function: f(t)=1/(1+t), set t(i)=y(i)/z(i), so one has
: t(1)*...*t(n)=[y(1)*...*y(n)]/[x(1)*...*x(n)] which is fixed. i wonder whether the continuous case: to maximize the sum of f[t(i)] s.t. the product of t(i)=const. might help. (so instead of pairwise swap, i am thinking of adjusting all n elements with some constraints)
: unfortunately f is neither log-concave or log-convex, so the conv
| b***e
发帖数: 1419 | 26 独孤，I am wondering whether this problem, if solved, would generate
real-world value. It is very intriguing. | p*****k
发帖数: 318 | 27
one possible application is for the chess team championship (not necessarily round-robin tournament), with 4 members in each team. ignore the fact that games might end up with draw and the difference between white & black, team indeed cares about the points to gain in each round, rather than beating the other team.
(but 4 is a small number so presumably it's ok to enumerate)
back to the inequality, here are some special cases:
if t(1)*...*t(n) = 1, then sum of 1/[1+t(i)] < n-1
(with one -> inf
【在 b***e 的大作中提到】
: 独孤，I am wondering whether this problem, if solved, would generate
: real-world value. It is very intriguing.
| D**u
发帖数: 204 | 28 Here is another intepretation of the problem.
n bulbs has expected life x_i, each bulb's breaking time follows a
expernential distribution. There are another n bulbs y_i. If you turn on x_i
and y_j, then bulb x_i has x_i/(x_i+y_j) to outlast y_j.
So the question becomes: how to order x_i to max the expected number of
bulbs that outlast the opponent's.
【在 b***e 的大作中提到】
: 独孤，I am wondering whether this problem, if solved, would generate
: real-world value. It is very intriguing.
|
|
