Mixing
convex combination of complex numbers [closed]
$begingroup$
let $0<p_k<1$ $k=1,...,n$ such that $sum_k p_k=1$ I'm trying to find $varphi_1,varphi_2,...,varphi_n$ so that
$$sum_k p_ke^{ivarphi_k}=0$$
complex-analysis complex-numbers convex-geometry convex-hulls
edited Jan 14 at 14:44
Paul Frost
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
$endgroup$
closed as off-topic by José Carlos Santos, RRL, Arnaud D., Alexander Gruber♦ Jan 17 at 2:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, RRL, Arnaud D., Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
let $0<p_k<1$ $k=1,...,n$ such that $sum_k p_k=1$ I'm trying to find $varphi_1,varphi_2,...,varphi_n$ so that
$$sum_k p_ke^{ivarphi_k}=0$$
complex-analysis complex-numbers convex-geometry convex-hulls
edited Jan 14 at 14:44
Paul Frost
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
$endgroup$
closed as off-topic by José Carlos Santos, RRL, Arnaud D., Alexander Gruber♦ Jan 17 at 2:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, RRL, Arnaud D., Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
let $0<p_k<1$ $k=1,...,n$ such that $sum_k p_k=1$ I'm trying to find $varphi_1,varphi_2,...,varphi_n$ so that
$$sum_k p_ke^{ivarphi_k}=0$$
complex-analysis complex-numbers convex-geometry convex-hulls
edited Jan 14 at 14:44
Paul Frost
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
$endgroup$
let $0<p_k<1$ $k=1,...,n$ such that $sum_k p_k=1$ I'm trying to find $varphi_1,varphi_2,...,varphi_n$ so that
$$sum_k p_ke^{ivarphi_k}=0$$
complex-analysis complex-numbers convex-geometry convex-hulls
complex-analysis complex-numbers convex-geometry convex-hulls
edited Jan 14 at 14:44
Paul Frost
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
edited Jan 14 at 14:44
Paul Frost
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
edited Jan 14 at 14:44
Paul Frost
10.9k3934
edited Jan 14 at 14:44
Paul Frost
10.9k3934
edited Jan 14 at 14:44
Paul Frost
10.9k3934
10.9k3934
asked Jan 14 at 14:11
Cfu Cfu
34
asked Jan 14 at 14:11
Cfu Cfu
34
asked Jan 14 at 14:11
Cfu Cfu
34
34
closed as off-topic by José Carlos Santos, RRL, Arnaud D., Alexander Gruber♦ Jan 17 at 2:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, RRL, Arnaud D., Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by José Carlos Santos, RRL, Arnaud D., Alexander Gruber♦ Jan 17 at 2:54
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – José Carlos Santos, RRL, Arnaud D., Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I provide here a complete answer, taking into account the cases where it is not possible (as explained by @Fred and @Yanko), but concentrating on the cases where the problem has a solution (which is almost certain for $n>5$ say), and how we can obtain appropriate directions.
One can find a very sophisticated solution in https://mathoverflow.net/q/96669 under a certain condition which is nothing else that a generalized form of triangle identity : a solution exists iff we have :
$$text{Condition (C) : none of the lengths exceeds the sum of the others}.$$
In fact, this question becomes clear when expressed without the complex number apparatus. It can be made equivalent to this one : being given segments with lengths $p_1, p_2,cdots p_n$, find vectors $V_1,V_2,cdots V_n$ with $|V_k|=p_k$ such that the broken line obtained by concatenating $V_1, V_1+V_2, V_1+V_2+V_3, cdots$ can be closed (i.e., generates a polygon). See Fig. 1 and 2 below.
Fig. 1 : (corresponding to Method B). Initial points $A_1,A_2,A_3$ as vertices of the triangle in blue. In the final solution (in red), the successive points (read anticlockwise) are $ A_1,A_2,A_3,cdots A_n$ (where $A_n$ is the former $A_3$).
Fig. 2 : A solution to the problem : the sum of all these vectors (obtained by following counterclockwise the contour given in Fig. 1, with given lengths $p_k$s) is $0$. The polar angles of these vectors are the looked for values $varphi_k$.
I now give 2 methods for obtaining solutions :
Method A) **An analog solution based on a principle of statics ("closing the polygon of forces") ** : let us consider the longest segment as being $p_1$ and placed horizontaly. Then hang to the endpoints of this longest segment all segments with length $p_k (k>1)$, attached one to the other (in any order) like a (closed) pasta necklace. Out of the equilibrium position taken by the necklace, one deduces vectors $V_k (k>1)$.
[I am conscious that this still has to be established mathematically, but it isn't important because the algorithmic method 2) presented below is mathematicaly rigorous].
Remark : In fact, vector $V_1$ hasn't to be necessarily
horizontal : to each position of $V_1$, horizontal or not, corresponds a different equilibria, thus a different set of vectors $V_k$. This means that if condition (C) is fulfilled (and $n>3$ see below), there is an infinite set of solutions !
Method B) An algorithmic recursive solution [Matlab program giving Fig 1 in Appendix]
Let us assume that, if we have $n$ segments, the initial largest segment with length $p_1$ is placed horizontally with endpoints $A_1=(0,0)$ and $A_n=(p_1,0)$ (this will be preserved at the end of each iteration step). Let us more generally denote by $A_k$ the position of the connecting point between line segments with lengths $p_k$ and $p_{k+1}$.
[initialization] The case for $n=3$ segments is treated apart (see below).
Let us assume that we can construct a closed necklace till $n$ segments inclusively. Let us prove that (out of it) we can build a closed necklace with $n+1$ segments.
Let us rotate horizontal line segment with length $p_1$ around $0$ (like lifting a drawbridge) with an angle $$theta_{n+1}:=2 mathrm{asin}frac{p_{n+1}}{2p_1}.tag{1}$$
In this way, we are able to place the $(n+1)$st line segment in-between (i.e., connecting) line segment number $n$ and line segment number $1$.
(in an algorithmic perspective) Apply a backwards $-theta_{n+1}$ rotation around the origin to place back the "drawbridge" in its initial horizontal position in order to be ready for the next iteration step. Apply this rotation to all other articulation points $A_k$.
Let us work apart the case $n=3$. We take for $p_1$ the longest length and $V_1=binom{p_1}{0}$. Then it suffices to consider circle $C$ (resp $C'$) with radius $p_2$ (resp. $p_3$) centered in $A_1=(0,0)$ (resp. $A_3=(p_1,0)$ ; because condition (C) is fulfilled, $p_2+p_3> p_1$, $C$ and $C'$ intersect in a certain point $A_2$. Then, if we define $V_2=-A_1A_2$ and $V_3=-A_2A_3$ we have $V_1+V_2+V_3=0$.
Remarks :
1) Relationship (1) gives the angle between the equal sides of isoceles triangle $A_nA_1A_{n+1}$.
2) It is not at all compulsory to take the longest segment as the reference initial segment. Any other segment is suitable.
Appendix : Matlab program :
clear all;close all;hold on;axis equal off;
n=7;LW='linewidth';
p=[25,20,19,14,13,6,3]; % p=sort(rand(1,n),'descend');
s=sum(p);
p=p/s;% optional
if p(1) < s/2 && p(1) < (p(2)+p(3))
% 6 following lines : coordinates of vertices P_1, P_2, P_3
x(1)=0;y(1)=0;
x(3)=p(1),y(3)=0;
x(2)=(p(1)^2+p(2)^2-p(3)^2)/(2*p(1));
y(2)=-sqrt(p(2)^2-x(2)^2);
z=zeros(1:n,1);z(1:3)=x+i*y;
plot(z([1,2,3,1]),'b',LW,2);
for k=4:n
ra=2*asin(p(k)/(2*p(1)));% rotation angle
R=exp(i*ra);
z(k)=R*p(1);
z(1:k)=conj(R)*z(1:k); % clockwise rotation
plot(z(1:k),'k');
end;
plot(z(1:n),'r',LW,2);
end;
Remark : one can notice supplementary condition $p_1 < p_2+p_3$. What is it about ? We need a
Lemma : Being given a set $p_1, p_2, cdots p_n$ of positive real numbers, there is at least one triple $(i,j,k)$ in the sequence of values $p_k$ such that :
$$p_i leq p_j+p_ktag{2}$$
Proof : By contradiction. Let $s:=sum_k p_k$. If for any triple $(i,j,k), (i neq j neq k neq i)$, we had $p_i > p_j+p_k$, adding together these $(n-2)binom{n}{2}$ inequalities, it yields $s>2s$, which is contradictory.
Consequence : if, with the present ordering, (2) isn't fulfilled for $i=1, j=2$ and $k=3$, we just have to modify this ordering. This will not affect the algorithm.
Related : https://www.geeksforgeeks.org/find-number-of-triangles-possible/
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
$endgroup$
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
add a comment |
$begingroup$
This is false. I'll prove that we can choose $p_1,...,p_n$ such that there is no $phi_1,...,phi_n$ with the property in your question: First observe that,
$sum_k p_k e^{iphi_k} = p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}$
By the reverse triangle inequality $|p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}| > |p_1|-|sum_{knot = 1} p_k e^{iphi_k}|$ and by the triangle inequality
$$|sum_k p_k e^{iphi_k}|geq |p_1|-(|p_2|+...+|p_k|)$$
Hence if you choose $p_1$ sufficiently close to $1$ and $p_2,...,p_k$ small such that $sum_k p_k =1$ you will have that the right hand side of the last inequality is positive (in fact arbitrary close to $1$). Therefore can't be zero.
answered Jan 14 at 14:19
YankoYanko
6,8931629
$endgroup$
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
add a comment |
$begingroup$
Supose that we have $sum_{k=1}^n p_ke^{ivarphi_k}=0$. Then
$p_1=|p_1e^{ivarphi_1}|= |sum_{k=2}^n p_ke^{ivarphi_k}| le p_2+....+p_n =1-p_1$.
Thus $p_1 le 1/2$. In the same way we see that $p_k le 1/2$ for $k=2,...,n$.
Conclusion: if $p_j > 1/2 $ for some $j$, then $sum_{k=1}^n p_ke^{ivarphi_k}=0$ is not possible !
answered Jan 14 at 14:24
FredFred
46.8k1848
$endgroup$
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I provide here a complete answer, taking into account the cases where it is not possible (as explained by @Fred and @Yanko), but concentrating on the cases where the problem has a solution (which is almost certain for $n>5$ say), and how we can obtain appropriate directions.
One can find a very sophisticated solution in https://mathoverflow.net/q/96669 under a certain condition which is nothing else that a generalized form of triangle identity : a solution exists iff we have :
$$text{Condition (C) : none of the lengths exceeds the sum of the others}.$$
In fact, this question becomes clear when expressed without the complex number apparatus. It can be made equivalent to this one : being given segments with lengths $p_1, p_2,cdots p_n$, find vectors $V_1,V_2,cdots V_n$ with $|V_k|=p_k$ such that the broken line obtained by concatenating $V_1, V_1+V_2, V_1+V_2+V_3, cdots$ can be closed (i.e., generates a polygon). See Fig. 1 and 2 below.
Fig. 1 : (corresponding to Method B). Initial points $A_1,A_2,A_3$ as vertices of the triangle in blue. In the final solution (in red), the successive points (read anticlockwise) are $ A_1,A_2,A_3,cdots A_n$ (where $A_n$ is the former $A_3$).
Fig. 2 : A solution to the problem : the sum of all these vectors (obtained by following counterclockwise the contour given in Fig. 1, with given lengths $p_k$s) is $0$. The polar angles of these vectors are the looked for values $varphi_k$.
I now give 2 methods for obtaining solutions :
Method A) **An analog solution based on a principle of statics ("closing the polygon of forces") ** : let us consider the longest segment as being $p_1$ and placed horizontaly. Then hang to the endpoints of this longest segment all segments with length $p_k (k>1)$, attached one to the other (in any order) like a (closed) pasta necklace. Out of the equilibrium position taken by the necklace, one deduces vectors $V_k (k>1)$.
[I am conscious that this still has to be established mathematically, but it isn't important because the algorithmic method 2) presented below is mathematicaly rigorous].
Remark : In fact, vector $V_1$ hasn't to be necessarily
horizontal : to each position of $V_1$, horizontal or not, corresponds a different equilibria, thus a different set of vectors $V_k$. This means that if condition (C) is fulfilled (and $n>3$ see below), there is an infinite set of solutions !
Method B) An algorithmic recursive solution [Matlab program giving Fig 1 in Appendix]
Let us assume that, if we have $n$ segments, the initial largest segment with length $p_1$ is placed horizontally with endpoints $A_1=(0,0)$ and $A_n=(p_1,0)$ (this will be preserved at the end of each iteration step). Let us more generally denote by $A_k$ the position of the connecting point between line segments with lengths $p_k$ and $p_{k+1}$.
[initialization] The case for $n=3$ segments is treated apart (see below).
Let us assume that we can construct a closed necklace till $n$ segments inclusively. Let us prove that (out of it) we can build a closed necklace with $n+1$ segments.
Let us rotate horizontal line segment with length $p_1$ around $0$ (like lifting a drawbridge) with an angle $$theta_{n+1}:=2 mathrm{asin}frac{p_{n+1}}{2p_1}.tag{1}$$
In this way, we are able to place the $(n+1)$st line segment in-between (i.e., connecting) line segment number $n$ and line segment number $1$.
(in an algorithmic perspective) Apply a backwards $-theta_{n+1}$ rotation around the origin to place back the "drawbridge" in its initial horizontal position in order to be ready for the next iteration step. Apply this rotation to all other articulation points $A_k$.
Let us work apart the case $n=3$. We take for $p_1$ the longest length and $V_1=binom{p_1}{0}$. Then it suffices to consider circle $C$ (resp $C'$) with radius $p_2$ (resp. $p_3$) centered in $A_1=(0,0)$ (resp. $A_3=(p_1,0)$ ; because condition (C) is fulfilled, $p_2+p_3> p_1$, $C$ and $C'$ intersect in a certain point $A_2$. Then, if we define $V_2=-A_1A_2$ and $V_3=-A_2A_3$ we have $V_1+V_2+V_3=0$.
Remarks :
1) Relationship (1) gives the angle between the equal sides of isoceles triangle $A_nA_1A_{n+1}$.
2) It is not at all compulsory to take the longest segment as the reference initial segment. Any other segment is suitable.
Appendix : Matlab program :
clear all;close all;hold on;axis equal off;
n=7;LW='linewidth';
p=[25,20,19,14,13,6,3]; % p=sort(rand(1,n),'descend');
s=sum(p);
p=p/s;% optional
if p(1) < s/2 && p(1) < (p(2)+p(3))
% 6 following lines : coordinates of vertices P_1, P_2, P_3
x(1)=0;y(1)=0;
x(3)=p(1),y(3)=0;
x(2)=(p(1)^2+p(2)^2-p(3)^2)/(2*p(1));
y(2)=-sqrt(p(2)^2-x(2)^2);
z=zeros(1:n,1);z(1:3)=x+i*y;
plot(z([1,2,3,1]),'b',LW,2);
for k=4:n
ra=2*asin(p(k)/(2*p(1)));% rotation angle
R=exp(i*ra);
z(k)=R*p(1);
z(1:k)=conj(R)*z(1:k); % clockwise rotation
plot(z(1:k),'k');
end;
plot(z(1:n),'r',LW,2);
end;
Remark : one can notice supplementary condition $p_1 < p_2+p_3$. What is it about ? We need a
Lemma : Being given a set $p_1, p_2, cdots p_n$ of positive real numbers, there is at least one triple $(i,j,k)$ in the sequence of values $p_k$ such that :
$$p_i leq p_j+p_ktag{2}$$
Proof : By contradiction. Let $s:=sum_k p_k$. If for any triple $(i,j,k), (i neq j neq k neq i)$, we had $p_i > p_j+p_k$, adding together these $(n-2)binom{n}{2}$ inequalities, it yields $s>2s$, which is contradictory.
Consequence : if, with the present ordering, (2) isn't fulfilled for $i=1, j=2$ and $k=3$, we just have to modify this ordering. This will not affect the algorithm.
Related : https://www.geeksforgeeks.org/find-number-of-triangles-possible/
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
$endgroup$
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
add a comment |
$begingroup$
I provide here a complete answer, taking into account the cases where it is not possible (as explained by @Fred and @Yanko), but concentrating on the cases where the problem has a solution (which is almost certain for $n>5$ say), and how we can obtain appropriate directions.
One can find a very sophisticated solution in https://mathoverflow.net/q/96669 under a certain condition which is nothing else that a generalized form of triangle identity : a solution exists iff we have :
$$text{Condition (C) : none of the lengths exceeds the sum of the others}.$$
In fact, this question becomes clear when expressed without the complex number apparatus. It can be made equivalent to this one : being given segments with lengths $p_1, p_2,cdots p_n$, find vectors $V_1,V_2,cdots V_n$ with $|V_k|=p_k$ such that the broken line obtained by concatenating $V_1, V_1+V_2, V_1+V_2+V_3, cdots$ can be closed (i.e., generates a polygon). See Fig. 1 and 2 below.
Fig. 1 : (corresponding to Method B). Initial points $A_1,A_2,A_3$ as vertices of the triangle in blue. In the final solution (in red), the successive points (read anticlockwise) are $ A_1,A_2,A_3,cdots A_n$ (where $A_n$ is the former $A_3$).
Fig. 2 : A solution to the problem : the sum of all these vectors (obtained by following counterclockwise the contour given in Fig. 1, with given lengths $p_k$s) is $0$. The polar angles of these vectors are the looked for values $varphi_k$.
I now give 2 methods for obtaining solutions :
Method A) **An analog solution based on a principle of statics ("closing the polygon of forces") ** : let us consider the longest segment as being $p_1$ and placed horizontaly. Then hang to the endpoints of this longest segment all segments with length $p_k (k>1)$, attached one to the other (in any order) like a (closed) pasta necklace. Out of the equilibrium position taken by the necklace, one deduces vectors $V_k (k>1)$.
[I am conscious that this still has to be established mathematically, but it isn't important because the algorithmic method 2) presented below is mathematicaly rigorous].
Remark : In fact, vector $V_1$ hasn't to be necessarily
horizontal : to each position of $V_1$, horizontal or not, corresponds a different equilibria, thus a different set of vectors $V_k$. This means that if condition (C) is fulfilled (and $n>3$ see below), there is an infinite set of solutions !
Method B) An algorithmic recursive solution [Matlab program giving Fig 1 in Appendix]
Let us assume that, if we have $n$ segments, the initial largest segment with length $p_1$ is placed horizontally with endpoints $A_1=(0,0)$ and $A_n=(p_1,0)$ (this will be preserved at the end of each iteration step). Let us more generally denote by $A_k$ the position of the connecting point between line segments with lengths $p_k$ and $p_{k+1}$.
[initialization] The case for $n=3$ segments is treated apart (see below).
Let us assume that we can construct a closed necklace till $n$ segments inclusively. Let us prove that (out of it) we can build a closed necklace with $n+1$ segments.
Let us rotate horizontal line segment with length $p_1$ around $0$ (like lifting a drawbridge) with an angle $$theta_{n+1}:=2 mathrm{asin}frac{p_{n+1}}{2p_1}.tag{1}$$
In this way, we are able to place the $(n+1)$st line segment in-between (i.e., connecting) line segment number $n$ and line segment number $1$.
(in an algorithmic perspective) Apply a backwards $-theta_{n+1}$ rotation around the origin to place back the "drawbridge" in its initial horizontal position in order to be ready for the next iteration step. Apply this rotation to all other articulation points $A_k$.
Let us work apart the case $n=3$. We take for $p_1$ the longest length and $V_1=binom{p_1}{0}$. Then it suffices to consider circle $C$ (resp $C'$) with radius $p_2$ (resp. $p_3$) centered in $A_1=(0,0)$ (resp. $A_3=(p_1,0)$ ; because condition (C) is fulfilled, $p_2+p_3> p_1$, $C$ and $C'$ intersect in a certain point $A_2$. Then, if we define $V_2=-A_1A_2$ and $V_3=-A_2A_3$ we have $V_1+V_2+V_3=0$.
Remarks :
1) Relationship (1) gives the angle between the equal sides of isoceles triangle $A_nA_1A_{n+1}$.
2) It is not at all compulsory to take the longest segment as the reference initial segment. Any other segment is suitable.
Appendix : Matlab program :
clear all;close all;hold on;axis equal off;
n=7;LW='linewidth';
p=[25,20,19,14,13,6,3]; % p=sort(rand(1,n),'descend');
s=sum(p);
p=p/s;% optional
if p(1) < s/2 && p(1) < (p(2)+p(3))
% 6 following lines : coordinates of vertices P_1, P_2, P_3
x(1)=0;y(1)=0;
x(3)=p(1),y(3)=0;
x(2)=(p(1)^2+p(2)^2-p(3)^2)/(2*p(1));
y(2)=-sqrt(p(2)^2-x(2)^2);
z=zeros(1:n,1);z(1:3)=x+i*y;
plot(z([1,2,3,1]),'b',LW,2);
for k=4:n
ra=2*asin(p(k)/(2*p(1)));% rotation angle
R=exp(i*ra);
z(k)=R*p(1);
z(1:k)=conj(R)*z(1:k); % clockwise rotation
plot(z(1:k),'k');
end;
plot(z(1:n),'r',LW,2);
end;
Remark : one can notice supplementary condition $p_1 < p_2+p_3$. What is it about ? We need a
Lemma : Being given a set $p_1, p_2, cdots p_n$ of positive real numbers, there is at least one triple $(i,j,k)$ in the sequence of values $p_k$ such that :
$$p_i leq p_j+p_ktag{2}$$
Proof : By contradiction. Let $s:=sum_k p_k$. If for any triple $(i,j,k), (i neq j neq k neq i)$, we had $p_i > p_j+p_k$, adding together these $(n-2)binom{n}{2}$ inequalities, it yields $s>2s$, which is contradictory.
Consequence : if, with the present ordering, (2) isn't fulfilled for $i=1, j=2$ and $k=3$, we just have to modify this ordering. This will not affect the algorithm.
Related : https://www.geeksforgeeks.org/find-number-of-triangles-possible/
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
$endgroup$
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
add a comment |
$begingroup$
I provide here a complete answer, taking into account the cases where it is not possible (as explained by @Fred and @Yanko), but concentrating on the cases where the problem has a solution (which is almost certain for $n>5$ say), and how we can obtain appropriate directions.
One can find a very sophisticated solution in https://mathoverflow.net/q/96669 under a certain condition which is nothing else that a generalized form of triangle identity : a solution exists iff we have :
$$text{Condition (C) : none of the lengths exceeds the sum of the others}.$$
In fact, this question becomes clear when expressed without the complex number apparatus. It can be made equivalent to this one : being given segments with lengths $p_1, p_2,cdots p_n$, find vectors $V_1,V_2,cdots V_n$ with $|V_k|=p_k$ such that the broken line obtained by concatenating $V_1, V_1+V_2, V_1+V_2+V_3, cdots$ can be closed (i.e., generates a polygon). See Fig. 1 and 2 below.
Fig. 1 : (corresponding to Method B). Initial points $A_1,A_2,A_3$ as vertices of the triangle in blue. In the final solution (in red), the successive points (read anticlockwise) are $ A_1,A_2,A_3,cdots A_n$ (where $A_n$ is the former $A_3$).
Fig. 2 : A solution to the problem : the sum of all these vectors (obtained by following counterclockwise the contour given in Fig. 1, with given lengths $p_k$s) is $0$. The polar angles of these vectors are the looked for values $varphi_k$.
I now give 2 methods for obtaining solutions :
Method A) **An analog solution based on a principle of statics ("closing the polygon of forces") ** : let us consider the longest segment as being $p_1$ and placed horizontaly. Then hang to the endpoints of this longest segment all segments with length $p_k (k>1)$, attached one to the other (in any order) like a (closed) pasta necklace. Out of the equilibrium position taken by the necklace, one deduces vectors $V_k (k>1)$.
[I am conscious that this still has to be established mathematically, but it isn't important because the algorithmic method 2) presented below is mathematicaly rigorous].
Remark : In fact, vector $V_1$ hasn't to be necessarily
horizontal : to each position of $V_1$, horizontal or not, corresponds a different equilibria, thus a different set of vectors $V_k$. This means that if condition (C) is fulfilled (and $n>3$ see below), there is an infinite set of solutions !
Method B) An algorithmic recursive solution [Matlab program giving Fig 1 in Appendix]
Let us assume that, if we have $n$ segments, the initial largest segment with length $p_1$ is placed horizontally with endpoints $A_1=(0,0)$ and $A_n=(p_1,0)$ (this will be preserved at the end of each iteration step). Let us more generally denote by $A_k$ the position of the connecting point between line segments with lengths $p_k$ and $p_{k+1}$.
[initialization] The case for $n=3$ segments is treated apart (see below).
Let us assume that we can construct a closed necklace till $n$ segments inclusively. Let us prove that (out of it) we can build a closed necklace with $n+1$ segments.
Let us rotate horizontal line segment with length $p_1$ around $0$ (like lifting a drawbridge) with an angle $$theta_{n+1}:=2 mathrm{asin}frac{p_{n+1}}{2p_1}.tag{1}$$
In this way, we are able to place the $(n+1)$st line segment in-between (i.e., connecting) line segment number $n$ and line segment number $1$.
(in an algorithmic perspective) Apply a backwards $-theta_{n+1}$ rotation around the origin to place back the "drawbridge" in its initial horizontal position in order to be ready for the next iteration step. Apply this rotation to all other articulation points $A_k$.
Let us work apart the case $n=3$. We take for $p_1$ the longest length and $V_1=binom{p_1}{0}$. Then it suffices to consider circle $C$ (resp $C'$) with radius $p_2$ (resp. $p_3$) centered in $A_1=(0,0)$ (resp. $A_3=(p_1,0)$ ; because condition (C) is fulfilled, $p_2+p_3> p_1$, $C$ and $C'$ intersect in a certain point $A_2$. Then, if we define $V_2=-A_1A_2$ and $V_3=-A_2A_3$ we have $V_1+V_2+V_3=0$.
Remarks :
1) Relationship (1) gives the angle between the equal sides of isoceles triangle $A_nA_1A_{n+1}$.
2) It is not at all compulsory to take the longest segment as the reference initial segment. Any other segment is suitable.
Appendix : Matlab program :
clear all;close all;hold on;axis equal off;
n=7;LW='linewidth';
p=[25,20,19,14,13,6,3]; % p=sort(rand(1,n),'descend');
s=sum(p);
p=p/s;% optional
if p(1) < s/2 && p(1) < (p(2)+p(3))
% 6 following lines : coordinates of vertices P_1, P_2, P_3
x(1)=0;y(1)=0;
x(3)=p(1),y(3)=0;
x(2)=(p(1)^2+p(2)^2-p(3)^2)/(2*p(1));
y(2)=-sqrt(p(2)^2-x(2)^2);
z=zeros(1:n,1);z(1:3)=x+i*y;
plot(z([1,2,3,1]),'b',LW,2);
for k=4:n
ra=2*asin(p(k)/(2*p(1)));% rotation angle
R=exp(i*ra);
z(k)=R*p(1);
z(1:k)=conj(R)*z(1:k); % clockwise rotation
plot(z(1:k),'k');
end;
plot(z(1:n),'r',LW,2);
end;
Remark : one can notice supplementary condition $p_1 < p_2+p_3$. What is it about ? We need a
Lemma : Being given a set $p_1, p_2, cdots p_n$ of positive real numbers, there is at least one triple $(i,j,k)$ in the sequence of values $p_k$ such that :
$$p_i leq p_j+p_ktag{2}$$
Proof : By contradiction. Let $s:=sum_k p_k$. If for any triple $(i,j,k), (i neq j neq k neq i)$, we had $p_i > p_j+p_k$, adding together these $(n-2)binom{n}{2}$ inequalities, it yields $s>2s$, which is contradictory.
Consequence : if, with the present ordering, (2) isn't fulfilled for $i=1, j=2$ and $k=3$, we just have to modify this ordering. This will not affect the algorithm.
Related : https://www.geeksforgeeks.org/find-number-of-triangles-possible/
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
$endgroup$
I provide here a complete answer, taking into account the cases where it is not possible (as explained by @Fred and @Yanko), but concentrating on the cases where the problem has a solution (which is almost certain for $n>5$ say), and how we can obtain appropriate directions.
One can find a very sophisticated solution in https://mathoverflow.net/q/96669 under a certain condition which is nothing else that a generalized form of triangle identity : a solution exists iff we have :
$$text{Condition (C) : none of the lengths exceeds the sum of the others}.$$
In fact, this question becomes clear when expressed without the complex number apparatus. It can be made equivalent to this one : being given segments with lengths $p_1, p_2,cdots p_n$, find vectors $V_1,V_2,cdots V_n$ with $|V_k|=p_k$ such that the broken line obtained by concatenating $V_1, V_1+V_2, V_1+V_2+V_3, cdots$ can be closed (i.e., generates a polygon). See Fig. 1 and 2 below.
Fig. 1 : (corresponding to Method B). Initial points $A_1,A_2,A_3$ as vertices of the triangle in blue. In the final solution (in red), the successive points (read anticlockwise) are $ A_1,A_2,A_3,cdots A_n$ (where $A_n$ is the former $A_3$).
Fig. 2 : A solution to the problem : the sum of all these vectors (obtained by following counterclockwise the contour given in Fig. 1, with given lengths $p_k$s) is $0$. The polar angles of these vectors are the looked for values $varphi_k$.
I now give 2 methods for obtaining solutions :
Method A) **An analog solution based on a principle of statics ("closing the polygon of forces") ** : let us consider the longest segment as being $p_1$ and placed horizontaly. Then hang to the endpoints of this longest segment all segments with length $p_k (k>1)$, attached one to the other (in any order) like a (closed) pasta necklace. Out of the equilibrium position taken by the necklace, one deduces vectors $V_k (k>1)$.
[I am conscious that this still has to be established mathematically, but it isn't important because the algorithmic method 2) presented below is mathematicaly rigorous].
Remark : In fact, vector $V_1$ hasn't to be necessarily
horizontal : to each position of $V_1$, horizontal or not, corresponds a different equilibria, thus a different set of vectors $V_k$. This means that if condition (C) is fulfilled (and $n>3$ see below), there is an infinite set of solutions !
Method B) An algorithmic recursive solution [Matlab program giving Fig 1 in Appendix]
Let us assume that, if we have $n$ segments, the initial largest segment with length $p_1$ is placed horizontally with endpoints $A_1=(0,0)$ and $A_n=(p_1,0)$ (this will be preserved at the end of each iteration step). Let us more generally denote by $A_k$ the position of the connecting point between line segments with lengths $p_k$ and $p_{k+1}$.
[initialization] The case for $n=3$ segments is treated apart (see below).
Let us assume that we can construct a closed necklace till $n$ segments inclusively. Let us prove that (out of it) we can build a closed necklace with $n+1$ segments.
Let us rotate horizontal line segment with length $p_1$ around $0$ (like lifting a drawbridge) with an angle $$theta_{n+1}:=2 mathrm{asin}frac{p_{n+1}}{2p_1}.tag{1}$$
In this way, we are able to place the $(n+1)$st line segment in-between (i.e., connecting) line segment number $n$ and line segment number $1$.
(in an algorithmic perspective) Apply a backwards $-theta_{n+1}$ rotation around the origin to place back the "drawbridge" in its initial horizontal position in order to be ready for the next iteration step. Apply this rotation to all other articulation points $A_k$.
Let us work apart the case $n=3$. We take for $p_1$ the longest length and $V_1=binom{p_1}{0}$. Then it suffices to consider circle $C$ (resp $C'$) with radius $p_2$ (resp. $p_3$) centered in $A_1=(0,0)$ (resp. $A_3=(p_1,0)$ ; because condition (C) is fulfilled, $p_2+p_3> p_1$, $C$ and $C'$ intersect in a certain point $A_2$. Then, if we define $V_2=-A_1A_2$ and $V_3=-A_2A_3$ we have $V_1+V_2+V_3=0$.
Remarks :
1) Relationship (1) gives the angle between the equal sides of isoceles triangle $A_nA_1A_{n+1}$.
2) It is not at all compulsory to take the longest segment as the reference initial segment. Any other segment is suitable.
Appendix : Matlab program :
clear all;close all;hold on;axis equal off;
n=7;LW='linewidth';
p=[25,20,19,14,13,6,3]; % p=sort(rand(1,n),'descend');
s=sum(p);
p=p/s;% optional
if p(1) < s/2 && p(1) < (p(2)+p(3))
% 6 following lines : coordinates of vertices P_1, P_2, P_3
x(1)=0;y(1)=0;
x(3)=p(1),y(3)=0;
x(2)=(p(1)^2+p(2)^2-p(3)^2)/(2*p(1));
y(2)=-sqrt(p(2)^2-x(2)^2);
z=zeros(1:n,1);z(1:3)=x+i*y;
plot(z([1,2,3,1]),'b',LW,2);
for k=4:n
ra=2*asin(p(k)/(2*p(1)));% rotation angle
R=exp(i*ra);
z(k)=R*p(1);
z(1:k)=conj(R)*z(1:k); % clockwise rotation
plot(z(1:k),'k');
end;
plot(z(1:n),'r',LW,2);
end;
Remark : one can notice supplementary condition $p_1 < p_2+p_3$. What is it about ? We need a
Lemma : Being given a set $p_1, p_2, cdots p_n$ of positive real numbers, there is at least one triple $(i,j,k)$ in the sequence of values $p_k$ such that :
$$p_i leq p_j+p_ktag{2}$$
Proof : By contradiction. Let $s:=sum_k p_k$. If for any triple $(i,j,k), (i neq j neq k neq i)$, we had $p_i > p_j+p_k$, adding together these $(n-2)binom{n}{2}$ inequalities, it yields $s>2s$, which is contradictory.
Consequence : if, with the present ordering, (2) isn't fulfilled for $i=1, j=2$ and $k=3$, we just have to modify this ordering. This will not affect the algorithm.
Related : https://www.geeksforgeeks.org/find-number-of-triangles-possible/
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
edited Jan 18 at 9:12
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
answered Jan 14 at 17:11
Jean MarieJean Marie
29.9k42051
29.9k42051
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
add a comment |
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
$begingroup$
This answer has been completely re-written.
$endgroup$
– Jean Marie
Jan 16 at 22:23
add a comment |
$begingroup$
This is false. I'll prove that we can choose $p_1,...,p_n$ such that there is no $phi_1,...,phi_n$ with the property in your question: First observe that,
$sum_k p_k e^{iphi_k} = p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}$
By the reverse triangle inequality $|p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}| > |p_1|-|sum_{knot = 1} p_k e^{iphi_k}|$ and by the triangle inequality
$$|sum_k p_k e^{iphi_k}|geq |p_1|-(|p_2|+...+|p_k|)$$
Hence if you choose $p_1$ sufficiently close to $1$ and $p_2,...,p_k$ small such that $sum_k p_k =1$ you will have that the right hand side of the last inequality is positive (in fact arbitrary close to $1$). Therefore can't be zero.
answered Jan 14 at 14:19
YankoYanko
6,8931629
$endgroup$
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
add a comment |
$begingroup$
This is false. I'll prove that we can choose $p_1,...,p_n$ such that there is no $phi_1,...,phi_n$ with the property in your question: First observe that,
$sum_k p_k e^{iphi_k} = p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}$
By the reverse triangle inequality $|p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}| > |p_1|-|sum_{knot = 1} p_k e^{iphi_k}|$ and by the triangle inequality
$$|sum_k p_k e^{iphi_k}|geq |p_1|-(|p_2|+...+|p_k|)$$
Hence if you choose $p_1$ sufficiently close to $1$ and $p_2,...,p_k$ small such that $sum_k p_k =1$ you will have that the right hand side of the last inequality is positive (in fact arbitrary close to $1$). Therefore can't be zero.
answered Jan 14 at 14:19
YankoYanko
6,8931629
$endgroup$
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
add a comment |
$begingroup$
This is false. I'll prove that we can choose $p_1,...,p_n$ such that there is no $phi_1,...,phi_n$ with the property in your question: First observe that,
$sum_k p_k e^{iphi_k} = p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}$
By the reverse triangle inequality $|p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}| > |p_1|-|sum_{knot = 1} p_k e^{iphi_k}|$ and by the triangle inequality
$$|sum_k p_k e^{iphi_k}|geq |p_1|-(|p_2|+...+|p_k|)$$
Hence if you choose $p_1$ sufficiently close to $1$ and $p_2,...,p_k$ small such that $sum_k p_k =1$ you will have that the right hand side of the last inequality is positive (in fact arbitrary close to $1$). Therefore can't be zero.
answered Jan 14 at 14:19
YankoYanko
6,8931629
$endgroup$
This is false. I'll prove that we can choose $p_1,...,p_n$ such that there is no $phi_1,...,phi_n$ with the property in your question: First observe that,
$sum_k p_k e^{iphi_k} = p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}$
By the reverse triangle inequality $|p_1e^{iphi_1k} + sum_{knot = 1} p_k e^{iphi_k}| > |p_1|-|sum_{knot = 1} p_k e^{iphi_k}|$ and by the triangle inequality
$$|sum_k p_k e^{iphi_k}|geq |p_1|-(|p_2|+...+|p_k|)$$
Hence if you choose $p_1$ sufficiently close to $1$ and $p_2,...,p_k$ small such that $sum_k p_k =1$ you will have that the right hand side of the last inequality is positive (in fact arbitrary close to $1$). Therefore can't be zero.
answered Jan 14 at 14:19
YankoYanko
6,8931629
answered Jan 14 at 14:19
YankoYanko
6,8931629
answered Jan 14 at 14:19
YankoYanko
6,8931629
answered Jan 14 at 14:19
YankoYanko
6,8931629
6,8931629
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
add a comment |
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
2
2
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
Nice! – Note that the RHS of the last inequality is $2p_1 - 1$, so $p_1 > frac 12$ already makes it fail.
$endgroup$
– Martin R
Jan 14 at 14:22
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
@MartinR good point.
$endgroup$
– Yanko
Jan 14 at 14:23
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
$begingroup$
Also, a minimal example of $n=2$ has a solution only if $p_1=frac12$.
$endgroup$
– orion
Jan 15 at 10:04
add a comment |
$begingroup$
Supose that we have $sum_{k=1}^n p_ke^{ivarphi_k}=0$. Then
$p_1=|p_1e^{ivarphi_1}|= |sum_{k=2}^n p_ke^{ivarphi_k}| le p_2+....+p_n =1-p_1$.
Thus $p_1 le 1/2$. In the same way we see that $p_k le 1/2$ for $k=2,...,n$.
Conclusion: if $p_j > 1/2 $ for some $j$, then $sum_{k=1}^n p_ke^{ivarphi_k}=0$ is not possible !
answered Jan 14 at 14:24
FredFred
46.8k1848
$endgroup$
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
add a comment |
$begingroup$
Supose that we have $sum_{k=1}^n p_ke^{ivarphi_k}=0$. Then
$p_1=|p_1e^{ivarphi_1}|= |sum_{k=2}^n p_ke^{ivarphi_k}| le p_2+....+p_n =1-p_1$.
Thus $p_1 le 1/2$. In the same way we see that $p_k le 1/2$ for $k=2,...,n$.
Conclusion: if $p_j > 1/2 $ for some $j$, then $sum_{k=1}^n p_ke^{ivarphi_k}=0$ is not possible !
answered Jan 14 at 14:24
FredFred
46.8k1848
$endgroup$
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
add a comment |
$begingroup$
Supose that we have $sum_{k=1}^n p_ke^{ivarphi_k}=0$. Then
$p_1=|p_1e^{ivarphi_1}|= |sum_{k=2}^n p_ke^{ivarphi_k}| le p_2+....+p_n =1-p_1$.
Thus $p_1 le 1/2$. In the same way we see that $p_k le 1/2$ for $k=2,...,n$.
Conclusion: if $p_j > 1/2 $ for some $j$, then $sum_{k=1}^n p_ke^{ivarphi_k}=0$ is not possible !
answered Jan 14 at 14:24
FredFred
46.8k1848
$endgroup$
Supose that we have $sum_{k=1}^n p_ke^{ivarphi_k}=0$. Then
$p_1=|p_1e^{ivarphi_1}|= |sum_{k=2}^n p_ke^{ivarphi_k}| le p_2+....+p_n =1-p_1$.
Thus $p_1 le 1/2$. In the same way we see that $p_k le 1/2$ for $k=2,...,n$.
Conclusion: if $p_j > 1/2 $ for some $j$, then $sum_{k=1}^n p_ke^{ivarphi_k}=0$ is not possible !
answered Jan 14 at 14:24
FredFred
46.8k1848
answered Jan 14 at 14:24
FredFred
46.8k1848
answered Jan 14 at 14:24
FredFred
46.8k1848
answered Jan 14 at 14:24
FredFred
46.8k1848
46.8k1848
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
add a comment |
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
$begingroup$
Clear counter-example. But what about the favorable cases ? How to find the good $varphi_k$ being given the $p_k$s ?
$endgroup$
– Jean Marie
Jan 14 at 22:46
add a comment |
