Let a1 through an be real numbers such that:
What is the maximum possible value of a1a2 + a2a3 + ... + ana1?
This is a Lagrange optimization problem, with the first two equations as constraints.
If A=(a1,a2,...,an), g(A)=Sum(ai,i,1,n), h(A)=Sum(ai2,i,1,n)-1, and f(A)=Sum(aiai+1,i,1,n-1)+a1an
The system to solve is g(A)=0, h(A)=0, Grad(f(A))-r*Grad(g(A))-s*Grad(h(A))=0.
The ith element of Grad(f(A)) is ai-1+ai+1 for 1<i<n; the first element is a2+an, and the nth element is a1+an-1.
The ith element of Grad(g(A)) is 1, and the ith element of Grad(h(A)) is 2ai.
Therefore, for 1<i<n, we have ai-1+ai+1=r+2s*ai, and similarly cyclic equations for the cases i=1 and i=n; adding them all up yields
2Sum(ai,i,1,n)=nr+2ns*Sum(ai,i,1,n), and from the first constraint, 0=nr, so r=0.
Then we have, for i<1<n, ai-1+ai+1=2s*ai, and similarly cyclic equations for the cases i=1 and i=n.
Now multiply both sides by ai and then add all of these equations together to get 2f(A)=2s*Sum(ai2,i,1,n), and from the second constraint we have f(A)=s.
If instead both sides were multiplied by ai-1 or a similarly appropriate term for the i=1 and i=n cases, and then all terms were added together, the second constraint would yield 1+f(A)=2s*f(A), from which f(A)=1/(2s-1).
Therefore, s=1/(2s-1), so 2s2-s-1=0, so (2s+1)(s-1)=0, so s=-1/2 or 1; because f(A)=s at the critical points, the global maximum must be 1 (and the global minimum must be -1/2), because the intersection of the constraints is a smooth manifold.
The preceding logic only works if n>2, however, because only then are the terms in f(A) distinct and only then is the intersection of the constraints a smooth manifold (of dimension n-2): For n=2 f(A)=-1 at both points of the intersection (which is not a smooth manifold), for n=1 the intersection of constraints is empty, and for n=0 the second constraint is impossible while the first is trivial.
The last problem reminded me of one that I dreamed up a while ago.
1) Find a difference equation for q such that the sum
sum( f(qi, qi-qi-1, i) )
is minimized for an arbitrary function f. In the sum, i ranges from 1 to N and you may assume that q0 and qN are both given so that the problem is well-posed. (Hint: Take your partial derivatives carefully!)
2) Introduce a symbol (if you haven't already done so) that will make your solution to (1) instantly familiar to any physicist or mathematician with a background in calculus of variations.
3) Apply your solution to the function
f=2qi - (qi-qi-1)^2
subject to the boundary conditions q0=0, qN=0, and N=11. What physical problem is this analogous to?
Sorry, I conflated "Div" with "derivative" (of a multi-variable function)
Bobo the King wrote:
The last problem reminded me of one that I dreamed up a while ago.
1) Find a difference equation for q such that the sum
sum( f(qi, qi-qi-1, i) )
is minimized for an arbitrary function f. In the sum, i ranges from 1 to N and you may assume that q0 and qN are both given so that the problem is well-posed. (Hint: Take your partial derivatives carefully!)
2) Introduce a symbol (if you haven't already done so) that will make your solution to (1) instantly familiar to any physicist or mathematician with a background in calculus of variations.
3) Apply your solution to the function
f=2qi - (qi-qi-1)^2
subject to the boundary conditions q0=0, qN=0, and N=11. What physical problem is this analogous to?
I'm guessing here that you meant sum(f(qi,qi-qi-1),i)...
1) The partial derivative with respect to qi of this sum is f1(qi,qi-qi-1)+f2(qi,qi-qi-1)-f2(qi+1,qi+1-qi) where 0<i<N, while the derivative with respect to qN is f1(qN,qN-qN-1)+f2(qN,qN-qN-1) and the derivative with respect to q0 is -f2(q1,q1-q0); here fn is the partial derivative with respect to the nth variable.
Setting all of those partial derivatives equal to 0 and then adding the equations yields sum(f1(qi,qi-qi-1),i)=0; however I don't know how to derive a difference equation here...
Maybe it would be better to take the Div of the aforementioned Grad, to get the Laplacian...
Second partial in qi for 0<i<N is f1,1(qi,qi-qi-1)+f1,2(qi,qi-qi-1)+f2,1(qi,qi-qi-1)+f2,2(qi,qi-qi-1)+f2,2(qi+1,qi+1-qi), second partial in qN is f1,1(qN,qN-qN-1)+f1,2(qN,qN-qN-1)+f2,1(qN,qN-qN-1)+f2,2(qN,qN-qN-1), and second partial in q0 is f2,2(q1,q1-q0), so the Laplacian, assuming that all of the respective functions are sufficiently well-behaved, is sum(f1,1(qi,qi-qi-1)+2f1,2(qi,qi-qi-1)+2f2,2(qi,qi-qi-1),i)
but I'm still not sure how to get any relations among the qi themselves...
2) I'll try to take a variational derivative here...
For a test function F, a perturbation is given by sum(f((qi,qi-qi-1)+E*F((qi,qi-qi-1),i) for some E>0; its derivative with respect to E is sum(F((qi,qi-qi-1),i) and this is also the derivative when E=0, so I think the variational derivative with respect to f is N...I'm not sure how this helps with the problem.
3) To make it easier, f(x,y)=2x-y2, so f1(x,y)=2 and f2(x,y)=-2y; then for 0<i<11, the partial of that sum with respect to qi is 2-2(qi-qi-1)+2(qi+1-qi), which is simplified to 2qi+1-4qi+2qi-1+2, the partial with respect to q0 is 2q1-2q0, and the partial with respect to q11 is 2-2q11+2q10. Setting all of these partials equal to 0 and adding equations yields 22=0, which is impossible; the Laplacian is 44, although I'm not sure of its significance.
I'm guessing here that you meant sum(f(qi,qi-qi-1),i)...
Actually, no, I truly meant that f is (or may be) a function of i. Fortunately for you, this doesn't have any meaningful effect on the problem. Unfortunately for you, it therefore doesn't make the problem any easier.
I misspoke, however, when I said that f is minimized. I should have said it's extremized. In the example of part 3, the sum happens to be maximized. I just am used to minimizing things because I'm a physicist.
arflech wrote:
1) The partial derivative with respect to qi of this sum is f1(qi,qi-qi-1)+f2(qi,qi-qi-1)-f2(qi+1,qi+1-qi) where 0<i<N, while the derivative with respect to qN is f1(qN,qN-qN-1)+f2(qN,qN-qN-1) and the derivative with respect to q0 is -f2(q1,q1-q0); here fn is the partial derivative with respect to the nth variable.
Setting all of those partial derivatives equal to 0 and then adding the equations yields sum(f1(qi,qi-qi-1),i)=0; however I don't know how to derive a difference equation here...
Maybe it would be better to take the Div of the aforementioned Grad, to get the Laplacian...
Second partial in qi for 0<i<N is f1,1(qi,qi-qi-1)+f1,2(qi,qi-qi-1)+f2,1(qi,qi-qi-1)+f2,2(qi,qi-qi-1)+f2,2(qi+1,qi+1-qi), second partial in qN is f1,1(qN,qN-qN-1)+f1,2(qN,qN-qN-1)+f2,1(qN,qN-qN-1)+f2,2(qN,qN-qN-1), and second partial in q0 is f2,2(q1,q1-q0), so the Laplacian, assuming that all of the respective functions are sufficiently well-behaved, is sum(f1,1(qi,qi-qi-1)+2f1,2(qi,qi-qi-1)+2f2,2(qi,qi-qi-1),i)
but I'm still not sure how to get any relations among the qi themselves...
You seem to be on the right track but it's a little hard to follow your work. I suggest taking the derivative with respect to qk so you don't get your is and ks mixed up.
Big hint 1: Some Kronecker delta functions will pop out.
Even bigger hint 2: Re-index one of the terms to obtain the final answer.
Done carefully, the problem can be completed in about five lines of work, but it helps a lot to know what to look for. It's a tricky little bastard and a lesson in taking partial derivatives.
arflech wrote:
2) I'll try to take a variational derivative here...
For a test function F, a perturbation is given by sum(f((qi,qi-qi-1)+E*F((qi,qi-qi-1),i) for some E greater than 0; its derivative with respect to E is sum(F((qi,qi-qi-1),i) and this is also the derivative when E=0, so I think the variational derivative with respect to f is N...I'm not sure how this helps with the problem.
Good guess, but make the perturbation in q, not f. This strategy will lead you to the answer the long way. I have a nine line proof, plus a small lemma.
Hint related to hint 2 above: You'll need to re-index a sum at some point.arflech wrote:
3) To make it easier, f(x,y)=2x-y2, so f1(x,y)=2 and f2(x,y)=-2y; then for 0<i<11, the partial of that sum with respect to qi is 2-2(qi-qi-1)+2(qi+1-qi), which is simplified to 2qi+1-4qi+2qi-1+2, the partial with respect to q0 is 2q1-2q0, and the partial with respect to q11 is 2-2q11+2q10. Setting all of these partials equal to 0 and adding equations yields 22=0, which is impossible; the Laplacian is 44, although I'm not sure of its significance.
This is correct up until you sum the equations together. The middle 10 terms do indeed sum to 20, but remember that q0 and q11 are fixed by the boundary conditions (both are zero) so you can't take partial derivatives with respect to them. I'm not 100% sure that's where the error lies, but that's my current guess.
Edit: It seems that the real problem is that the terms don't cancel completely. If you sum over a long string of equations, all but four terms, not two, will cancel.
Now go back and attempt parts 1 and 2 again.
On another note, how do you guys make those snazzy-looking math formulas (like p4wn3r, a few posts back)? It would help to know how to do it if I'm going to write up a solution to my problem. If not, I'll just punch it up in LaTeX and copy a screenshot of the PDF.
Edit: Fixed quotes.
Edit 2: Effing hell. It doesn't want to format properly. Seems to be related to the inequalities in your quotes. Therefore, I've spelled out your "greater than" inequality in the second quote.
Be sure to check "Disable HTML in this post"
Also, to make those nice-looking images, try playing around with the mathematical typesetting in Wikipedia, which uses LaTeX internally; I looked at p4wn3r's post and he just uploaded the images to his Photobucket account and linked them from there.
Given three non-collinear points A, B, and C, and two other points X and Y not coplanar with A, B, and C, find a set of conditions to determine whether the line segment XY passes through triangle ABC.
If you project XY into the plane defined by ABC, you should be easily able to test if any part of that projection is within ABC (standard line-line intersection tests and "is point in triangle" tests). If it isn't, then clearly XY does not pass through ABC -- in order for that to happen, there must be a point on XY that is within ABC, which would also automatically be within ABC when projected.
If some part of XY projects into ABC, then that defines a new line segment (call it UV) which is the set of possible points that could intersect ABC. Find the projection direction for each endpoint of UV (i.e. if the endpoint is "above" or "below" ABC). If the directions are opposed (one is "above" and one is "below") then UV intersects ABC.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Since this topic is moving on without me, I'm working on typing up the solution to my problem. It will be a little while before it's up. In the meantime, I encourage you to give the third part a shot (it's pretty easy at this point).
Also, I endorse Derakon's solution to petrie911's problem. I'm not sure exactly how I'd test whether an arbitrary point is within the bounds of a triangle, but I have an idea: test that it's on the same side of line AB as point C, test that it's on the same side of line BC as point A, test that it's on the same side of line CA as point B. Projection operators ahoy!
The system that Jetblade uses for detecting if a point P is inside an arbitrary convex polygon ABCDE... involves taking the cross products of PA x AB, PB x BC, PC x CD, etc. If any of those cross products points in a different direction from the others, then the point lies outside; otherwise it lies inside.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Derakon: There's another way to do this check for general convex polygons, it's a classical problem in computational geometry. It uses O(n) preprocessing time to answer queries at O(lg n) speed.
Preprocessing:
1. Pick an arbitrary point in the polygon P0 (usually the one with smallest y, breaking the tie with the smaller x).
2. For each point Pk, evaluate the angle that the line (Pk - P0) makes with an arbitrary line (normally the x axis).
Assuming the polygon is convex, the angles will be in increasing order.
Querying
1. Given a point P, find the lowerbound/binary search for the angle of the line (P-P0) with the arbitrary line.
2. Let Pn be the point with angle smaller than P and P(n+1) the one with grater angle.
3. Evaluate (Pn-P0) x (P(n+1) - P0) dot (Pn - P) x (P(n+1)-P). If positive, the point is inside the polygon.
Of course, there are a lot of checks for degenerate cases, which makes computational geometry very annoying, but the main idea is there.
This problem is the most interesting one I've come across that uses those concepts, unless you want to actually submit a solution to it, in this case the precision errors will tear your brain apart: http://uva.onlinejudge.org/external/118/11836.pdf
The system that Jetblade uses for detecting if a point P is inside an arbitrary convex polygon ABCDE... involves taking the cross products of PA x AB, PB x BC, PC x CD, etc. If any of those cross products points in a different direction from the others, then the point lies outside; otherwise it lies inside.
Detecting if a point is inside an arbitrary (non-self-intersecting) polygon, on the other hand, requires a slightly different approach, but isn't significantly more complex. A standard problem in computer graphics (and something I buggered students with for quite many years).
This actually came handy in an actual program I once had to develop (it was a library which you could use to define the boundaries of a 2D sprite with an arbitrary polygon; you could, among other things, move the sprite by clicking and dragging with the mouse inside the polygon which, of course, required applying this algorithm).
I just learned about a couple of interesting families of functions that can be used to make Dirac delta distributions, and I was greatly aided by my intuition after plotting them out in Mathematica
As you may be aware, the function e-x^2, suitably normalized, can be made into a family of functions, by means of horizontal compression and vertical expansion by a factor of b, that all have integrals of 1 over the real line and converge to a Delta distribution as b->0; it turns out the envelope of the graphs of this family has the equation 1=2e*pi*x2y2.
Then I tried out the same thing with another obvious choice: 1/(1+x2); this time, however, the envelope turns out to be 1=2pi2x2y2, which is closer to the coordinate axes.
I thought that maybe a tweaking of that original base-function may work; one idea is to try to just raise the exponent on the x, but it turns out that the envelope of the family based on 1/(1+x2n) approaches 1=4x2y2, and the normalized family itself approaches one based on Heaviside step functions: H(x+1/2)-H(x-1/2).
Oddly Mathematica was unable to determine this analytically except when x>1/2, but a numerical plot made it unmistakable.
Another one turned out to be more fruitful, just raising that entire rational function to the power of n; then the envelopes of the normalized family turn out to reach their greatest extent in the limit as n->infinity, when the envelopes become exactly the same as for that Gaussian family, and the normalized family based on 1/(1+x2)nbecomes the normalized Gaussian family based on e-x^2; I'm thinking about releasing a .nb file that can be viewed in MathPlayer to show this sort of thing, because it is truly astounding. Maybe the normalized Gaussian family is the most "open" possible family of functions converging to a delta distribution, in the sense of having envelopes with the greatest distance from the origin.
Here's one which is easy enough to find online solutions to, but don't cheat. Show algebraically that when you have an Ultra Metric, IE a distance function satisfying D(x,z)<=Max{D(x,y), D(y,z)}, then:
1-All triangles are isosceles.
2-Any point in an open/closed ball can be regarded as the center of that ball.
1- By contradiction:
Suppose there exists a scalene triangle formed by points X, Y and Z. By the metric's property D(x,y) <= max{D(y,z),D(x,z)}. First, we assume that D(y,z) is larger and we have D(x,y)<=D(y,z) and since they are different D(x,y)<D(y,z). We now have D(y,z)>D(x,y) and D(y,z)>D(x,z), so D(y,z) is the largest distance. However, from the property D(y,z)<=max{D(x,y),D(x,z)}, this is absurd.
The case where D(x,z) is larger is completely analogous and also leads to an absurd. Therefore, scalene triangles don't exist and they must all be isosceles.
2- Let's consider the open ball centered at C with radius r Br(C). Consider an arbitrary point P inside the ball, that is, D(C,P)<r. We now pick an arbitrary point in the metric space X and consider two cases:
a) D(C,X)<r: We have D(P,X)<=max{D(C,X),D(C,P)}<r
b) D(C,X)>=r: We have max{D(P,X),D(C,P}>=D(C,X). Since D(C,P)<r and D(C,X)>=r, for the maximum of the set to be larger than or equal to D(C,X), we must have D(P,X)>D(C,P) and so, D(P,X)>=D(C,X)>=r
From this, we conclude that, taking any point P inside the ball, for any point X in space, D(C,X)<r if and only if D(P,X)<. Thus, Br(C) = Br(P), so P can also be considered the center of the ball. For a closed ball, just separate into D(C,X)<=r and D(C,X)>r.
Another one turned out to be more fruitful, just raising that entire rational function to the power of n; then the envelopes of the normalized family turn out to reach their greatest extent in the limit as n->infinity, when the envelopes become exactly the same as for that Gaussian family, and the normalized family based on 1/(1+x2)nbecomes the normalized Gaussian family based on e-x^2; I'm thinking about releasing a .nb file that can be viewed in MathPlayer to show this sort of thing, because it is truly astounding. Maybe the normalized Gaussian family is the most "open" possible family of functions converging to a delta distribution, in the sense of having envelopes with the greatest distance from the origin.
The fact that those functions approach gaussians as n->infinity can be readily seen from the fact that
(1+x2/n)-n -> exp(-x^2) as n-> Infinity.
This result isn't just true of 1/(1+x^2); it actually works for any function that is twice differentiable at the origin. This fact is the reason behind the Central Limit Theorem.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
I'll give number 1 a shot.
Call the three nodes of the triangle P1, P2 and P3. Let D(x,y) be the distance (using our distance function in this ultra metric) between points x and y. Consider two paths from P1 to P2: path 1, the straight line P1-P2, and path 2, the path that goes through P3, i.e. P1-P3-P2. Path 2 passes through the middle node P3, which corresponds to the point y in your expression D(x,z)<=Max{D(x,y), D(y,z)}.
Now, define
d1=D(P1,P2)
d2=D(P1,P3)
d3=D(P2,P3)
These are the sides of the triangle.
Since we are in an ultra metric, we now get
d2>=d1 OR d3>=d1 (1)
which represents that one of the straight lines in path 2 must be bigger than the straight line in path 1.
We can apply the same strategy for the other two combinations, ending up with
d1>=d2 OR d3>=d2 (2)
and
d1>=d3 OR d2>=d3 (3)
This means that we can't have a side of the triangle that is strictly bigger than the other two, because if we have, one of (1), (2), or (3) won't be satisfied: for example, if d3 is strictly biggest, condition (3) breaks. Thus at least two sides of the triangle must be equal, making it isosceles.
Is this solution correct?
EDIT: Argh, p4wn3r solved it while I was writing this post. Oh well...
The fact that those functions approach gaussians as n->infinity can be readily seen from the fact that
(1+x2/n)-n -> exp(-x^2) as n-> Infinity.
This result isn't just true of 1/(1+x^2); it actually works for any function that is twice differentiable at the origin. This fact is the reason behind the Central Limit Theorem.
That's actually more relevant than I thought at first...
This is the member of the normalized family that attains the value 1 when x=0:
(1+pi*(Gamma(n-1/2))/Gamma(n)))2x2)-n
Gamma(n-1/2)/Gamma(n) is asymptotic to 1/sqrt(n), so in the limit this really does behave just like (1+pi*x2/n)-n, which does obviously approach e-pi*x^2 as n approaches infinity.
The normalized family itself, parameterized by b for each fixed n, is
b*(1 + pi*(Gamma(n-1/2))/Gamma(n)))2b2x2)-n
However, when I decided to make a neat animation, I instead substituted n=1/m and b=tan(a), so that constant steps in m or a would yield a smoother animation and cover the relevant range better.
The envelopes of the family are
±x-1(1+1/(2n-1))-nGamma(n)/(sqrt(pi)sqrt(2n-1)Gamma(n-1/2))
and the limit as n approaches infinity is
±x-1/sqrt(2e*pi)
which is also the envelope of the family of normalized Gaussians
b*e-pi*b^2*x^2
(I discovered this part before discovering that the family of Gaussians was actually the limit of the families of inverted polynomials, and this actually inspired me to see whethe it was, and fortunately this particular diagram did commute.)
The last problem reminded me of one that I dreamed up a while ago.
1) Find a difference equation for q such that the sum
sum( f(qi, qi-qi-1, i) )
is minimized for an arbitrary function f. In the sum, i ranges from 1 to N and you may assume that q0 and qN are both given so that the problem is well-posed. (Hint: Take your partial derivatives carefully!)
2) Introduce a symbol (if you haven't already done so) that will make your solution to (1) instantly familiar to any physicist or mathematician with a background in calculus of variations.
3) Apply your solution to the function
f=2qi - (qi-qi-1)^2
subject to the boundary conditions q0=0, qN=0, and N=11. What physical problem is this analogous to?
1) Since the function depends on i, I like to think of this as sum(Fi(qi,qi-qi-1)). The function you are trying to minimize then depends on the q's. I'll introduce: L(q0,q1,...,qn) = L(q)
This will be extremized when the gradient of L is the null vector. Taking the partial derivative del L / del qk, k between 0 and n-1, we see that only Fk and Fk+1 depend on qk. to find the partial derivative, we can apply the chain rule for multivariate functions. Assuming Fi(x,y).
del Fk(qk,qk-qk-1) / del qk + del Fk+1(qk+1,qk+1-qk) / del qk= del Fk(qk,qk-qk-1) / del x + del Fk(qk,qk-qk-1) / del y - del Fk+1(qk+1,qk+1-qk) / del y = 0
For k=n:
del Fn(qn,qn-qn-1) / del qn = del Fn(qn,qn-qn-1) / del x + del Fn(qn,qn-qn-1) / del y
If the Fi's are known, you have these difference equations. If you have two of the q's and the equation has solutions, you can find all of them.
2) Since you use q's, I think that hints to Lagrange's or Hamilton's interpretation of classical mechanics, so I used L to denote the function of all q's. In variational calculus, we deal with functionals and attempt to minimize the integral int(F(y,y',x)dx), deriving a differential equation. The difference here is that we are dealing with a finite sum instead of an integral and a difference equation instead of a differential one, hence we can use simple multivariate calculus.
3) F(x,y) = 2x - y2
del F/ del x = 2
del F/del y = -2y
del F(qk,qk-qk-1) / del x + del F(qk,qk-qk-1) / del y - del Fk+1(qk+1,qk+1-qk) / del y = 0
This implies 2 - 2(qk-qk-1) + 2(qk+1-qk) = 0 -> 1 - 2qk + qk-1 + qk+1 = 0 -> qk+1 = 2qk - qk-1 - 1
With q0=0, we eventually reach q11=3q1-11=0 -> q1 = 11/3, with solution:
{0, 11/3, 19/3, 8, 7, 6, 5, 4, 3, 2, 1, 0}
I have no idea what physical problem this is analogous to... One could tell by the function F, I think, perhaps a catenary? I don't know...
The last problem reminded me of one that I dreamed up a while ago.
1) Find a difference equation for q such that the sum
sum( f(qi, qi-qi-1, i) )
is minimized for an arbitrary function f. In the sum, i ranges from 1 to N and you may assume that q0 and qN are both given so that the problem is well-posed. (Hint: Take your partial derivatives carefully!)
2) Introduce a symbol (if you haven't already done so) that will make your solution to (1) instantly familiar to any physicist or mathematician with a background in calculus of variations.
3) Apply your solution to the function
f=2qi - (qi-qi-1)^2
subject to the boundary conditions q0=0, qN=0, and N=11. What physical problem is this analogous to?
1) Since the function depends on i, I like to think of this as sum(Fi(qi,qi-qi-1)). The function you are trying to minimize then depends on the q's. I'll introduce: L(q0,q1,...,qn) = L(q)
This will be extremized when the gradient of L is the null vector. Taking the partial derivative del L / del qk, k between 0 and n-1, we see that only Fk and Fk+1 depend on qk. to find the partial derivative, we can apply the chain rule for multivariate functions. Assuming Fi(x,y).
del Fk(qk,qk-qk-1) / del qk + del Fk+1(qk+1,qk+1-qk) / del qk= del Fk(qk,qk-qk-1) / del x + del Fk(qk,qk-qk-1) / del y - del Fk+1(qk+1,qk+1-qk) / del y = 0
For k=n:
del Fn(qn,qn-qn-1) / del qn = del Fn(qn,qn-qn-1) / del x + del Fn(qn,qn-qn-1) / del y
If the Fi's are known, you have these difference equations. If you have two of the q's and the equation has solutions, you can find all of them.
2) Since you use q's, I think that hints to Lagrange's or Hamilton's interpretation of classical mechanics, so I used L to denote the function of all q's. In variational calculus, we deal with functionals and attempt to minimize the integral int(F(y,y',x)dx), deriving a differential equation. The difference here is that we are dealing with a finite sum instead of an integral and a difference equation instead of a differential one, hence we can use simple multivariate calculus.
3) F(x,y) = 2x - y2
del F/ del x = 2
del F/del y = -2y
del F(qk,qk-qk-1) / del x + del F(qk,qk-qk-1) / del y - del Fk+1(qk+1,qk+1-qk) / del y = 0
This implies 2 - 2(qk-qk-1) + 2(qk+1-qk) = 0 -> 1 - 2qk + qk-1 + qk+1 = 0 -> qk+1 = 2qk - qk-1 - 1
With q0=0, we eventually reach q11=3q1-11=0 -> q1 = 11/3, with solution:
{0, 11/3, 19/3, 8, 7, 6, 5, 4, 3, 2, 1, 0}
I have no idea what physical problem this is analogous to... One could tell by the function F, I think, perhaps a catenary? I don't know...
Good effort, and I think both you and arflech have part 1 down, but parts 2 and 3 remain elusive.
Your difference equation for part 3 is correct, but the answer you gave does not satisfy it. (For example, 6 =/= 2*7 - 8 - 1 = 5.) Assuming I didn't flub the problem statement, you should not have q11=3q1-11=0. Give it a quick second shot and I think you'll see the physical significance as well, especially if you graph the solution.
As for part 2, that's a tough problem because I'm basically asking you to read my mind. If your solution makes sense to you, that's all that matters, but I think the goal should be to make it as alluringly close to the continuous version of the solution (minor spoiler): the Euler-Lagrange equation. Think about what operator exists in the continuous version that's absent from the discrete version and what its analogue would be.
I'll keep working on my write-up of the solutions.
Uh, I'm sorry, I suck at evaluating things by hand. I had to solve the recurrence...
Anyway, the solution for that recurrence is qk=k q1 - k(k-1)/2, solving for q11 gives:
{0, 5, 9, 12, 14, 15, 15, 14, 12, 9, 5, 0}
It's all so clear now! This is a parabola, so this is probably the motion of an object suffering gravitational force after being thrown with horizontal speed.
EDIT: Thinking better, it must be a free fall, since L = mv^2/2 +mg x
For part 2, well:
We have to find the extrema of int(L(q,q',t)dt). This occurs when d/dt (del L / del q' ) - del L / del q = 0
In this problem, if we let Dqi denote qi-qi-1, we have to find the extrema of sum(Fi(qi,Dqi),i), using some strange notation, that happens when D(del Fi/del qi) = D(del Fi/del Dqi), or something like that. Is the analogy clearer now?
Uh, I'm sorry, I suck at evaluating things by hand. I had to solve the recurrence...
Anyway, the solution for that recurrence is qk=k q1 - k(k-1)/2, solving for q11 gives:
{0, 5, 9, 12, 14, 15, 15, 14, 12, 9, 5, 0}
It's all so clear now! This is a parabola, so this is probably the motion of an object suffering gravitational force after being thrown with horizontal speed.
For part 2, well:
We have to find the extrema of int(L(q,q',t)dt). This occurs when d/dt (del L / del q' ) - del L / del q = 0
In this problem, if we let Dqi denote qi-qi-1, we have to find the extrema of sum(Fi(qi,Dqi),i), using some strange notation, that happens when D(del Fi/del qi) = D(del Fi/del Dqi), or something like that. Is the analogy clearer now?
Very good! The only thing I should point out is that the parabola is more directly analogous to the path of an object under gravitational influence through time (one degree of freedom). I just think of it as the discrete version of a ball thrown straight up.
The discrete Lagrangian was obtained by discretizing the continuous Lagrangian (replacing dq/dt with qi-qi-1), then multiplying it by -2 to distract you just a little bit more. I suppose I could have also gone the route of canonical transformations and added DG to the Lagrangian, where G is any function of qi and qi-qi-1, to further obscure the physical analogy.
Finally, the symbol I prefer to use is a Greek capital delta, but capital D is fine and has the advantage of being able to type it in the forum. I define D (or delta) such that whatever it acts upon, it spits out the index minus the index minus one. Okay, that doesn't make a lot of sense, so let me just define it like so:
D•i = •i - •i-1
where • is the usual mathematical placeholder (is there a name for this?).
Under this notation, I believe the discrete Euler-Lagrange equation is
D(del F/del Dqi+1) - del F/del qi = 0
so there's actually a subtle qi+1 in there. Using Dqi changes the difference equation and the nature of the solution.
I like this problem a lot because it shows that there is a discrete analogue to the Euler-Lagrange equation, which can be nice because the continuous version is a little tricky to derive at first. Although this version requires you to introduce new notation to put it in its most succinct form and you must take your partial derivatives very carefully, it has the advantage of not requiring any perturbations, introduction of arbitrary functions, or integration by parts. Just take your derivatives, reorganize terms, and you're home free.
Here's a new challenge I just came up with. I have no idea how hard it is or even if I derived or copied the problem statement correctly. Here's hoping I did.
Show that
a+b+|a-b|+2|c-d|+2|a+b+|a-b|-c-d-|c-d|| = |a+b+|a-b|-2c|+2d+|a+b+|a-b|+2c+|a+b+|a-b|-2c|-4d|.
That's a whole lot of absolute values to keep track of, so I'm including a color-coded version:
a+b+|a-b|+2|c-d|+2|a+b+|a-b|-c-d-|c-d|| = |a+b+|a-b|-2c|+2d+|a+b+|a-b|+2c+|a+b+|a-b|-2c|-4d|.
Well, green didn't show up as clearly as I was hoping it would, but I'll replace it if anyone is confused. Good luck!
Edit: And here's a new version in which the entire expression within an absolute value sign is given the same color:
a+b+|a-b|+2|c-d|+2|a+b+|a-b|-c-d-|c-d|| = |a+b+|a-b|-2c|+2d+|a+b+|a-b|+2c+|a+b+|a-b|-2c|-4d|.
By the way, a, b, c, and d are all real numbers. It can be modified to work with complex numbers as well, but it would make it a tad bit messier.
Fun fact: you can only nest your color tags two deep before the BBCode gets confused. Here's my proof of it .
Edit 2: I've verified that the problem statement is correct and written up my own proof. It's not a very difficult problem with the right strategy.
You get bonus points, however, if you can deduce how I came up with the problem statement.
To solve it I used a small lemma I deduced. It can be shown by trial and error that a + b + | a - b | = 2 max(a,b)
This allows one to trade the variables a and b for only one, I'll call it u=max(a,b) to simplify things. So, we have:
2u + 2 | c - d | + 2 | 2u - c - d - | c - d | | = | 2u - 2c | + 2d + | 2u + 2c + | 2u - 2c | - 4d |
Simplify by two:
u + | c - d | + | 2u - c - d - | c - d | | = | u - c | + d + | u + c + | u - c | - 2d |
Sum u+c+d on both sides:
2u + c + d + | c - d | + | 2u - c - d - | c - d | | = u + c + 2d + | u - c | + | u + c + | u - c | - 2d |
Can't see the beauty yet? Making it clearer:
2u + (c + d + | c - d |) + | 2u - (c + d + | c - d |) | = (u + c + | u - c |) + 2d + | (u + c + | u - c |) - 2d |
Applying the lemma:
2u + 2max(c,d) + | 2u - 2max(c,d) | = 2max(u,c) + 2d + | 2max(u,c) - 2d |
And using it yet again:
4max(u,c,d) = 4max(u,c,d)
Equality is obvious. I'm not very sure how Bobo got to this, but my best guess is starting from max(a,b,c,d)=max(a,b,c,d) and using repeated nesting of the property 2max(a,b) = a+b+|a-b|
What is the maximum possible value of a1a2 + a2a3 + ... + ana1?
