Wikipedia:Reference desk/Archives/Mathematics/2013 May 14

Mathematics desk
< May 13	<< Apr | May | Jun >>	May 15 >

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.

May 14

Need suggestions for a math topic

I want to explain to a middle schooler how to best approach learning math. I need a math topic to use as example, and could use some suggestions. The topic should contain a small but interesting set of concepts and facts that can be covered in a short time, and is not something that a middle schooler is likely to have learned or read about. Any suggestions? — Preceding unsigned comment added by 173.49.17.171 (talk) 01:35, 14 May 2013 (UTC)

How about the Hilbert Hotel, or Cantor's diagonal argument? --Trovatore (talk) 01:37, 14 May 2013 (UTC)

Thanks for the suggestions, but that's not the kind of topics I have in mind. What I'm trying to do is to explain how math is often presented in textbooks, especially those written for college-level readers. I want to use a mini-topic as an example to illustrate some useful tips on what to pay attention to and what to do when learning a new math topic. --173.49.17.171 (talk) 03:06, 14 May 2013 (UTC)

Hmm, how about very very basic group theory? The basics are not at all too hard for a bright student that age, very unlikely to be familiar, and could be quite a decent example for how such things are presented to college math students. A student who is introduced early to abstraction will have a huge advantage when he/she reaches linear algebra in college — that's a very easy topic, or rather the content usually presented to students in an introductory course is very easy, but a large fraction of students are completely bewildered by it simply because they've never seen anything like it before. It isn't too difficult for them by any means, but they think it is, and so it becomes that way, completely unnecessarily.

(I don't recommend using linear algebra itself as your middle-school example because there are too many axioms.) --Trovatore (talk) 04:30, 14 May 2013 (UTC)

Do you mean theoretical math or applied math? Looie496 (talk) 01:40, 14 May 2013 (UTC)

I've not thought of it along those lines; maybe the theoretical vs. applied distinction is not that important. I think a good topic would be something unfamiliar but not too difficult, requires learning new definitions/notations and their properties. --173.49.17.171 (talk) 03:06, 14 May 2013 (UTC)

How old is the middle schooler (does that mean Grade 7/8?) and how would you describe their level of ability? 96.46.198.58 (talk) 01:53, 14 May 2013 (UTC)

You get the age right. The child likes math, has good intuition, but is not very mature skillwise. --173.49.17.171 (talk) 03:06, 14 May 2013 (UTC)

Well, you could try some elementary combinatorics or number theory if you think they can handle it. (For these, you might try using "Mathematics of Choice" by Ivan Niven or "Invitation to Number Theory" by Øystein Ore.) If the child isn't at a level to handle this, then I probably wouldn't recommend teaching them a nonstandard topic with proofs in a structured way. Instead I would just work on problems at a higher level of difficulty than usual and teach them any "standard" material they're not familiar with, as it comes up. You might find some of the material here useful for this. "Mathematical Circles" by Fomin, Genkin and Itenberg is also a good source of difficult problems for ages 12-14. If you can read Russian, there is a wealth of (legal) free material at math.ru and mccme.ru, although right at the moment, there seems to be a server problem at math.ru.96.46.198.58 (talk) 03:48, 14 May 2013 (UTC)

Voting systems and various voting paradoxes. Very little computation necessary, and a great example of an apparently simple topic which turns out to be much more interesting than most people think. Staecker (talk) 11:44, 14 May 2013 (UTC)

Modular arithmetic is a suitable subject. Just start with the set {0,1,2} and the definition of addition and multiplication such that 1+1 = 2, 1+2 = 0, 2+2 = 1, and 1*x = x, 2*2 = 1 etc. Let the child consider if addition and multiplication defined in this way has the usual properties. And then you can generalize this to modulo different primes, defining equivalence relations to construct Z_p from Z, what changes if you compute modulo a number that is not a prime, etc. etc. You can probably go all the way to the proof of the quadratic reciprocity law. Count Iblis (talk) 13:27, 14 May 2013 (UTC)

I would second the suggestion of modular arithmetic. It is concrete enough to be accessible for a bright middle schooler, but also offers a lot of scope for expansion. If you want to compare different levels of explanation, you can look at the difference between the informal "remainder" definition and the formal equivalence relation definition of a congruence class. Chapters 2-4 of A Pathway Into Number Theory by R.P. Burn cover modular arithmetic and quadratic residues. Gandalf61 (talk) 14:25, 14 May 2013 (UTC)

I probably should have mentioned above that the "New Mathematical Library" series [1] has books on a variety of topics written for high schoolers, including the books by NIven and Ore above. It has a book on graphs, which might possibly be a suitable topic. I've realized however that there's an obvious question I didn't ask - does the student know any algebra? If not, then I'd probably feel they should just work on problems and/or learn the rudiments of algebra at this point, but perhaps from a source that can make it interesting. Then again, the series contains an elementary book "The Lore of Large Numbers" which doesn't really require algebra. 96.46.198.58 (talk) 01:19, 15 May 2013 (UTC)

Shortest paths between 3d co-ordinates

Hi,

Can someone help explain how I can find the shortest way to join up a set of 7 points in 3 dimensional space?

I have 7 sets of co-ordinates, in the format (x,y,z). I want to join them all up by the most direct paths possible.

I'm not great at maths, so please try and keep it as simple as possible :-) Maybe there is some tool I can use to help me (wolfram?).

BTW, it's not "homework" - it's for a hobby-project. Thanks in advance. — Preceding unsigned comment added by 88.104.28.206 (talk) 02:28, 14 May 2013 (UTC)

What you've described is the Steiner tree problem for seven vertices in space. It might also be the minimum spanning tree problem, depending on whether you only allow direct paths between your seven points, or you allow intermediate points to be introduced in order to make the whole graph shorter. 96.46.198.58 (talk) 02:38, 14 May 2013 (UTC)

Interesting but, is there any way to help calculate it? Or is it just something best done by eye? 88.104.28.206 (talk) 03:48, 14 May 2013 (UTC)

There appears to be an algorithm to solve the Steiner problem. (There is an obvious way to solve the spanning tree problem, which is to try all possibilities - of course, it may not be the best way.) I'm not sure beyond this, but if you use those search terms along with "algorithm" you might turn up a procedure or even some software to solve the problem.96.46.198.58 (talk) 03:51, 14 May 2013 (UTC)

I wish it was 'obvious' to me :-)

I guess you mean, join each of the 7 points to the other 6, and somehow choose the best ones from all those links.

Sorry but as noted, I'm not a mathematician... it's a real-world problem; I'm trying to think how I could work it out. Maybe I can somehow plot all those lines (no idea how, but I guess that's possible; I find it hard to think/plot on paper in 3D).

Or how about if I simplify things; the 'height' co-ordinate (y) isn't too important. So what if it was just 7 sets of (x,z) that I wanted to link efficiently? Think of it like 7 train-stations, kinda thing. 88.104.28.206 (talk) 04:07, 14 May 2013 (UTC)

I already plotted the x,z of all 7 on paper; so I am staring at 7 dots, wondering the best way to join 'em up. It's literally like train-line; doesn't have to be all 'direct' links, just some way from all to each other but via intermediates is fine... sorry, IDK if I'm explaining it clearly enough. 88.104.28.206 (talk) 04:09, 14 May 2013 (UTC)

Maybe I can re-phrase it; I have a brand-new country, with 7 cities. I want to link them all via railway lines. Can maths help me work out sensible line-placement? 88.104.28.206 (talk) 04:13, 14 May 2013 (UTC)

Please have a look at the illustrations in the article Steiner tree problem. If you had points A, B, C (and possibly D) as in the figures, would you require these points to be linked directly by straight edges, or would you allow additional points such as those labelled S in the figures ("Steiner points") whose introduction might make the overall graph shorter? 96.46.198.58 (talk) 04:18, 14 May 2013 (UTC)

No additional points. The only junctions would be at the 7 stations. 88.104.28.206 (talk) 04:22, 14 May 2013 (UTC)

Since you're not allowing any additional junctions, your network may be longer as a result. This is the minimum spanning tree problem. What I meant by "obvious" earlier was simply trying all possible ways of connecting the cities and seeing which one was shortest. However, looking into it further, there are more efficient algorithms. Have a look at Kruskal's algorithm to get started. The article also contains links to other algorithms that can be used. The external links have information about computer implementations of Kruskal's algorithm. 96.46.198.58 (talk) 04:30, 14 May 2013 (UTC)

The page on Kruskal's algorithm could probably use a simpler explanation. Basically, just consider the potential links in order of increasing cost, and keep only those links that connect two cities not previously connected. Bobmath (talk) 04:58, 14 May 2013 (UTC)

Why not list the actual coords of the 7 pts here ? BTW, since nobody has listed the formula for the distance between two points, here it is:

2D: D = sqrt(X2 + Y2)

3D: D = sqrt(X2 + Y2 + Z2)

Of course, if you plot them out on graph paper, you can just use a ruler to measure the distances and call that good enough. I suspect that the shortest overall length will be an open ring, where 5 of the pts connect to 2 others, while the two endpoints only have one connection. This isn't necessarily a circular shape, though, it could be a spiral or other shape, depending on the data. StuRat (talk) 05:59, 14 May 2013 (UTC)

Brute-force approach: For only 7 points, it's quite possible to try every combo out. Every pair of points will either have a direct link or not. So, since each of the 7 points can potentially be connected to each of the other 6, that's 42 possible connections, but this counts connections in both directions, and we don't care about direction, so we only have 21 possible links. That gives us 2²¹ or 2,097,152 possible combos. A computer could handle all of those, checking each for connectivity to all points and finding the minimum total length.

Pruning: However, we can do better at pruning down the list of possibilities. There need to be a minimum of 6 links to connect 7 points, so we don't need to consider cases with fewer links than that. I'm not sure if it can be proven mathematically, but I bet the minimum case will have exactly 6 links, so we can also prune off all cases with more than 6 links. This reduces the number of possibilities to 21! / ((21-6)!×6!) = 21×20×19×18×17×16 / 6×5×4×3×2×1 = 54,264 (somebody please check my math here). So, you'd still want to run a computer program. You might also run the cases with one extra link (7 links total), if you don't trust that the minimum case will have exactly 6 links. The number of cases there is 21! / ((21-7)!×7!) = 21×20×19×18×17×16×15 / 7×6×5×4×3×2×1 = 116,280.

I can write a program to solve this problem, if you'll supply the point coords. StuRat (talk) 18:00, 14 May 2013 (UTC)

Or use Kruskal's algorithm, which is simple to work through by hand for such a small problem, and runs in O(N log N) time. Bobmath (talk) 22:01, 14 May 2013 (UTC)

I agree with Bobmath that the explanation of Kruskal's algorithm in the article is not terrific, at least for quick understanding. 88, I didn't know about it previously, so I wasn't sure whether it could be explained simply. Now that I've had time to have a closer look at the page, I can explain Kruskal's algorithm to you. It is simpler than I thought it would be. Here is what Bobmath said above, but perhaps in more detail.

First, call your seven points A, B, ..., G. Second, find all of the distances between them - AB, AC, ... FG. There should be 21 distances in all. Third, list the distances in increasing order. Now go through the list in order and start adding edges to connect points. For example, if CE is listed first, then you connect points C and E. Similarly, you connect the points with the second-shortest distance listed. You keep doing this, except that beginning with the third-shortest edge, you need to pay attention to one additional condition, which is the following. You don't add an edge if adding it would form a loop. ("Forming a loop" amounts to saying that the edge connects two cities directly which have already been connected by some indirect path using edges you have drawn previously.) If this happens, you skip that edge and move on to the next-shortest one in the list. Now keep going until you have connected all the cities. This will necessarily happen by the time you reach the end of the list.

It wasn't obvious to me at first that this would produce a graph of minimal length, but the proof given in the Kruskal's algorithm article explains why this is in fact the case. I hope this helps. 96.46.198.58 (talk) 02:50, 15 May 2013 (UTC)

Add-on question for the math-buffs here, if i may (this is intriguing). Kruskal's algorithm seems to indicate, that the result could be 2 or more disconnected trees (see "description"). Is that correct and is there a good way to avoid those results? (and yes, the example is more confusing than explaining for a layman, the method became somewhat clear after 3-4 reads) GermanJoe (talk) 07:47, 15 May 2013 (UTC)

That's because Kruskal's algorithm also applies to a graph in which all the vertices aren't necessarily directly linked. In our example, this would mean that some cities can't be connected by direct rail links. In cases where there is in fact no indirect path permitted from one city to another, Kruskal's algorithm certainly can't create one! All it can do is connect those cities that can be connected, and do this as efficiently as possible. 96.46.198.58 (talk) 11:44, 15 May 2013 (UTC)

Prim's algorithm will do the same, and may seem intuitively simpler.--Gilderien Chat|List of good deeds 19:09, 15 May 2013 (UTC)

You could use a soap film to show the most economical path. [[2]] [[3]] Ap-uk (talk) 00:10, 16 May 2013 (UTC)