Chaitanya's Random Pages

August 31, 2014

Players with high test cricket + one day international cricket batting averages

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

Jacques Kallis recently retired from international cricket with a phenomenal record of close to 25,000 runs, almost 600 wickets and 300+ catches on the international stage. He ended up with batting averages of 55.37 in test cricket and 44.36 in one day internationals (ODIs), leading to a sum just shy of 100. In turns out this is the highest sum of averages for any retired player who has played both of these forms of the game, just ahead of Michael Hussey (not counting players with a small number of innings).

The following tables show current and former players with a sum of test and ODI batting average above 90. Sangakkara has improved his numbers in both formats dramatically in recent years while Amla and de Villiers are the only players with sum exceeding 100. Statistics are current to August 30 2014.

 

Current players

Test cricket One day international cricket
Player Innings Runs Average Innings Runs Average Strike Rate Test Average + ODI Average
HM Amla 137 6415 51.32 89 4539 55.35 89.84 106.67
AB de Villiers 159 7296 51.02 159 6701 50.38 95.04 101.40
KC Sangakkara 221 11988 58.76 357 12844 40.14 77.55 98.90
IJL Trott 87 3763 46.45 65 2819 51.25 77.06 97.71
MJ Clarke 180 8240 51.50 215 7683 44.67 78.76 96.17
S Chanderpaul 266 11414 51.88 251 8778 41.60 70.74 93.48
MS Dhoni 140 4808 38.46 215 8098 53.28 89.31 91.74
V Kohli 51 1855 39.47 128 5674 51.58 89.75 91.05
AD Mathews 74 3054 52.66 111 3013 38.14 84.06 90.79
Misbah-ul-Haq 84 3285 46.93 136 4594 43.75 73.82 90.68

(NB: Fawad Alam would qualify but only played 3 test matches.)

 

Former players

Test cricket One day international cricket
Player Innings Runs Average Innings Runs Average Strike Rate Test Average + ODI Average
DG Bradman 80 6996 99.94 Bradman predated ODI cricket 99.94
JH Kallis 280 13289 55.37 314 11579 44.36 72.89 99.73
MEK Hussey 137 6235 51.53 157 5442 48.16 87.16 99.69
SR Tendulkar 329 15921 53.79 452 18426 44.83 86.23 98.62
IVA Richards 182 8540 50.24 167 6721 47.00 90.20 97.24
ML Hayden 184 8625 50.74 155 6133 43.81 78.96 94.54
Javed Miandad 189 8832 52.57 218 7381 41.70 67.01 94.27
GS Chappell 151 7110 53.86 72 2331 40.19 75.70 94.05
Mohammad Yousuf 156 7530 52.29 273 9720 41.72 75.10 94.01
RT Ponting 287 13378 51.85 365 13704 42.04 80.39 93.89
BC Lara 232 11953 52.89 289 10405 40.49 79.51 93.38
Zaheer Abbas 124 5062 44.80 60 2572 47.63 84.80 92.43
GM Turner 73 2991 44.64 40 1598 47.00 68.05 91.64
R Dravid 286 13288 52.31 318 10889 39.17 71.24 91.48
DM Jones 89 3631 46.55 161 6068 44.62 72.56 91.17

The above statistics are from ESPN Cricinfo here and here.

August 30, 2014

Waiting times and the size biased distribution

Filed under: mathematics — ckrao @ 12:48 pm

Suppose buses arrive at a stop after independent random intervals of T minutes, where T is uniformly distributed between 10 and 20. It is natural to wonder how long one is expected to wait from some random point in time t until the first bus arrives. For example on the one hand the bus could arrive immediately, or one could be unlucky with time t just after the previous bus left and we could wait as many as 20 minutes for the next bus. Interestingly this waiting time W is no longer uniformly distributed.

In general if interarrival times T have (cumulative) distributive function F_T and mean \mathbb{E}[T], the following is true.

The probability density of waiting time is f_W(x) = \text{Pr}(T \geq x)/\mathbb{E}[T] = (1-F_T(x))/\mathbb{E}[T].\quad\quad(1)

Applying this formula to the above bus example, we have \mathbb{E}[T] = 15 and

\displaystyle F_T(x) = \begin{cases}0, & x < 10\\  (x-10)/10, & 10 \leq x \leq 20\\  1, & x > 20\end{cases}

Using (1), the probability density function of waiting time f_W(x) is plotted below.

waitingtimeforbus

We see that the density function is a rectangle (centred at x = 5 and having 2/3 of the total probability mass) appended to a triangle (having centroid at x=40/3 and 1/3 of the total probability mass). From this we can say the expected waiting time is \mathbb{E}[W] = 5 \times (2/3) + 40/3 \times (1/3) = 70/9 \approx 7.78 minutes. This is more than half the mean interarrival time of 15/2 = 7.5 minutes that one might initially expect.

To prove (1), we shall first look at the length of a particular renewal period that contains a given point t, and the waiting time can then be the part of this after time t. We make use of the following result from alternating renewal process theory [1]:

Proposition: Consider a system that alternates between on and off states where:

  • the on durations X_1, X_2, \ldots are independent and identically distributed according to random variable X, and
  • the off durations Y_1, Y_2, \ldots are independent and identically distributed according to random variable Y.

(However it may be that X_n and Y_n are dependent in general.)

Let p(t) be the probability that the system is in the on state at time t. Then if X+ Y has finite mean and is non-lattice (i.e. takes on more values than just an integral multiple of some positive number), then

\displaystyle \lim_{t \rightarrow \infty} p(t) = \frac{\mathbb{E}[X]}{\mathbb{E}[X+Y]}.\quad\quad(2)

This result is easily understood: the probability the system is on at a given time is the mean on time divided by the mean total cycle time. However it is based on the key renewal theorem, a limit theorem which is not so straightforward to prove.

Now consider a random process with independent and identically distributed interarrival times T_1, T_2, \ldots with common distribution T with probability distribution function F_T. Consider the length of the particular renewal period T^* that contains some point t. We shall determine the distribution of T^*. We define an on-off system as follows.

  • If T^* is greater than some given x > 0, let our system be on for the entire renewal period (i.e. X_{n} = T_n, Y_{n} = 0).
  • If the length of the renewal period is less than or equal to x let our system be off for the renewal period (i.e. X_{n} = 0, Y_{n} = T_n).

renewalperiodcontainingtThen by this definition the conditions of the above proposition are met and so

\begin{aligned} \text{Pr}(T^* > x) &= \text{Pr(system is on at time t)}\\  &= \frac{\mathbb{E}[X_n]}{\mathbb{E}[X_n+Y_n]}\quad\text{(by (2))}\\ &= \frac{\mathbb{E}[T_n \mid T_n > x]\text{Pr}(T_n > x)}{\mathbb{E}[T_n]}\\  &= \frac{\int_x^{\infty} t\ \ dF_T(t)}{\mathbb{E}[T]}.\quad\quad(3)\end{aligned}

Equivalently, \text{Pr}(T^* \leq x) = \frac{\int_0^{x} t\ \ dF_T(t)}{\mathbb{E}[T]}, and if T has probability density f_T, differentiating both sides of this equation gives the probability density function of the length of renewal period containing a point t:

\displaystyle f_{T^*}(x) = xf_T(x)/\mathbb{E}[T].\quad\quad (4)

Intuitively, longer periods are more likely to contain the point t, with probability in direct proportion to the length of the interval. Hence the original density f_T(x) is scaled by the length x and then normalized by \int_0^{\infty} x f_T(x)\ dx = \mathbb{E}[T] to make xf_T(x)/\mathbb{E}[T] a valid probability density. T^* defined by (3) is known as the size-biased transform of T.

Note that the length of the particular renewal interval T^* is stochastically larger than any of the identically distributed interarrival times T. In other words,

\displaystyle \text{Pr}(T^* > x) \geq \text{Pr}(T > x).\quad\quad(5)

This is the so-called inspection paradox, which can be proved by the Chebyshev correlation inequality (a form of rearrangement inequality) which states than when f and g are functions of the random variable X having the same monotonicity (i.e. both non-increasing or both non-decreasing), then f(X) and g(X) are non-negatively correlated:

\displaystyle \mathbb{E} [f(X)g(X)] \geq \mathbb{E}[f(X)] \mathbb{E}[g(X)].\quad\quad(6)

Applying this result with the non-decreasing functions f(T) = T and g(T) = {\bold 1}_{(T > x)} (which is 1 when T > x and 0 otherwise):

\begin{aligned} \text{Pr}(T^* > x) &= \frac{\int_x^{\infty} t\ \ dF_T(t)}{E[T]}\\ &= \frac{\mathbb{E}[T {\bold 1}_{(T>x)}]}{\mathbb{E}[T]}\\ &\geq \frac{\mathbb{E}[T] \mathbb{E}[{\bold 1}_{(T>x)}]}{\mathbb{E}[T]}\\ &= \mathbb{E}[{\bold 1}_{(T>x)}]\\ &= \text{Pr}(T > x).\quad\quad(7)\end{aligned}

The inspection paradox is a form of sampling bias, where results are modified as a result of a non-intended sampling of a given space. Another example is the friendship paradox, where in a graph of acquaintances with vertices having some differing degrees (number of friends), the average degree of a friend is greater than the average degree of a randomly chosen node. For one thing a friend will never have degree zero while a randomly chosen person might! The degree of a friend is an example of sampling from a size-biased distribution.

How about the distribution of the waiting time W for the next arrival? For fixed x > 0 we consider another on-off system where this time the system is in an off state during the last x units of time of a renewal interval, and in the on state otherwise. That is,

  • Y_n = \min(x,T_n),
  • X_n = T_n - Y_n.

waitingperiodThen we have

\begin{aligned} \text{Pr}(W \leq x) &= \text{Pr(system is off at time t)}\\  &= \frac{\mathbb{E}[Y_n]}{\mathbb{E}[X_n+Y_n]} \quad\quad \text{(by (2))}\\  &= \frac{\mathbb{E}[\min(x,T_n)]}{\mathbb{E}[T_n]}\\  &= \frac{\int_0^{x} t\ \ dF_T(t) + \int_x^{\infty} x\ \ dF_T(t) }{\mathbb{E}[T_n]}\\  &= \frac{ \left[tF_T(t) \right]_{0}^x - \int_0^xF_T(t)\ dt + x(1-F_T(x))}{\mathbb{E}[T_n]}\quad \quad \text{(integrating the first term by parts)}  \\&= \frac{xF_T(x) - \int_0^x (1-F_T(t))\ dt - xF_T(x)}{\mathbb{E}[T_n]}\\  &= \frac{\int_0^x (1-F_T(t))\ dt }{\mathbb{E}[T_n]}.\quad\quad(8)\end{aligned}

Alternatively this form can be found by imagining our time t to be uniformly distributed within the current interarrival interval, thus partitioning our inspection renewal interval T^* into (1-X)T^* and XT^*, where X is the uniform random variable X \sim U(0,1). Hence the distribution of W = XT^* is found by integrating over the distribution of T^* and using the fact that dF_T^*(t) = \frac{t}{\mathbb{E}[T]}\ dF_T(t) from (3):

\begin{aligned} \text{Pr}(W \leq x) &= \text{Pr}(XT^* \leq x)\\&= \int_0^{\infty} \text{Pr}(Xt \leq x \mid T^* = t)\ dF_{T^*}(t)\\&= \int_0^{\infty} \text{Pr}(U \leq x/t)\ dF_{T^*}(t)\\&=\int_0^x 1\ dF_{T^*}(t) + \int_x^{\infty} (x/t)\ dF_{T^*}(t)\\&=\int_0^x \frac{t}{\mathbb{E}[T]}\ dF_T(t) + x\int_x^{\infty} \frac{1}{t}\frac{t}{\mathbb{E}[T]}\ dF_T(t)\\&= \frac{\left[tF_T(t)\right]_0^x - \int_0^x F_T(t)\ dt + x(1-F_T(x))}{\mathbb{E}[T]} \quad\quad \text{(integrating the first term by parts)}\\&= \frac{- \int_0^xF_T(t)\ dt + x}{\mathbb{E}[T]}\\&= \frac{\int_0^x (1-F_T(t))\ dt }{\mathbb{E}[T]}.\quad\quad(9)\end{aligned}

Differentiating both sides of (8) or (9) with respect to x leads to (1), the probability density function of waiting time f_W(x) = (1-F_T(x))/\mathbb{E}[T].

Finally, if we wish to find any moments E[W^k] we write W = XT^* where X \sim U(0,1) and X is independent of the size-biased variable T^*:

\begin{aligned}\mathbb{E}[W^k] &= \mathbb{E}[(XT^*)^k]\\ &= \mathbb{E}[X^k] \mathbb{E}[(T^*)^k]\\&= \mathbb{E}[X^k]\int_0^{\infty}\frac{x}{\mathbb{E}[T]} (x^k)\ dF_T(x)\quad\quad \text{(}dF_T^*(x)\text{ related to }dF_T(x)\text{ via (3))}\\ &= \frac{\mathbb{E}[X^k]\mathbb{E}[T^{k+1}]}{\mathbb{E}[T]}\\ &= \frac{\int_0^1 x^k\ dx \mathbb{E}[T^{k+1}]}{\mathbb{E}[T]}\\ &= \frac{\mathbb{E}[T^{k+1}]}{(k+1)\mathbb{E}[T]}.\quad\quad(10)\end{aligned}

In particular

\begin{aligned} \mathbb{E}[W] &= \mathbb{E}[T^2]/(2\mathbb{E}[T])\\ &\geq (\mathbb{E}[T])^2/(2\mathbb{E}[T])\\ &= \mathbb{E}[T]/2\quad\quad(11)\end{aligned}.

Hence we can say that the mean waiting time for the next arrival from any given point in time is more than half the mean interarrival time, unless \mathbb{E}[T^2] = (\mathbb{E}[T])^2 (i.e. zero variance in T, meaning T is deterministic).

For example, in the initial bus example where T \sim U(10,20):

  • E[T] = 15,
  • E[T^2] = \int_10^20 (t^2/10)\ dt = (20^3-10^3)/30 = 700/3 and
  • E[T^3] = \int_10^20 (t^3/10)\ dt = (20^4-10^4)/40 = 3750,

so E[W] = E[T^2]/(2E[T]) = 700/90 = 70/9 \approx 7.78 > E[T]/2 = 7.5 and E[W^2] = E[T^3]/(3E[T]) = 250/3 \approx 83.33. Hence the waiting time has mean 7.78 and standard deviation of \sqrt{250/3-(70/9)^2} \approx 4.78.

References

[1] S. Ross, Stochastic Processes, John Wiley & Sons, 1996.

[2] R. Arratia and L. Goldstein, Size bias, sampling, the waiting time paradox, and infinite divisibility: when is the increment independent? Available at arxiv.org/pdf/1007.3910.

[3] This answer by Did on math.stackexchange.

July 30, 2014

A minimal list of countries whose borders span all nations

Filed under: geography — ckrao @ 11:39 am

 

There is an interesting Sporcle quiz here that asks one to list the countries of the world, where by listing each country all its neighbouring countries also appear. In that way there is no need to list all 197 countries. For example typing Russia or China alone leads to 14 more countries appearing since that is how many countries each of those countries borders. It led me to think of what is a minimal list of countries I could type in order to have all the countries listed. Mathematically speaking, if each country were represented as a node and I connect two nodes with an edge if they share a land border, then I am looking for a minimum vertex cover for the resulting graph.

After some trial and error I came up with the list below that may or not be minimal. Listed first are the continental countries and secondly the island nations.

The only island nations to share borders with other nations are:

  • UK with Ireland and Cyprus (at Akrotiri and Dhekelia)
  • Indonesia with East Timor
  • Indonesia with Papua New Guinea
  • Haiti with the Dominican Republic

Not counted are artificial bridge or tunnel borders such as between:

  • Singapore and Malaysia
  • Bahrain and Saudi Arabia (via the artificial Passport Island)
  • Denmark and Sweden
  • UK and France (via the Channel Tunnel).

Other curious borders are:

  • France with the Netherlands (at the Caribbean island of Saint Martin)
  • France with Brazil and Suriname (via French Guiana)
  • Spain with the United Kingdom (at Gibraltar)
  • Spain with Morocco (at three places on the African mainland)

 

As the following list shows, 149 continental countries can be covered by 9 + 10 + 8 + 3 + 2 = 32 countries which border the other 117.

continental Africa (9):

  • South Africa
  • Democratic Republic of Congo
  • Ethiopia
  • Senegal
  • Burkina Faso
  • Libya
  • Cameroon
  • any country that borders or is Malawi
  • one of Guinea, Liberia, Sierra Leone

continental Europe (including Russia) (10):

  • Germany
  • Spain
  • Italy
  • France or Monaco
  • one of Liechtenstein, Austria, Switzerland
  • Montenegro (borders all former Yugoslavia countries except Slovenia and Macedonia)
  • Norway or Sweden
  • Ukraine
  • Bulgaria
  • Russia

continental Asia (excluding Russia) (8):

  • Israel
  • Saudi Arabia
  • Iran
  • Uzbekistan
  • India
  • Vietnam
  • Malaysia
  • one of North/South Korea

continental North America (3):

  • Costa Rica
  • Guatemala
  • Canada or USA

continental South America (2):

  • Brazil (borders all except Chile and Ecuador)
  • Peru

For completeness we give a minimal list (42 entries) of the island sovereign states too.

Island sovereign states

Africa (6): Cape Verde, Comoros, Madagascar, Mauritius, São Tomé and Príncipe, Seychelles

Europe (3): Iceland, Malta, United Kingdom
(Ireland borders the United Kingdom)

Asia (8): Bahrain, Indonesia, Japan, Maldives, Philippines, Singapore, Sri Lanka, Taiwan
(East Timor borders Indonesia, Cyprus borders the United Kingdom, Brunei borders Malaysia)

North America (12): Antigua and Barbuda, Bahamas, Barbados, Cuba, Dominica, Dominican Republic or Haiti, Grenada, Jamaica, St Kitts and Nevis, St Lucia, St Vincent and the Grenadines, Trinidad and Tobago

Oceania (13): Australia, Fiji, Kiribati, Marshall Islands, Federated States of Micronesia, Nauru, New Zealand, Samoa, Solomon Islands, Palau, Tonga, Tuvalu, Vanuatu
(all except Papua New Guinea which borders Indonesia)

 

Below is a map of the world showing in black the countries listed above. It should be possible to reach a non-black labelled sovereign country from a black-labelled country via one land border crossing. Recall that Morocco is accessed via its small land border with Spain.

 

borders_covering_all_countries

References

http://en.wikipedia.org/wiki/Land_borders

http://en.wikipedia.org/wiki/List_of_island_nations

http://en.wikipedia.org/wiki/List_of_divided_islands

July 26, 2014

Harmonic numbers in terms of binomial coefficients

Filed under: mathematics — ckrao @ 11:48 am

Harmonic numbers H_n are the sums of reciprocals of the first n natural numbers.

\displaystyle H_n := \sum_{k=1}^n \frac{1}{k}\quad\quad(1)

The first few terms are 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, …

An interesting sum relating the harmonic numbers to the binomial coefficients is

\displaystyle H_n = \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(2)

For example, for n=7:

\begin{aligned} & \quad \frac{7}{1} - \frac{21}{2} + \frac{35}{3} - \frac{35}{4} + \frac{21}{5} - \frac{7}{6} + \frac{1}{7}\\ &= \frac{363}{140}\\ &= \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}. \end{aligned}

One way of proving this is by mathematical induction on n, where we also use the following result that looks similar but is easier to prove.

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

For example, for n = 7:

\displaystyle \frac{1}{1} - \frac{7}{2} + \frac{21}{3} - \frac{35}{4} + \frac{35}{5} - \frac{21}{6} + \frac{7}{7} - \frac{1}{8} = \frac{1}{8}.

Equation (3) can be proved by using the identity \frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1} \binom{n+1}{k+1}. From this,

\begin{aligned} & \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1}\\  &= \frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1} (-1)^{k}\\  &= \frac{1}{n+1}\sum_{k'=1}^{n+1} \binom{n+1}{k'} (-1)^{k'-1}\\  &= \frac{1}{n+1}\left(\sum_{k'=0}^{n+1} \binom{n+1}{k'} (-1)^{k'} (-1) - \binom{n+1}{0} (-1)^{-1}\right)\\  &= \frac{1}{n+1}\left[ \left( (1-1)^{n+1} . (-1)\right) - (-1)\right]\\  &= \frac{1}{n+1},  \end{aligned}

as required.

Then to prove (2) firstly note that for n=1, \sum_{k=1}^1 \binom{1}{k} \frac{(-1)^{k-1}}{k} = 1 = H_1, so the result is true when n = 1. Assume it is true for n = m for some positive integer m. That is, assume

\displaystyle H_m = \sum_{k=1}^m \binom{m}{k} \frac{(-1)^{k-1}}{k}.\quad\quad(4)

Then

\begin{aligned}  \sum_{k=1}^{m+1} \binom{m+1}{k} \frac{(-1)^{k-1}}{k}  &= \sum_{k=1}^{m} \binom{m+1}{k} \frac{(-1)^{k-1}}{k} + \binom{m+1}{m+1} \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \left( \binom{m}{k} + \binom{m}{k-1} \right) \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k=1}^{m} \binom{m}{k-1} \frac{(-1)^{k-1}}{k} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m-1} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} + \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \sum_{k'=0}^{m} \binom{m}{k'} \frac{(-1)^{k'}}{k'+1} - \binom{m}{m} \frac{(-1)^{m}}{m+1}+ \frac{(-1)^{m}}{m+1}\\  &= \sum_{k=1}^{m} \binom{m}{k} \frac{(-1)^{k-1}}{k} + \frac{1}{m+1} \quad \text{(using (3))}\\  &= H_m + \frac{1}{m+1} \quad \text{(using (4))}\\  &= H_{m+1}.  \end{aligned}

Hence we have shown that if (2) is true for n=m, it is also true for n=m+1. Then by the principle of mathematical induction (2) is true for all natural numbers n.

A more beautiful proof of (2), taken from here, is to write 1/(k+1) = \int_0^1 x^k\ \text{d}x and so

\begin{aligned}  H_n &= \sum_{k=0}^{n-1} \frac{1}{k+1}\\  &= \sum_{k=0}^{n-1} \int_0^1 x^k\ \text{d}x\\  &= \int_0^1 \left( \sum_{k=0}^{n-1} x^k \right) \ \text{d}x\\  &= \int_0^1 \frac{1-(1-u)^n}{u} \text{d}u\\  &= \int_0^1 \frac{-\sum_{k=1}^n \binom{n}{k} (-1)^k u^k}{u} \text{d}u\\  &= \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \int_0^1 u^{k-1} \text{d}u\\  &= \sum_{k=1}^n\binom{n}{k} \frac{(-1)^{k-1}}{k},\\  \end{aligned}

as required.

June 29, 2014

Melbourne’s late start to cooler temperatures in 2014

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

It occurred to me that Melbourne has had an unusual number of cooler days in 2014 up to the middle of June. After some checking here, I found that from January 1 to June 17 this year, the Melbourne Regional Office has only twice recorded days with a maximum temperature less than 15°C (May 2 [14.3°C] and May 4 [14.2°C]). This beats 2003 when the previous fewest number of 5 such instances took place prior to June 18. The graph and table below show that in the past this number has been as high as 40, but in recent years there is a clear downward trend.

lackofcooldays_regionaloffice

Melbourne Regional Office Average number of sub-15°C days before June 18
Average 1856-2013 21.6
Average 1971-2013 15.0
Average 2004-2013 11.7
2014 2

 

If we do the same calculation for a station further away from the city centre, say the international airport just over 20km away, there is not as much historical data and the effect is not as pronounced, but this year still equals the previous record of 2003 (11 times). In recent times the sub-15°C days prior to June 18 have been about twice as frequent here as the Regional Office.

lackofcooldays_airport

Melbourne Airport Average number of sub-15°C days before June 18
Average 1971-2013 24.7
Average 2004-2013 23.1
2014 11

The data is from Australia’s Bureau of Meteorology website.

June 28, 2014

A few sums involving inverses of binomial coefficients

Filed under: mathematics — ckrao @ 11:11 am

One of the problems from the 1990 Australian Mathematical Olympiad ([1]) asks one to prove the following result.

\displaystyle \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}} = \frac{1}{n+1}.\quad\quad (1)

One solution in [1] makes use of the following identity:

\begin{aligned}  \frac{1}{\binom{m}{k}} &= \frac{k!(m-k)!}{m!}\\  &= \frac{k!(m-k)!(m+1)(m+2)}{m!(m+1)(m+2)}\\  &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!(m+2)}{(m+1)!}\\  &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!((m-k+1) + (k+1))}{(m+1)!}\\  &=\left(\frac{m+1}{m+2}\right)\frac{k!(m-k+1)! + (k+1)!(m-k)!}{(m+1)!}\\  &= \frac{m+1}{m+2}\left(\frac{1}{\binom{m+1}{k}}+ \frac{1}{\binom{m+1}{k+1}}\right).\quad\quad(2)  \end{aligned}

Then setting m=2n, (1) becomes a telescoping sum:

\begin{aligned}  \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}}  &= \sum_{k=1}^{2n-1} \frac{2n+1}{2n+2}\left(\frac{(-1)^{k-1}}{\binom{2n+1}{k}}+ \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\  &= \frac{2n+1}{2n+2}\left( \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\  &= \frac{2n+1}{2n+2}\left( \frac{(-1)^0}{\binom{2n+1}{1}} + \sum_{k=2}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \frac{(-1)^{2n-1-1}}{\binom{2n+1}{2n-1+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\  &= \frac{2n+1}{2n+2}\left( \frac{1}{2n+1} + \frac{1}{2n+1} + \sum_{k=1}^{2n-2} \frac{(-1)^{k}}{\binom{2n+1}{k+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\  &= \frac{2n+1}{2n+2} \left(\frac{2}{2n+1} + 0\right)\\  &= \frac{1}{n+1}.  \end{aligned}

Using a similar argument one can prove the more general identity

\displaystyle \sum_{k=0}^n\frac{(-1)^k}{\binom{n}{k}} = \frac{n+1}{n+2}\left(1 + (-1)^n\right).\quad\quad (3)

How about the sum \displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}}? Using (1) we find the recursion

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

Hence we have the recurrence relation

\displaystyle S(n+1) = \frac{n+2}{2(n+1)}S(n) + 1.\quad\quad(5)

From this S(n) does not have a closed form solution but using induction on n we can prove the following relations found in [2].

\displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}} = \frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k} = (n+1)\sum_{k=0}^n \frac{1}{(n+1-k)2^k}.\quad\quad(6)

Firstly note that when n=0, the three expressions in (5) become \frac{1}{\binom{0}{0}},  \frac{1}{2^{1}}\frac{2^1}{1} and \frac{1}{1}, which are all equal to 1. Hence (6) holds for n=0. Assume it holds for n =m. That is,

\displaystyle S(m) := \sum_{k=0}^{m}\frac{1}{\binom{m}{k}} = \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} = (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}.\quad\quad(7)

Then using (5), on the one hand,

\begin{aligned}  S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\  &= 1 + \frac{m+2}{2(m+1)} \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} \\  &= 1 + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\  &= \frac{(m+2)2^{m+2}}{2^{m+2}(m+2)} + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\  &= \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+2}\frac{2^k}{k},\quad\quad(8)  \end{aligned}

while on the other,

\begin{aligned}S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\  &= 1 + \frac{m+2}{2(m+1)} (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}\\  &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+1-k)2^{k+1}}\\  &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+2-(k+1))2^{k+1}}\\  &= 1 + (m+2)\sum_{k=1}^{m+1} \frac{1}{(m+2-k)2^{k}}\\  &= (m+2)\sum_{k=0}^{m+1} \frac{1}{(m+2-k)2^k}.\quad \quad(9)  \end{aligned}

Equations (8) and (9) show that if (6) holds for n=m, then it does for n=m+1. By the principle of mathematical induction, (6) then is true for all integers n\geq 0.

Another related sum that can be expressed in terms of S(n) is \displaystyle \frac{1}{\binom{2n}{0}} + \frac{1}{\binom{2n}{2}} + \frac{1}{\binom{2n}{4}} + \ldots + \frac{1}{\binom{2n}{2n}}. We have

\begin{aligned}& \sum_{k=0}^{2n} \frac{1}{\binom{2n}{2k}}\\&= \frac{2n+1}{2n+2}\sum_{k=0}^{2n} \frac{1}{\binom{2n+1}{k}}\text{\quad \quad (by (5))}\\  &= \frac{2n+1}{2n+2} S(2n+1).\quad\quad(10)  \end{aligned}

Note that more identities with inverses of binomial coefficients are in [2] (and references therein), where the integral

\displaystyle \frac{1}{\binom{n}{k}} = (n+1) \int_0^1 t^k (1-t)^{n-k}\ \text{d}t

is utilised.

References

[1] A. W. Plank, Mathematical Olympiads: The 1990 Australian Scene, University of Canberra, 1990.

[2] T. Mansour, Combinatorial Identities and Inverse Binomial Coefficients, available at http://math.haifa.ac.il/toufik/toupap02/qap0204.pdf

May 31, 2014

The world’s fastest growing countries by population

Filed under: geography — ckrao @ 7:24 am

I was amazed to learn recently how rapidly the population of some African countries is increasing. The following table shows those countries that grew by at least half a million people in the mid 2012 to mid 2013 year (see references below). Note that Nigeria is at least 50% ahead of every country other than India and China. Also note the complete absence of European countries (Italy had the largest growth there of 416,000 which is only 47th in the world). Note that the figures are estimates only.

Country Continent Annual Population Growth (mid 2012 – mid 2013)
India Asia 20,290,000
China Asia 6,688,000
Nigeria Africa 5,551,000
Pakistan Asia 3,696,000
Indonesia Asia 3,553,000
Democratic Republic of Congo Africa 2,334,000
United States North America 2,281,000
Ethiopia Africa 2,253,000
Bangladesh Asia 2,081,000
Mexico North America 2,026,000
Egypt Africa 1,893,000
Philippines Asia 1,825,000
Brazil South America 1,685,000
Kenya Africa 1,266,000
Uganda Africa 1,232,000
Tanzania Africa 1,204,000
Myanmar Asia 1,160,000
Iraq Asia 1,051,000
Saudi Arabia Asia 997,000
Iran Asia 976,000
Vietnam Asia 922,000
Sudan Africa 863,000
Algeria Africa 792,000
Mozambique Africa 790,000
Malaysia Asia 734,000
Yemen Asia 725,000
Ivory Coast Africa 717,000
South Africa Africa 704,000
Ghana Africa 659,000
Niger Africa 649,000
Angola Africa 647,000
Madagascar Africa 585,000
Burkina Faso Africa 550,000
Colombia South America 544,000
Cameroon Africa 543,000
Mali Africa 532,000
Syria Asia 531,000
Afghanistan Asia 517,000
Thailand Asia 508,000

 

The next table shows that more than 6/7 of the world’s current population growth is from Asia or Africa.

Continent Annual population growth in millions from mid 2012 to mid 2013 (% of world total)
Asia 51.3 (55.2%)
Africa 29.3 (31.5%)
North America 6.2 (6.6%)
South America 4.4 (4.7%)
Europe 1.1 (1.2%)
Oceania 0.66 (0.7%)
World 92.9

References from Wikipedia

[1] List of Asian countries by population

[2] List of African countries by population

[3] List of North American countries by population

[4] List of South American countries by population

[5] List of European countries by population

[6] List of Oceanian countries by population

May 17, 2014

Forms of Stewart’s theorem

Filed under: mathematics — ckrao @ 10:41 am

Stewart’s theorem finds the length of a cevian d=AD in terms of the side lengths of the triangle ABC and the lengths m, n into which point D on BC divides that side. Here are some forms of the same formula.

Stewart

1. The most common form we see is

\displaystyle b^2 m + c^2 n = a(d^2 + mn) \quad \Rightarrow \quad d^2 = \frac{b^2m + c^2n}{a} - mn.\quad\quad(1)

An easy-to remember form of this is rewriting the above as man + dad = bmb + cnc (a man and his dad hid a bomb in the sink!). This can be proved by applying the cosine rule to triangles ACD and then ABC:

\begin{aligned}  d^2 &= AD^2\\  &= AC^2 + CD^2 - 2AC.CD\cos \angle DCA\\  &= AC^2 + CD^2 - 2AC.CD \cos \angle BCA\\  &= AC^2 + CD^2 - 2AC.CD \frac{CA^2 + CB^2 - AB^2}{2CA.CB}\\  &= b^2 + n^2 - 2bn \frac{b^2 + a^2 - c^2}{2ba}\\  &= b^2 + n^2 - n \frac{b^2 + a^2 - c^2}{a}\\  &= \frac{b^2(m+n) - n(b^2 + a^2 - c^2)}{a} + n^2\\  &= \frac{b^2 m + c^2n}{a} + n^2 - \frac{na^2}{a}\\  &= \frac{b^2 m + c^2n}{a} + n(n-a)\\  &= \frac{b^2 m + c^2n}{a} - mn.\\  \end{aligned}

2. If D divides the side BC in the ratio BD:DC = r:s,

\displaystyle d^2 = \frac{rb^2 + sc^2}{r+s} - \frac{rsa^2}{(r+s)^2} = \frac{r^2b^2 + s^2c^2 + rs(b^2 + c^2 - a^2)}{(r+s)^2} .\quad\quad(2)

3. Similar to (2) but substituting \displaystyle \lambda = r/(r+s) = BD:BC,

\displaystyle d^2 = \lambda b^2 + (1-\lambda)c^2 - \lambda(1-\lambda)a^2.\quad\quad(3)

This and the previous form are conveniently proved using vectors. Writing the vector \mathbf{AD} = \lambda \mathbf{AC} + (1-\lambda) \mathbf{AB},

\begin{aligned}  d^2 &= \mathbf{AD}. \mathbf{AD}\\  &= \left(\lambda \mathbf{AC} + (1-\lambda) \mathbf{AB}\right).\left(\lambda \mathbf{AC} + (1-\lambda) \mathbf{AB}\right)\\  &= \lambda^2 \mathbf{AC}.\mathbf{AC} + (1-\lambda)^2 \mathbf{AB}.\mathbf{AB} + 2\lambda(1-\lambda)\mathbf{AB}.\mathbf{AC}\\  &= \lambda^2 b^2 + (1-\lambda)^2 c^2 + \lambda(1-\lambda)\left(b^2 + c^2 - a^2\right)\\  &= b^2(\lambda^2 + \lambda(1-\lambda)) + c^2((1-\lambda)^2 + \lambda(1-\lambda)) - a^2\lambda(1-\lambda)\\  &= \lambda b^2 + (1-\lambda)c^2 - \lambda(1-\lambda)a^2.  \end{aligned}

Note that this is valid for any real \lambda, so D may lie beyond segment BC.

4. Writing (3) as a quadratic in \lambda:

\displaystyle d^2 = \lambda^2 a^2 + \lambda(c^2-b^2 -a^2) + b^2.\quad\quad(4)

5. A symmetric form [1], where the following distances are taken as directed segments (CD = -DC etc.)

\displaystyle \frac{BA^2}{BC.BD} + \frac{CA^2}{CB.CD} + \frac{DA^2}{DB.DC} = 1\quad\quad(5)

 Note that this is equivalent to BA^2 . CD + CA^2 . DB = DA^2.CB + CD.DB.CB = CB(DA^2 + CD.DB) which is (1).

 

Here are a few special cases of this formula applying form (3).

  • D = C (i.e. \lambda = 1): d^2 = b^2
  • D is a third of the way along CB (closer to C) (\lambda = 2/3): \displaystyle d^2 = 2b^2/3 + c^2/3 - 2a^2/9
  • AD is the internal angle bisector of \angle BAC (\lambda = c/(b+c)):

\begin{aligned}  d^2 &= cb^2/(b+c) + bc^2/(b+c) - bca^2/(b+c)^2\\  &= bc\left[\frac{b}{b+c} + \frac{c}{b+c}- \left(\frac{a}{b+c}\right)^2\right]\\  &= bc\left[1 - \left(\frac{a}{b+c}\right)^2\right]\\  &= bc - mn.  \end{aligned}

  • AD is the external angle bisector of \angle BAC (assume b > c so \lambda = -c/(b-c)):

Stewart external bisector

\begin{aligned}  d^2 &= \frac{-c}{b-c} b^2 + \frac{b}{b-c}c^2 + \frac{bc}{(b-c)^2}a^2\\  &= bc\left[\frac{-b}{b-c} + \frac{c}{b-c}+ \left(\frac{a}{b-c}\right)^2\right]\\  &= bc\left[ \left(\frac{a}{b-c}\right)^2 - 1\right]\\  &= mn - bc.  \end{aligned}

Reference

[1] Darij Grinberg – Unpublished Notes – Geometry

April 29, 2014

Historical world population distribution

Filed under: geography — ckrao @ 2:31 pm

The following plots show the percentage distribution of the world’s population over a 2400 year period. To my surprise China had over a third of the world population during much of the 1800s, while the Indian subcontinent has historically had a higher share than now. It’s interesting to see the growth of the New World in the bottom right plot too. One expects Asia minus China and Africa to have significant proportional growth at least in the first half of this century.

population percentage distributions

Reference

http://www.worldhistorysite.com/population.html – using Colin McEvedy and Richard Jones, Atlas of World Population History (Penguin, 1978)

April 25, 2014

Three and four tangent circles

Filed under: mathematics — ckrao @ 12:14 pm

If we are given two tangent circles how do we find a third circle tangent to both of them? If the two circles are internally tangent, the third circle is also internally tangent to the larger circle.

internal

If the two circles are externally tangent, the third circle is either internally or externally tangent to both.

external

Note that we disregard cases where the third circle has the same point of tangency as the other two such as shown below.

disallowed

Locus of centre of third circle

If we let the centres of the three circles C_1, C_2, C_3 be O_1, O_2, O_3 and with respective radii R_1, R_2, R_3 (assume R_1 > R_2) then what is the locus of O_3 as O_1, R_1, O_2, R_2 are fixed while R_3 is allowed to vary?

We note in the internally tangent case,

O_2 O_3 + O_3 O_1 = (R_2 + R_3) + (R_1 - R_3) = R_1 + R_2.\quad\quad (1)

Since this distance is independent of R_3, O_3 is on an ellipse with foci at O_1 and O_2 shown in green below.

threecircles2

In the externally tangent case, there are two subcases depending on whether the third circle is internally or externally tangent to the other two:

O_3 O_2 - O_3 O_1 = (R_3 - R_2) - (R_3 - R_1) = R_1 - R_2.\quad\quad (2)

O_3 O_1 - O_3 O_2 = (R_3 + R_1) - (R_3 + R_2) = R_1 - R_2.\quad\quad (3)

This corresponds to the two branches of a hyperbola with foci at O_1 and O_2 shown in green below.

external2

Notice that similar results hold when the original two circles are not necessarily tangent to each other.

 

Distances

Denoting the points of tangency between C_2, C_3 by T_1 and similarly defining T_2, T_3, we shall find some distances in the figure below.

setup2

By the cosine rule in \triangle O_1O_2O_3,

\begin{aligned} \cos \angle O_1 O_2 O_3 &= \frac{O_1 O_2^2 + O_2O_3^2 - O_1O_3^2}{2O_1 O_2. O_2O_3}\\  &= \frac{(R_1 - R_2)^2 + (R_2 + R_3)^2- (R_1 - R_3)^2 }{2(R_1 - R_2)(R_2 + R_3)}\\  &=\frac{2R_2^2 - 2R_1 R_2 + 2R_2 R_3 + 2R_1 R_3}{2(R_1 - R_2)(R_2 + R_3)}\\  &= \frac{-(R_1 - R_2)(R_2+R_3) + 2R_1R_3}{(R_1 - R_2)(R_2 + R_3)}\\  &= -1 + \frac{2R_1R_3}{(R_1 - R_2)(R_2 + R_3)}.\quad\quad (4)  \end{aligned}

The perimeter of \triangle O_1O_2O_3 is (R_1 - R_2) + (R_1 - R_3) + (R_2 + R_3) = 2R_1, so by Heron’s formula its area is

\displaystyle \sqrt{R_1(R_1 - (R_1 - R_2)) (R_1 - (R_1 - R_3)) (R_1 - (R_2 + R_3))} = \sqrt{R_1R_2 R_3(R_1 - R_2 - R_3)}.\quad\quad (5)

If the points T_3, O_1, O_2 have coordinates (0,0), (R_1,0), (R_2,0) respectively, then O_3 has coordinates (R_2 + (R_2 + R_3)\cos \angle O_1 O_2 O_3, (R_2 + R_3)\sin \angle O_1 O_2 O_3). We have \cos \angle O_1 O_2 O_3 found above and \sin \angle O_1 O_2 O_3 can be found via

\displaystyle \frac{1}{2}O_1O_2.O_2O_3 \sin \angle O_1 O_2 O_3 = |O_1O_2O_3| = \sqrt{R_1R_2 R_3(R_1 - R_2 - R_3)}.\quad\quad (6)

Hence the coordinates of O_3 are

\begin{aligned} & (R_2 + (R_2 + R_3)\cos \angle O_1 O_2 O_3, (R_2 + R_3)\sin \angle O_1 O_2 O_3)\\ &= \left(R_2 + (R_2 + R_3)\left(-1 + \frac{2R_1R_3}{(R_1 - R_2)(R_2 + R_3)}\right), (R_2 + R_3)2\frac{\sqrt{R_1R_2 R_3(R_1 - R_2 - R_3)}}{O_1 O_2.O_2O_3}\right)\\  &= \left(R_2 - R_2 - R_3+ \frac{2R_1R_3}{(R_1 - R_2)}, (R_2 + R_3)2\frac{\sqrt{R_1R_2 R_3(R_1 - R_2 - R_3)}}{(R_1-R_2)(R_2+R_3)}\right)\\  &= \left(\frac{R_3(R_1 + R_2)}{R_1 - R_2}, \frac{2\sqrt{R_1R_2 R_3(R_1 - R_2 - R_3)}}{R_1-R_2}\right).\quad\quad (7)  \end{aligned}

Note here that the first coordinate varies with R_3 linearly for R_1, R_2 fixed. The distance T_3O_3 is found from

\begin{aligned} T_3O_3^2 &= \frac{1}{(R_1 - R_2)^2}\left([R_3(R_1 + R_2)]^2 + 4R_1R_2R_3(R_1 - R_2 - R_3)\right)\\  &= \frac{1}{(R_1 - R_2)^2}\left(R_3^2 ((R_1 + R_2)^2 - 4R_1 R_2) + 4R_1 R_2 R_3(R_1 - R_2)\right)\\  &= \frac{1}{(R_1 - R_2)^2}\left(R_3^2 (R_1 - R_2)^2 + 4R_1 R_2 R_3(R_1 - R_2)\right)\\  &= R_3^2 + \frac{4R_1 R_2 R_3}{R_1 - R_2}.\quad\quad (8)  \end{aligned}

Hence we have found that interestingly the power of the tangency point T_3 with respect to circle C_3 is the relatively simple form \frac{4R_1R_2R_3}{R_1 - R_2}.

We may also find the distance between points of tangency T_1T_3 as 2R_2 \cos (\angle O_1 O_2 O_3/2) using the identity \cos^2 (A/2) = (1 + \cos A)/2. From (4),

\begin{aligned} T_1 T_3 &= 2R_2 \cos (\angle O_1 O_2 O_3/2)\\  &= 2R_2 \sqrt{\frac{R_1R_3}{(R_1 - R_2)(R_2 + R_3)}}\\  &= \frac{2\sqrt{R_1R_2R_3} \sqrt{R_2}}{\sqrt{(R_1 - R_2)(R_2 + R_3)}}.\quad\quad(9)  \end{aligned}

Next we perform the same calculations (4)-(9) with the configuration of three circles tangent externally.

setup

By the cosine rule in \triangle O_1O_2O_3,

\begin{aligned} \cos \angle O_1 O_2 O_3 &= \frac{O_1 O_2^2 + O_2O_3^2 - O_1O_3^2}{2O_1 O_2. O_2O_3}\\  &= \frac{(R_1 + R_2)^2 + (R_2 + R_3)^2- (R_1 + R_3)^2 }{2(R_1 + R_2)(R_2 + R_3)}\\  &=\frac{2R_2^2 + 2R_1 R_2 + 2R_2 R_3 - 2R_1 R_3}{2(R_1 + R_2)(R_2 + R_3)}\\  &= \frac{(R_1 + R_2)(R_2+R_3) - 2R_1R_3}{(R_1 + R_2)(R_2 + R_3)}\\  &= 1 - \frac{2R_1R_3}{(R_1 + R_2)(R_2 + R_3)}. \quad\quad (10)  \end{aligned}

The perimeter of \triangle O_1O_2O_3 is (R_1 + R_2) + (R_1 + R_3) + (R_2 + R_3) = 2(R_1+R_2+R_3), so by Heron’s formula its area is the attractive form

\displaystyle \sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}.\quad\quad (11)

If the points T_3, O_1, O_2 have coordinates (0,0), (-R_1,0), (R_2,0) respectively, then O_3 has coordinates (R_2 - (R_2 + R_3)\cos \angle O_1 O_2 O_3, (R_2 + R_3)\sin \angle O_1 O_2 O_3). We have \cos \angle O_1 O_2 O_3 found above and \sin \angle O_1 O_2 O_3 can be found via

\displaystyle \frac{1}{2}O_1O_2.O_2O_3 \sin \angle O_1 O_2 O_3 = |O_1O_2O_3| = \sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}.\quad\quad (12)

Hence the coordinates of O_3 are

\begin{aligned} & (R_2 - (R_2 + R_3)\cos \angle O_1 O_2 O_3, (R_2 + R_3)\sin \angle O_1 O_2 O_3)\\ &= \left(R_2 - (R_2 + R_3)\left(1 - \frac{2R_1R_3}{(R_1 + R_2)(R_2 + R_3)}\right), (R_2 + R_3)2\frac{\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{O_1 O_2.O_2O_3}\right)\\  &= \left(R_2 - R_2 - R_3+ \frac{2R_1R_3}{(R_1 + R_2)}, (R_2 + R_3)2\frac{\sqrt{R_1R_2 R_3(R_1 +R_2 + R_3)}}{(R_1+R_2)(R_2+R_3)}\right)\\  &= \left(\frac{R_3(R_1 - R_2)}{R_1 + R_2}, \frac{2\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{R_1+R_2}\right).\quad\quad (13)  \end{aligned}

Note again that the first coordinate varies with R_3 linearly for R_1, R_2 fixed. Formulas (7) and (13) were used to generate the diagrams in this post.

The distance T_3O_3 is found from

\begin{aligned} T_3O_3^2 &= \frac{1}{(R_1 + R_2)^2}\left([R_3(R_1 - R_2)]^2 + 4R_1R_2R_3(R_1 + R_2 + R_3)\right)\\  &= \frac{1}{(R_1 + R_2)^2}\left(R_3^2 ((R_1 - R_2)^2 + 4R_1 R_2) + 4R_1 R_2 R_3(R_1 + R_2)\right)\\  &= \frac{1}{(R_1 + R_2)^2}\left(R_3^2 (R_1 + R_2)^2 + 4R_1 R_2 R_3(R_1 + R_2)\right)\\  &= R_3^2 + \frac{4R_1 R_2 R_3}{R_1 + R_2}.\quad\quad (14)  \end{aligned}

Hence we have found that the power of the tangency point T_3 with respect to circle C_3 is \frac{4R_1R_2R_3}{R_1 + R_2}.

The distance between points of tangency T_1T_3 is 2R_2 \sin (\angle O_1 O_2 O_3/2) and using the identity \sin^2 (A/2) = (1 - \cos A)/2 with (10),

\begin{aligned} T_1 T_3 &= 2R_2 \sin (\angle O_1 O_2 O_3/2)\\  &= 2R_2 \sqrt{\frac{R_1R_3}{(R_1 + R_2)(R_2 + R_3)}}\\  &= \frac{2\sqrt{R_1R_2R_3} \sqrt{R_2}}{\sqrt{(R_1 + R_2)(R_2 + R_3)}}.\quad\quad(15)  \end{aligned}

Many of the formulas here are found from the first case by replacing R_1 with -R_1. Other distances between points in the figure can be found through similar means.

Finally, we remark that the radical axes of each pair of circles intersect at the radical centre – that point is the circumcentre of the triangle passing through the three points of tangency. With this circle being orthogonal to the three existing circles, inversion in this circle preserves the figure.

radical

Four circles

For the case of four mutually tangential circles (where there is more than one point of tangency), there is an amazing relationship involving the complex number coordinates z_1, z_2, z_3, z_4 of the centres of the circles and their curvatures (reciprocals of radii) k_i= 1/R_i:

\displaystyle 2\left((k_1z_1)^2 + (k_2z_2)^2 + (k_3z_3)^2 + (k_4z_4)^2\right) = \left(k_1z_1 + k_2z_2 + k_3z_3 + k_4z_4\right)^2.\quad\quad (16)

This is known as the complex Descartes theorem. Note that for this formula to be valid for internally tangent circles, we make the sign of the curvature of the larger circle negative.

Interestingly this was only proven in 2001 in [1] with a nice proof shown in [2]. That proof assigns a sphere to each of the six points of tangency with curvature equal to the sums of the curvatures of the two circles meeting there. It then turns out that three spheres corresponding to the tangency points on the same circle are mutually tangent. If one does the same construction of spheres for the dual configuration of circles shown in blue below (the original four circles are in black), the same set of six spheres is obtained!

dualconfig

Note that we have more results from (16). Since the relationships remain when the points are translated by the same complex number z we have

\displaystyle 2\left((k_1(z_1-z))^2 + (k_2(z_2-z))^2 + (k_3(z_3-z))^2 + (k_4(z_4-z))^2\right) = \left(k_1(z_1-z) + k_2(z_2-z) + k_3(z_3-z) + k_4(z_4-z)\right)^2.\quad\quad (17)

Expanding this as a quadratic in z and comparing coefficients of z^2, z [1] gives further two relationships:

\begin{aligned} 2\left(k_1^2 + k_2^2 + k_3^2 + k_4^2\right) &= \left(k_1 + k_2 + k_3 + k_4\right)^2, \quad\quad & (18)\\  2\left(k_1^2 z_1 + k_2^2 z_2 + k_3^2 z_3 + k_4^2 z_4\right) &= \left(k_1 + k_2 + k_3 + k_4\right)\left(k_1 z_1 + k_2 z_2 + k_3 z_3 + k_4 z_4 \right).\quad\quad& (19)  \end{aligned}

 Equation (18) is known as Descartes’ Theorem, discovered in 1643.

To see (16) and (18) in action, let us set for example z_1 = 3, R_1 = 3, z_2 = 1, R_2 = 1, R_3 = 1. Then applying (7) we find

\begin{aligned} z_3 &= \frac{R_3(R_1 + R_2)}{R_1 - R_2} + \frac{2\sqrt{R_1R_2R_3(R_1 - R_2 - R_3)}}{R_1 - R_2}i\\  &= \frac{1(3+1)}{3-1} + \frac{2\sqrt{3.1.1(3-1-1)}}{3-1}i\\  &= 2 + i\sqrt{3}.\quad\quad(20)  \end{aligned}

From (18) we may write

k_4 = k_1 + k_2 + k_3 \pm 2\sqrt{k_1 k_2 + k_2 k_3 + k_1 k_3},\quad\quad(21)

which for k_1 = -1/3 (negative as the larger circle is internally tangent), k_2 = k_3 = 1 leads to k_4 = 5/3 \pm 2\sqrt{1/3}[ or R_4 = 1/k_4 = 3(7 \mp \sqrt{15})/34.]

From (16) we may write

z_4 = (k_1z_1 + k_2z_2 + k_3z_3 \pm 2\sqrt{k_1 k_2z_1z_2 + k_2 k_3z_2z_3 + k_1 k_3z_1z_3})/k_4,\quad\quad(22)

which for k_1 z_1 = -1, k_2 z_2 = 1, k_3 z_3 = 2 + i\sqrt{3}, k_4 = 5/3 \pm 2\sqrt{1/3} leads to

\begin{aligned} z_4 &= \left(-1 + 1 + 2 + \sqrt{3}i \pm 2\sqrt{-1}\right)/(5/3 \pm 2\sqrt{1/3})\\  &=\frac{2+(\sqrt{3}+ 2)i}{5/3 + 2/\sqrt{3}}\quad \text{or}\quad\frac{2+(\sqrt{3}- 2)i}{5/3 - 2/\sqrt{3}}.\quad\quad(23)\end{aligned}

This is used to generate the sketch below. As can be seen there are two possible circles shown in red.

example

Here is how one may prove (19) without the insight of the dual configuration, alluded to in [3] and [4]. Let us consider the externally tangent case with two possible fourth circles shown in red.

example2

If we perform an inversion of the configuration in a circle of radius R centred at the tangency point T_3 of C_1 and C_2, the circles C_1 and C_2 invert to parallel lines while the circles C_3, C_4 invert to equal-radii circles C_3', C_4' tangent to the parallel lines as shown below. Note that in this new configuration it is easier to see that there are two possible choices for C_4'.

example3

What distance separates the two parallel lines? We need only look at the image of the points diametrically opposite T_3 in C_1 and C_2. This leads to the distance d = R^2/(2R_1) + R^2/(2R_2). Hence the radii of the images of C_3 and C_4 is half this, or R^2(1/R_1 + 1/R_2)/4.

If we know the distance of the centre of the image of C_4 from T_3, the following lemma will enable us to determine R_4. We shall use the following useful lemma which tells us how to find the radius of a circle from quantities involving its inverse.

Lemma

If a circle has radius r and distance x from the origin, its inverse in a circle of radius R centred at the origin has radius r' = rR^2/|x^2-r^2| and its centre has distance x' = xR^2/|x^2 - r^2| from the origin. (Hence x'/r ' = x/r.)

Proof of lemma

lemmaproofIn the above figure the dashed circle is the circle of inversion while the separate cases x > r and x < r are shown in blue and red respectively.

The points on the original circle collinear with the origin are at distance x+r and |x-r| from the origin. The inverses of these points have distance R^2/(x+r) and R^2/(x-r) from the origin (this quantity is negative if x < r). Hence the centre of the inverted circle has distance x' = |R^2(1/(x+r) + 1/(x-r))/2| = xR^2/|x^2 - r^2| from the origin and radius r'= |R^2(1/(x-r) - 1/(x+r))/2| = rR^2/|x^2-r^2| as required. Note that if x=r the circle inverts to a line which can be thought of as a circle with centre at infinity with infinite radius.

From (12), if the origin is at T_3, O_3 has coordinates

\displaystyle (x,y):= \left(\frac{R_3(R_1 - R_2)}{R_1 + R_2}, \frac{2\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{R_1+R_2}\right).\quad\quad (24)

Suppose O_3' has coordinates (x',y') (we note that while C_3' is the image of C_3 under the inversion, the centre O_3' is generally not the image of O_3). Then O_4' is at distance

\displaystyle d:= \frac{R^2}{2}\left(\frac{1}{R_1} + \frac{1}{R_2}\right)\quad\quad (25)

above or below O_3' (the distance between the parallel lines), so has coordinates (x',y'\pm d). By the above lemma with r = d/2, the radius of C_4 with centre O_4 is dR^2/2(x'^2 + (y'\pm d)^2 - (d/2)^2). Hence its curvature is

\displaystyle \frac{1}{R_4} = \frac{2(x'^2 + y'^2 + 3d^2/4 \pm 2y'd)}{dR^2}.\quad\quad(26)

Firstly from (13)

x^2 + y^2 = T_3O_3^2 = R_3^2 + \frac{4R_1 R_2 R_3}{R_1 + R_2}, so by the lemma, we find x'^2 + y'^2 via the ratio of radii (d/2) to R_3:

\displaystyle x'^2 + y'^2 = (d/2R_3)^2(x^2 + y^2),\quad\quad (27)

so

\begin{aligned}\frac{2(x'^2 + y'^2 + 3d^2/4)}{dR^2} &= \frac{2(d/2R_3)^2(x^2 + y^2) + 3d^2/2}{dR^2}\\  &=\frac{d[(x^2 + y^2)/2R_3^2 + 3/2]}{R^2}\\  &=\frac{d}{R^2}\left[ \frac{R_3^2}{2R_3^2} + \frac{4R_1 R_2 R_3}{(R_1 + R_2)2R_3^2} + \frac{3}{2}\right]\\  &= \frac{d}{R^2}\left[ 2 + \frac{2R_1R_2}{(R_1 + R_2)R_3} \right]\\  &= \frac{2d}{R^2}\left[ \frac{R_3(R_1 + R_2) + R_1 R_2}{(R_1 + R_2)R_3} \right]\\  &= \left(\frac{1}{R_1} + \frac{1}{R_2}\right) \left[ \frac{R_3(R_1 + R_2) + R_1 R_2}{(R_1 + R_2)R_3} \right]\quad \text{(by (25))}\\  &= \frac{R_1 R_2 + R_2 R_3 + R_1 R_3}{R_1 R_2 R_3}\\  &= \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3}.\quad\quad(28)  \end{aligned}

Next,

\begin{aligned} \frac{4y'}{R^2} &= \frac{4 y (d/2R_3)}{R^2}\\  &= \frac{4d\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{R^2(R_1+R_2)R_3}\quad \text{(by (24))}\\  &= \frac{4\frac{(R^2)(R_1 + R_2)}{2R_1R_2}\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{R^2(R_1+R_2)R_3}\quad \text{(by (25))}\\  &= \frac{2\sqrt{R_1R_2 R_3(R_1 + R_2 + R_3)}}{R_1R_2R_3}\\  &= 2\sqrt{\frac{1}{R_1R_2} + \frac{1}{R_2R_3} + \frac{1}{R_1R_3}}.\quad\quad(29)  \end{aligned}

Using (28) and (29) in (26) gives us

\begin{aligned} \frac{1}{R_4} &= \frac{2(x'^2 + y'^2 + 3d^2/4 \pm 2y'd)}{dR^2}\\  &= \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3} \pm 2\sqrt{\frac{1}{R_1R_2} + \frac{1}{R_2R_3} + \frac{1}{R_1R_3}}.\quad\quad(30)  \end{aligned}

With k_i = 1/R_i, this becomes k_4 = k_1 + k_2 + k_3 \pm 2\sqrt{k_1 k_2 + k_2 k_3 + k_1 k_3}, establishing (21).

For the case of C_2 and C_3 internally tangent to C_1 a similar computation to the above can be carried out and we obtain

\displaystyle \frac{1}{R_4} = -\frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3} \pm 2\sqrt{-\frac{1}{R_1R_2} + \frac{1}{R_2R_3} - \frac{1}{R_1R_3}},\quad\quad(31)

which is the same as (28) with R_1 replaced with -R_1.

Note that Descartes’ theorem also holds in the special cases of two parallel lines tangent to two equal circles or a single line tangent to three mutually tangent circles. In the latter case we may set k_4 = 0 and assuming k_1 \geq k_2 we obtain from (18) the nice formula

\sqrt{k_3} = \sqrt{k_1} \pm \sqrt{k_2}.\quad\quad(32)

We see these two solutions below in the right figure.

degenerate_cases

Further generalisations of Descartes’ theorem to further dimensions are in [1], and more can be read about tangent circle packings in [5].

References

[1] J.C. Lagarias, C.L. Mallows, and A. Wilks, Beyond the Descartes Circle Theorem, American Mathematical Monthly, 109 (2002), 338-361. Available at http://www.arxiv.org/abs/math?papernum=0101066.

[2] S. Northshield, Complex Descartes Circle Theorem, to appear, American Mathematical Monthly.

[3] D. Pedoe, On a theorem in geometry, American Mathematical Monthly, 74 (1967), 627-640.

[4] P. Sarnak, Integral Apollonian Packings, American Mathematical Monthly, 118 (2011), 291-306.

[5] D. Austin, When Kissing Involves Trigonometry, Feature Column from the AMS, March 2006.

 

Next Page »

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: