Wikipedia:Reference desk/Archives/Mathematics/2007 June 12

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.

June 12

Differential Equation for Gravity

What is the general solution to the following DE

${\frac {d^{2}x}{dt^{2}}}=-{\frac {k}{x^{2}}}$ where k > 0

I'm asking because I am trying to solve the equation for Gravity.

$F=m\,{\frac {d^{2}r}{dt^{2}}}=-{\frac {G\,M\,m}{r^{2}}}$

202.168.50.40 03:48, 12 June 2007 (UTC)

Equations like this can be solved by trying $x=at^{n}$. In this case, I believe this gives one solution to be $x={\sqrt[{3}]{\frac {9kt^{2}}{2}}}$. -- Meni Rosenfeld (talk) 04:06, 12 June 2007 (UTC)

Of course, you can use $t-t_{0}\;\!$ instead of $t\;\!$; but the general solution is, I think, much harder to find, and probably not expressible using elementary functions. -- Meni Rosenfeld (talk) 04:16, 12 June 2007 (UTC)

To solve an equation of the form

${\frac {d^{2}x}{dt^{2}}}=u(x)\,,$

first find the antiderivative U(x) of the r.h.s. with respect to x (including a constant of integration). If this is not an analytic expression, give up. Otherwise, put $v={\frac {dx}{dt}}\,.$ Then

${\frac {d^{2}x}{dt^{2}}}={\frac {dv}{dt}}={\frac {d{\tfrac {1}{2}}v^{2}}{dt}}\left/v\right.={\frac {d{\tfrac {1}{2}}v^{2}}{dt}}\left/{\frac {dx}{dt}}\right.={\frac {d{\tfrac {1}{2}}v^{2}}{dx}}\,.$

Then

${\tfrac {1}{2}}v^{2}=U(x)\,.$

Note that if both sides are multiplied by mass m, we can interpret one side as kinetic energy and the other side as mechanical work (integral of force mu(x) with respect to distance travelled x). So, solving for v,

${\frac {dx}{dt}}=v=\pm (2U(x))^{\tfrac {1}{2}}\,.$

With some luck, this too has an analytic solution. It does for this case (see List of integrals of irrational functions, the last section Integrals involving $S={\sqrt {ax+b}}$), but I'm insufficiently motivated to go through the labour, especially as programs like Maxima, Maple and Mathematica should be able to cough up a solution.  --Lambiam^Talk 08:17, 12 June 2007 (UTC)

Just a little warning. I hope you are considering an object falling straight toward Earth (or being thrown upward). If you want sideways motion, like the orbit of a satellite, your equation isn't quite correct. —Bromskloss 09:54, 12 June 2007 (UTC)

Thank you very much for your efforts. I'm justing trying to work out motion under gravity in one dimension which is as I see it, quite complicated already without bring in three dimensions or movements of planets and moons. 202.168.50.40 00:25, 13 June 2007 (UTC)

Eh, how did you get the following

${\frac {d^{2}x}{dt^{2}}}={\frac {dv}{dt}}={\frac {d{\tfrac {1}{2}}v^{2}}{dt}}\left/v\right.$

All I can get is

${\frac {d^{2}x}{dt^{2}}}={\frac {dv}{dt}}={\frac {dv}{dx}}\times {\frac {dx}{dt}}=v{\frac {dv}{dx}}\,$

202.168.50.40 00:31, 13 June 2007 (UTC)

It's a little trick involving the chain rule: ${\frac {d(1/2v^{2})}{dt}}={\frac {d}{dv}}\left({\frac {1}{2}}v^{2}\right)\times {\frac {dv}{dt}}=v{\frac {dv}{dt}}$ Confusing Manifestation 04:14, 13 June 2007 (UTC)

Note that ${\frac {dx}{dt}}=\pm (2U(x))^{\tfrac {1}{2}}$ above is itself a differential equation, for which I see no way to obtain any solution other than the trivial one above. My version of Mathematica is not able to find a solution to the original equation. As you have correctly observed, working in higher dimensions increases the complication greatly - for example, if you take the motion of a projectile in a constant gravity field under drag proportional to the square of its speed, this is trivial to solve for one dimension but virtually impossible (that is, I doubt there is a solution in elementary functions) for two dimensions. -- Meni Rosenfeld (talk) 23:02, 13 June 2007 (UTC)

Practice Exam

I've spent a considerable amount of time trying to solve this particular problem in a practice exam, so I hope it will not be viewed as trying to get help with 'homework'. Even just how to obtain a solution would be fine.

The question is written thus: The Western section of a football ground has its seating organised in two section. The upper section has its seating arranged in rows of 19 and tickets in in this section cost $18 each. The lower section has seats in rows of 22 and tickets here cost $28. In the Western section of the ground there are 29 more rows n the upper section than the lower and the overall capacity of this section is 8119. If the game were sold out, how much money woul dbe made from ticket sales for the Western Section?

Thanks heaps Mix Lord 08:31, 12 June 2007 (UTC)

Let $c_{u}$ be the cost of the ticketing in the upper section, $c_{l}$ be the cost of the ticketing in the lower section. Let $n_{u}$ be the length of a row in the upper section and $n_{l}$ be the length of a row in the lower section. Now, just draw relationships as expressed in the question to obtain a set of equations. Then solve the equations.

don't think there's a solution ... if the upper section had x more rows than the lower section, x would have to be a non-negative integer smaller than or equal to 23..

A quick calculation shows that the number of rows is not an integer, but the number of dollars is. Looks like whoever wrote this question did not give it much thought. -- Meni Rosenfeld (talk) 15:48, 12 June 2007 (UTC)

(edit conflict) Here's how you can obtain a solution if there is one. Upper section total seats, $u_{t}$, = 22 times upper section rows or, $22u_{r}$

Lower section total seats $l_{t}$ = 19 times lower section rows or, $19l_{r}$

Total capacity: $8119=u_{t}+l_{t}$, or

$8119=22u_{r}+19l_{r}$

If indeed $u_{r}=29+l_{r}$, then $8119=22(29+l_{r})+19l_{r}$, then $8119-22*29=22l_{r}+19l_{r}$ or $7841=41l_{r}$. The problem with this is that 7841 is not a multiple of 41. If instead you misread and it is actually $u_{t}=29+l_{t}$, then $8119=(29+l_{t})+l_{t}$. But this is a problem since this implies $2l_{t}=8090$ and 8090 needs to be a multiple of 19 (see above)... So looks like there was a typo in the word problem (or they just plumb messed up). If you were able to find integral solutions, then all you need to do is to plug the upper and lower totals into $$18u_{t}$ + $$28l_{t}$. Root⁴(one) 16:09, 12 June 2007 (UTC)

Nodal Relationships

This question has been hopped over from the Miscellaneous Desk. Tamfang suggested that this may be most closely related to graph theory. Unfortunately, my maths skills aren't good enough to be able to get enough out of the graph theory article to solve my problem. I'm sorry about the length of the question, but I'm trying to make myself as clear as I can (I'm failing quite miserably though). If you still don't understand what I'm getting at, I'll try doing a different set of diagrams to explain (I have plenty of time to wait for an answer). Thanks for any help you can give. In order to try and prevent confusion, I've superscripted the parts that don't really help your understanding. --80.229.152.246 16:16, 12 June 2007 (UTC)

Question starts here: Sorry about the title, but I don't really have a clue what to call this question. Anyway, say I have a room of 100 people and I ask each of these 100 people to pick 2 friends/people to link with (it doesn't have to be 100, or 2 or anything, but I thought I'd use it as an example). Are computers/algorithms good at sorting out the resulting links into groups of 5 or 6 people, or would it be better to do it by hand? If algorithms are good, are there any simple ones I can use (ones that preferably don't require a degree in calculus or graph theory or anything).

My follow-up starts here: Here's a quick diagram I have created in order to try and illustrate my question better: Image ^{(I have linked to the file rather than embed it because the arrowheads don't seem to show up properly if I embed it)} Using these data as an example, I would like to know if there are any nice, easy ways of quickly arranging these nodes (in this case names) into small groups (for this example, 4 members would probably be about right) based on the relationships shown by the diagram (there are no weightings of the relationships, the thickness/length of the line means nothing).

Would it be quicker/easier to do this by hand (bearing in mind I will probably be looking to do this for at most 33 people (more likely to be somewhere around 25)). If my calculations are correct, this will mean there will be a maximum of 66 links to deal with in order to fit into groups of 5/6/7.

Please also bear in mind that my maths knowledge is not that good, although I am prepared to try and learn. Also, it doesn't matter if some of the links are broken quite badly, the only thing I require is that everybody is in a group with at least one person they have directly linked to, or have indirectly linked to by a factor of 1 step (i.e. a person they have directly linked to has directly linked to the other person).

This requirement isn't strictly strict though, I'm quite prepared to break it ^{(and deal with all hell that comes if I do - that's the only downside to doing this sort of thing, you can't please everyone. It's interesting, but you always get people who are annoyed. Hopefully this method will cause fewer complaints, or rather complaints that will cancel each other out, than last time)}

One more thing. The two direct links going out from a node is strict. This cannot/will not/should not/has absolutely no chance of being changed. In other words, each person much choose TWO and only TWO links with people. No more, no less. ^{(Also, God knows why I'm trying to sort this out now, I don't even have any data, this sorting out is being done about 8 months before it needs to be done, and I don't even know if I am actually doing it! Oh well, at least it is interesting)} --80.229.152.246 16:16, 12 June 2007 (UTC)

Data clustering is the article to look at. There is software which can do this for you touchgraph might do ter job (google and look for the sourceforge page). --Salix alba (talk) 18:53, 12 June 2007 (UTC)

I'm not sure how data clustering really applies to this; that usually deals with finding similar items, trends, etc., not with discrete relationships between individual items. I think this is a graphing problem, and I think the question you are trying to solve is something like "what is the collection of groups with the strongest connections between group members?", am I correct? What you first need is a way to determine what makes a strong group, perhaps take a look at all the members in the group and how they are connected, if there is a two way connection between two members, make it 0 points, if only one way, make it 1, and if no connection make it 2, or something like this, this gives you a number that you can use to evaluate a group, if the number is smaller, it is a stronger group. Next, you want to try combinations of groups until you find the strongest one. If you were to try every combination of about 30 people, I guess it would be about ${\tbinom {30}{5}}{\tbinom {25}{5}}{\tbinom {20}{5}}{\tbinom {15}{5}}{\tbinom {10}{5}}=142506*53130*15504*3003*252\approx 9*10^{19}$ which isn't possible to do.

Instead, I would suggest a heuristic algorithm (something that guesses what would be good) of a greedy variety: maybe start with the 30 people as 30 unconnected groups, and then at each step (of 30 steps): figure out adding which person to which group would give the lowest total score for all groups together (and once a group is full, remove it from the possibilities). Each step would require at most 30*30 evaluations of the groups scores (and usually a lot less), which would be a breeze for a computer, so it would be pretty fast to calculate. It would probably give a pretty good result, though it wouldn't be guaranteed to be the best one. To improve this you could even add a bit of randomness to the selection (e.g. when the scores are equal, select from the options at random) and run it many times and select the outcome with the best score (this too could be automated by a computer). - Rainwarrior 19:25, 12 June 2007 (UTC)

Wow! Thanks for that answer. Not only is it really useful and interesting, but I can understand it all. Looks like the answer came at the right time as well - I was just beginning to calculate whether or not it would be possible to brute force it, but as you have pointed out, that would give about 9*10¹⁹ possibilities. After thinking about it for a while, I have decided that I will do it by hand for the proper one (there's far too much other information that I know but that won't actually be collected in the questionnaire about the two links people would have that would influence the linkages). However, I am very intrigued by this method of solving this problem and I will be sure to look into it. Thanks very much for pointing it out. --80.229.152.246 19:52, 12 June 2007 (UTC)

Oh, just one more point. With the greedy solution, would it not matter on which person you started with? It's not a problem if it does, I just want to make sure I understand it properly. --80.229.152.246 19:58, 12 June 2007 (UTC)

Well, with the one I was suggesting, you would see what the score would be if you combined any group with any other group of what you have available (a group might be just 1 person, or you might be combining a group of 2 with a group of 3 or whatever), so at each step you'd be checking them all to see which is the best merge to make. So, no, the order in which you make these checks wouldn't really matter. However, because at any step there could potentially be several choices with the same score, which one you choose can affect the outcome. The algorithm I suggested is just a "good guess" kind of thing, though, sometimes compromising of what looks like a really good merge at this step could work out better several steps later, and a greedy algorithm can't see that. As an alternative you could probably make an intelligent search of all the possibilities (maybe look at the Branch and bound article, I haven't read it but that is the applicable term) that if the data was well behaved enough could potentially find the optimal solution in a reasonable amount of time, but only if there is a way to reject bad solutions early on (and this is often possible). There are ways to narrow the search from the 10^19 brute force down to something that's doable, like if you can figure out what the best and worst possible scores could be if you made a particular choice you can throw it away (along with all choices that would have followed it) if its best is worse than the worst of another case you already know of. It's more complicated to figure out a best/worst kind of thing, but that's another way to approach the problem which could potentially give better results. It depends on the situation though, and sometimes it still can't narrow it down to a reasonable number of possibilities. - Rainwarrior 20:36, 12 June 2007 (UTC)

Thanks for that, it looks like I was right to ask. Looks like I was looking at the problem from a local level rather than a global one. Thanks very much for the extra info. --80.229.152.246 20:58, 12 June 2007 (UTC)

(ec) It's quite possible for there to be several equally good solutions, in which case even an optimal algorithm (for whatever meaning of "optimal" you'd like) could produce different results depending on initial choices. For example, in your sample graph, if Ian and Fred are in different groups, which group should Simon be assigned to? How about Mike, if Henry and Emily are not in the same group? (Ps. Though it probably won't help you with this problem, you might be interested in the stable marriage problem, which is a well known conceptually similar problem. It's notorious for having a simple, elegant and easily computable solution which a) is highly asymmetric despite the problem being symmetric, and b) does not generalize even to very trivial modifications of the problem, some of which are known to be intrinsically hard.) —Ilmari Karonen (talk) 21:00, 12 June 2007 (UTC)

Thanks for that as well! It looks like my problem could be sort of done as a special case of the stable marriage problem (if I have understood it correctly). It could be interesting to see how the results I get by doing it by hand differ from the algorithmically generated groups. I suspect it would be much more than I would predict, due to the fact that I know much more about the people concerned than the data the computer would be given (some of which is just not practical to make machine-readable). The only problem I can see with the algorithmic solutions would be defining what a 'good' solution would be. I don't think there is enough data to ensure that it will work quite as I want it to. Anyway, I'll try and give it a shot. EDIT: Oops, looks like I didn't fully register the last sentence. Looks like it could be a bad idea to try a generalisation... --80.229.152.246 21:06, 12 June 2007 (UTC)

Thanks very much for all the answers everyone. They were all much more detailed that I was expecting. I wish I could give you all some kind of award/reward (I can only think of Barnstars, but I don't think I'm allowed to give them out...). You've definitely opened up some new avenues that I hadn't even thought about pursuing. Thanks also for showing me the futility of brute forcing it (I was just about to calculate whether or not it would be worth it). --80.229.152.246 21:06, 12 June 2007 (UTC)

Just a little follow-up: After having a proper look at the stable marriage problem, it looks like my situation is most like the 'residents problem with couples', which looks like it is NP-complete. I think I'll stick with doing it by hand... --80.229.152.246 21:23, 12 June 2007 (UTC)

Please note your requirements may appear too strong to be satisfied. If your people happen to form cliques of three, there will be no four people connected (link Will to Ian instead of George on your image, and link Simon and George to each other, and you'll get non-extendible group of three: Ian–Matt–Will). Also if links form long chains, you will be unable to find groups of 4 or more people, such that every two persons in group are friends or have common friend (are linked directly or through one intermediate person). Your image gives the example of such chain: Mike, Emily and George form a properly linked group, but you can't extend this group to 4 people. The only two candidates are Henry and Will, but Henry is not properly linked to George, and Will is not properly linked to Mike. So the desired grouping does not exist for your data. --CiaPan 05:50, 13 June 2007 (UTC)

I don't think it's necessarily a bad thing for him to be grouping unconnected people. He just wants to maximize the connections within the final groups. - Rainwarrior 11:39, 13 June 2007 (UTC)

When a problem is NP-hard, that does not always mean that good heuristics can't give you a reasonable result; only that there is no sure way of always getting a guaranteed optimal result in an acceptable amount of time. If the problem is hard for computers, it is often also hard to do a good job by hand, and you may actually get a better result by having a program using a good heuristic or having it examine many possibilities.

Here is what I would try by way of an algorithm. I only sketch the idea; the details need fleshing out. Basically, it is a clustering algorithm, with some bells and whistles. For the sake of efficiency you may need to maintain some suitable data structures, as described in Disjoint-set data structure and Heap (data structure), depending on the size of the problem.

Initially, every vertex of the graph forms a singleton cluster. You can form larger clusters by merging two clusters. You may need to break up existing clusters, in which case the pair of smaller clusters is blacklisted as not being allowed to cluster again, to prevent getting stuck in a loop.

There is a (symmetric) matrix M, indexed by clusters, where M_ij is an indication how good it is (expected to be) to merge clusters i and j. Repeatedly:

• Find a pair i and j that are clusterable (combined size ≤ 5, not blacklisted) maximizing M_ij.
• Merge by i := i ∪ j, and set M_ik := M_ik + M_jk for all other clusters k, and likewise for M_ki. Erase or ignore the row M_jk and column M_kj, since j no longer exists as a cluster.
• If it is impossible to find a clusterable pair before all groups have the desired size, split an existing cluster into two, blacklisting it. Choose a split such that merging that pair would have had a low value. It may be best to split some cluster of some size n+1 into one of size n and a singleton. Repeat until a clusterable pair is found.

Initially, M_{p},{q} could be set equal to L_pq, the number of edges in the graph between vertices p an q. To improve performance, sort the values of L_pr + L_qr for r ≠ p, q in descending order, giving a sequence v₁ ≥ v₂ ≥ ..., and set M_{p},{q} := L_pq + 0.8×v₁ + 0.5×v₂. This will give an incentive to cluster vertices p and q that have significant growth potential by adding a suitable vertex r. The weights 0.8 and 0.5 are chosen somewhat haphazardly, but should be decreasing.

Finally, you could have attempted improvements by exchanges between clusters. If one cluster is A ∪ B and another is C ∪ D, where all components mentioned are mutually disjoint, and A and C have the same size, see if it is an improvement to cluster like A ∪ D and C ∪ B instead. Repeat as long as time allows and improvements are found.  --Lambiam^Talk 14:47, 13 June 2007 (UTC)

Thanks for even more answers! I'll be sure too look into your idea Lambian, but it looks like it will take me a long time to understand it fully (I don't even have a GCSE in maths yet!). Once again, thanks everyone. --80.229.152.246 16:47, 13 June 2007 (UTC)

As another point, would anyone be interested in helping to write a Wikibook on this subject? I think that participating in a project such as this would be the best way to learn as I would then have to learn enough about it to teach it to other people. If you are interested, please leave a message for me on my talk page. Even if you are not, can you think of any good titles for it? I personally think it should be called "Grouping" as this means we can incorporate ideas from different branches of mathematics, computer science and any other subjects we like. Also, I couldn't think of anything else... Thanks. --80.229.152.246 19:21, 13 June 2007 (UTC)