Chaitanya's Random Pages

August 28, 2015

The discriminant trick

Filed under: mathematics — ckrao @ 12:22 pm

Suppose you wish to find the maximum value of y =\frac{8}{2x+1} - \frac{1}{x} for x > 0. One way to do this without calculus is to massage the expression until one can apply an elementary inequality such as u + \frac{1}{u} \geq 2. To apply this particular result we aim to minimise 1/y and apply polynomial division.

\begin{aligned}  \frac{1}{y} &= \frac{1}{\frac{8}{2x+1} - \frac{1}{x}}\\  &= \frac{x(2x+1)}{8x - (2x+1)}\\  &=\frac{2x^2+x}{6x-1}\\  &= \frac{(6x-1)(x/3 + 2/9) + 2/9}{6x-1}\\  &= \frac{1}{9}\left( 3x+2 + \frac{2}{6x-1} \right)\\  &= \frac{1}{9}\left( \frac{5}{2} + \frac{6x-1}{2} + \frac{2}{6x-1} \right)\\  &\geq \frac{1}{9}\left(\frac{5}{2} + 2 \right)\\  &= \frac{1}{9}\left(\frac{9}{2}\right)\\  &= \frac{1}{2}\quad\quad \quad \quad \quad (1)  \end{aligned}

In the above steps we assume 6x-1 > 0, otherwise y is non-positive for x > 0. Hence y \leq 2 with equality when \frac{6x-1}{2} = 1 or x = 1/2.

Another elementary way that applies to quotients of quadratic polynomials is to re-write the expression as a quadratic in x:

\begin{aligned}  y &= \frac{8}{2x+1} - \frac{1}{x}\\  x(2x+1)y &= 8x - (2x+1)\\  2x^2y + (y-6)x + 1 &= 0.\quad \quad \quad \quad \quad \quad (2)  \end{aligned}

For fixed y this quadratic equation will have 0, 1 or 2 solutions in x depending on whether its discriminant is negative, zero, or positive respectively. At any maximum or minimum value y_0 of the function, the discriminant will be zero since on one side of y_0 the quadratic equation will have a solution (discriminant non-negative) while on the other it will not (discriminant negative). In the image below a maximum is reached at y_0 = 2 while it is of opposite signs either side of this.

discriminant

Hence setting the discriminant of the left side of (2) to 0, (y-6)^2 - 4(2y) = 0 from which y^2 - 20y + 36 = (y-18)(y-2) = 0. Hence extrema are at y=2 and y = 18. We can solve (y-18)(y-2) \geq 0 to find that y \leq 2 or y \geq 18 is the range of the function y = \frac{8}{2x+1} - \frac{1}{x}. This tells us that y = 2 is a local maximum (illustrated above) and y = 18 is a local minimum (occurring when x < 0).

fullplot

One advantage of this method is that unlike elementary calculus, one bypasses the step of finding the corresponding x value (i.e. by solving dy/dx = 0) before substituting this into the function to find the extremum value for y.

Another advantage is that the equation need not be polynomial in y. For example below is a plot of x^2 + 4x\sin y + 1 = 0. Using the above-mentioned discriminant trick we solve 16 \sin^2 y - 4 \geq 0 and find the range of the function is when \displaystyle \sin^2 y \geq 1/4, or y \in \bigcup_{k \in \mathbb{Z}} [k\pi + \pi/6, k\pi + 5\pi/6] . Below is a plot confirming this using WolframAlpha.

x^2+4xsiny

The reader is encouraged to try out other examples, for example this method should work for any equation of the form \displaystyle h(y) = \frac{ax^2 + bx + c}{dx^2 + ex + f} where h is a continuous function of y. Of course one should also take care in noting when the function is defined before cross-multiplying.

Further Reading

[1] Finding the range of rational functions – Mathematics Stack Exchange

[2] Find Range of Rational Functions – analyzemath.com

[3] Critical point (mathematics): Use of the discriminant – Wikipedia, the free encyclopedia

July 30, 2015

Nineteenth century non-avian dinosaur discoveries

Filed under: nature,science — ckrao @ 11:05 am

Below is an attempted chronological list of non-avian dinosaur discoveries of the 19th century that today are considered valid genera. There may still be some where there are only scant remains of the fossil (e.g. a tooth or single bone remain). The list came from [1] with some help from [2] and Wikipedia to filter out doubtful names. Many of the best known dinosaurs are listed here and it looks like most of the major groups are covered. Good histories of dinosaur paleontology are in [3] and [4].

 

Genus Discoverer Year Dinosaur type
Megalosaurus Buckland 1824 tetanuran (stiff-tailed) theropod
Iguanodon Mantell 1825 beaked ornithopod
Streptospondylus von Meyer 1830 megalosaurid
Hylaeosaurus Mantell 1833 armoured
Thecodontosaurus Riley & Stutchbury 1836 prosauropod
Plateosaurus von Meyer 1837 prosauropod
Poekilopleuron Eudes-Deslongchamps 1838 megalosaurid
Cardiodon Owen 1841 sauropod
Cetiosaurus Owen 1841 sauropod
Pelorosaurus Mantell 1850 brachiosaur
Aepisaurus Gervais 1852 sauropod
Oplosaurus Gervais 1852 sauropod
Massospondylus Owen 1854 prosauropod
Nuthetes Owen 1854 maniraptoran
Troodon Leidy 1856 raptor
Stenopelix von Meyer 1857 pachycephalosaur
Astrodon Johnston 1858 sauropod
Hadrosaurus Leidy 1858 duckbilled ornithopod
Compsognathus J. A. Wagner 1859 coelurosaur (fuzzy theropod)
Scelidosaurus Owen 1859 armoured
Echinodon Owen 1861 heterodontosaurid (early bird-hipped dinosaur)
Polacanthus Owen vide [Anonymous] 1865 armoured
Calamospondylus Fox 1866 oviraptorosaur
Euskelosaurus Huxley 1866 prosauropod
Acanthopholis Huxley 1867 armoured
Hypselosaurus Matheron 1869 sauropod
Hypsilophodon Huxley 1869 beaked ornithopod
Rhabdodon Matheron 1869 beaked ornithopod
Ornithopsis Seeley 1870 sauropod
Struthiosaurus Bunzel 1870 armoured
Craterosaurus Seeley 1874 stegosaurian
Chondrosteosaurus Owen 1876 sauropod
Macrurosaurus Seeley 1876 sauropod
Allosaurus Marsh 1877 carnosaur
Apatosaurus Marsh 1877 sauropod
Camarasaurus Cope 1877 sauropod
Dryptosaurus Marsh 1877 tyrannosaur
Dystrophaeus Cope 1877 sauropod
Nanosaurus Marsh 1877 early bird-hipped dinosaur
Stegosaurus Marsh 1877 plated dinosaur
Diplodocus Marsh 1878 sauropod
Brontosaurus Marsh 1879 sauropod
Anoplosaurus Seeley 1879 armoured
Coelurus Marsh 1879 coelurosaur (fuzzy theropod)
Mochlodon Seeley 1881 beaked ornithopod
Craspedodon Dollo 1883 horned dinosaur
Ceratosaurus Marsh 1884 theropod
Anchisaurus Marsh 1885 prosauropod
Camptosaurus Marsh 1885 beaked ornithopod
Aristosuchus Seeley 1887 coelurosaur (fuzzy theropod)
Ornithodesmus Seeley 1887 raptor
Cumnoria Seeley 1888 beaked ornithopod
Priconodon Marsh 1888 armoured
Coelophysis Cope 1889 early theropod
Nodosaurus Marsh 1889 armoured
Triceratops Marsh 1889 horned dinosaur
Barosaurus Marsh 1890 sauropod
Claosaurus Marsh 1890 duckbilled ornithopod
Ornithomimus Marsh 1890 ostrich dinosaur
Ammosaurus Marsh 1891 prosauropod
Torosaurus Marsh 1891 horned dinosaur
Argyrosaurus Lydekker 1893 sauropod
Sarcolestes Lydekker 1893 armoured
Dryosaurus Marsh 1894 beaked ornithopod

References

[1] Dinosaur Genera List – http://www.polychora.com/dinolist.html

[2] Genus List for Holtz (2007) Dinosaurshttp://www.geol.umd.edu/~tholtz/dinoappendix/HoltzappendixWinter2011.pdf

[3] Benton, M. J. 2000. A brief history of dinosaur paleontology. Pp. 10-44, in Paul, G. S. (ed.), The Scientific American book of dinosaurs. St Martin’s Press, New York. – http://palaeo.gly.bris.ac.uk/Essays/dinohist.html

[4] Equatorial Minnesota The generic history of dinosaur paleontology 1699 to 1869 – http://equatorialminnesota.blogspot.com.au/2014/06/the-generic-history-of-dinosaur.html

July 25, 2015

Compositions of positive integers where adjacent parts have different parity

Filed under: mathematics — ckrao @ 5:39 am

Here is an interesting problem based on one I found in the 2008 AIME (Q11).

How many compositions of the positive integer n have adjacent parts with different parity?

For example, a valid composition of n=14 is

14 = 1 + 2 + 5 + 2 + 1 + 2 + 1,

since the 1,2,5,2,1,2,1 alternate between being odd and even.

The first terms of the sequence are (OEIS A062200)

1, 1, 3, 2, 6, 6, 11, 16, 22, 37, 49, 80, …

Interestingly the sequence decreases between n=3 and 4 since the only valid compositions of 4 are 4 = 1 + 2 + 1 and 4, while 3 = 1 + 1 + 1 = 2 + 1 = 1 + 2.

Here is the first approach I came up with to solve the problem. Let a_n be the number of such compositions starting with an even number and let b_n be the number of compositions starting with an odd number. We wish to find t_n := a_n + b_n. We identify four cases:

  • If n is odd and the composition starts with an even number 2c, we remove that even number and have a composition of n-2c starting with an odd number. Summing over choices of c,
    a_{2k+1} = b_{2k-1} + b_{2k-3} + \ldots + b_1. \quad (1)
  • If n is odd and the composition starts with an odd number 2c+1, we either have the single term composition n, or we remove that odd number and have a composition of n-(2c+1) starting with an even number. Summing over choices of c,
    b_{2k+1} = 1 + a_{2k} + a_{2k-2} + \ldots + a_2. \quad (2)
  • If n is even  and the composition starts with an even number 2c, we either have the single term composition n, or we remove that even number and have a composition of n-2c starting with an odd number. Summing over choices of c,
    a_{2k} = 1 + b_{2k-2} + b_{2k-4} + \ldots + b_2. \quad (3)
  • If n is even and the composition starts with an odd number 2c+1, we remove that odd number and have a composition of n-(2c+1) starting with an even number. Summing over choices of c,
    b_{2k} = a_{2k-1} + a_{2k-3} + \ldots + a_1.\quad (4)

Recursions (1)-(4) with the initial conditions a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0 allows us to generate the following table.

n 1 2 3 4 5 6 7 8 9 10 11 12
a_n 0 1 1 1 3 2 6 6 11 16 22 37
b_n 1 0 2 1 3 4 5 10 11 21 27 43
t_n 1 1 3 2 6 6 11 16 22 37 49 80

After writing out some terms I noticed the pattern

\displaystyle a_n = a_{n-2} + b_{n-2} \text{ and } b_n = a_{n-1} + b_{n-2}.\quad \quad (5)

I later saw why this is so. Firstly, a composition of n that starts with an even number can be obtained from any composition of n-2 by adding 2 to the first term if even or inserting 2 at the start if odd. Hence a_n = t_{n-2} = a_{n-2} + b_{n-2}. For the second relation, if the composition of n starts with an odd number, it either is 1 plus an even-starting composition of n-1 or it can be obtained from an odd-starting composition of n-2 by adding 2 to the first term. Hence b_n = a_{n-1} + b_{n-2}.

 From (5) and using t_n = a_n + b_n we find that

\begin{aligned}  t_n &= a_n + b_n\\  &= t_{n-2} + (a_{n-1} + b_{n-2})\\  &= t_{n-2} + t_{n-3} + t_{n-2} - a{n-2}\\  &= 2t_{n-2} + t_{n-3} - t_{n-4}.\quad \quad (6)  \end{aligned}

Together with the initial terms t_1 = 1, t_2 = 1, t_3 = 3, t_4 = 2, (6) enables us to generate our desired terms without requiring a_n or b_n.

The OEIS page also gives the following expression for t_n:

\displaystyle t_n = \sum_{k=0}^{n+1} \binom{n-k+1}{3k-n+1}.\quad \quad (7)

Here is how to show this result, with help from the solution at AoPS here. For ease of exposition convert the problem to one of binary strings: we require the number of length-n 0-1 strings so that maximal continguous blocks of 1s have even length and maximal contiguous blocks of 0s have odd length.

Suppose there are b maximal blocks of 0s. All but the last such block must necessarily be followed by a pair of 1s. That is, the string has the form

\displaystyle [....][....0][11....][....0][11....] \ldots [....0][....],

where blocks enclosed by [] contain the same digit (0 or 1) and 0 or more pairs of digits are in place of the sets of four dots. We have shown 2b+1 blocks above but the first and last may be empty.

Let k = (n-b)/2, which is the number of pairs of digits to use after b 0s are used (noting that n-b must be even). We have b 0s used above along with b-1 pairs of 1s. Therefore (n-(b + 2(b-1)))/2 pairs of 0s or 1s need to inserted into the 2b+1 blocks above. The blocks that they end up determine whether they are 0 or 1.

Now x pairs can be inserted into y blocks in \binom{x+y-1}{x} ways, since we write out x+y-1 symbols in a row and choose x of them to be pairs, with the remaining symbols representing separators between blocks. In our case,

x = \frac{n-(b + 2(b-1))}{2}, y = 2b+1 and b = n-2k, so

\begin{aligned}  x &= \frac{n-3b+2}{2}\\  &= \frac{n-3n+6k+2}{2}\\  &= 3k-n+1,\end{aligned}

and x+y-1 = 3k-n+1 + 2(n-2k) + 1 = n-k+1.

Summing over choices of k gives (7) as desired. Note that some of the terms will be 0 as k ranges from 0 to n+1.

For example, when n=11 and 12, we have

\displaystyle t_{11} = \binom{8}{2} + \binom{7}{5} = 28 + 21 = 49,

\displaystyle t_{12} = \binom{9}{1} + \binom{8}{4} + \binom{7}{7} = 9 + 70 + 1= 80,

matching the values given in the table above.

 

June 30, 2015

The Pakistan heat wave of 2015

Filed under: climate and weather — ckrao @ 11:39 am

This month a heatwave has killed over 1500 people in Pakistan, most of them in Karachi. Here are the temperatures recorded at Karachi airport at that time: note that the average for this time of year is 28-35°C with high humidity. Rarely does the temperature reach 39.5°C three days in a row but here it did so six days in a row plus there seemed to be no relief at night.

Date 16-Jun 17-Jun 18-Jun 19-Jun 20-Jun 21-Jun 22-Jun 23-Jun 24-Jun
Min (°C) 30 29.3 29.5 31 31.6 33 33 33 30.5
Max (°C) 36 38.5 39.5 40.5 44.8 42.5 42.5 41.2 37

Most of the dead were homeless and it was also during the time of Ramadan where fasting is observed during daylight hours. This and the recent heatwave in India are two of the three most fatal on the Indian subcontinent in recent times.

References

[1] Temperatures: http://www.ogimet.com/cgi-bin/gsynres?lang=en&ind=41780&ano=2015&mes=6&day=30&hora=6&min=0&ndays=30 [2] Average Weather For Karachi, Pakistan – WeatherSpark [3] Dr. Jeff Masters’ WunderBlog: Pakistan’s Deadliest Heat Wave on Record Kills at Least 800: Weather Underground [4] News: Majority of Karachi heatwave victims were homeless minister – The Express Tribune

June 22, 2015

Places we see powers of 2

Filed under: mathematics — ckrao @ 11:44 am

Here are some obvious and less obvious places where we encounter the sequence f(n) = 1,2,4,8,16,.... Most of these come from the corresponding OEIS page.

  • as a solution to the recurrence f(n+1) = 2f(n), f(0) = 1.
  • the number of subsets of a n-element set: To each element there are two choices – to include it or not include it in the subset. Hence there are 2\times 2\times \ldots \times 2 = 2^n subsets.
  • the sum of the numbers in the n’th row of Pascal’s triangle This is a consequence of the binomial theorem applied to (1+1)^n = \sum_{i=0}^n \binom{n}{i}.
  • the sum of the coefficients of (x+1)^n, which is the sum of binomial coefficients
  • the number of even or odd-sized subsets of an (n+1)-element set, i.e. \sum_{i=0}^{\lfloor{(n+1)/2}\rfloor} \binom{n+1}{2i} = \sum_{i=0}^{\lfloor{n/2}\rfloor} \binom{n+1}{2i+1} = 2^n, a consequence of the binomial theorem (1-1)^n = \sum_{i=0}^n (-1)^i \binom{n}{i}.
  • each term in the sequence is the smallest natural number that is not the sum of any number of distinct earlier terms, an example of a sum-free sequence
  • the sequence forms the set of every natural number that is not the sum of 2 or more consecutive positive integers: Such a sum has the form a + (a+1) + \ldots + (a+ k) = (2a + k)(k+1)/2. If this were a power of 2 then (2a+k) and (k+1) must both be powers of 2 greater than or equal to 2. But their difference 2a-1 is odd, which is impossible for the difference of even powers of 2. Conversely if a natural number is not a power of two it is of the form 2^m d where d is an odd number at least 3. Then 2^m d may be written as the sum of either d consecutive positive integers with middle (mean) term 2^m (if (d+1)/2 \leq 2^m) or 2^{m+1} consecutive positive integers with mean d/2 (if 2^m < d/2). For example, 48 = 2^4\times 3 and 48 = 15 + 16 + 17 while 44 = 2^2\times 11 and 44 = 2+3+4+5+6+7+8+9.
  • the number of ordered partitions of n+1 is 2^n: for example, the eight ordered partitions of 4 are: 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3, 4 To see why this result is true, imagine n+1 items in a row. Imagine separating them with dividers so that the number of items between each divider gives us the ordered partition. For example with 4 items we may place a divider between the third and fourth item to give the partition 3+1. We have n possible locations for dividers (between any adjacent items) and each location has a choice of being assigned to a divider or not. This leads to 2^n possible partitions. Alternatively, an ordered partition of n+2 may be derived inductively from an ordered partition of n+1 = a_1 + \ldots + a_k by either forming n+2 = 1 + a_1 + \ldots + a_k or n+2 = (a_1+1) + a_2 + \ldots + a_k. Also any ordered partition of n+2 has one of these forms as we may form from it an ordered partition of n+1 by either subtracting 1 from the first element of the partition (if it is greater than 1) or deleting the first element if it is 1. Hence the number of partitions doubles as n+1 is increased by 1 and for n = 1 we have the single partition.
  • the number of permutations of {1,2,...,n+1} with exactly one local maximum: for example, for n=3 we have the permutations 1234, 1243, 1342, 2341, 1432, 2431, 3421, 4321. Here we have the highest element n+1 somewhere and there are 2^n possible subsets of {1,2,...,n} that we may choose to precede it. These elements must be in ascending order, while the elements after n+1 are in descending order to ensure exactly one local maximum at n+1. Hence the order of terms is determined once the subset is chosen and we have 2^n permutations.
  • the number of permutations of n+1 elements where no element is more than one position to the right of its original place: for example, for n=3 the allowed permutations are 1234, 1243, 1324, 1423, 2134, 2143, 3124, 4123. This can be seen inductively: if a_1a_2\ldots a_{n+1} is a valid permutation of n+1 elements, then 1(1+a_1)(1+a_2)\ldots (1+a_{n+1}) and (1+a_1)1(1+a_2)\ldots (1+a_{n+1}) are valid permuations of n+2 elements. Also any valid (n+2) element permutation is of this form as it may be reduced to a valid (n+1) element permutation by deleting the 1 (which must occur in either the first or second position) and subtracting 1 from every other element. This describes a one to two mapping between valid permutations of n+1 and n+2 elements. Finally for 1 element there is 1 = 2^0 allowed permutation, so the result follows by induction.

May 31, 2015

Test pace bowlers to have conceded 100 runs in an innings the most

Filed under: cricket,sport — ckrao @ 10:16 am

 

Below is a list of pace bowlers who have conceded 100 or more runs in an innings at least 14 times (* indicates active players).

Name Tests Innings Bowled Wickets times conceded 100 runs innings per century
Botham 102 168 383 31 5.42
Kapil Dev 131 227 434 25 9.08
Ntini 101 190 390 23 8.26
Hadlee 86 150 431 21 7.14
Caddick 62 105 234 20 5.25
Imran Khan 88 142 362 20 7.1
M Johnson* 64 123 283 20 6.15
Vaas 111 194 355 20 9.7
Lillee 70 132 355 19 6.95
McDermott 71 124 291 19 6.53
I Sharma* 61 107 187 18 5.94
Anderson* 104 194 401 17 11.41
Gough 58 95 229 17 5.59
Srinath 67 121 236 17 7.12
F Edwards 55 97 165 16 6.06
Lawson 46 78 180 16 4.88
Mohammad Sami 36 66 85 16 4.13
Sarfraz Nawaz 55 95 177 16 5.94
Hoggard 67 122 248 15 8.13
Lee 76 150 310 15 10
Martin 71 126 233 15 8.4
Morrison 48 76 160 15 5.07
Steyn* 78 147 396 15 9.8
Bedser 51 92 236 14 6.57
Z Khan 92 165 311 14 11.79

 

Here are the numbers for remaining pace bowlers with at least 200 test wickets (Ray Lindwall a stand-out here):

Name Tests Innings Bowled Wickets times conceded 100 runs innings per century
Waqar Younis 87 154 373 13 11.85
Harmison 63 115 226 13 8.85
Wasim Akram 104 181 414 12 15.08
McKenzie 60 113 246 12 9.42
Cairns 62 104 218 12 8.67
Walsh 132 242 519 11 22
Sobers (not always pace) 93 159 235 11 14.45
Snow 49 93 202 11 8.45
Broad 79 143 285 11 13
Donald 72 129 330 10 12.9
Pollock 108 202 421 10 20.2
Willis 90 165 325 10 16.5
Hughes 53 97 212 10 9.7
Thomson 51 90 200 10 9
McGrath 124 243 563 9 27
Trueman 67 127 307 9 14.11
Statham 70 129 252 8 16.13
Flintoff 79 137 226 8 17.13
Streak 65 102 216 8 12.75
Roberts 47 90 202 8 11.25
Morkel 62 117 217 7 16.71
Gillespie 71 137 259 6 22.83
Marshall 81 151 376 5 30.2
Holding 60 113 249 5 22.6
Garner 58 111 259 4 27.75
Kallis 166 272 292 4 68
Lindwall 61 113 228 1 113

The numbers are generally higher for spin bowlers – the top six centurions overall are all spin bowlers:

Muralitharan (61), Kumble (57), Harbhajan Singh (43), Warne (40), Kaneria (39), Vettori (34).

References

[1] Bowling records:  Test matches:  Cricinfo Statsguru – ESPN Cricinfo

[2] Records:  Test matches:  Bowling records:  Most wickets in career – ESPN Cricinfo

May 24, 2015

A collection of proofs of Ptolemy’s Theorem

Filed under: mathematics — ckrao @ 11:39 am

Here we collect some proofs of the following nice geometric result.

If ABCD is a quadrilateral, then AB.CD + BC.DA \geq AC.BD with equality if ABCD is cyclic.

Ptolemy

In words, the sum of the product of the lengths of the opposite sides of a quadrilateral is at least the product of the lengths of its diagonals.

The equality for a cyclic quadrilateral is known as Ptolemy’s theorem while the more general inequality applying to any quadrilateral is called Ptolemy’s inequality. Many of the proofs below that establish Ptolemy’s theorem can be modified slightly to prove the inequality.

Proofs of Ptolemy’s Theorem

Proof 1:

Choose point P on line CD extended beyond D as shown so that \angle DAP = \angle BAC.

Ptolemy2

Then

a) \triangle ABC \sim \triangle ADP (\angle ABC = \angle ADP and \angle BAC = \angle DAP).

b) \triangle BAD \sim \triangle CAP (\angle BAD = \angle CAP and \angle ADB = \angle APC).

From a) BC.DA = BA.DP so AB.CD + BC.DA = AB(CD + DP) = AB.CP = AC.BD by b) and we are done.

Proof 2: (a slightly different choice of constructed point)

Let K be the point on AC so that \angle CBK = \angle ABD.

Ptolemy3

Then

a) \triangle ABD \sim \triangle KBC (\angle ABD = \angle KBC and \angle BDA = \angle BCK) so KC = AD.BC/BD.

b) \triangle ABK \sim \triangle DBC (\angle ABK = \angle DBC and \angle KAB = \angle CDB) so AK = DC.AB/DB.

Adding the two gives AC = (AD.BC + DC.AB)/BD or AC.BD = AD.BC + DC.AB as required.

Proof 3: (ref: http://mathafou.free.fr/themes_en/kptol.html)

Let the diagonals AC, BD intersect at P and construct E on the circumcircle so that CE is parallel to BD. A short angle chase shows that BCED is an isosceles trapezium.

Ptolemy5

Then \sin \angle ABE = \sin \angle ACE = \sin \angle BPC (angles on common arc AE and using BD \parallel CE). Also triangles BDE and BDC have the same base and height and hence the same area.

Hence the area of ABCD is the sum of the areas of triangles ABE and ADE, or

\begin{aligned}  & \frac{1}{2} \left( AB.BE\sin \angle ABE + AD.DE\sin \angle ADE \right)\\  &= \frac{1}{2} \left( AB.BE\sin \angle ABE + AD.DE\sin \angle ABE \right) \quad \text{as } \angle ABE \text{ and } \angle ADE \text{ are supplementary }\\  &= \frac{1}{2} \left( AB.BE+ AD.DE \right)\sin \angle ABE\\  &= \frac{1}{2} \left(AB.CD + AD.BC \right)\sin \angle ABE, \quad (1)  \end{aligned}

where the last step follows from BDEC being an isosceles trapezium.

But also this area is \frac{1}{2} AC.BD\sin \angle BPC and recall from above that \sin \angle BPC = \sin \angle ABE. Therefore equating this with (1) we end up with AB.CD + AD.BC = AC.BD.

Proof 4 (ref: [1])

Here three of the triangles of the cyclic quadrilateral are scaled to fit together to form a parallelogram. Namely,

  • \triangle ABD is scaled by AC,
  • \triangle ABC is scaled by AD,
  • \triangle ACD is scaled by AB.

A simple angle chase based on the coloured angles shown reveals that a parallelogram is formed when the triangles are joined together. Ptolemy’s theorem then follows from equating two of its opposite side lengths.

Ptolemy7

Proof 5: (from here)

Using the cosine rule in triangles ABC and ADC respectively gives

AC^2 = AB^2 + BC^2 - 2AB.BC\cos \angle ABC = AD^2 + CD^2 - 2AD.CD\cos \angle ADC.

Since \angle ABC + \angle ADC = 180^{\circ}, this becomes

\begin{aligned}  AB^2 + BC^2 - 2AB.BC\cos \angle ABC &= AD^2 + CD^2 + 2AD.CD\cos \angle ABC\\  \Rightarrow \cos \angle ABC &= \frac{AB^2 + BC^2 - AD^2 - CD^2}{2(AB.BC + AD.CD)}.  \end{aligned}

Hence

\begin{aligned}  AC^2 &= AB^2 + BC^2 - 2AB.BC\cos \angle ABC\\  &= AB^2 + BC^2 - 2AB.BC \frac{AB^2 + BC^2 - AD^2 - CD^2}{2(AB.BC + AD.CD)}\\  &= \frac{(AB^2+BC^2)(AB.BC + AD.CD) - AB.BC(AB^2 + BC^2 - AD^2 - CD^2)}{AB.BC + AD.CD}\\  &= \frac{(AB^2+BC^2)(AD.CD) + AB.BC(AD^2 + CD^2)}{AB.BC + AD.CD}\\  &= \frac{AB.AD(AB.CD+BC.AD) + BC.CD(BC.AD+AB.CD)}{AB.BC + AD.CD}\\  &= \frac{(AB.AD+BC.CD)(AB.CD+BC.AD)}{AB.BC + AD.CD}.\\  \end{aligned}

By a similar argument we may write

\displaystyle BD^2 = \frac{(AB.BC + AD.CD)(BC.AD+AB.CD)}{BC.CD + AB.AD}.

Multiplying these last two equations by each other and taking the square root gives

\displaystyle AC.BD = AB.CD + BC.AD,

which is Ptolemy’s theorem.

Proof 6 (via this):

Let the angles subtended by AB, BC, CD respectively be \alpha, \beta, \gamma and let the circumradius of the quadrilateral be R. By the sine rule AB = 2R \sin \alpha, BC = 2R\sin \beta, CD = 2R \sin \gamma, AD = 2R\sin (\alpha + \beta + \gamma ), AC = 2R \sin (\alpha + \beta), BD = 2R \sin (\beta + \gamma ). Then the equality to be proved is equivalent to

\displaystyle \sin (\alpha + \beta)\sin (\beta + \gamma) = \sin \alpha \sin \gamma + \sin \beta \sin (\alpha + \beta + \gamma).

But we have

\begin{aligned}  & \sin (\alpha + \beta)\sin (\beta + \gamma)\\ &= (\sin \alpha \cos \beta + \cos \alpha \sin \beta)(\sin \beta \cos \gamma + \cos \beta \sin \gamma)\\  &= \sin \alpha \sin \beta \cos \beta \cos \gamma + \sin \alpha \cos^2 \beta \sin \gamma + \cos \alpha \sin^2 \beta \cos \gamma + \cos \alpha \sin \beta \cos \beta \sin \gamma\\  &= \sin \alpha \sin \beta \cos \beta \cos \gamma + \sin \alpha (1- \sin^2 \beta ) \sin \gamma + \cos \alpha \sin^2 \beta \cos \gamma + \cos \alpha \sin \beta \cos \beta \sin \gamma\\  &= \sin \alpha \sin \gamma + \sin \beta (\sin \alpha \cos \beta \cos \gamma - \sin \alpha \sin \beta \sin \gamma + \cos \alpha \sin \beta \cos \gamma + \cos \alpha \cos \beta \sin \gamma )\\  &= \sin \alpha \sin \gamma + \sin \beta (\sin(\alpha + \beta ) \cos \gamma + \cos (\alpha + \beta ) \sin \gamma )\\  &= \sin \alpha \sin \gamma + \sin \beta \sin (\alpha + \beta + \gamma ),  \end{aligned}

as required.

Proofs of Ptolemy’s Inequality (all make use of the triangle inequality)

Proof 7:

Denote the points A, B, C, D by vectors or complex numbers a, b, c, d. Then we have the equality

\displaystyle (a-b).(c-d) + (a-d).(b-c) = (a-c).(b-d).

Applying the modulus (length) to both sides and then the triangle inequality leads to

\displaystyle |(a-b).(c-d)| + |(a-d).(b-c)| \geq |(a-c).(b-d)|,

which is Ptolemy’s inequality.

Proof 8: (ref: [2])

Place the origin at the point D so that A, B, C are represented by the vectors a, b, c respectively. Let a' = a/|a|^2, b' = b/|b|^2, c' = c/|c|^2. Then

\begin{aligned} |a'-b'|^2 &= \left| \frac{a}{|a|^2} - \frac{b}{|b|^2}\right|^2\\  &= \frac{|a|^2}{|a|^4} + \frac{|b|^2}{|b|^4} - 2\frac{\langle a, b \rangle}{|a|^2|b|^2}\\  &= \frac{|b|^2 + |a|^2 - 2\langle a, b \rangle}{|a|^2|b|^2}\\  &= \frac{|a-b|^2}{|a|^2|b|^2}.  \end{aligned}

Similarly, |b'-c'| = \frac{|b-c|}{|b||c|} and |c'-a'| = \frac{|c-a|}{|c||a|}. By the triangle inequality, \displaystyle |a'-b'| \leq |b'-c'| + |c'-a'|, or in other words,

\begin{aligned}  \frac{|a-b|}{|a||b|} &\leq \frac{|b-c|}{|b||c|} + \frac{|c-a|}{|c||a|}\\  \Rightarrow |a-b||c| \leq |b-c||a| + |c-a||b|,  \end{aligned}

which is another way of writing Ptolemy’s inequality.

Proof 9: (inversion)

Recall that under inversion under a point P a circle passing through P maps to a line. If X, Y are points on the circle mapping to X, Y' respectively under inversion in a circle of radius R centred at P, then

\displaystyle X'Y' = R^2.XY/(PX.PY).

inversion

To see this, since XP.X'P = YP.Y'P = R^2 by the definition of the inverse, XP/YP = Y'P/X'P. This together with the fact that angle P is common implies that triangles XPY and Y'PX' are similar. This gives us the relationship X'Y' = YX.PY'/PX = XY.R^2/(PX.PY) as desired.

Ptolemy4

For our quadrilateral ABCD apply an inversion centred at D with radius R. Then A, B, C map to points A', B', C' which are collinear if ABCD is cyclic. Using the result above A'B' = AB.R^2/(DA.DB) and similarly A'C' = AC.R^2/(DA.DC) and B'C' = BC.R^2/(DB.DC). By the triangle inequality A'C' \leq AB' + BC' and so this becomes

\begin{aligned}  \frac{AC.R^2}{DA.DC} &\leq \frac{AB.R^2}{DA.DB} + \frac{BC.R^2}{DB.DC}\\  \Rightarrow AC.DB &\leq AB.DC + BC.DA,  \end{aligned}

which is Ptolemy’s inequality.

Proof 10: (ref: [3])

Construct E on AC so that EC = BC, then draw F on CD with EF \parallel AD. Finally rotate \triangle FEC about C to map to \triangle F'BC.

Ptolemy6

Then F'B = FE and by similarity of triangles ACD and ECF, FE/DA = CE/CA = CB/CA so that

(a) F'B = FE = AD.BC/CA

Secondly, \triangle DF'C \sim ABC as F'C/BC = FC/EC = DC/AC and \angle F'CD = \angle BCA. This gives

(b) DF' = AB.CD/AC

Adding (a) and (b) and applying the triangle inequality,

\displaystyle BD \leq BF' + F'D = (AD.BC + AB.CD)/AC,

from which

\displaystyle AC.BD \leq AD.BC + AB.CD

which is Ptolemy’s inequality.

References

[1] A. Bogomolny, Ptolemy Theorem – Proof Without Words from Interactive Mathematics Miscellany and Puzzles
http://www.cut-the-knot.org/proofs/PtolemyTheoremPWW.shtml, Accessed 30 May 2015

[2] W.H. Greub, Linear Algebra, Springer Science & Business Media, 2012 (p 190).

[3] C. Alsina, R. B. Nelsen, When Less is More: Visualizing Basic Inequalities, MAA, 2009.

April 30, 2015

Number of countries that have abolished the death penalty by year

Filed under: Uncategorized — ckrao @ 11:36 am

The graph below is generated from data at this Wikipedia page.

By 1978 only 20 or so countries had abolished the death penalty but over 80 countries have followed suit since. Around 36 countries still retain capital punishment in law and practice with the remaining 50+ countries inactive in its use.

deathpenalty

April 19, 2015

Distances to a line from vertices of a regular polygon

Filed under: mathematics — ckrao @ 11:01 am

If we take a regular polygon and any line through its centre, then the sum of the squares of the distances from the vertices of the polygon to the line is independent of the orientation of the line or polygon. For example, in the following two diagrams, the sum of the squares of the lengths of the 5 blue line segments is the same.

regularpolywithline

Such a result is amenable to a proof via complex numbers. Without losing generality the real number line may be our line of interest and the points of the n-sided polygon may be described by the complex numbers z_k := R\exp(2\pi i k / n + i \phi) for k = 0, 1, ..., n-1, where R is the circumradius of the polygone and \phi is an arbitrary real-numbered phase. Then the squared distance from a point to the real line is R^2\cos^2 (2\pi k / n + \phi) = \left(z_k + \overline{z_k})\right)^2/4 where \overline{z_k} = R^2/z_k. Summing this over k gives our sum of squared distances as

\begin{aligned} \frac{1}{4} \sum_{k=0}^{n-1} \left(z_k + \overline{z_k}\right)^2  &= \frac{1}{4} \sum_{k=0}^{n-1} \left(z_k^2 + 2z_k\overline{z_k} + \overline{z_k}^2\right)\\  &= \frac{1}{4} \sum_{k=0}^{n-1} \left(z_k^2 + 2R^2 + \overline{z_k}^2\right)\\  &= \frac{nR^2}{2} + \frac{1}{4} \left(\sum_{k=0}^{n-1} z_k^2 + \sum_{k=0}^{n-1} \overline{z_k}^2\right).\quad\quad(1)\end{aligned}

 Each of these sums is geometric in nature so can be simplified. For example,

\begin{aligned}\sum_{k=0}^{n-1} z_k^2 &= \sum_{k=0}^{n-1} R^2\exp(4\pi i k / n + 2i\phi)\\&= R^2 \exp(2i\phi)\sum_{k=0}^{n-1} \exp(4\pi i k / n)\\  &= \begin{cases}R^2 \exp(2i\phi)\frac{1-\exp(4\pi i n / n)}{1- \exp(4\pi i / n)}, & \text{if }\exp(4\pi i/n)\neq 1 \\  R^2 \exp(2i\phi)n, & \text{if }\exp(4\pi i/n)= 1 \end{cases}\\  &= R^2 \exp(2i\phi)\frac{1-\exp(4\pi i)}{1- \exp(4\pi i / n)}, \quad \text{as }n \geq 3\text{ means }\exp(4\pi i/n)\neq 1\\  & = 0.\quad\quad(2)\end{aligned}

Similarly, \sum_{k=0}^{n-1} \overline{z_k}^2 = 0, being the conjugate of (2), and so from (1) our required sum of squared distances is nR^2/2, which is independent of \phi proving the orientation independence.

More generally,

\begin{aligned}\sum_{k=0}^{n-1} z_k^m &= R^m\exp(i m \phi) \sum_{k=0}^{n-1} \exp(2\pi i k m / n) \\  &= \begin{cases} R^m\exp(i m \phi) n, & \text{if }m/n \text{ is an integer}\\ 0, & \text{otherwise}\end{cases}.\quad\quad(3)\end{aligned}

This enables us to generalise the above result to the following.

Given a regular n-sided polygon and line through its circumcentre, the sum of the mth power signed distances from the vertices of the polygon to the line is independent of the orientation when n > m.

By signed distances, we mean that points on different sides of the line will have distances of opposite sign.

To prove this, we define z_k := R\exp(2\pi i k / n + i \phi) as before and this time our desired sum is

\begin{aligned}\sum_{k=0}^{n-1} \left(\frac{z_k + \overline{z_k}}{2}\right)^m  &= \frac{1}{2^m}\sum_{k=0}^{n-1} \sum_{j=0}^m z_k^j \overline{z_k}^{m-j} \binom{m}{j}\\  &= \frac{1}{2^m}\sum_{k=0}^{n-1} \sum_{j=0}^m z_k^j (R^2/z_k)^{m-j}\binom{m}{j}\\  &= \frac{1}{2^m}\sum_{k=0}^{n-1} \sum_{j=0}^m z_k^{2j-m} (R^2)^{m-j}\binom{m}{j}\\  &= \frac{1}{2^m} \sum_{j=0}^m (R^2)^{m-j}\binom{m}{j}\sum_{k=0}^{n-1}z_k^{2j-m}. \quad\quad(4)\\  \end{aligned}

By (3), \sum_{k=0}^{n-1}z_k^{2j-m} = 0 unless (2j-m)/n is an integer. For m < n this can only occur in the case j = m/2 (if m is even). Hence (4) becomes

\begin{aligned}\sum_{k=0}^{n-1} \left(\frac{z_k + \overline{z_k}}{2}\right)^m &= \begin{cases} \left(\frac{R}{2}\right)^m\binom{m}{m/2}n, & \text{if }m\text{ is even,}\\ 0, & \text{otherwise.}\end{cases}\end{aligned} \quad\quad(5)

Finally, what if the line does not pass through the centre of the polygon but is instead at distance d from the centre?

regularpolywithline2

This corresponds to replacing \left(\frac{z_k + \overline{z_k}}{2}\right) with \left(\frac{z_k + \overline{z_k}}{2}-d\right) in the above calculations and we find

\begin{aligned} \sum_{k=0}^{n-1} \left(\frac{z_k + \overline{z_k}}{2}-d\right)^m &= \sum_{k=0}^{n-1} \sum_{j = 0}^m\left(\frac{z_k + \overline{z_k}}{2}\right)^j (-d)^{m-j} \binom{m}{j}\\  &= \sum_{j = 0}^m (-d)^{m-j} \binom{m}{j}\sum_{k=0}^{n-1} \left(\frac{z_k + \overline{z_k}}{2}\right)^j\\  &= \sum_{i = 0}^{\lceil{m/2}\rceil} (-d)^{m-2i} \binom{m}{2i} \left(\frac{R}{2}\right)^{2i}\binom{2i}{i} n\\  &= (-1)^m n \sum_{i = 0}^{\lceil{m/2}\rceil} \frac{m!}{(m-2i)!i!i!}d^{m-2i}\left(\frac{R}{2}\right)^{2i}.\quad\quad(6)\end{aligned}

Once again we find the sum is independent of the orientation of the line or polygon. In the particular case of m=2 this sum is nR^2/2 + nd^2, which also may be obtained by an application of the parallel axis theorem.

March 31, 2015

2015 ICC Cricket World Cup Attendances

Filed under: cricket,sport — ckrao @ 10:26 am

The 2015 ICC Cricket World Cup held in Australia and New Zealand saw over one million people attend its 49 matches, with attendances shown below, taken from here.

Match # Date Match Venue Attendance
1 14/02/15 New Zealand d Sri Lanka Hagley Oval, Christchurch 17,228
2 14/02/15 Australia d England Melbourne Cricket Ground 84,336
3 15/02/15 South Africa d Zimbabwe Seddon Park, Hamilton 8,332
4 15/02/15 India d Pakistan Adelaide Oval 41,587
5 16/02/15 Ireland d West Indies Saxton Oval, Nelson 4,143
6 17/02/15 New Zealand d Scotland University Oval, Dunedin 4,684
7 18/02/15 Bangladesh d Afghanistan Manuka Oval, Canberra 10,972
8 19/02/15 Zimbabwe d UAE Saxton Oval, Nelson 2,643
9 20/02/15 New Zealand d England Westpac Stadium, Wellington 30,148
10 21/02/15 West Indies d Pakistan Hagley Oval, Christchurch 14,461
11 21/02/15 Australia v Bangladesh Gabba, Brisbane washed out
12 22/02/15 Sri Lanka d Afghanistan University Oval, Dunedin 2,711
13 22/02/15 India d South Africa Melbourne Cricket Ground 86,876
14 23/02/15 England d Scotland Hagley Oval, Christchurch 12,388
15 24/02/15 West Indies d Zimbabwe Manuka Oval, Canberra 5,544
16 25/02/15 Ireland d UAE Gabba, Brisbane 5,249
17 26/02/15 Afghanistan d Scotland University Oval, Dunedin 3,229
18 26/02/15 Sri Lanka d Bangladesh Melbourne Cricket Ground 30,012
19 27/02/15 South Africa d West Indies Sydney Cricket Ground 23,612
20 28/02/15 New Zealand d Australia Eden Park, Auckland 40,053
21 28/02/15 India d UAE WACA Ground, Perth 8,718
22 1/3/2015 Sri Lanka d England Westpac Stadium, Wellington 18,183
23 1/3/2015 Pakistan d Zimbabwe Gabba, Brisbane 9,847
24 3/3/2015 South Africa d Ireland Manuka Oval, Canberra 8,831
25 4/3/2015 Pakistan d UAE McLean Park, Napier 2,406
26 4/3/2015 Australia d Afghanistan WACA Ground, Perth 12,710
27 5/3/2015 Bangladesh d Scotland Saxton Oval, Nelson 3,491
28 6/3/2015 India d West Indies WACA Ground, Perth 17,557
29 7/3/2015 Pakistan d South Africa Eden Park, Auckland 22,713
30 7/3/2015 Ireland d Zimbabwe Blundstone Arena, Hobart 4,048
31 8/3/2015 New Zealand d Afghanistan McLean Park, Napier 10,022
32 8/3/2015 Australia d Sri Lanka Sydney Cricket Ground 39,951
33 9/3/2015 Bangladesh d England Adelaide Oval 11,963
34 10/3/2015 India d Ireland Seddon Park, Hamilton 10,192
35 11/3/2015 Sri Lanka d Scotland Blundstone Arena, Hobart 3,549
36 12/3/2015 South Africa d UAE Westpac Stadium, Wellington 4,901
37 13/03/15 New Zealand d Bangladesh Seddon Park, Hamilton 10,347
38 13/03/15 England d Afghanistan Sydney Cricket Ground 9,203
39 14/03/15 India d Zimbabwe Eden Park, Auckland 30,076
40 14/03/15 Australia d Scotland Blundstone Arena, Hobart 12,177
41 15/03/15 West Indies d UAE McLean Park, Napier 1,221
42 15/03/15 Pakistan d Ireland Adelaide Oval 9,889
43 18/03/15 QF1: South Africa d Sri Lanka Sydney Cricket Ground 27,259
44 19/03/15 QF2: India d Bangladesh Melbourne Cricket Ground 51,552
45 20/03/15 QF3: Australia d Pakistan Adelaide Oval 35,516
46 21/03/15 QF4: New Zealand d West Indies Westpac Stadium, Wellington 30,250
47 24/03/15 SF1: New Zealand d South Africa Eden Park, Auckland 41,279
48 26/03/15 SF2: Australia d India Sydney Cricket Ground 42,330
49 29/03/15 Final: Australia d New Zealand Melbourne Cricket Ground 93,013

If we compare these numbers with the ground capacities shown below (largely taken from ground pages at ESPNcricinfo), we can make a graph of ground occupancy for each game.

Ground Capacity
Melbourne Cricket Ground 95,000
Adelaide Oval 50,000
Sydney Cricket Ground 44,000
Eden Park, Auckland 41,000
Gabba, Brisbane 37,000
Westpac Stadium, Wellington 33,500
WACA Ground, Perth 24,500
Hagley Oval, Christchurch 18,000
Blundstone Arena, Hobart 16,200
Manuka Oval, Canberra 12,000
Seddon Park, Hamilton 12,000
McLean Park, Napier 10,500
Saxton Oval, Nelson 6,000
University Oval, Dunedin 5,000

 

attendancesbymatch

We see that most of the first 10 matches (up to the wash-out between Australia and Bangladesh) were close to capacity, while some of the later matches leading up the quarter final had attendances well under 50% of capacity.

Finally, the table below shows the total attendances for games involving each country, as well as average ground occupancy percentages for their matches.

Team total attendance average % occupancy #matches attendance per match
New Zealand    277,024 94.2 9 30,780
Australia    360,086 83.7 8 45,011
India    288,888 73.8 8 36,111
South Africa    223,803 65.1 8 27,975
Scotland      39,518 63.7 6 6,586
Afghanistan      48,847 63.1 6 8,141
West Indies      96,788 60.4 7 13,827
Sri Lanka    138,893 58.6 7 19,842
England    166,221 57.8 6 27,704
Bangladesh    118,337 57.6 6 19,723
Pakistan    136,419 51.3 7 19,488
Ireland      42,352 47.8 6 7,059
Zimbabwe      60,490 47.4 6 10,082
UAE      25,138 23.8 6 4,190

Australia had a lowish attendance for its game against Afghanistan while New Zealand had every match at least 86% full.

Next Page »

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: