How Many Squares On A Chessboard?

Fig. 29 How many squares can you find?

          This problem is much like the previous one (see How Many Triangles in a Triangle?), in that a relationship must be proven for the number of geometrical figures that can be constructed from the arrangement given, as a function of the order.  In this problem, a range of different sized chessboards are given, with the conventional board being of order eight (8 sides).

Fig. 30 Unconventional Chessboards

          The text investigates the properties of these first few, then asks how many squares could be found on the one with eight squares on each side.  It then leaves as an exercise for the reader to find a general rule that could be applied.  It can be verified easily for these first few that for a function N(O = n), where N is the number of squares and O is the order of the figure, that N(O = n) = (n/6)(n + 1)(2n + 1).  I have found two different proofs for this relationship, but there may well be many more.

          Firstly we take a look at the square of order n (I'll use n = 3 to illustrate), and assume that we have already counted those for that of order n - 1 which appears in the bottom left, so we are only looking at the top and right edges (and those parts that are overlapped by the larger sized squares).  Now we can see that there will be one square of side length n (there is only one three by three square in that of order three.).  Looking at the next largest square, with side length n - 1, we can fit along the edge three of these (since it shifts one space from the top left corner and then reaches the corner and must shift down a space for the next one), in the 3x3 square, three 2x2 squares can be fit along the edge like this.

Fig. 31 2x2 squares on the edge of 3x3 square

          We can continue this through, forming a sum of a series of odd numbers up until we reach 1x1 squares of which there are 2n - 1, since there are n on the top row and n - 1 on the right, since the top right square was counted in the top.  So now we have this series:

                               N(O = n) - N(O = n - 1) = 1 + 3 + ... + (2n - 1)    -- (1)

           It can be shown by induction that (1) is equal to the square of n.  So for each value of n the function gives a square plus the function before, which was its square plus the function before it, and so on.  Since N(O = 1) = 1², we can say that N(O = 2) = 2² + 1², and so on up through all values of n.  Now we have reached the formula:

                               N(O = n) = n² + (n - 1)² + ... + 2² + 1²     -- (2)

          To reach the formula given at the beginning we can use an inductive approach as follows.

                    Assuming that N(O = n = k) = (k/6)(k + 1)(2k + 1),

                    N(O = n = k + 1) = (k/6)(k + 1)(2k + 1) + (k + 1)²

                                                = [(k + 1)/6][k(2k + 1) + 6(k + 1)]

                                                = [(k + 1)/6](2k² + k + 6k + 6)

                                                = [(k + 1)/6](2k² + 7k + 6)

                                                = [(k + 1)/6](2k² + 4k + 3k + 6)

                                                = [(k + 1)/6][2k(k + 2) 3(k + 2)]

                                                = [(k + 1)/6](k + 2)(2k + 3)

                                                = [(k + 1)/6][(k + 1) + 1][2(k + 1) + 1]

                     So if it is true for O = n = k it is also true for O = n = k + 1, and in turn O = n = (k + 1) + 1 = k + 2, and so on for all integer values of O = n > k.

                     But N(O = 1) = 1, and (1/6)(1 + 1)(2 x 1 + 1) = (2 x 3)/6 = 1.  Therefore it is true for all O = n greater than or equal to 1.

         The second method for this proof involves the derivation of (2).  Once again we assume that all the squares in the square of order n - 1 that appears in the bottom left have been counted.  Now, we notice that along the top row there will be 1 nxn square, 2(n - 1)x(n - 1) squares, and so on until we notice n 1x1 squares.  On the right edge we now have one less of each square (since those that fit in the top right corner have been counted).  So on the edge we have the triangular number of n (T_n) and the triangular number of n - 1 (T_{n - 1}).

         By induction it can be shown that the triangular number for a given value x, is given by T_x = (x² + x) / 2.  So now we have:

                             N(O = n) - N(O = n -1) = (x² + x) / 2 + [(x - 1)² + (x - 1)] / 2

                                                                   = (x² + x + x² - 2x + 1 + x - 1) / 2

                                                                   = (2x²) / 2

                                                                   = x²

          This is equivalent to (2) and the proof is completed in the same way from there.

How Many Triangles in a Triangle?

Fig. 27 Checkered Triangles

          This diagram appeared in the, afore mentioned, puzzle book (see The Art Of Mathematical Origami).  The problem?  Prove that in this series of triangles, there appear as many triangles as the cube of the order.  In other words, if we examined triangle n, we would find that it contained n³ unique triangles within in it (eg. 2³ = 8, 3³ = 27 are easily verified).  I especially like this proof as it shows how unifying mathematics can reap benefits.  This particular proof uses Combinations, used in probability theory and binomial expansions, to generate a result in geometry.  Although not specifically shown, I assume the triangle that corresponds to n = 1, would look like this.

Fig. 28 Triangle of the First Order

          To prove the relation given, firstly, we recognize that any triangle created must contain either of the points A, or C, since all other points are either not connected or lie on the same line as each other.  Now, we tackle each case separately.

          For those triangles that contain A, there are n lines produced from C that are intersected by the n lines produced from A, and also inherently by C, giving a total of n + 1 intersection points.  Three points must be chosen from this selection of points in order to make up a triangle.  The number of arrangements possible is given by the number of lines (n) multiplied by the number of possibilities on each line.  Assuming A is already chosen, this leaves nⁿ⁺¹C₂.

          The situation is similar for those triangles containing C, however those triangles containing A have already been accounted for and thus there is one less point available to be chosen on each line (as A lies on all of these lines).  Using the same logic as that followed for A, we can see that the number of possibilities for triangles containing B, and not A, is nⁿC₂.  Since we have covered all possible triangles, the total number of possibilities is the sum of those expressions already derived.

        Total N^o ∆s = n(ⁿ⁺¹C₂ + ⁿC₂)

                            = n[(n + 1)!/2!(n – 1)! + n!/2!(n – 2)!]

                            = n[n(n + 1) + n(n – 1)]/2

                            = n(2n²/2)

                            = n³

          Isn’t that beautiful?

The Art Of Mathematical Origami

         Over the holidays I came across a puzzle book entitled ‘Can You Solve These?’  Naturally I had the instant urge to prove that indeed I could solve every puzzle that appeared in the book.  As indeed I did, and in fact the next few posts on this blog will be regarding some of the techniques I used and some nice little proofs I came up with along the way.

         This particular post concerns a geometric puzzle in which the puzzler is required to determine whether a particular arrangement of paper is reachable by means of a finite number of folds (without cutting or tearing).  The first step in my solution was to establish that to fold one point of the paper onto another, a fold must be made that is the perpendicular bisector of the line joining the two points.  It makes sense intuitively that the point to be translated and the destination be equidistant from the fold line, and it seems quite acceptable that this fold always be at right angles to the segment between these points, but this result can be proved rigourously.

        Firstly, we state that we wish to translate point A on a sheet of arbitrarily sized paper onto point a on the same paper.  To do this, we make a fold from points B and C on the edges of the paper.  Now we know that AB will end up lying on aB, and AC will lie on aC, and therefore |AB| = |aB| and |AC| = |aC|.  Marking these in we see that ABaC is a kite, and therefore the vertical diagonal, BC is the perpendicular bisector of the horizontal one, Aa.

Fig. 25 Translating points on a page by folding.

          The next step in my investigation was to extend the method to a translation of two points simultaneously.  I soon established a means for doing so.  Beginning with any sheet of paper with two points, A and B marked on it, and two others with the same distance as the previous, a and b, which are not necessarily on the same angle.

Fig. 26 Translating a set of points

          We now make a fold, CD, in order to translate A such that AB is parallel to ab, A’B.  If B were below this fold line, the process would be more difficult.  Thankfully, in my case B was well above, but in this example B lies on the fold lie, which is permissible, since B needn’t move from its original position.  Now, since A’B || ab, the distance apart is equal and a line which is perpendicular to one is necessarily perpendicular to the other, and therefore, the fold that translates A onto a, C’D’, also translates B onto b (excuse the diagram, the points aren't placed perfectly parallel and equal in distance).  This was all I needed to complete the proof!

Irrationality of Fermat's Last Theorem

         This little bit of inspiration came while reading Simon Singh's 'Fermat's Last Theorem.'  Now that Fermat's Last Theorem has been proven, I have been able to construct an argument to show that in fact, the equation must have a least one irrational value in it's solution.  We begin with an ordinary number line of whole integers.  By proving Fermat's Last Theorem, it has been shown that any solution to the equation must include values that do not lie on any of the currently marked points on this line.  Now we will attempt to find a fully rational solution.  Firstly, we divide the current intervals to include all rational numbers, and then locate a solution (m/n) for one of the values x, y or z in the equation (xⁿ + yⁿ = zⁿ, n > 2).

Fig. 24 Number line with rational solutions for Fermat's Last Theorem.

         We can now adjust the scale of the number line to place our rational solution in line with an integer.  Now, by Fermat's Last Theorem, the other variables in the solution must not be integers.  Therefore for them to remain rational, they must be fractions.  Let us find one of the other variables (p/q).  We can now readjust the scale so that both our elements are in line with integers (this is because they exhibit a property called commensurability i.e. there exists a smaller segment that will divide into both, which is the geometrical equivalent of rationality).  This process can then be extended t the third element (say r/s).  However now we have found a scale on which all three fractions; m/n, p/q, and r/s, result in integers.  This is impossible however because Fermat's Last Theorem has proven that no such solutions exist, and hence the third rational term cannot be possible.  So, at least one of x, y or z in the equation of the theorem must be irrational (or imaginary but I won't go there)!

         This proof can be established algebraically as well as geometrically.  If a solution is fully rational, then (m/p)ⁿ + (q/r)ⁿ = (s/t)ⁿ

        mⁿ.rⁿ.tⁿ + qⁿ.pⁿ.tⁿ = sⁿ.pⁿ.rⁿ     (multiply through by the product of the bases - pⁿ.rⁿ.tⁿ)

        (mrt)ⁿ + (qpt)ⁿ = (spr)ⁿ

      But this is impossible since Fermat's Last Theorem stated that xⁿ + yⁿ ≠ zⁿ

        ∴ One of the terms in the equation is not rational.

         This means that the nth root of any rational number that can be expressed as the sum of the nth roots of two rational numbers, must be irrational.  For example the cubed root of 2 (13 + 13) is irrational and the cubed root of a quarter (which is twice a half cubed) is irrational and therefore that of four is also irrational, since rationalizing the denominator gives the cubed root of four divided by four and then if the cubed root of four was a rational number than the cubed root of a quarter would be that number divided by four, another rational number!  Since the cubed root of a quarter is irrational this cannot be so, and the irrationality of the cubed root of four is established.  This can be a very powerful tool for proving the irrationality of the roots of numbers.

Triangular Combinations

          During my work on polynomial expansions, I came across this pleasing result.  Enjoy!

                    ²C₂ = 1

                            = (2 - 1)

                    Assuming that ^kC₂ = 1 + 2 + ... + (k - 1),

                    To prove that ^{k + 1}C₂ = 1 + 2 + ... + k,

                    Note that to choose 2 from a set with 1 more item than the previous, we simply include the new item and find the number of combinations of two that include that item.  The new sets contain the number in the old set, each combined with the new item, and hence we simply add k.  So:

                     ^{k + 1}C₂ = ^kC₂ + k

                                   = 1 + 2 + ... + (k - 1) + k    (as required)

                     ∴ if true for k, it is true for k + 1

                     But it is true for 2, so it is true for 2 + 1 = 3, 3 + 1 = 4 and so on for all integers > 2

                     ∴ By induction, all combinations of 2, in a set of x, are the triangular number for n = x - 1

General Polynomial Expansion

          This idea came to me while reading "Basic Concepts of Probability and Statistics -Second Edition," written by J. L. Hodges, Jr. and E. L. Lehmann It is based on the idea that the general binomial expansion is not general enough as it only allows for those expansions involving two initial terms.  To expand the current process (excuse the pun), we can simply look over how the original formula was obtained.  In the binomial expansion, we express (a₁ + a₂)ⁿ, as (a₁ + a₂)(a₁ + a₂)(a₁ + a₂)..., then choose a term from each of the n sets, to obtain a result where the terms are given with each possibility of combinations of powers on the two terms, the sum of the powers being n.  The coefficients of each term in the expansion is then given by the number of ways each term can be chosen from by taking one term from each bracket.  This gives the well known result:

                                        _n

                    (a₁ + a₂)ⁿ = ∑   ⁿC_ka₁^{n - k}a₂^k

                                      ^{k = 0} 

          The same principal can be applied to obtain the general polynomial expansion.  Thus, to expand (a₁ + a₂ + a₃ + … + a_x)ⁿ, we first must look at the process as that of choosing n terms, with replacement, from the set E = {a₁, a₂, a₃, …, a_x}.  From this we achieve all possible combinations of a₁^p, a₂^q, a₃^r, ..., a_x^x where q + r + s + ... + x = n.  By first choosing the objects of E that correspond to the power of a₁, then those for a₂, and so on through to a_x, we find the number of ways this particular term can be extracted, and thus the coefficient on the term in the expansion.  Thus, the coefficient on a₁^pa₂^qa₃^r...a_x^x in (a₁ + a₂ + a₃ + … + a_x)ⁿ is given by:

                    ⁿC_p.^{n - p}C_q.^{n – (p + q)}C_r...^{n – (p + q + r + …)}C_x

          From this we can observe that changing the position of a power (i.e. having a^qb^p, instead of a^pb^q), should not change the coefficient.  This corresponds to the intuitive notion that selecting p objects from a group of n objects, then choosing another set of q objects should have the same number of possibilities as if the q objects were chosen first, since the end result of two sets of p and q objects is the same.  Algebraically:

                    ⁿC_q.^{n - q}C_p = n! / q!(n - q)! . (n - q)! / p!(n - q - p)!

                                       = n! / q!p!(n - p - q)!

                    ⁿC_p.^{n - p}C_q = n! / p!(n - p)! . (n - p)! / q!(n - p - q)!

                                       = n! / p!q!(n - q - p)!

                                       = ⁿC_q.^{n - q}C_p                    (as required)

                     This then carries on to any rearrangement of powers as the first can then be expressed as (p + q) for further coefficients.  Notice, that when the sum of the powers reach n, subsequent coefficients will be equal to 1 (by definition of ⁿC_n), and subsequent powers (which must equal 0 to keep the sum of powers at n) will contribute nothing to the product (simply multiplying the current coefficient by 1)

          We can also determine a few properties of this expansion that relate to those found in the specific case for binomial expansions.  We determined in the binomial expansion that the sum of the coefficients is equal to 2ⁿ, by setting x = 1 in the expansion of (1 + x)ⁿ.  Similarly, by setting a₁ = a₂ = a₃ = ... = a_x = 1 in the polynomial expansion we find that the coefficients of the polynomial expansion sum to xⁿ.

          Another property studied in binomial theorem is that of maximum coefficients.  In the polynomial expansion there are ^xC₂ local maximums that exist between each pair of terms in the original, unexpanded form.  This can be represented by writing out the terms in the expansion in a set of rows, each containing all terms possible for each successive term of the unexpanded form, disregarding any terms that appear in previous rows.  When such a list is compiled (as below), generally, no row will contain more than one local maximum (see below for the exceptions).

                    a₁ⁿ, a₁^{n - 1}a₂, a₁^{n - 1}a₃, ..., a₁^{n - 1}a_x, a₁^{n - 2}a₂², a₁^{n - 2}a₃², ..., a₁^{n - 2}a_x², a₁^{n - 2}a₂a₃, ...

                    a₂ⁿ, a₂^{n - 1}a₃, a₂^{n - 1}a₄, ..., a₂^{n - 1}a_x, a₂^{n - 2}a₃², a₂^{n - 2}a₄², ..., a₂^{n - 2}a_x², a₂^{n - 2}a₃a₄, ...

                    a₃ⁿ, a₃^{n - 1}a₄, a₃^{n - 1}a₅, ..., a₃^{n - 1}a_x, a₃^{n - 2}a₄², a₃^{n - 2}a₅², ..., a₃^{n - 2}a_x², a₃^{n - 2}a₄a₅, ...

                    ...

                    a_{x - 1}ⁿ, a_{x - 1}^{n - 1}a_x, a_{x - 1}^{n - 2}a_x², ..., a_{x - 1}a_x^{n = 1}

                    a_xⁿ

          Of these maximums, if we define the largest term of the expression in unexpanded form as the term with the largest coefficient, for the m largest terms that are equal, there are mC₂ absolute maximums which are all equal.  Absolute maximums will only appear on the list in the rows for those original largest terms (Note: unless the last of these has a maximum when its power is n, its corresponding row on the list will not contain a maximum as they appear earlier in the list).  If there are only one or two largest terms then there is a unique absolute maximum between the largest two terms (whether the terms are equal or not), appearing in the list in the row of higher (in appearance) of the two largest terms.

          For either type of maximum, they may not always be mutually explicit.  As we have double and triple roots of polynomials, we also have poly-ple maximums of polynomial expansions.  This may occur when the local maximum between two terms is given when one of the powers is equal to 0 and the another set of two terms, having a term in common (that did not have a power of 0 at the local maximum) with the first set has its other term given a power of 0.  This also occurs with equal terms, a special result of which we discussed, which is when absolute maximums occur.  When these occur, the term appearing higher on the list will include the local maximum in its row, and this term will be ignored in the latter terms row.  This may lead to an exception of the rule stated above that no row will contain more than one maximum, as there may exist a set of maximums that are common to a few rows.

          The expansion list above, when fully expanded for any values of x and n, will actually form an odd sided triangle.  This reflects the following method for finding the number of terms in an expansion, which, for simplicity, will here be denoted as t(x, n).  This can be seen as a function which takes the input of x number of starting terms, and n the power of the expansion, outputting t the number of terms in the expanded (and simplified via gathering like terms) form.  In order to find the value for t given by a specific set of inputs, we use the following identities:

                    1.  t(x, n) = t(x - 1, n) + t(x - 1, n - 1) + ... + t(x - 1, 0)

                    2.             = t(x - 2, n) + 2t(x - 2, n -1) + ... + (k + 1)t(x - 2, n - k) + ... + (n + 1)t(x - 2, n - n = 0)

                    3.  t(2, n) = n + 1

                    4.  t(1, n) = 1

                    5.  t(0, n) = 0

                    6.  t(x, 0) = 1

                    7.  t(x, 1) = x

          The first two equations are derived from the fact that an expression can be represented by taking one of the terms, a_k, out and, for each power from 0 to n of this term, multiplying by the expansion of the remaining terms to the conjugate power, or n minus the power on a_k.  The second equation is found through a second application on the first and a gathering of like terms.  The other formulas are given by previously recognised relations; respectively, binomial expansions, power of a single term, power of empty set, taking the power of 0, and 1.  By subsequent applications of the first two equations, one can reduce the expression to a set of the other five, and evaluate.  For elaboration, look over the following examples.

Example 1

          Find the number of terms in the general trinomial expansion, in terms of the power.

          t(x, 3) = t(2, n) + t(2, n - 1) + t(2, n - 2) + ... + t(2, 0)      (by equation 1)

                     = n + 1 + n + n - 1 + ... + 1                          (by equations 2 & 6)

          which is the triangular number  for n + 1.  As proven by induction on series, this is given by:

          ((n + 1)2 + (n + 1)) / 2 = (n2 + 2n + 2) / 2

Example 2

          Find the number of terms in a quadratic expansion in terms of the number of initial terms.

          t(x, 2) = t(x - 2, 2) + 2t(x - 2, 1) + 3t(x - 2, 0)                (by equation 1)

                     = t(x - 2, 2) + 2(x - 2) + 3                           (by equations 6 & 7)

                     = t(x - 2, 2) + 2x - 1

           This will continue, adding 2(x - 2k) + 3 for each of the k applications, until x - 2k is equal to 2 or 1 which can be solved by means of equations 3 & 4.  The number of applications required by this process is given by:

          1 + 2k = x (if x is odd)   OR    2 + 2k = x (if x is even)

                  k = (x - 1) / 2                            k = (x - 2) / 2

          This leads to the result (from working above):

                                     _{(x - 1) / 2}

          t(x, 2) = t(1, 2) +    ∑    [2(x - 2k) + 3]       (if x is odd)

                                      ^{k = 1}

                     = 1 + {the sum above}              (by equation 4)

                                       OR

                                    _{(x - 2) / 2}

          t(x, 2) = t(2, 2) +   ∑    [2(x - 2k) + 3]       (if x is even)

                                     ^{k = 1}

                     = 3 + {the sum above}               (by equation 3)

          Note: The result for even x could have been obtained using an extra application and equation 5 as follows:

                                     _{x / 2}

          t(x, 2) = t(0, 2) +  ∑  [2(x - 2k) + 3]

                                    ^{k = 1}

                     = 0 + {the sum above}               (by equation 5)

          So for the last value of k, 2(x - 2k) + 3 = 3, we can see why by the following result:

                2(x - 2k) + 3 = 3
                      2(x - 2k) = 0
                                  k = x / 2    (which is true for the last value of k)