# Chaitanya's Random Pages

## November 30, 2013

Filed under: cricket,sport — ckrao @ 11:54 pm

Recently retired Sachin Tendulkar is probably the sportsman who gave me the most total enjoyment over my lifetime. His peak batting period was probably from 1993 to the 2003 World Cup but he came back from injury well to become ICC Player of the year in 2010 at age 37 and after more than 20 years of playing internationally. He has been adored by millions and through all the pressure and expectations over such a long period managed to remain a likeable humble figure. His solid compact batting technique allowed him to flourish in both longer and shorter formats of the game better than almost all players during his time (he played with or against 982 others in international matches!). He also chipped in handily with the ball taking over 150 ODI wickets – Steve Waugh said Tendulkar could spin the ball more than regular spinners and could have taken 100 wickets had he put his mind to it [ref].

Here are his test and ODI career summarised by two graphs. The last 30 innings averages are intended his “form” at the time.

Below are some links collected about his career highlights and statistics, I may add to these over time.

HowSTAT! player profile for tests, ODIs (including career graphs for tests and ODIs)

Cricbuzz:

Video:

## November 29, 2013

### Critical points of polynomials with respect to the roots

Filed under: mathematics — ckrao @ 1:28 pm

Recall that a critical point of a polynomial $p:\mathbb{C} \rightarrow \mathbb{C}$ is a point $w$ for which $p'(w) = 0$. The Gauss-Lucas theorem states that the critical points of $p$ all lie within the convex hull of its set of zeros and we shall explain why this holds below. The real-number analogue of this is that the stationary points of a polynomial with real roots all lie between the smallest and largest root.

Denote the roots of the polynomial by $z_1, z_2, \ldots, z_n$ (we’ll assume they are distinct) and the critical points by $w_1, w_2, \ldots, w_{n-1}$. We then may write our polynomial as $p(z) = k \prod_{i=1}^n (z - z_i)$ for some constant $k$ and its derivative by the product rule is

$\displaystyle p'(z) = k \sum_{j=1}^n \prod_{i=1}^n \frac{z-z_i}{z-z_j} = p(z) \sum_{j=1}^n \frac{1}{z-z_j}.\quad \quad ...(1)$

If $p(w_i) \neq 0$ then as $w_i$ is a critical point of $p$, $p'(w_i) = 0$ and so

$\displaystyle 0 = \sum_{j=1}^n \frac{1}{w_i-z_j} = \sum_{j=1}^n \frac{\bar{w_i} - \bar{z_j}}{|w_i - z_j|^2},$

from which

$\displaystyle w_i \sum_{j=1}^n \frac{1}{|w_i - z_j|^2} = \sum_{j=1}^n \frac{z_j}{|w_i - z_j|^2}.\quad\quad...(2)$

In other words,

$\displaystyle w_i = \sum_{k=1}^n \alpha_k z_k,\quad\quad...(3)$

where $\alpha_k = \frac{1/|w_i - z_k|^2}{\sum_{j=1}^n 1/|w_i - z_j|^2}$.

Since $\sum_{k=1}^n \alpha_k = \frac{\sum_{k=1}^n 1/|w_i - z_k|^2}{\sum_{j=1}^n 1/|w_i - z_j|^2} = 1$, $w_i$ is a convex combination of the roots $z_k$ of $p(z)$. In other words, $w_i$ is in the convex hull of the set of roots $z_k$.

In the other case of $p(w_i) = 0$, $w_i$ is equal to one of the roots and so is also in the convex hull of the set of roots. This completes the proof of the theorem.

However as mentioned in [1] an interpretation of (3) by Cesàro in 1885 is that if we fix unit masses at the roots $z_i$ (if there are repeated roots place mass equal to the multiplicity), the critical points will be at precisely those points experiencing zero net force, assuming particles repel with a force proportional to the inverse of the distance between them (as opposed to an inverse square law). To see why this is so, if the force at a point $w$ due to a mass at $z$ is proportional to the vector $\frac{1}{|z-w|^2}(z-w)$ (an inverse law, as this has magnitude $1/|z-w|$), then the net force is the sum of these over the masses at all the roots. In terms of any critical point $w_i$, this is the following:

\begin{aligned} \sum_{k=1}^n \frac{1}{|z_k-w|^2}(z_k-w) &= \sum_{k=1}^n \frac{1}{|z_k-w|^2}z_k- w\sum_{k=1}^n \frac{1}{|z_k-w|^2}\\&= w_i\sum_{k=1}^n \frac{1}{|z_k-w|^2}- w\sum_{k=1}^n \frac{1}{|z_k-w|^2} \quad \text{by (2)}\\&=(w_i-w)\sum_{k=1}^n \frac{1}{|z_k-w|^2}, \end{aligned}

which is zero if and only if $w=w_i$, i.e. the point having zero net force is a critical point of $p$.

Bôcher’s theorem generalises this result, replacing polynomials with rational functions (ratios of polynomials) and simply applying negative unit masses at poles.

Another interesting result, mentioned in [2], is that the product of the distances from a root $z_1$ to the other roots (assuming all distinct roots) is precisely $n$ times the product of the distances from $z_1$ to the critical points $w_j$. That is,

$\prod_{i=2}^n |z_1 - z_i| = n \prod_{j=1}^{n-1} |z_1 - w_j|.\quad\quad ...(4)$

To see this, if $p(z) = k \prod_{i=1}^n (z-z_i)$, $p'(z)$ will have the form $kn \prod_{j=1}^{n-1} (z-w_j)$ (since it has leading term $nz^{n-1}$. Note that $z_1$ is not a critical point since we assume the roots are distinct. Hence we may consider the quotient

\begin{aligned} \frac{\prod_{i=2}^n (z_1 - z_i)}{\prod_{j=1}^{n-1} (z_1 - w_j)} &= \frac{\lim_{z \rightarrow z_1} p(z)/(z-z_1)}{p'(z_1)/n}\\&= \lim_{z \rightarrow z_1} \frac{np(z)}{(z-z_1)p'(z)}\\ &= \lim_{z \rightarrow z_1} \frac{np(z)}{(z-z_1)p(z) \sum_{j=1}^n 1/(z-z_j)} \quad \text{from (1)} \\&= \lim_{z \rightarrow z_1} \frac{n}{\sum_{j=1}^n (z-z_1)/(z-z_j)} \\ &= \lim_{z \rightarrow z_1} \frac{n}{1 + \sum_{j=2}^n (z-z_1)/(z-z_j)}\\ &= n.\end{aligned}

Taking magnitudes of both sides leads to the desired result (4). One also can obtain an angular relationship by taking the argument of both sides.

The critical points for the case $n = 3$ have a beautiful geometric interpretation as described in [3]: from the triangle formed by the roots, the critical points are the foci of the largest ellipse that is inscribed in the triangle (this ellipse also happens to pass through the triangle’s midpoints) – this is now known as Marden’s theorem. A generalisation proved by Marden in 1945 and mentioned in [1] is that the critical points of an $n$-degree polynomial are the foci of a degree $n-1$ plane curve tangent to each of the $n(n-1)/2$ line segments formed by taking pairs of the $n$ roots. The points of tangency divide each line segment into a ratio corresponding to the multiplicities of the roots at the endpoints. Also, if the $n$-dimensional polygon is a linear (affine) transform of a regular polygon, it will have an inscribed ellipse passing through its midpoints (called the Steiner inellipse) and the foci of that ellipse will correspond to critical points.

Below are some other nice results about the critical points of a polynomial, gathered from [4] (also see references therein):

• The centre of mass of the roots of $p$ coincides with the centre of mass of the critical points of $p$ (a nice exercise to prove).
• (Anderson) The polynomial root dragging theorem for polynomials with real distinct roots: as roots are dragged to the right by at most $\epsilon$ (so as not to coincide), the critical points also move to the right, each by less than $\epsilon$.
• (Boelkins et al., later Frayer) The polynomial root squeezing theorem for polynomials with real distinct roots: if two roots $z_i, z_j$ are squeezed together by the same amount without passing other roots, the critical points move towards $(z_i + z_j)/2$ or stay fixed.
• (Peyser) Critical points are not too close to the roots: if a polynomial has only real roots $z_1 < z_2 < \ldots < z_n$ and critical points $w_1 < w_2 < \ldots w_{n-1}$ the critical points satisfy
$\displaystyle z_k + \frac{z_{k+1} - z_k}{n - k + 1} \leq w_k \leq z_{k+1} - \frac{z_{k+1} - z_k}{k+1}, \quad k= 1, \ldots, n-1.$
Equality cases are satisfied by Bernstein polynomials. Replacing $1/(n-k+1)$ and $1/(k+1)$ by $m_k/(n-k+m_k)$ and $m_{k+1}/(k + m_{k+1}$ respectively gives a corresponding result (due to Melman) taking into account multiplicities $m_k$ for root $z_k$.

#### References

[1] Qazi Ibadur Rahman, Gerhard Schmeisser, Analytic Theory of Polynomials, Oxford University Press, 2002.

[2] Maxime Bocher, Some Propositions Concerning the Geometric Representation of Imaginaries, Annals of Mathematics, Vol. 7, No. 1/5 (1892 – 1893), pp. 70-72.

[3] Dan Kalman, The Most Marvelous Theorem in Mathematics,  The Journal of Online Mathematics and Its Applications, Vol. 8, March 2008, Article ID 1663.

[4] Neil Biegalle, Investigations in the Geometry of Polynomials, McNair Scholars Journal, Volume 13, Issue 1, Article 3. Available at: http://scholarworks.gvsu.edu/mcnair/vol13/iss1/3

## October 30, 2013

### Sparsely populated regions of Australia

Filed under: geography — ckrao @ 1:11 pm

Upon seeing a population density map of Australia at the Australian Bureau of Statistics site here, I wanted to find out how much of the country has a populaton density less than 0.1 person per square kilometre. This corresponds to the white region below (map uses shapefiles from here and 2012 population estimation data from here). Several of the red regions in the outback only just missed the cutoff having slightly more than 0.1 people per square kilometre.

Red regions have population density > 0.1/sq km

The table below gives population details of the numbered regions in the map above. We see that the sparsest region is western South Australia (3 – Western) with just 112 people in an area close to 75% of the entire state of Victoria! Regions labelled 7,8 of WA, 2,3 of SA, 5,6 of NT, 3,7,9 of QLD and 1 of NSW are the regions with less than 0.02 people per square kilometre.

In summary almost 5.6 million square kilometres, or 73% of the land area of Australia, is occupied by just over 140 thousand people, or 0.6% of the population! The unlabelled white regions are mostly mountainous regions plus the South West Wilderness of Tasmania.

Numbered regions in more detail

 State Number on map Area Name Population Area (sq km) Density (people/sq km) WA 1 Kununurra 8,490 117,663.8 0.0722 2 Roebuck 2,489 55,602.9 0.0448 3 Derby – West Kimberley 9,258 110,883.6 0.0835 4 Halls Creek 3,968 135,357.6 0.0293 5 East Pilbara 8,000 389,540.9 0.0205 6 Exmouth 4,197 134,986.0 0.0311 7 Meekatharra 4,263 414,506.0 0.0103 8 Leinster – Leonora 6,050 496,740.6 0.0122 9 Mukinbudin 3,554 50,125.2 0.0709 10 Kambalda – Coolgardie – Norseman 5,739 217,989.9 0.0263 11 Esperance Region 4,430 55,408.3 0.0800 NT 1 Daly 2,270 34,793.8 0.0652 2 Elsey 2,380 92,949.5 0.0256 3 Gulf 4,741 92,351.7 0.0513 4 Victoria River 2,864 133,608.5 0.0214 5 Barkly 3,089 303,252.5 0.0102 6 Tanami 3,423 192,631.2 0.0178 7 Yuendumu – Anmatjere 2,392 71,841.5 0.0333 8 Sandover – Plenty 4,354 129,514.9 0.0336 9 Petermann – Simpson 2,497 175,251.0 0.0142 SA 1 APY Lands 2,692 102,331.5 0.0263 2 Outback 3,516 519,520.0 0.0068 3 Western 112 168,690.3 0.0007 QLD 1 Cape York 7,602 113,022.7 0.0673 2 Carpentaria 5,340 114,279.0 0.0467 3 Croydon – Etheridge 1,249 68,688.1 0.0182 4 Mount Isa Region 4,097 84,072.8 0.0487 5 Northern Highlands 3,761 108,506.6 0.0347 6 Dalrymple 3,991 68,331.8 0.0584 7 Far Central West 2,515 271,262.1 0.0093 8 Barcaldine – Blackall 5,602 83,909.7 0.0668 9 Far South West 3,342 188,802.5 0.0177 NSW 1 Far West 2,820 146,691.0 0.0192 2 Bourke – Brewarrina 4,524 56,850.2 0.0796 3 Wentworth-Balranald Region 3,742 49,724.6 0.0753 Totals from labelled white region 143,353 5,549,682.3 0.0258 Totals from unlabelled white region 289 41,521.7 0.0070 Totals from white region 143,642 5,591,204.0 0.0257

The above numbered regions do not include the following outback towns which are listed below (seen mostly as dots in the above map). As can be seen their total population is comparable to that of the vast white region shown above. Note that towns such as Cobar, Newman, Cloncurry and Kununurra are larger than Coober Pedy but still are part of the white numbered regions.

 Town Population Area (sq km) Density Kalgoorlie-Boulder 32,859 102.7 320.0 Alice Springs 28,605 327.6 87.3 Mount Isa 21,945 62.8 349.4 Broken Hill 19,103 170.3 112.2 Charters Towers 8,440 41.7 202.4 Roxby Downs 4,953 281.2 17.6 Tennant Creek 3,570 42.1 84.8 Coober Pedy 1,768 77.7 22.8 Totals 121,243 1,106.1 109.6

Even after including these towns, we have just over a quarter of a million people (1.1% of the nation’s population) in such a vast connected region.

## October 24, 2013

### A lower bound for the tail probability of a normal distribution

Filed under: mathematics — ckrao @ 11:17 am

If the random variable $X$ has a normal distribution with mean 0 and variance 1, we know that its tail probability $\text{Pr}(X >x)$ is given by the integral

$\displaystyle \text{Pr}(X >x) = \frac{1}{\sqrt{2\pi}} \int_x^{\infty} \exp (-t^2/2)\ \text{d}t$

(that is, the area under a standard normal bell-shaped curve from $x$ up to $\infty$).

This integral does not have a closed form in terms of elementary functions (unless $x = 0$). However we can find a good lower bound as

$\displaystyle \frac{\sqrt{4 + x^2} - x}{2} \cdot \frac{1}{\sqrt{2\pi}} \exp (-x^2/2) \leq \text{Pr}(X >x) \quad x > 0. \quad \quad (1)$

We show the proof of this result based on [1]. Interestingly it involves Jensen’s inequality: recall that this states that if $f$ is a convex function and ${\mathbb E}$ denotes expectation with respect to some probability distribution, then $f({\mathbb E} Y) \leq {\mathbb E} f(Y)$ for any random variable $Y$. Applied to the convex function $f(u) = 1/u (u > 0)$ this becomes

$\displaystyle \frac{1}{{\mathbb E} Y} \leq {\mathbb E} \frac{1}{Y}. \quad \quad (2)$

For fixed $x > 0$ we now let $Y$ have the distribution

$\displaystyle f_Y(t) = \begin{cases}\frac{te^{-t^2/2}}{\int_x^{\infty} te^{-t^2/2}\ d\text{t} } & \text{if } t \geq x,\\ 0 & \text{if } t < x. \end{cases} \quad \quad (3)$

Applying this in (2) gives

$\displaystyle \frac{\int_x^{\infty} te^{-t^2/2}\ d\text{t}}{\int_x^{\infty} t^2 e^{-t^2/2} \ d\text{t}} \leq \frac{\int_x^{\infty} e^{-t^2/2} \ d\text{t}}{\int_x^{\infty} te^{-t^2/2}\ d\text{t} } \quad \quad (4)$

Evaluating these terms,

$\displaystyle \int_x^{\infty} te^{-t^2/2}\ d\text{t} = \left[-e^{-t^2/2} \right]_x^{\infty} = e^{-x^2/2}$

and

\begin{aligned} \int_x^{\infty} t^2 e^{-t^2/2}\ d\text{t} &= \left[-t e^{-t^2/2} \right]_x^{\infty} - \int_x^{\infty} e^{-t^2/2}\ d \text{t}\\ &= xe^{-x^2/2} + \int_x^{\infty} e^{-t^2/2}\ d \text{t},\end{aligned}

so (4) becomes

$\displaystyle \left(e^{-x^2/2}\right)^2 \leq \left(xe^{-x^2/2} + \int_x^{\infty} e^{-t^2/2}\ d \text{t}\right) \left(\int_x^{\infty} e^{-t^2/2} \ d\text{t}\right).$

This is a quadratic inequality in $a(x):= \left(\int_x^{\infty} e^{-t^2/2} \ d\text{t}\right)$ being of the form

$\displaystyle c(x) \leq (b(x) + a(x))a(x),$

where $c(x) = \left(e^{-x^2/2}\right)^2$ and $b(x) = xe^{-x^2/2}$.

This is equivalent to $c(x) + b^2(x)/4 \leq (a(x) + b(x)/2)^2$, or

$\displaystyle \sqrt{c(x) + b^2(x)/4} - b(x)/2 \leq a(x)$

since the quantities involved are non-negative. In other words we have

$\displaystyle e^{-x^2/2} \frac{\sqrt{4 + x^2} - x}{2} \leq \int_x^{\infty} e^{-t^2/2} \ d\text{t},$

which is equivalent to (1), as desired.

Another lower and upper bounds for the tail probability of a normal distribution are

$\displaystyle \frac{x}{x^2+1} \frac{1}{\sqrt{2\pi}} \exp(-x^2/2) \leq \text{Pr}(X >x) \leq \frac{1}{x}\frac{1}{\sqrt{2\pi}} \exp(-x^2/2),$

a proof of which can be seen, e.g. in [2].
The bound we have looked at can be combined with the following upper bound to arrive at the following tighter bounds.

$\displaystyle \frac{1}{x+ \sqrt{4 + x^2} } \leq \sqrt{\frac{\pi}{2}}\exp (x^2/2) \text{Pr}(X >x) \leq \frac{1}{\sqrt{x+ 8/\pi + x^2}}$

See [3] and [4] for a derivation of the upper bound as well as similar bounds.

#### References

[1] Z. W. Birnbaum, An Inequality for Mill’s Ratio, Ann. Math. Statist. Volume 13, Number 2 (1942), 245-246.

[2] J. D. Cook, Upper and lower bounds for the normal distribution function, 2009.

[4] L. Duembgen, Bounding Standard Gaussian Tail Probabilities, University of Bern Technical Report 76, 2010

## September 18, 2013

### Spacecraft missions to outer planets, minor planets or comets

Filed under: science — ckrao @ 11:50 am

After recently hearing news about Voyager 1 being the first human-made object to leave our solar system, I looked up other spacecraft that have visited the outer planets, minor planets (e.g. asteroids) and comets.

#### Outer Planets

 Spacecraft Launch Date Agency Remarks Pioneer 10 3-Mar-72 NASA / ARC flyby of Jupiter in Dec 1973, lost contact in Jan 2003 when 12b km from earth Pioneer 11 6-Apr-73 NASA /ARC flyby of Jupiter in Dec 1974, Saturn in May 1979, lost contact in 1995 Voyager 2 20-Aug-77 NASA / JPL flyby of all outer planets, the only one to fly by Uranus and Neptune Voyager 1 5-Sep-77 NASA / JPL flyby of Jupiter in Sep 1977, Saturn in Mar 1979, now 19b km from earth Galileo 18-Oct-89 NASA flyby of Venus, Earth, asteroids Gasra and Ida (both incidental) before detailed study of Jupiter and its moons, probe dropped into its atmosphere Ulysses 6-Oct-90 NASA / ESA flyby of Jupiter (Feb 1992), orbiting sun, measuring solar wind and gamma ray bursts Cassini–Huygens 15-Oct-97 NASA/ESA flyby of Jupiter & Saturn, Huygens deployed from Cassini, landed on Saturn’s moon Titan in Jan 2005 New Horizons 19-Jan-06 NASA expected to fly by Pluto in July 2015 Juno 5-Aug-11 NASA expected to reach Jupiter in Aug 2016

#### Minor Planets and comets (other than Halley)

 Spacecraft Launch Date Agency Remarks Dawn 27-Sep-07 NASA orbited Vesta July ’11-Sep ’12, expected to reach Ceres in Feb ’15 Hayabusa 9-May-03 JAXA visited asteroid Itokawa bringing back to earth tiny grains of asteroidal material in June 2010 NEAR Shoemaker 17-Feb-96 NASA studied near-earth asteroid Eros, touched down in Feb 2001 Deep Space 1 24-Oct-98 NASA/JPL flybys of asteroid Braille and Comet Borelly Stardust 7-Feb-99 NASA/JPL returned dust samples from Comet Wild 2, also intercepted comet Tempel 1 in Feb 2011 Deep Impact 12-Jan-05 NASA/JPL impactor collided with nucleus of comet Tempel in July 2005, extended mission EPOXI flew by Comet 103P/Hartley, now on its way to asteroid 2002 GT Rosetta 2-Mar-04 ESA flybys of asteroids Steins and Lutetia in 2008, 2010; expected to reach comet 67P/Churyumov-Gerasimenko in mid 2014 deploying the lander Philae Chang’e-2 1-Oct-10 CNSA flew by asteroid 4179 Toutatis in Dec 2012 after orbiting moon International Cometary Explorer (ICE) 12-Aug-78 NASA/ESA first spacecraft to pass through comet tail (Comet Giacobini-Zinner)

#### Halley’s Comet (during its most recent near-earth encounter in 1985-6)

 Spacecraft Launch date Agency Remarks Giotto 2-Jul-85 ESA passed within 600km of Halley’s comet, then flew by Comet Grigg-Skjellerup in Jul 1992 Vega 1 15-Dec-84 USSR flyby of Venus (descent craft surfaced on Venus) and Halley’s Comet (within 9,000km Mar ’86) Vega 2 21-Dec-84 USSR flyby of Venus (descent craft surfaced on Venus) and Halley’s Comet (Mar ’86) Suisei 18-Aug-85 ISAS (now part of JAXA) within 151,000km of Comet Halley in Mar ’86 Sakigake 7-Jan-85 ISAS (now part of JAXA) within 7m km of Comet Halley

## September 16, 2013

### Polynomial extrapolation of finite exponential sequences

Filed under: mathematics — ckrao @ 11:40 am

Here is a cute problem I first encountered many years ago:

A polynomial $P(x)$ of degree $n$ satisfies $P(k) = 2^k$ for $k = 0, 1, 2, \ldots, n$. Determine $P(n+1)$.

Recall that a polynomial of degree $n$ is uniquely determined by its value at $n+1$ points. Hence $P(n+1)$ could have only one possible value. Is it $2^{n+1}$? Let’s see: here is the solution I saw at the time.

Consider the polynomial $\displaystyle P(x) = \binom{x}{0} + \binom{x}{1} + \ldots + \binom{x}{n}$. Then $P(x)$ is a polynomial of degree $n$ (the $k$‘th term has degree $k+1$). Furthermore, since $\binom{x}{k} = 0$ for $x = 0, 1, \ldots, k-1$, we have for $k = 0, 1, 2, \ldots, n$ the following:

$\displaystyle P(k) = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{n} = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{k} = 2^k.$

(Here we recall that the sum of a row of Pascal’s triangle is a power of 2.)

This shows that $P(x)$ is our unique polynomial with the desired properties, and we find

$\displaystyle P(n+1) = \binom{n+1}{0} + \binom{n+1}{1} + \ldots + \binom{n+1}{n} = 2^{n+1} - 1.$

Neat isn’t it that the polynomial almost climbs up to $2^n$ but ends up one short. Let’s see how this result generalises. Modify the above question so that $P(k) = a^k$ for $k = 0, 1, 2, \ldots, n$ (where $a$ is a constant not equal to 1). What is $P(n+1)$? This time we let

$\displaystyle P(x) := (a-1)^0 \binom{x}{0} + (a-1)^1 \binom{x}{1} + \ldots + (a-1)^n \binom{x}{n} = \sum_{i=0}^n (a-1)^i \binom{x}{i}.$

As before $P(x)$ is clearly a degree $n$ polynomial. Furthermore, for $k = 0, 1, 2, \ldots, n$ we apply the binomial theorem to obtain

\begin{aligned} P(k) &= \sum_{i=0}^n (a-1)^i \binom{k}{i}\\ &= \sum_{i=0}^k (a-1)^i \binom{k}{i}\\ &= (a-1+1)^k\\ &= a^k. \end{aligned}

This constructed polynomial has the desired properties, so by uniqueness we simply substitute $x=n+1$ to find $P(n+1)$:

\begin{aligned} P(n+1) &= \sum_{i=0}^n (a-1)^i \binom{n+1}{i}\\ &= \sum_{i=0}^{n+1} (a-1)^i \binom{n+1}{i} - (a-1)^{n+1} \binom{n+1}{n+1}\\ &= a^{n+1} - (a-1)^{n+1}.\end{aligned}

The way such polynomials can be constructed (i.e. not pulled out of thin air!) is to write down a finite difference table – refer to an earlier blog post here: if the first diagonal of the table is $a_0, a_1, \ldots, a_n$ where $a_0 = P(0)$, then

$\displaystyle p(x) = \sum_{i=0}^n a_i \binom{x}{i}.$

In the first problem it is easy to verify that $a_i = 1$, in the generalisation $a_i = (a-1)^i$.

## August 31, 2013

### UNESCO World Heritage sites with both natural and cultural significance

Filed under: geography — ckrao @ 11:29 am

As of now there are 981 places on the UNESCO World Heritage list, of which 759 have cultural value, 193 are significant natural landmarks and 29 are both. Here are the 29 with mixed properties listed with a brief description, I feel I should have learned more about them long ago. Most of the information is from the UNESCO site (maps found there too) and Wikipedia.

 Country Name Significance Algeria Tassili n’Ajjer geological formations and more than 15,000 drawings dating back to 6000BC Australia Kakadu National Park a third of Australia’s bird species and a quarter of its freshwater fish species here, rock paintings date back 20,000 years, evidence of settlement for 40,000 Willandra Lakes Region oldest known human cremation site (26,000 years old), evidence of settlement 45-60,000 years ago, clay dune formations Tasmanian Wilderness one of world’s last expanses of temperate rainforest, 37 Aboriginal cave sites dating back up to 30,000 years Uluru-Kata Tjuta National Park sandstone monolith and conglomerate rock domes, symbolic of Aboriginal spiritual connection to the land China Mount Taishan a traditional scenic place of worship with its geological birth over 3 billion years ago Mount Huangshan granite peaks often emerging from clouds, inspiring source of art and literature Mount Emei Scenic Area, including Leshan Giant Buddha Scenic Area largest Buddha statue in the world (71m high),3200 plant species including 100 endemic Mount Wuyi largest and most representative forest encompassing the diversity of the Chinese Subtropical Forest and the South Chinese Rainforest, cradle of Neo-Confucianism France/Spain Pyrénées – Mont Perdu display of deep canyons and spectacular cirque walls, illustrates traditional mountain way of life now rare in Europe Gabon Ecosystem and Relict Cultural Landscape of Lopé-Okanda last remnants of grass savannas created in central Africa created during last Ice Age, home to many endangered land mammals, migration route for very early human settlement Greece Meteora six monasteries on sandstone rock pillars up to 400m above the valley below Mount Athos Orthodox spiritual centre with 20 monasteries and school of painting, well preserved Mediterranean forest Guatemala Tikal National Park major centre of Mayan civilisation from 6th to 10th century, rainforest includes over 300 bird species Jordan Wadi Rum Protected Area 25,000 petroglyphs dating back 12,000 years, large diversity of desert landforms Lesotho/South Africa Maloti-Drakensberg Park more than 250 endemic plant species, vast gallery of rock paintings by the San people over a period of 4000 years, a refuge for many threatened large mammals Mali Cliff of Bandiagara (Land of the Dogons) 150km long sandstone cliff up to 500m high, some of impressive architecture dates back to 14th century New Zealand Tongariro National Park volcanic summits in central North Island sacred to Maoris Palau Rock Islands Southern Lagoon mushroom-shaped limestone islands, highest concentration of marine lakes in the world, human remains date back over 3000 years Peru Historic Sanctuary of Machu Picchu symbolic of Inca Empire at its height, mountainous scenery Río Abiseo National Park outstanding example of early human occupation at high altitudes in the Andean region with over 30 sites found, much undisturbed landscape Spain Ibiza, Biodiversity and Culture well-preserved seagrass, evidence of Phoenician settlements Sweden Laponian Area world’s largest unmodified nature area to be still cultured by natives (Sami people), variety of natural glacial phenomena, large population of brown bear and alpine flora Tanzania Ngorongoro Conservation Area world’s largest inactive, intact, and unfilled volcanic caldera, evidence of hominid evolution dating back 4 million years, part of large mammal migration route, high density of lions the Former Yugoslav Republic of Macedonia Natural and Cultural Heritage of the Ohrid region one of most ancient European settlements, early manuscripts of Slavonic literature, more than 200 endemic species in lake Turkey Göreme National Park and the Rock Sites of Cappadocia mountain ridges, valleys and pinnacles known as “fairy chimneys”, large cave dwelling complexes, settled in Roman times Hierapolis-Pamukkale Greco-Roman ruins, visually appealing landforms and pools of mineralised water from hot springs United Kingdom St Kilda Scottish archipelago with architectural features from historic and prehistoric times, breeding ground for many seabird species including gannets and puffins USA Papahānaumokuākea spiritually significant to Hawaiians, supporting 7000 marine species, a quarter endemic

## August 28, 2013

### Permutations of 1,1,2,2,…,n,n with no two adjacent terms equal

Filed under: mathematics — ckrao @ 9:12 pm

A nice question from the Australian Mathematics Competition of 1983 asks how many ways 4 differently coloured pairs of socks can be lined up so that no socks of the same pair are adjacent. More generally, in how many ways can we permute the numbers $1,1,2,2,...,n,n$, so that no two consecutive terms are equal? For example, $1,2,3,2,3,1$ is permitted but $1,2,2,3,1,3$ is not.

This can be solved by the principle of inclusion-exclusion as follows. For $i=1,...,n$ Let $P_i$ be the set of permutations of $1,1,2,2,...,n,n$ in which that the two copies of $i$ are adjacent. We wish to find the number of permutations in $\left( \cup_{i=1}^n P_i \right)^c$, as we are interested in permutations not contained in any $P_i$. The total number of permutations (without restriction of order) is $(2n)!/2^n$. Using symmetry the cardinality $a_n$ of this set can be enumerated as

\begin{aligned} a_n &= \left| \left( \cup_{i=1}^n P_i \right)^c \right| \\ &= \frac{(2n)!}{2^n} - \sum_{i=1}^n \left|P_i \right| + \sum_{i .

The general term $\left| P_1 \cap P_2 \ldots \cap P_k \right|$ can be found by permuting the k + 2(n-k) objects 1-1, 2-2, …, k-k, k+1, k+1, k+2, k+2, …, n, n, where the adjacent terms 1-1 up to k-k are treated as one compound object. This can be done in $(2n-k)!/2^{n-k}$ ways, where the division by $2^{n-k}$ is performed as the last $n-k$ pairs are indistinguishable when permuted. We end up with

$\displaystyle a_n = \sum_{k= 0}^n (-1)^{k} \binom{n}{k} \frac{(2n-k)!}{2^{n-k}}.$

Evaluating this for $n = 4$ gives $\displaystyle a_4 = 8!/2^4 - 4.7!/2^3 + 6.6!/2^2 - 4.5!/2 + 4! = 1080 - 240 + 24 = 864$ (noting that the first two terms always cancel). The Venn diagram below shows the number of permutations of $1,1,2,2,3,3,4,4$ that contain each consecutive pair of 11, 22, 33, 44. For example, there are 246 permutations containing the two 2s adjacent, but the two 1s, two 3s and two 4s are not adjacent. All the numbers shown are found again by inclusion-exclusion. For example,

\begin{aligned} \left|P_1^c \cap P_2 \cap P_3^c \cap P_4^c \right| &= \left|P_2 \right| - 3 \left|P_1 \cap P_2 \right| + 3 \left|P_1 \cap P_2 \cap P_3 \right| - \left| P_1 \cap P_2 \cap P_3 \cap P_4 \right| \\&= \frac{7!}{2^3} - 3 \frac{6!}{2^2} + 3\frac{5!}{2} - 4! \\ &= 630 - 540 + 180 - 24 \\ &= 246.\end{aligned}

All of the numbers shown in the Venn diagram add to $864 + 4\times 246 + 6 \times 84 + 4 \times 36 + 24 = 2520 = 8!/2^4$, the total number of permutations of 1,1,2,2,3,3,4,4.

Note that our answer of 864 to the original question is divisible by 4! – this makes sense since we can permute the numbers 1,2,3,4 in any of 24 ways to arrive at another way of arriving at a sequence with the same property that no adjacent terms are equal. With this in mind, let us turn our attention to the sequence $b_n = a_n / n!$. The first terms are 0,1,5,36,329 and we can think of $b_n$ as counting the number of ways we can permute $1,1,2,2,...,n,n$ so that no two adjacent terms are equal and the first occurrence of $i$ always precedes the first occurrence of $i+1$ ($i = 1,2,..., n-1$). Call such a sequence allowable. For example 1,2,3,2,3,1 is allowable but 2,3,1,3,1,2 is not. It turns out that the sequence $b_n$ is linked to the Bessel polynomial $y_n(x)$ evaluated at $x=1$ (hence it’s the sum of the coefficients of the polynomials – see OEIS A000806 for more information).

Interestingly the $b_n$s are linked by the recurrence relation

$b_n = (2n-1) b_{n-1} + b_{n-2}, \quad b_0 = 1, b_1 = 0,$

which we shall now derive.

To be more concrete we shall link $b_4 = 864/4! = 36$ to $b_3 = 5$ and $b_2 = 1$ ($b_4 = 36 = (2(4)-1) \times 5 + 1$). The general case follows similarly.

We can list the allowed permutations of 1,1,2,2 and 1,1,2,2,3,3 as

• (1,2,1,2) for $n=2$ and
• (1,2,1,3,2,3), (1,2,3,1,2,3), (1,2,3,2,1,3), (1,2,3,2,3,1), (1,2,3,1,3,2) for $n = 3$.

We now create an allowable permutation for $n=4$ in one of three ways:

1. from each $n=2$ sequence, add 1 to each element, insert 1 at the start of the sequence and 4,1,4 at the end (e.g. (1,2,1,2) $\leftrightarrow$ (1,2,3,2,3,4,1,4)).
2. from each $n=3$ sequence, firstly move the final element next to its other occurrence in the sequence, then add 1 to each element, insert a 1 at the start of the sequence and finally insert a 1 between the two duplicated elements to prevent them from appearing twice in a row (e.g. (1,2,3,1,3,2) $\leftrightarrow$ (1,2,2,3,1,3) $\leftrightarrow$ (1,2,3,1,3,4,2,4)).
3. from each $n = 3$ sequence, add 1 to each element, insert 1 at the start of the sequence and a second 1 in any of the remaining $(2n-2) = 6$ allowable positions – it cannot be placed next to the first 1 (e.g. (1,2,3,1,3,2) $\leftrightarrow$ (1,2,3,1,4,2,4,3)).

Below we see how the $n=2$ and $n=3$ generate allowable $n=4$ sequences.

(1,2,1,2) $\leftrightarrow$ (1,2,3,2,3,4,1,4)

(1,2,1,3,2,3) $\leftrightarrow$ (1,2,3,2,4,1,4,3), (1,2,1,3,2,4,3,4), (1,2,3,1,2,4,3,4), (1,2,3,2,1,4,3,4), (1,2,3,2,4,1,3,4), (1,2,3,2,4,3,1,4), (1,2,3,2,4,3,4,1)
(1,2,3,1,2,3) $\leftrightarrow$ (1,2,3,4,1,4,2,3), (1,2,1,3,4,2,3,4), (1,2,3,1,4,2,3,4), (1,2,3,4,1,2,3,4), (1,2,3,4,2,1,3,4), (1,2,3,4,2,3,1,4), (1,2,3,4,2,3,4,1)
(1,2,3,2,1,3) $\leftrightarrow$ (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,2,4), (1,2,3,1,4,3,2,4), (1,2,3,4,1,3,2,4), (1,2,3,4,3,1,2,4), (1,2,3,4,3,2,1,4), (1,2,3,4,3,2,4,1)
(1,2,3,2,3,1) $\leftrightarrow$ (1,2,3,4,1,4,3,2), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,2,3,1) $\leftrightarrow$ (1,2,1,2,3,4,3,4), (1,2,1,3,4,3,4,2), (1,2,3,1,4,3,4,2), (1,2,3,4,1,3,4,2), (1,2,3,4,3,1,4,2), (1,2,3,4,3,4,1,2), (1,2,3,4,3,4,2,1)
(1,2,3,1,3,2) $\leftrightarrow$ (1,2,3,1,3,4,2,4), (1,2,1,3,4,2,4,3), (1,2,3,1,4,2,4,3), (1,2,3,4,1,2,4,3), (1,2,3,4,2,1,4,3), (1,2,3,4,2,4,1,3), (1,2,3,4,2,4,3,1)

Let us now see why all allowable $n=4$ sequences have indeed been generated and that no allowable sequence has been repeated (justifying the use of double arrows above).

If we take an allowable $n=4$ sequence, either it ends with 4,1,4 or it does not – if it does it begins to class 1 above. Deleting the 1 at the start and 4,1,4 at the end, then subtracting 1 from each element will map it to an allowable $n=2$ sequence.

e.g. (1,2,3,2,3,4,1,4) $\rightarrow$ (2,3,2,3) $\rightarrow$ (1,2,1,2)

If it does not end in 4,1,4, the second 1 either is between two repeated elements (class 2) or it is not (class 3).  The two repeated elements cannot appear at the end since such a sequence could only end with 4,1,4 and we are back to class 1. (If say a 3,1,3 were at the end, the first 4 could only appear after the first 3 and so has not occurred earlier in the sequence.) Deleting the two 1s, moving the second of the repeated elements to the end (we have just seen it is not already at the end so it will become separated from its partner) and then subtracting 1 from each element maps it to an allowable $n =3$ sequence. The first occurrence of $i$ will still precede the first occurrence of $i+1$ in the $n=3$ sequence.

e.g. (1,2,3,4,1,4,3,2) $\rightarrow$ (2,3,4,4,3,2) $\rightarrow$ (2,3,4,3,2,4) $\rightarrow$ (1,2,3,2,1,3)

In class 3, since the second 1 is not between two repeated elements, deleting it and the first 1, then subtracting 1 from each element would lead to an allowable $n=3$ sequence.

e.g. (1,2,1,3,4,3,4,2) $\rightarrow$ (2,3,4,3,4,2) $\rightarrow$ (1,2,3,2,3,1)

This shows that all allowable $n = 4$ sequences can be mapped uniquely into one of class 1, 2 or 3, so we have a desired generation of new $n = 4$ sequences from $n=2$ and $n = 3$ through steps 1-3 above. The above can be generalised by replacing 4 with $n$. Enumerating these now, we have $b_{n-2}$ sequences from case 1, $b_{n-1}$ sequences from case 2 and $(2n-2)b_{n-1}$ sequences from case 3. In total,

$\displaystyle b_n = b_{n-2} + b_{n-1} + (2n-2) b_{n-1} = (2n-1) b_{n-1} + b_{n-2},$

as we wished to show. The $b_0 = 1, b_1 = 0, b_2 = 1$ instances are easy to verify and satisfy the above recurrence.

## July 27, 2013

### Wide range in maximum temperatures within a month in Melbourne

Filed under: climate and weather,geography — ckrao @ 5:02 am

This month Melbourne recorded its highest July recorded maximum temperature of 23.3°C. Then just two days later the maximum was just 9.7°C. This temperature difference seemed highly unusual to me and indeed it was. The difference of 13.6°C is easily the highest recorded for the month of July in over 150 years of records (the previous record was 12° in 1975 when it was 11.1°C on the 3rd and 23.1°C on the 30th of the month). The graph below shows the distribution of the difference between highest maximum and lowest maximum temperatures for each month (data from the Australian Bureau of Meteorology website). In a box and whisker plot the thick horizontal lines represent the medians and the box boundaries are the 25th and 75th percentiles. Outliers are shown for data more than 1.5 times the inter-quartile range away from the 25th or 75th percentiles. We see that in Melbourne much larger maximum temperature fluctuations are expected in the warmer months. July has a median range of just 7.7°C between its highest and lowest maximum temperatures.

Here are a few other outliers indicated on the graph when there were large extremes in maximum temperatures during the month.

• Dec 1867: 10.4°C (12th – coldest Dec maximum on record), 40.3°C (19th)
• May 1905: 28.7°C (9th – warmest May day on record), 11.4°C (11th)
• Nov 1911: 12.2°C (1st), 40.7°C (30th)
• Oct 1922: 35.8°C (22nd), 9.0°C (29th – coldest Oct maximum on record)
• Dec 1924: 40.1°C (12th), 11.5°C (26th)

It’s interesting that it has been so long since we have had such an anomaly in maximum temperatures within a month!

## July 25, 2013

### Solving a tricky geometry problem using cross ratios

Filed under: mathematics — ckrao @ 12:17 pm

I recently had fun playing around with the following problem, based on the last question of the 2003 AIME I.

In triangle $ABC$ let be the midpoint of $CA$, and let $D$ be the point on $CA$ such that $BD$ bisects angle $ABC$. Let $F$ be the point on $BC$ such that $DF$ and $BD$ are perpendicular. If $DF$ meets $BM$ at $E$, find the ratio $DE/EF$ in terms of the side lengths of $ABC$.

The interested reader might like to have an attempt at this problem before reading further.

Initially I solved this using vector geometry applying facts such as $\vec{BM} = (\vec{BA} + \vec{BC})/2$, $\vec{BD} = (|BC|\vec{BA} + |AB|\vec{BC})/(|BC| + |AB|)$ and $\vec{DB}. \vec{DF} = 0$ (see below). After seeing it led to a relatively simple answer I started looking for a more elegant approach and after seeing this page that shows methods using mass point geometry and applications of Menelaus’ theorem, came up with the following nice solution.

Extend $FD$ to meet $BA$ in $G$ as shown below. As $BD$ is an angle bisector perpendicular to $GF$, $F$ reflects in line $BD$ to $G$ so $D$ is the midpoint of $GF$.

Also the lines $ADMC$ and $GDEF$ are both perspective from the point $B$, so the cross ratios $(AM/MC)/(AD/DC)$ and $(GE/EF)/(GD/DF)$ are equal (indeed, by using the triangle area formula $\frac{1}{2}ab\sin C$ these ratios can be shown to be equal to $(\sin \angle ABM/ \sin \angle MBC)/(\sin \angle ABD / \sin \angle DBC)$). Since $M$ and $D$ are midpoints of $AC$ and $GF$ respectively, $AM/MC = GD/DF = 1$, so we are left with

$\displaystyle \frac{GE}{EF} = \frac{DC}{AD}.$

By the angle bisector theorem, this ratio is equal to $a/c$, where $a = BC, c = AB$. We finally have

$\displaystyle \frac{DE}{EF} = \frac{GE-EF}{2EF} = \frac{GE/EF - 1}{2} = \frac{a-c}{2c},$

as required. It’s interesting that the answer has no dependence on the length of side $AC$.

Here is the original way I had solved the problem. Let $B$ be the origin and define vectors $\boldsymbol{a} = \vec{BA}$ and $\boldsymbol{c} = \vec{BA}$ of length $c$ and $a$ respectively. Then as $BD$ is the angle bisector,  we can write $\vec{BD} = \lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c}$, where $\lambda_1 = a/(a+c)$ and $\lambda_2 = c/(a+c)$.

Also let $\vec{BF} = k \boldsymbol{c}$ where $k = BF/BC$. We find $k$ by using the fact that $DF \perp DB$:

$\displaystyle \left(kc - (\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})\right).(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c}) = 0.$

From this,

$\displaystyle k = \frac{(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c}).(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})}{\boldsymbol{c}.(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})} = \frac{BD^2}{\boldsymbol{c}.(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})}.$

Since $E$ is on $DF$, for some $\mu$ between 0 and 1,

$\displaystyle \vec{BM} = \mu \vec{BD} + (1-\mu) \vec{BF} = \mu \lambda_1 \boldsymbol{a} + (\mu \lambda_2 + (1-\mu) k )\boldsymbol{c}.$

Since $E$ is also on the median $BM$, it and have equal components of $a$ and $c$ (being a median).

Hence, $\mu \lambda_1 = \mu \lambda_2 + (1-\mu) k$ from which

$\displaystyle \frac{\lambda_1 - \lambda_2}{k} = \frac{1-\mu}{\mu} = \frac{(\lambda_1 - \lambda_2) \boldsymbol{c}.(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})}{BD^2}. \quad \quad (1)$

We wish to find the ratio $DE/EF = (1-\mu)/\mu$, which is as above.

Here is one easy way to find $k = BF/BC$ that I found only afterwards. If $P$ is the midpoint of $BF$ then since $BDF$ is a right-angled triangle, $BP = PD = PF$ and so $\angle PDB = \angle DPE = \angle DBA$, from which $AB \parallel DP$.

Then $\triangle BCA$ and $\triangle PCD$ are similar, from which

$\displaystyle \frac{BP}{BC} = \frac{AD}{AC} = \frac{c}{a+c}.$

Hence $k = BF/BC = \frac{2c}{a+c}$ and so

$\displaystyle \frac{DE}{EF} = \frac{\lambda_1 - \lambda_2}{k} = \frac{(a-c)}{(a+c)} \frac{(a+c)}{2c} = \frac{a-c}{2c}.$

The original way I had found $k$ was without the benefit of this construction and by pure computation instead. Referring back to (1), we have $\boldsymbol{c}.\boldsymbol{c} = a^2$ and by the cosine rule, $\boldsymbol{c}.\boldsymbol{a} = (a^2 + c^2 - b^2)/2$. Recalling that $\lambda_1 = a/(a+c)$ and $\lambda_2 = c/(a+c)$,

\begin{aligned} \boldsymbol{c}.(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c}) &= \lambda_1 \boldsymbol{c}.\boldsymbol{a} + \lambda_2 \boldsymbol{c}.\boldsymbol{c}\\ &= \frac{a(a^2 + c^2 - b^2) + 2ca^2}{2(a+c)} \\ &= \frac{a(a+b+c)(a-b+c)}{2(a+c)}. \quad \quad (2) \end{aligned}

Secondly the denominator of (1) is

\begin{aligned} BD^2 &= (\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c}).(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})\\ &= \lambda_1^2 c^2 + \lambda_2^2 a^2 + 2\lambda_1 \lambda_2 \boldsymbol{a}.\boldsymbol{c} \\ &= \frac{1}{(a+c)^2} \left[a^2 c^2 + c^2 a^2 + ac(a^2 + c^2 - b^2) \right]\\ &= \frac{ac}{(a+c)^2} \left[2ac + a^2 + c^2 - b^2 \right] \\ &= \frac{ac(a+b+c)(a-b+c)}{(a+c)^2}. \quad \quad (3)\end{aligned}

Combining (2) and (3) in (1) leads to the following feast of cancellation:

\begin{aligned} \frac{DE}{EF} &= \frac{(\lambda_1 - \lambda_2) \boldsymbol{c}.(\lambda_1 \boldsymbol{a} + \lambda_2 \boldsymbol{c})}{BD^2} \\&= \frac{(a-c)}{(a+c)} \frac{a(a+b+c)(a-b+c)}{2(a+c)} \frac{(a+c)^2}{ac(a+b+c)(a-b+c)} \\ &= \frac{a-c}{2c},\end{aligned}

as was found before. Note that expressions (2) and (3) are respectively the square of the length of the angle bisector $BD^2$ and the dot product $\vec{BC}.\vec{BD}$ in terms of the side lengths of any triangle, and we have found them to be similar in form.

Next Page »

The Rubric Theme. Blog at WordPress.com.