Fret Spacing on a Guitar

As you look down the neck of a guitar, the frets get closer and closer. What is the rule for deciding how close the frets should be?

Preliminary Information:

1. A string halved in length vibrates at twice the frequency (physics).
2. An octave is the interval between one musical pitch and another with half or double its frequency (Wikipedia article on octaves).
3. There are 12 notes in an octave (music theory).

To go up one octave, you have to halve your string. To go up another octave you must quarter your string. In general, to go up t octaves you need to have a string of length 

To have our length function, l, go up by twelfths of an octave (notes) rather than octaves, we need to adjust it to be:

The Myth of the Right Answer

Some time ago, a math student asked me and my fellow tutors a question from his class: how many diagonals are there in an n-sided regular polygon? We all went to work and came up with different solutions. When finished, the student asked which answer was the right one. Here are our solutions:

Counting

The student's solution was simple: draw a regular polygon and simply count how many diagonals. This works, and I've put together an applet that allows you to do exactly that (Java needs to be enabled):

Use "+" to increase the number of vertices and "-" to decrease them.

If you let n be 4, you can clearly see that there are 2 diagonals (in purple). Letting n equal 5, you can count 5 diagonals. The counting solution works, but with a catch. Let n be 10; can you still count how many diagonals there are? What if n is 15? At some point it just gets ridiculously hard to count the number of diagonals. This doesn't mean the solution is wrong (it's not, in principle you'll always be able to count how many diagonals), only that it's not a very useful solution.

Recursion

My first approach to a problem like this is usually looking for a recursive formula (this post for example). Recursive formulae are not very easy to work with, but recursive patterns are relatively easy to spot. Patterns are easier to see when the data is organized, so I'm going to arrange what I found by the counting solution:

n	3	4	5	6	7
d	0	2	5	9	14

For every n-gon, there are d diagonals. Can you see the pattern here? Look at how much the d row changes each step:

Each blue number is the difference between the two d values above it. As you can see, the blue numbers are always one less than the n numbers. This suggests the following formula:

With the initial condition d3 = 0.  This predicts that the next d value should be 20 (14+6), which can be confirmed by counting. This is an improvement over the counting solution, it no longer means drawing time and space consuming pictures, but it's far from optimal. Recursion is messy and a bit of a pain. In order to find a particular d, you first have to find the d that comes before it. But to find that d, you first have to find the one that comes before it. And it goes on that way until you get to the beginning. It takes a lot of work:

It takes the above video 3 minutes to evaluate something as simple as d6, whereas the counting method would take only 30 seconds. So is this the better solution? It depends. This method is purely algebraic, which means it can be programmed [footnote 1]. It also has the advantage of being cumulative, if you have d6, it's really easy to find d7, just add (6-1). With the drawing method you would have to draw a whole new picture.
 
Summation
If you expand the recursive formula from above, you'll start to see a pretty simple pattern:

This pattern shows that to find dn you just have to add all the numbers from 2 to n -2. This is just simple addition that can be quickly computed by hand, on a calculator, or in a spreadsheet. With sigma notation, this can be condensed to:

Is this the best answer? Well, it's certainly simpler than the recursive definition, but it's still a lot of computation.

Multiplication
We have the result

which can also be rewritten as

(Same thing as before, just with the terms reordered.) If we add the first to the second we get:

In the sum, n appears exactly (n-3) times, so we have the result

and with some algebra magic we get

This is a fantastic result, but is it a better result? All all of our previous results required a bunch of computation, this just requires three steps: subtract 3, multiply by n, divide by 2. But on the other hand, I think this ultra tidy result masks the meaning of the solution. It doesn't give any indication as to why that's the answer, it only gives you an answer. In other words, easy to use, difficult to understand.

Extrapolation
If we're technologically inclined, we can just take a few values (from the counting solution) and pop them into a spreadsheet application. From there we can extrapolate the data using a trend line. If you're used to this kind of thing, you might have a hunch that the data fits a quadratic, if not, you would have to try a few different options before determining which is best:

With an R squared value of 1, we can be pretty sure that this is the curve of best fit. Since 2E-14 = .00000000000002, I'm going to assume the curve of best fit is 

which is equivalent to our other solutions.

Is this the best solution? It certainly is the least amount of work. But it doesn't come from any reasoning and doesn't offer any insights. In this case it works, but in general interpolation methods are an unreliable way to come to an answer.

Combinatorics
Different solutions provide different insights. In addition to what we've already done, this problem can be solved with combinatorics.

Each edge is just a connection between two vertices (it's a handshake problem!). Thus, asking how many edges there are is essentially the same thing as asking how many ways can you choose 2 things from a set of n. The answer to that is n choose 2, which can be written many different ways:

We don't want to count the  n edges on an n sided polygon, so the the solution we're looking for is:

This is equivalent to our previous definition [footnote 2]. Is this a best solution? Stop asking that!. It does have a much shorter derivation (assuming you know a little bit of probability theory), but it's more computation (in its unsimplified form; see footnote 2). It certainly provides a different perspective, and having multiple vantage points is always a good thing.

Graph theory

A theorem in graph theory tells us that a complete graph of degree n has n(n-1)/2 edges. This number includes the outside edges, so we adjust for that by subtracting n:

Graph theory is definitely overkill for this problem, but I thought I'd include it to give a taste of what other approaches are out there.

Conclusion
So what is the right answer? An elementary student might say the counting solution. An algebra 1 student might give the summation, a bright algebra 2 student might give the algebraic solution. A college student might solve it with recursion or combinatorics [see footnote 3]. A Statistician may use a interpolation. A more advanced mathematician could give a more advanced solution like the graph theoretical one [see footnote 4].

Solution	Advantages	Disadvantages
Counting	Easy to understand	Absurdly difficult for large numbers A new picture has to be drawn for every n
Recursion	Relatively simple  Cumulative answers	Computation intensive Relies heavily on notation
Summation	Straight forward computation	Computation is tedious
Multiplication	Very simple computation	Solution is difficult to discover May not be clear why it works
Extrapolation	Very easy to find solution	Extrapolation is often an unreliable No way in advance to know what type of curve (linear, polynomial, exponential...)
Combinatorics	Simple solution Easily computable when simplified	Relies on a branch of mathematic that many students may be unfamiliar with.

While these answers are all equivalent [see footnote 5], they are not all the same. There are plenty of wrong answers, there really is no one right answer.

Footnotes:
[1] For example, in Python:

def diagonals(n):
        if n == 3:
                return 0
        else:
                return diagonals(n-1) + n-2

[2]

[3] As part of my research for this post, I gave this problem to a small group of very bright 8th graders. I gave them a brief explanation about how to use subscript, and then gave them about a half hour to figure things out. I told them when they got a wrong answer, but other than that, no coaching. At the end of the half hour, they came up with both the recursive and summation solutions. To say the least, I'm impressed.

[4] A set theorist might do something like:

(set theorists hate you)

[5] They're all equivalent for natural numbers greater than three. For other values, some strange things happen:

Solution	n = 3	n = 2	n = 1	n =1/2
Counting	0	0	0	undefined
Recursion	0	undefined	undefined	undefined
Summation	undefined	undefined	undefined	undefined
Multiplication	0	-1	-1	-5/8
Extrapolation	0	-1	-1	-0.625
Combinatorics	0	undefined	undefined	-1/8*

* nCr is technically undefined for non-natural values of n, but you can use the gamma function to extend the factorial function and get the answer -1/8.

Reflexivity, Symmetry and Transitivity

In this post, I will show (using "organic" examples) that Reflexivity, Symmety and Transitivity are independent of each other.

Definitions


(The diamond represents some arbitrary relation)

The following table summarizes this post:

	Reflexive	Symmetric	Transitive
.
	x
		x
	x	x
			x
	x		x
		x	x
	x	x	x

Membership


Non-membership
By the axiom of regularity, no set is a member of itself:
Using the above A,B and C:


Inequality

Everything is equal to itself, therefore (by duality) nothing is not equal to itself, and inequality is irreflexive.


Approximation


This definition for approximation is not universal, but I think it's good enough. The basic idea behind it not being transitive is that little bits added to little bits eventually make big bits.

Less than
By definition, less than is irreflexive, symmetric, and transitive.

Implication

Reflexive:

a	a → a
T    F	T T

Symmetric:

a     b	(a → b) ↔ (b→a)
T     T   T F F T F F	T F F T

Transitive:

a     b     c	((a → b) Λ (b → c)) → (a → c)
T     T     T   T T F T F T T F F F T T F T F F F T F F F	T T T T T T T T

The reflexive and transitive truth tables are tautologies, therefore implication is reflexive and transitive. The symmetric truth table is contingent, therefore implication is not symmetric.

Logical And
And is not reflexive because .
The only time x Λ y is when x = y = 1. Therefore, it is trivially the case that .
The proof for transitivity is similarly trivial.

And is not usually thought of as a relation, but technically it is so I'm using it.

Equals
By definition, equality is reflexive, symmetric, and transitive.

Commutativity and Non-Associativity

This is part three of my three part series on Commutativity and Associativity. In the first part we looked at the definitions of commutativity and associativity. In part two we looked at a system that was associative but not commutative. Now let's look at a system that commutative but not associative.

Rock, Paper, Scissors, Shoot!

This example (found on Wikipedia) is based on the game Rock, Paper, Scissors. (If you don't know how to play look here; if you want to get some practice in, play here.) Recall that Rock beats Scissors, Scissors beats Paper, and Paper beats Rock (for some reason). Let r, p, and s represent rock, paper, and scissors respectively, and let x * y mean "x is played against y." After a match is played, the match is equal to the winner of the match; in a tie, the winner is whatever hand was played. Some examples:

English Language Version	Notation
"rock is played against paper and paper wins"	r * p = p
"scissors is played against paper and scissors wins"	s * p = s
"paper is played against paper and paper wins"	p * p = p

Like before, we can keep all of our information organized by arraigning it as a table:

*	r	p	s
r	r	p	r
p	p	p	s
s	r	s	s

You can tell by the symmetry of the table that it's commutative (the order in which you evaluate expressions doesn't matter). However, it's non-associative:

(s * p) * r = s * r = r

but

s * (p * r) = s * p = s

It doesn't matter what order you evaluate terms, but it matters very much how you group them.

Conclusion

On this three part adventure (no, I don't think adventure is hyperbole) we've looked at structures that were commutative and associative, commutative and non-associative, non-commutative and associative, and non-commutative and non-associative. The table gives an example from all four categories:

	Commutative	Non-Commutative
Associative	Addition	Triangle Transformations
Non Associative	Rock, Paper, Scissors	Division

This shows that commutativity and associativity are independent notions. If you have one, that doesn't say anything about whether you have the other.

Non-Commutativity and Associativity

In my last post, I introduced the ideas of commutativity (order doesn't matter) and associativity (grouping doesn't matter). In this post I want to explore a structure that's associative, but not commutative.

Messing With Triangles: Ultra-Basic Group Theory

I'm going to start with an equilateral triangle:

Triangles are pretty symmetric; rotating it 120 degrees doesn't change it:

flipping it over also leaves the triangle unchanged:

All in all, there are 5 different things I can do to a triangle and still have it appear the same. I can rotate (clockwise or counterclockwise), or I can flip it over one of three axes:

I've labeled the corners to tell the triangles apart. Also included is what mathematicians call the Identity Element (top left corner): it's what you get when you do nothing.

In order to facilitate discussion, I think each of the possible 6 actions should have names. For the purposes of this post, I'm going to call the counterclockwise rotation R1 and the clockwise rotations R2. I've labeled each of the flip actions F1, F2 and F3. In keeping with mathematical tradition, I've labeled the identity I:

At this point, I would recommend cutting your own triangle out of paper (or better yet, cardboard) and playing with it. Notice what happens when you do two actions in a row. For example, if you do F1 followed by R1, then you end up in the same place as just doing F2. If you do F2 followed by F3 you end up at R2. F2 followed by F2 again is I. To make things more readable, I'm going to use use the notation x*y to mean x followed by y. So:

"R1 followed by F1 is R2"

can be written as:

R1 * F1 = R2

and 

"F1 followed by F1 is I"

is simply

F1 * F1 = I

This will making writing and (after some practice) reading about the different triangle operations much easier. I suggest pausing here to play with your newly cut out triangle. If you haven't bothered to make your own triangle (come on, it's not that much work), or if you just want to check what you're doing, you can play with this interactagraph I made:

At this point, you might begin to notice some patterns. For example:

• I * I = I.
• You can always get back to I with just one step.
• A rotation followed by another rotation is always a rotation (or I).
• A flip followed by a rotation (or visa versa) is always a flip.
• A flip followed by the same flip is I.
• A rotation followed by a different rotation is I.

It might be helpful at this point to collect all of our observations into a sort of multiplication table.

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

Reading this is just like reading a times table. If I want to know what R2 * F2 is, I just find where the R2 row meets the F2 column:

*	I	R1	R2	F1	F2	F3
I	I	R1	R2	F1	F2	F3
R1	R1	R2	I	F2	F3	F1
R2	R2	I	R1	F3	F1	F2
F1	F1	F3	F2	I	R2	R1
F2	F2	F1	F3	R1	I	R2
F3	F3	F2	F1	R2	R1	I

So R2 * F2 = F1.

Associativity and Non-Commutativity

With our multiplication table in place, we can now begin to look for patterns. It's clear that this structure is associative. For example:

R2 * (F1 * F2) = R2 * R2 = R1

and

(R2 * F1) * F2 = F3 * F2 = R1

More abstractly, 

(x * y) * z = x * (y * z)

for all x, y and z. But the interesting thing is that this structure is non-commutative; when evaluating equations, the order in which you evaluate matters. For example:

F1 * R1 = F3

but

R1 * F1 = F2

So the structure is non-commutative. (An important observation is that some equations are commutative: R1 * R2 = R2 * R1, but you'll remember from my last post that every pair of elements has to commute in order for an operation to be considered commutative.)

Conclusion

In my last post we saw structures that were commutative and associative (like addition), and non-commutative and non-associative (like division). In this post we looked at something non-commutative and associative. Up next, a post about something commutative and non-associative.

Follow-Up Questions:

• Consider just R1, R2 and I (so, ignore flips). Is this structure commutative? Is it still associative?
• Study the rotations and flips of a square. Is this structure commutative? Associative?
• Tetrahedrons also have four corners. Is the set of possible transformations the same as the squares? (i.e. is the tetrahedron multiplication table the same as the square multiplication table?)

Further Reading, (from easiest to hardest):

• Group Theory in the Bedroom, and Other Mathematical Diversions by Brian Hayes (Chapter 12)
• Abel's Proof: An Essay on the Sources and Meaning of Mathematical Unsolvability by Peter Pesic (Chapter 8)
• The Equation That Couldn't Be Solved: How Mathematical Genius Discovered the Language of Symmetry by Mario Livio (Chapter 6)

Commutativity and Associativity

This is the first of a three part post on the commutative and associative properties (stay tuned for parts two and three).

Commutativity: Order Doesn't Matter
When you add two things, the order in which you add them doesn't matter (2+4 is the same as 4+2). The name of this property is the commutative property. Examples of commutative operations are [note 1]:

• Multiplication: 2×3 is the same as 3×2
• Preparing a bowl of Cereal: it doesn't matter what order you add the milk and the cereal
• Putting on shoes: It doesn't matter what shoe you put on first
• Rotation: rotate left then right or right  then left , you end up at the same place
• The logical operator or: "Him or her" is the same as "Her or him."  
• Vector addition: 
• The intersection of sets: :
• Multidimensional Integration:

Sometimes the order of things do matter. For example, division: is not the same as (the first is 2 the second is one half). When an operation does not commute, we call it non-commutative (that's simple enough). Some examples of non-commutativity are:

• Subtraction: 5-3 is 2, but 3-5 is -2
• Division: 
• Exponentiation: 
• Matrix Multiplication: [see note 2]
• Making a cake: mix ingredients and then bake, order matters
• Putting your clothes on in the morning: underwear first, then pants
• Material Implication:  is not the same as
• Rotations on a Rubik's Cube: turning the top then the right is different than turning the right then the top:

One important note on non-commutativity is that the operation doesn't have to be non-commutative on everything for it to be non-commutative. Take exponentiation for example, and are both 16. (Or if you're less mathematically inclined, use the examples of putting on your clothes: it doesn't matter if you put your pants on first, or your shirt.) An operation is still non-commutative if there's at least one pair of things that doesn't commute.

Associativity: I Don't Care Who You Hang Out With

 When adding three (or more) numbers, it doesn't matter how you group those numbers. For example, if you wanted to add 2, 3 and 5, you could add 2 and 3, then add 5, or you could add 2 to 3 plus 5. This is much clearer with notation: 2+(3+5) is the same as (2+3)+5. The way you group the numbers doesn't change the answer. This is called this associativity. Other examples of associativity include:

• Multiplication: 2×(3×4) is the same as (2×3)×4
• Mixing trail mix: mixing raisins and granola then adding walnuts is the same as mixing raisins into a  granola/walnut mixture
• Translations on a plane: going up 4, then going to the left 3 and down 2 is the same as going up 4 and left 3 then going down 2
• Maximum function: max(a, max(b,c)) = max(max(a,b),c) 
• The logical operator and: 
• Composite functions:
• Putting together a puzzle:

You probably guessed it; some things are non-associative. The best example is division: is 1, but is 4. When dividing, the way you group things matters. Other non-associative examples include:

• Subtraction : (8-5)-2 = 1 but 8-(5-2) = 5 
• Exponentiation:  
• Doing the dishes: Washing and drying dishes, then putting them away is definitely not the same as washing dishes that are dried and put away
• English Expressions: A (smart dog) owner is someone that owns a smart dog, a smart (dog owner) is someone that is smart and owns a dog.
• Material implication: is not the same as
• The one dimensional distance formula d(x,y) = |x-y|:

Conclusion
Commutativity and associativity are important mathematical concepts. In part 2, we'll be looking at something associative and non-commutative. In part 3, We'll look at something commutative and non-associative.

[Notes]

[1] Some of my examples come from Wikipedia, some of them I heard before (in a classroom or in a conversation), some of them I just made up.

[2]