Wikipedia:Reference desk/Archives/Mathematics/2006 November 30

From Wikipedia, the free encyclopedia

Mathematics desk
< November 29 << Oct | November | Dec >> December 1 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


Contents


[edit] November 30

[edit] Question

A * [(B + C)(D - E) - F(G*H) ] / J = 10

Each variable is a unique, single-digit, nonzero number

C - B = 1

H - G = 3

What is the solution to each variable?

I think I might have to just use trial and error, but is there a way to solve this? Thanks Xcfrommars 01:56, 30 November 2006 (UTC)

Without the requirement of uniqueness, but still requiring each variable to be an integer in the range from 1 through 9, I find 902 solutions. The uniqueness requirement is non-algebraic, suggesting strongly that a brute force attack is needed – in which the search space can be somewhat confined by treating D−E as a single variable and using a few obvious constraints.  --LambiamTalk 06:11, 30 November 2006 (UTC)
I'll restate this using TeX markup for readability:
\begin{align} 10 &{}= \frac{A \left( (B+C)^{D-E} - F^{G H} \right) }{J}\\ 1 &{}= C - B\\ 3 &{}= H - G \end{align}
Reasoning can prune the possibilities.
  • From the first equation we know that A must be even (2, 4, 6, 8) or 5, because there is no other way to get 10.
  • From the second equation we know that C is greater than B, and that one is even and the other odd.
  • From the third equation we know that H is greater than G, and again one is even and the other odd.
  • Since B is at least 1, C must be at least 2; and B is at most 8.
  • Since G is at least 1, H must be at least 4; and G is at most 6.
  • The sum of B and C is odd, and at least 3.
  • The product of G and H is even, and at least 4.
And so on. Furthermore, constraints on one variable lead to constraints on others. If we determine, say, that A must be 5, then F must be odd. --KSmrqT 07:13, 30 November 2006 (UTC)
Why must A be even or 5? Disregarding uniqueness, a solution is given by A = 9, B = 5, C = 6, D = 3, E = 2, F = 1, G = 4, H = 7, J = 9 (since 9×(111−128)/9 = 10).  --LambiamTalk 11:46, 30 November 2006 (UTC)
My mistake; even demanding uniqueness we might, for example, have A equal 3, the parenthetical expression equal 20, and J equal 6. Working through constraints like this is laborious, and I was too eager to prune. --KSmrqT 14:17, 30 November 2006 (UTC)

[edit] Hard Integral

How do I find the indefinite integral of:

cos(radical x) or cos(squarerootof x) --69.105.97.233 02:40, 30 November 2006 (UTC)

That obviously is not an elementary integral. You may need to resort to representing it as an infinite power series, such as a Taylor series. --Doubleplusungood 03:50, 30 November 2006 (UTC)
What makes you say that? I say it does have an elementary antiderivative: 2(\cos\sqrt{x} + \sqrt{x}\sin\sqrt{x}). Take the derivative of that and see if I'm wrong. Now, the problem is finding an easy way to get that from the original integrand. —Keenan Pepper 03:58, 30 November 2006 (UTC)
First substitute x=u2 and then integrate by parts. McKay 04:34, 30 November 2006 (UTC)
Exactly. Omitting the explicit integration by parts since this is undoubtedly homework, we have
\begin{align}   \int \cos \sqrt{x} \, dx   &{}= \int 2u \cos u \, du && \qquad ; x = u^2, \qquad dx = 2u\,du\\   &{}= \cdots && \qquad \text{(integration by parts)} \\   &{}= 2 \sqrt{x} \, \sin \sqrt{x} + 2 \cos \sqrt{x} && \qquad ; u = \sqrt{x} \end{align}
Substitution to achieve a known or simpler form is such a good strategy, it leads to the powerful Risch algorithm for integration. It should be our first instinct when confronted with the given integral. --KSmrqT 09:34, 30 November 2006 (UTC)

[edit] Mapping a plane with holes into complete plane

Is there a way to map a plane with N rectangular or circular holes at specified locations into a complete plane R2. Alternately, is there a way to solve a boundary value problem involving x(s) and y(s), where x and y are not allowed to have certain ranges of values for any s. It would be great if someone could give some hints. Thanks. deeptrivia (talk) 15:09, 30 November 2006 (UTC)

It is not possible to map a plane with holes to a complete plane by a homeomorphism (a two-way continuous bijection), which is probably what you are seeking. What is the nature of the boundary value problem? Is it an elliptic partial differential equation, like Laplace's equation? What does the notation x(s) and y(s) signify? Is the value of the function given on the boundary of the holes? Is anything known about the function at infinity?  --LambiamTalk 16:11, 30 November 2006 (UTC)

The problem is like this. There are field variables x(s), y(s), theta(s), mu(s), nu(s), eta(s). s varies from 0 to 1. And,

dx/ds = f1(nu, eta,theta)
dy/ds = f2(nu, eta,theta)
dtheta/ds = mu
d_mu/ds = f4(mu, nu, eta, p1, p2)
d_nu/ds = f5(mu, nu, eta, p1, p2)
d_eta/ds = f6(mu, nu, eta, p1, p2)

where p1 and p2 are constant unknown parameters.

Boundary conditions: x(0) = 0, y(0) = 0, theta(0) = 0, x(1) = X, y(1) = Y, theta(1) = T, mu(1) = g1(p1,p2), eta(1) = E, nu(1) = g2(p1,p2). X,Y,T,E are known constants.

The aim is to find the field variable functions and the constant paramters. However, the solution should be such that nowhere from s = 0 to s = 1 does (x,y) lie in some predefined zones in the xy plane. x(s) and y(s) define a curve, and this curve should avoid certain predefined areas. I hope this makes sense. Thanks. deeptrivia (talk) 16:58, 30 November 2006 (UTC)

You did not use f3, but used f5 twice; is that a typo? Do I understand correctly that the functions f1–f5 and g1–g2 are given? And that you are allowed to pick p1 and p2, which are in fact the only thing you can vary? I'm afraid that there are no general methods for solving this kind of problem. Given a choice for p1 and p2, it seems everything else is determined: you can integrate the (ordinary) differential equations backwards from s = 1 to s = 0, and hope to end up where you should at s = 0 while avoiding the holes. Now the boundary condition at s = 0 gives you 3 equations, but you have only 2 unknowns you can vary, so even if there are no holes to be avoided this seems unlikely to have a solution. Perhaps I did not understand something about the problem.  --LambiamTalk 21:38, 30 November 2006 (UTC)

Yes, that's a typo. All functions are given. p1 and p2 are unknowns to begin with, and so are all functions of s. I can take away either theta(1) = T or eta(1) = E in order to solve it. Right now, I'm solving this problem using collocation method with BCs x(0) = y(0) = theta(0) = 0, mu(1) = g1(p1,p2), eta(1) = E, nu(1) = g2(p1,p2), p1 = known, p2 = known, with no holes in the domain.When you say "avoiding holes", what exactly do you suggest I can do to avoid them. I was thinking of adding some kind of penalty function, but couldn't think of a concrete idea. Thanks, deeptrivia (talk) 03:29, 1 December 2006 (UTC)

You say "I can take away either theta(1) = T or eta(1) = E in order to solve it." This little amount of additional freedom gives you two solutions of (x,y) as function of s, either of which may or may not fall into a hole, but there is nothing you can do about that. It is all determined by the other conditions. So what exactly are the rules of the game? Are there other conditions you can relax?
For a penalty function, you could select some function that becomes large inside the holes, for example for a circular hole with centre (xc , yc) and radius r, you could take f(r2/((x−xc)2+(y−yc)2)), for some monotonic function f (e.g., id, sqrt, or log), sum the function vallues over the holes, and integrate along s.  --LambiamTalk 08:38, 1 December 2006 (UTC)

One thing I can do is to make the x, y and theta boundary conditions approximate at s = 1. That is, x(1) Є (X-ε, X+ε) , y(1) Є (Y-ε, Y+ε), theta(1) Є (T-ε, T+ε). That is, any solution with x(1), y(1) and theta(1) within a distance ε around X, Y and T respectively, are fine as long as x(s) and y(s) avoid certain regions. There may or may not be solutions, depending upon the size and location of holes, and the values of X, Y, T, and ε. deeptrivia (talk) 16:26, 2 December 2006 (UTC)

You can try to do something like that, for example by adding a further penalty for the deviation from the boundary conditions. You further need to turn the collocation method into an optimization problem, and the result is probably not easily solved. The landscape of the total penalty as a function of p1 and p2 will have several mountain ranges, and standard descent methods are likely to converge on a local but non-global minimum. There is no guarantee that a hole-avoiding solution exists.  --LambiamTalk 20:09, 2 December 2006 (UTC)

[edit] Finding reachable points

I have N circular arcs Ci with lengths Li concatenated to each other (such that slopes match too, in addition to position) to form a long piecewise circular curve. I fix one end of this long curve to (0,0) with a slope dy/dx = 0. The curvature of each arc can vary between -μi and μi. By varying the curvatures, I can make the other end of the curve move to different points. I want to find out a condition to check whether any given point (x,y) is reachable by the end point of this curve or not. For example, obviously the point (sum(Li)+delta,0) is unreachable for any delta >0. How can I get a general condition? Thanks! deeptrivia (talk) 15:19, 30 November 2006 (UTC) PS: Even a solution for N = 3 will be a great help! deeptrivia (talk) 15:28, 30 November 2006 (UTC)

If you consider just a single segment with a µ that's large compared with L^-1, its set of reachable points will be a loopy double-earring curve. After broadening that out with a second segment, things could get pretty hairy... What's this for? Melchoir 23:37, 30 November 2006 (UTC)
I'm thinking about the case where the curvatures are unconstrained, and wondering about two issues:
  1. If a point p is reachable, are all points on the line segment from the origin to p also reachable?
  2. If p is on the boundary of the reachable region, is it possible for all but the first arc on the path to p to have curvature zero?
If both are true, it seems the problem should have a straightforward answer. But I don't know how to prove either of them. For the more general problem you've described in which the curvatures are constrained to within an interval, I'd think the analogous condition to the second point would be that some initial sequence of the arcs is maximally curved, the next arc may be partially curved, and all subsequent ones straight, in order to reach a total angle of at most π.
David Eppstein 23:57, 30 November 2006 (UTC)
The answer to (1) is generally no, since for a single arc, the set of reachable points is just a curve. I'm not sure what (2) means. Melchoir 00:26, 1 December 2006 (UTC)
A single arc is a special case that might be different from other cases, though. By (2) I mean: if p is a reachable point that is maximally far from the origin, is it possible to reach p by a set of arcs in which only the first arc is curved, and the rest are straight line segments? The answer is no in the curvature-constrained case, because you may not have enough curvature in just the first arc to reach points on the negative x axis, but I'm trying to understand the unconstrained case before adding the constraints. —David Eppstein 01:31, 1 December 2006 (UTC)
Points reachable with a 3 segment extensible piecewise circular curve
Points reachable with a 3 segment extensible piecewise circular curve
Points reachable with a 3 segment extensible piecewise circular curve (with curves shown for a few extreme exterior cases)
Points reachable with a 3 segment extensible piecewise circular curve (with curves shown for a few extreme exterior cases)
Points reachable with a 3 segment extensible piecewise circular curve. (with curves shown for a few  extreme interior cases, (ignore the one stray curve)
Points reachable with a 3 segment extensible piecewise circular curve. (with curves shown for a few extreme interior cases, (ignore the one stray curve)
Well, you could also defeat (1) with, say, a long first arc and a bunch of really short ones, too short to fill in the gaps.
As for (2), if you have two arcs of comparable length, then I somewhat suspect that the frontier of the reachable set might be traced out by configurations in which the second arc curves a little bit in the opposite direction as the first arc. I haven't worked it out though. Melchoir 02:22, 1 December 2006 (UTC)

David, I think your questions are in the right direction. On the right is a simulated result for a 3 segment curve, in which I discretized the curvature domain so that the curvvatures can have values only from a finite discrete set, leading to about 100,000 possible combinations of curvatures. This is a more complicated curve which can not only bend but also extend within constraints. The starting point of the curve is (0,0) and the slope at that point is 0. Based on this plot: (1) if p is reachable, all points on the line segment is not necessarily also reachable, and (2) By manually checking a lot of points on the external boundary, I noticed that for all those points, the last segment definitely had 0 curvature. Also, there's also a hole in this envelope right at the center. The shape looks roughly like a cardiod. I hope this was helpful. This plot takes 20 hours to be generated, and it would be great to have an analytical solution to this problem, at least for the case of inextensible curves. Thanks a ton! deeptrivia (talk) 03:38, 1 December 2006 (UTC)

Let me introduce some notation. An arc's initial conditions can be described by (\vec x,\theta) where \vec x is the end of the previous arc (or \vec0 for the first arc) and θ is the direction at that end, measured from the x-axis (or 0 for the first arc). The arc is characterized by (L,κ), its length and curvature. Let us say that positive curvatures denote counterclockwise-bending arcs. The end of the first arc is at (\kappa^{-1}\langle\sin \theta,(1-\cos \theta)\rangle,\theta) where θ: = Lκ. (It's interesting that x=L\,\operatorname{sinc}\theta.) This makes a cardioid-like curve for small | κ | , followed by increasingly circular spirals that are all tangent at the origin. However, I don't think it is one: its polar formula is \rho(\phi)={L\over\phi}(1-\cos2\phi), and we can write our vector as \left\langle{2\over\kappa}(1-\cos\theta)\,\angle\frac\theta2\right\rangle. In general, the beginning of arc i + 1 is \left(\vec x_{i-1}+\left\langle{2\over\kappa_i}(1-\cos\theta)\,\angle\frac{\theta_i}2+\Theta_i\right\rangle,\Theta_i+\theta_i\right), where \Theta_i:=\sum_{j=0}^{i-1}\theta_j (I have made our arcs 0-based, and θ0 = 0 for the 0th arc).
Now work backwards: take the last arc's final point as if it were rooted as the first arc is, then translate and rotate that point under the actions of the penultimate arc, etc. We can define an operator T_{L,\kappa}(\vec x):=R_{L\kappa}(\vec x)+\left\langle{2\over\kappa}(1-\cos L\kappa)\,\angle\frac{L\kappa}2\right\rangle, where Rθ rotates its argument by θ (counterclockwise, of course). Then the final point after N arcs is just T_{L_0,\kappa_0}(T_{L_1,\kappa_1}(\dots(T_{L_{N-1},\kappa_{N-1}}(\vec0)))), or \left(\prod_{i=N-1}^0 T_i\right)\vec0, where T_i:=T_{L_i,\kappa_i}, the product is allowed to run backwards, and I am composing operators. The set of all reachable points is then just \left\{\left(\prod_{i=N-1}^0 T_i\right)\vec0:\{\kappa_i\}\in \mathbb{R}^N\right\} (with |\kappa_i|\le\mu_i for the restricted-curvature case).
The point is that with one arc we get a curve (as Melchoir said), but for plural arcs we get a filled, simply-connected region. If we have L_i\mu_i\ge2\pi, the initial arc is closed and all points near the origin will be reachable (because each T may be chosen as the identity). Obviously, if for i=1,\dots,I,\; \mu_i\ll2\pi, the outermost operators will send the entire pattern some distance down the x-axis; if for i=I,\dots,N-1,\; \mu_i\ll2\pi\mbox{ and }L_i\gg L_j\;\forall j<I the final pattern will be some sort of (perhaps partial) annulus at some distance from the origin but largely centered on it because the outer operators' rotations dominate their translations. So, unfortunately, Melchoir's concerns are correct, even with \mu_i=\infty: there can be voids in the shape (consider L0 = 1,L1 = 1 / 10, as he said), and it's trivial to arrange for some point on the boundary of the final pattern to not lie on the curve defined by \mu_0=\infty,\mu_{i>0}=0. (Example: \not\!\exists \kappa \ni \left|T_{1,\kappa}(T_{1/3,0}(\vec0))\right|\ge\left|T_{1,\pi/2}(T_{1/3,-2}(\vec0))\right|; the latter is probably not a boundary point, but it shows that the proposed boundary isn't one. Is there a more rigorous way of saying this? A plot makes it obvious.) It is worth noting, though, that in the unrestricted case you will always get the origin included, and will always have a shape in-between a circle (the limit as L_0\rightarrow0) and the cardioid-like object (the limit as L_{i>0}\rightarrow0). More precise answers than that I'm afraid are beyond me at the moment, though it might be possible to derive a ray-tracing-like answer by calculating the intersections of radii with the various curves one obtains by varying all but the last κi. The problem there is once again the breakdown of David's first idea: the point on which to mount a new arc (for an inductive solution) to reach the frontier along a particular ray need not be the intersection of that ray with the N − 1st frontier, and might not be on that frontier at all (although surely it is most of the time). --Tardis 19:00, 1 December 2006 (UTC)

This was really useful. Thanks a lot! deeptrivia (talk) 16:14, 2 December 2006 (UTC)