Feeds:
Posts
Comments

Combinatorics

Yesterday in Pre-Calculus class we were discussing combinatorics and came across a series of questions on how many ways can a best 2 out of 3 sets tennis match be won and how many ways can a best 3 out of 5 tennis match be won.

For a 2 out of 3 scenario there are six possibilities (AA, ABA, BAA, BB, BAB, ABB) and for the 3 out of 5 scenario there are 20 possibilities (AAA, BAAA, ABAA, AABA, BBAAA, BABAA, BAABA, ABBAA, ABABA, AABBA and ten more in which B wins).

The question then came up of how to generalize these results.  The way I approached this was to consider how many ways one of the players could win and then double the answer to include the scenarios in which the other won.

One of the issues in this type of problem is that once the winner has won the required number of games the match ends, so that a best 2 out of 3 match could never end AAB, for instance.  Another issue is that each of the possibilities of winning in a different number of sets should be considered separately.  That is, winning in the minimum number of sets, then winning after having lost one set and so forth.

Taking all of these issues into account for a competition in which the winner must win \frac{n+1}{2} out of n leads to a general formula of 2*\displaystyle \sum_{k=0}^{\frac{n-1}{2}}{_\frac{n+2k-1}{2}}C_{k}.

Or – if the winner must win g out of 2g-1 then the formula would be 2*\displaystyle \sum_{k=0}^{g-1}{_{g+k-1}}C_{k}.

A few weeks ago, my colleague who teaches Physics asked me about the derivation and justification of the cross-product formula.

The cross product for two vectors will find a third vector that is perpendicular to the original two vectors given.

The given vectors are assumed to be perpendicular (orthogonal) to the vector that will result from the cross product.  This means that the dot product of each of the original vectors with the new vector will be zero.

So, given two vectors a=\begin{bmatrix} a_1\\ a_2\\ a_3 \end{bmatrix}

and b=\begin{bmatrix} b_1\\ b_2\\ b_3 \end{bmatrix}

we want to find a third vector n=\begin{bmatrix} n_1\\ n_2\\ n_3 \end{bmatrix}

 

so that n is perpendicular to both a and b

As I mentioned above this means that we want the dot product of n with each of the two original vectors to be zero.

a \cdot n=a_1n_1+a_2n_2+a_3n_3=0

and

b \cdot n=b_1n_1+b_2n_2+b_3n_3=0

This gives us two equations to work with.  Since we have three variables to solve for (n_1, n_2, n_3), we’ll need another equation to work with.

The website Heaven’s in the backyard introduces a third constraint that the modulus of the cross product vector n be equal to 1.

This creates a third equation n_1^2+n_2^2+n_3^2=1 and allows us to solve for n_1, n_2, and n_3 in terms of a_1, a_2, a_3, b_1, b_2 and b_3

 

As mentioned above the web page Heaven’s in the backyard does a nice job with the derivation of the values for n_1, n_2, and n_3 and ends up with the formula n=\begin{bmatrix} a_2b_3-a_3b_2\\ a_3b_1-a_1b_3\\ a_1b_2-a_2b_1 \end{bmatrix}.

 

I don’t see this mentioned in the derivation, but it appears that the \sqrt{Z} term that is factored out and defined to make the derivation work more smoothly is actually the modulus of the cross product vector n.

 

Assuming that the cross product vector has a length of 1 results in an answer that is multiplied by \frac{1}{\sqrt{Z}}, because the actual perpendicular (n) has a modulus equal to \sqrt{(a_2b_3-a_3b_2)^2+(a_3b_1-a_1b_3)^2+(a_1b_2-a_2b_1)^2} which is \sqrt{Z}.

 

After working through some of these ideas, I became interested in where the cross-product came from.

At Wikipedia, they mention that Joseph-Louis Lagrange, the French/Italian mathematician of the late 18th century provided a formula for this in a paper from 1773 that was focused on the properties of a tetrahedron.  The calculations related to the cross-product appear in the first few pages of the paper.  Lagrange posits 9 “quantités” x, y, z, x', y', z', x'', y'', z'' and then proceeds through a blizzard of calculations based on these quantities.

If each triplet of values q=(x, y, z), r=(x', y', z') and s=(x'', y'', z'') is considered as the coordinates of a vector, then the first calculations are the cross-products of each vector with each of the others.  In Lagrange’s notation, we could identify each of the cross products as

r \times s=\begin{bmatrix} \xi\\ \eta\\ \zeta \end{bmatrix}, q \times s=\begin{bmatrix} \xi'\\ \eta'\\ \zeta' \end{bmatrix}, q \times r=\begin{bmatrix} \xi''\\ \eta''\\ \zeta'' \end{bmatrix}

On the following page Lagrange identifies the square of the modulus for each of the cross-product vectors as \alpha, \alpha' and \alpha''

Several pages later Lagrange notes that the dot product of each original vector with the appropriate cross-product produces a zero result.

There are two things that fascinate me about this – (1) the depth of this seemingly simple question – how do you justify the cross-product formula? and (2) what was Lagrange up to in this paper? – what is the purpose of the multitude of calculations that he completes in the paper from 1773 (Solutions analytiques de quelques problèmes sur les pyramides triangulaires)?

One of my colleagues recently found an interesting paper that generalizes the synthetic division algorithm so that it can be used for any polynomial division problem.

The link is here.

I read a very interesting article today from the Notices of the American Mathematical Society (AMS) about the intelligent use of technology in mathematics.  This article, titled “The Misfortunes of a Trio of Mathematicians Using Computer Algebra Systems. Can We Trust in Them?” describes the experiences of these three researchers in using the mathematical software packages Mathematica and Maple.  The details of their research are interesting but the important point for students of mathematics is to be aware of the limitations of the technology you use.  A key quote from the article is:

…even more dramatically, his algorithm yielded different outputs given the same inputs.

A more detailed explanation of what was going wrong:

…given the same matrix, the determinant function can give different values!

The authors do give credit to technology as a groundbreaking aid in modern mathematical research, but as is true in other research disciplines, they recommend using multiple sources.  In this case, checking the results of one mathematical software package against another software package to compare the results:

Having made this criticism, let us stress that software systems have proved very useful to research mathematicians.  Some well-known instances are the proof of the four-color problem by Kenneth Appel and Wolfgang Haken and the Kepler conjecture by Thomas Hales….Software bugs should not prevent us from continuing this mutually beneficial relationship in the future.  However, for the time being, when dealing with a problem whose answer cannot be easily verified without a computer, it is highly advisable to perform the computations with at least two computer algebra systems.

And, for students of mathematics, I would add,

– When dealing with a problem whose answer CAN be easily verified without a computer, do so!

Synthetic Division

We just finished talking about synthetic division in the College Algebra course today and got into a discussion of how to represent the remainder.  For example, given the problem:

\frac{x^4-2x^3-x+10}{x-2}

The answer turns out to be: x^3-1 R: 8 or you can say that the answer is: x^3-1+\frac{8}{x-2}.  This all goes back to the division algorithm which says that given two numbers a and b, then solving the problem \frac{a}{b} means finding q, the quotient and r, the remainder such that a=b*q+r (with r<b) .

If we take the expression a=b*q+r and divide on both sides by b, then we’ll have \frac{a}{b}=\frac{b*q}{b}+\frac{r}{b} or \frac{a}{b}=q+\frac{r}{b}.

Which of these forms we prefer depends on whether we want to say that:

x^4-2x^3-x+10=(x-2)(x^3-1)+8

or

\frac{x^4-2x^3-x+10}{x-2}=x^3-1+\frac{8}{x-2}

Income Inequality

Back in May of 2013, I did a presentation on income inequality that focused on how the Gini index is calculated.

Recently, I came across a graph that shows how the income growth during economic expansions has been distributed over the last 60 years.

Income Growth INEQ

It’s seems clear to me that the change in income tax rates during the Reagan years had a radical effect on income distribution in the US.

In his latest blog post, Robert Reich has a good analysis of some of the other issues that have led to the level of inequality we experience today.

cos(108)

I came across an interesting tidbit of math today in solving a problem from the ever-fruitful, continuously engaging book Mathematics Review Exercises by David P. Smith Jr. and Leslie T. Fagan.

Apparently \sqrt{2-2\cos 108^\circ}=\phi.