# Chaitanya's Random Pages

## November 25, 2015

### An identity based on three numbers summing to zero

Filed under: mathematics — ckrao @ 11:06 am

Here is a nice identity which according to [1] appeared in a 1957 Chinese mathematics competition.

If $x + y + z = 0$ then

$\displaystyle \left(\frac{x^2 + y^2 + z^2}{2} \right)\left(\frac{x^5 + y^5 + z^5}{5} \right) = \left(\frac{x^7 + y^7 + z^7}{7} \right).\quad \quad (1)$

An elegant proof of this avoids any lengthy expansions. Let $x$, $y$ and $z$ be roots of the cubic polynomial

\begin{aligned} (X-x)(X-y)(X-z) &= X^3 - (x+y+z)X^2 + (xy + yz + zx)X - xyz\\ &:= X^3 + aX + b.\quad \quad (2)\end{aligned}

Then

\begin{aligned} x^2 + y^2 + z^2 &= (x+y+z)^2 - 2(xy + yz + xz)\\ &= 0 -2a\\ &= -2a\quad\quad (3)\end{aligned}

and summing the relation $X^3 = -aX - b$ for each of $X=x, X=y$ and $X=z$, gives

\begin{aligned}x^3 + y^3 + z^3 &= -a(x + y + z) - 3b\\ &= -3b.\quad\quad (4)\end{aligned}

In a similar manner, $X^4 = -aX^2 - bX$ and so

\begin{aligned} x^4 + y^4 + z^4 &= -a(x^2 + y^2 + z^2) - b(x + y + z)\\ &= -a(-2a)\\ &= 2a^2.\quad \quad (5)\end{aligned}

Next, $X^5 = -aX^3 - bX^2$ and so

\begin{aligned} x^5 + y^5 + z^5 &= -a(x^3 + y^3 + z^3) - b(x^2 + y^2 + z^2)\\ &= -a(-3b) -b(-2a)\\ &= 5ab.\quad \quad (6)\end{aligned}

Finally, $X^7 = -aX^5 - bX^4$ and so

\begin{aligned} x^7 + y^7 + z^7 &= -a(x^5 + y^5 + z^5) - b(x^4 + y^4 + z^4)\\ &= -a(5ab) -b(2a^2)\\ &= -7a^2b.\quad \quad (7)\end{aligned}

We then combine (3), (6) and (7) to obtain (1). It seems that $x^n + y^n + z^n$ for higher values of $n$ are more complicated expressions in $a$ and latex $b$, so we don’t get as pretty a relation elsewhere.

#### Reference

[1] Răzvan Gelca and Titu Andreescu, Putnam and Beyond, Springer, 2007.

## October 31, 2015

### Highest ODI batting averages over 100 consecutive innings

Filed under: cricket,sport — ckrao @ 11:13 am

The 3 centuries by A B de Villiers in the most recent ODI series against India has given him a sizeable lead over the rest in the following list of highest batting averages in 100 consecutive one day international cricket innings. On 92 out of those 100 innings he came in at number 4 or lower (and never opened in that time span), and still he managed to score over 54 runs per innings. All of his ODI hundreds to date have been scored at a strike rate of at least 100. Some very impressive numbers have been posted for other batsmen in the list too.

 Player Innings Not out Runs HS Average Balls faced Strike rate 100s 50s 0s Time period A B de Villiers* 100 21 5454 162* 69.04 4935 110.52 20 27 1 Nov 09-Oct 15 Bevan 100 40 3726 108* 62.10 4844 76.92 3 26 2 Sep 94-Aug 99 Dhoni* 100 34 4027 139* 61.02 4587 87.79 5 28 2 Feb 09-Jan 14 Amla* 100 7 5388 159 57.94 5991 89.93 20 27 2 Nov 08-Mar 15 Richards 100 19 4611 189* 56.93 5103 90.36 8 34 4 Jun 75-Nov 86 Kohli* 100 16 4668 183 55.57 5016 93.06 17 21 7 Mar 11-Mar 15 Tendulkar 100 11 4789 186* 53.81 5273 90.82 18 16 5 Apr 98-Jun 02 Hussey 100 33 3574 109* 53.34 4114 86.87 2 27 2 Feb 05-Nov 09 Jones 100 19 4317 145 53.30 5667 76.18 7 32 1 Jan 85-Feb 91 Sangakkara 100 10 4736 169 52.62 5417 87.43 14 28 5 Aug 11-Mar 15 Chanderpaul 100 21 4144 149* 52.46 5627 73.64 8 30 2 Sep 04-Jun 10 Lara 100 11 4575 169 51.40 5738 79.73 11 30 3 Mar 92-Dec 97 Kallis 100 21 4044 139 51.19 5474 73.88 7 27 3 Mar 00-Feb 04 Ponting 100 11 4397 164 49.40 5068 86.76 11 29 4 Nov 03-Dec 07 Greenidge 100 11 4382 133* 49.24 6583 66.57 10 27 3 Dec 75-Dec 85

Statistics are from ESPN Cricinfo. I would be interested to know if there are others who averaged 50+ over 100 consecutive ODI innings.

## October 28, 2015

### The product of distances to a point from vertices of a regular polygon

Filed under: mathematics — ckrao @ 11:12 am

Here is a cool trigonometric identity I recently encountered:

$\displaystyle \prod_{k=1}^n \sin \frac{(2k-1)\pi}{4n} = \prod_{k=1}^n \cos \frac{(2k-1)\pi}{4n} = \frac{\sqrt{2}}{2^n}.$

For example, for $n = 9$:

$\displaystyle \sin 5^{\circ} \sin 15^{\circ} \sin 25^{\circ} \ldots \sin 85^{\circ} = \frac{\sqrt{2}}{2^9}.$

After thinking about it for some time I realised that the terms on the left side can each be seen as half the lengths of chords of a unit circle with 4n evenly spaced points that can then be rearranged to be distances from a point on the unit circle to half of the points of a regular (2n)-gon, as shown in the figure below.

With the insight of this figure we then write

\begin{aligned} \prod_{k=1}^n \sin \frac{(2k-1)\pi}{4n} &= \left(\prod_{k=1}^{2n} \left| \sin \frac{(2k-1)\pi}{4n} \right|\right)^{1/2} \quad \text{ (all terms are positive)}\\ &= \prod_{k=1}^{2n} \left| \frac{\exp(i\frac{(2k-1)\pi}{4n}) - \exp(-i\frac{(2k-1)\pi}{4n})}{2i} \right|^{1/2} \\ &= \frac{1}{2^n} \prod_{k=1}^{2n} \left| \exp\left(-i \frac{(2k+1)\pi}{4n}\right) \left(\exp\left(i\frac{4k\pi}{4n}\right) - \exp\left(i\frac{2\pi}{4n}\right)\right) \right|^{1/2}\\ &= \frac{1}{2^n} \prod_{k=1}^{2n} \left| \exp\left(-i \frac{(2k+1)\pi}{4n}\right) \right|^{1/2} \left| \left(\exp\left(i\frac{4k\pi}{4n}\right) - \exp\left(i\frac{2\pi}{4n}\right)\right) \right|^{1/2}\\ &= \frac{1}{2^n} \prod_{k=1}^{2n} \left| \left(\exp\left(i\frac{2k\pi}{2n}\right) - \exp\left(i\frac{\pi}{2n}\right)\right) \right|^{1/2}\\ &= \frac{1}{2^n} \left|\prod_{k=1}^{2n} \left(z-\exp\left(i\frac{2k\pi}{2n}\right)\right) \right|^{1/2} \quad \text{where }z = \exp\left(i\frac{\pi}{2n}\right)\\ &= \frac{1}{2^n} |(z^{2n}-1)|^{1/2}\\ &= \frac{1}{2^n} |-1-1|^{1/2}\\ &= \frac{\sqrt{2}}{2^n}. \end{aligned}

(The cosine formula can be derived in a similar manner.)

In general, the product of the distances of any point $z$ in the complex plane to the n roots of unity $\omega_n$  is

$\displaystyle \prod_{k=0}^{n-1} |z-\omega_n| = |z^n - 1|.$

The above case was where $z^n = -1$. Two more cases are illustrated below, this time for n = 10. In the left example the product of distances is

$\displaystyle \prod_{k=0}^9 |(1+i)-\exp(2\pi i k/10)| = |(1+i)^{10}-1| = 5\sqrt{41}$

while for the right example it is

$\displaystyle \prod_{k=0}^9 |1/2-\exp(2\pi i k/10)| = |(1/2)^{10}-1| = 1023/1024.$

Note that earlier in the year I posted on the distances to a line from vertices of a regular polygon.

## September 28, 2015

### First space probes to visit bodies of the Solar System

Filed under: science — ckrao @ 11:11 am

The table below shows the first space probes to visit various bodies of the Solar System (and the year) by mission type (flyby, orbit, impact or soft landing). Notably 2015 had three events: MESSENGER ended its four year orbit of Mercury with the first impact on the planet, Dawn became the first spacecraft to orbit a dwarf planet (Ceres, in the asteroid belt), and New Horizons flew by Pluto.

 flyby orbit impact soft landing Sun Helios 2 1976 (within 43m km) Luna 1 1959 Mercury Mariner 10 1974 MESSENGER 2011 MESSENGER 2015 Venus Venera 1 1961 Venera 9 1975 Venera 3 1966 Venera 9 1975 Mars Mariner 4 1965 Mariner 9 1971 Mars 2 1971 Mars 3 1971 Jupiter Pioneer 10 1973 Galileo 1995 Galileo 1995 Saturn Pioneer 11 1979 Cassini 2004 Uranus Voyager 2 1986 Neptune Voyager 2 1989 Pluto New Horizons 2015 Ceres Dawn 2015 Moon Luna 1 1959 Luna 10 1966 Luna 2 1959 Luna 9 1966 Titan Huygens 2005 asteroid Galileo asteroid 951 Gaspra – 1991 NEAR Shoemaker asteroid 433 Eros – 2000 NEAR Shoemaker asteroid 433 Eros – 2000 comet ICE comet Giacobini-Zinner – 1985 Rosetta comet Churyumov-Gerasimenko – 2014 Deep Impact – Impactor comet Tempel -2005 Philae comet Churyumov-Gersimenko – 2014

## September 20, 2015

### The simplest Heronian triangles

Filed under: mathematics — ckrao @ 12:05 pm

Heronian triangles are those whose side lengths and area have integer value. Most of the basic ones are formed either by right-angled triangles of integer sides, or by two such triangles joined together. Following the proof in [1] it is not difficult to show that such triangles have side lengths proportional to $(x,y,z) = (n(m^2 + h^2), m(n^2 + h^2), (m+n)(mn-h^2))$ where $m,n$ and $h$ are integers with $mn > h^2$.  Firstly, if a triangle has integer side lengths and area, its altitudes must be rational, being twice the area divided by a side length. Also by the cosine rule, the cosine of its angles must be rational, so $z_1$ and $z_2$ in the diagram below are rational too (here assume $z$ is the longest side, so that the altitude is inside the triangle).

This gives us the equations

$\displaystyle h^2 = x^2 - z_1^2 = y^2 - z_2^2, z_1 + z_2 = z,\quad \quad (1)$

where $h, z_1, z_2 \in \mathbb{Q}$. Letting $x + z_1 = m$ and $y + z_2 = n$ it follows from the above equations that $x - z_1 = h^2/m, y-z^2 = h^2/n$ from which

$\displaystyle (x,y,z) = \left(\left(\frac{1}{2}(m + \frac{h^2}{m}\right), \frac{1}{2}\left(n + \frac{h^2}{n}\right), \frac{1}{2}\left( m - \frac{h^2}{m} + (n - \frac{h^2}{n}\right)\right). \quad\quad (2)$

Scaling the sides up by a factor of $2mn$, the sides are proportional to

$(x',y',z') = (n(m^2 + h^2), m(n^2 + h^2), (m+n)(mn-h^2)).\quad\quad(3)$

Next, letting $d$ be the common denominator of the rational numbers $h, z_1$ and $z_2$, we multiply the rational solution $(x', y', z')$ in (3) each by $d^3$ to obtain an integral solution. The altitude upon side length $z$ is proportional to $2hmn$ and the area is $hmn(m+n)(mn-h^2)$. Hence if we start with positive $m,n,h$ with no common factor and with $mn > h^2$, then (3) gives the side lengths of a Heronian triangle that can then be made primitive by dividing by a common factor.

Below the 20 primitive Heronian triangles with area less than 100 are illustrated to scale, where the first row has been doubled in size for easier viewing (a larger list is here). Note that all but one of them is either an integer right-angled triangle or decomposable into two such triangles as indicated by the blue numbers and sides. Refer to [2] for more on triangles which are not decomposable into two integer right-angled triangles. Here are the primitive Pythagorean triples that feature in the triangles:

• 3-4-5
• 5-12-13
• 8-15-17
• 20-21-29
• 7-24-25
• 28-45-53

#### References

[1] Carmichael, R. D., 1914, “Diophantine Analysis”, pp.11-13; in R. D. Carmichael, 1959, The Theory of Numbers and Diophantine Analysis, Dover Publications, Inc.

[2] Yiu, Paul (2008), Heron triangles which cannot be decomposed into two integer right triangles (PDF), 41st Meeting of Florida Section of Mathematical Association of America.

## August 31, 2015

### Recap of the 2015 World Championships in Athletics

Filed under: sport — ckrao @ 1:18 pm

The 15th IAAF World Championships in Athletics recently concluded in Beijing, with Kenya and Jamaica each winning 7 gold medals. Below are some of the many highlights that are worth mentioning.

• Usain Bolt became the most decorated World Championship athlete of all time taking his tally to 11 gold and 2 silver. In the 100m his best time this year out of just three races leading into the meet was 9.87s. After recovering from an early stumble in the semi final to qualify, he came over the top in the final by 0.01s to end Justin Gatlin‘s 28-race winning streak.
• Ashton Eaton broke his own world record in the decathlon, the only world record to fall at the meet. His time of 45.00s for the 400m was the fastest ever in a decathlon.
• Christian Taylor had the second longest triple jump of all time of 18.21m, just 8cm off the world record set in 1995. He and Pedro Pichardo were threatening something this special after both have cleared 18m this year.
• In the women’s hammer throw Anita Włodarczyk continued her stellar 2015 with another second throw beyond 80m this month. She now has the 9 of the top 13 throws of all time.
• The women’s 200m was possibly the best such race ever with Dafne Schippers and Elaine Thompson beating their personal best times by around 0.4s and becoming the 3rd and 5th fastest over the distance of all time.
• Almaz Ayana won the women’s 5000m by over 100 metres, with her last 3000m covered in 8:20.
• In the men’s marathon Ghirmay Ghebreslassie became the youngest ever world champion in the event at just 19 years of age. He also gave Eritrea its first ever gold medal at the championships.
• Allyson Felix won her 9th world championship gold medal with a personal best of 49.26s in the 400m. She also ran the third fastest 400m split ever (47.72s) in the 4x400m relay.
• Mo Farah repeated his 5000-10000m double from the World Championships two years ago. His last 800m of the 5000 was completed in 1:48.6.
• Ezekiel Kemboi won the 3000m steeplechase for the fourth time in a row.
• Jesús Ángel Garcia made his 12th appearance at the World Championships (50km walk) dating back to 1993. The event was won by Matej Tóth by almost 2 minutes despite a bathroom break in the middle.
• Only 0.05s separated the top five in the women’s 100m sprint with Shelly-Ann Fraser-Pryce triumphant again (she now has 7 gold meals at the Worlds).
• The men’s 4x100m had plenty of average baton handovers (including by winners Jamaica), but China’s were flawless and were rewarded with silver from lane 9.
• Kenya triumphed in the men’s 400m hurdles and javelin events (Nicholas Bett and Julius Yego respectively, not only the distance events.
• The women’s javelin was one of the most exciting events with multiple lead changes and Katharina Molitor won with a personal best and 2015-best in the very last throw of the competition.
• Asbel Kiprop became three-time champion in the men’s 1500m with just 0.41s separating the top 5.
• Recent world record holder Genzebe Dibaba won the women’s 1500m with 1:57.3s for the final 800m, faster than the winning time in the women’s 800m.
• The men’s 400m was very fast with the top three (led by Wayde van Niekerk) finishing under 44 seconds for the first time ever. Also an Asian record of 43.93s was set by Yousef Masrahi from Saudi Arabia in the heats.
• Jessica Ennis-Hill won the hepathlon, just over a year after giving birth to a second child.
• World record holder Aries Merritt won bronze in the 110m hurdles with his kidneys functioning at just 20%, just two days before a scheduled kidney transplant.

## August 28, 2015

### The discriminant trick

Filed under: mathematics — ckrao @ 12:22 pm

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

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

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

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

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

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

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

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

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

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

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

## July 30, 2015

### Nineteenth century non-avian dinosaur discoveries

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

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

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

#### References

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

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

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

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

## July 25, 2015

### Compositions of positive integers where adjacent parts have different parity

Filed under: mathematics — ckrao @ 5:39 am

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

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

For example, a valid composition of n=14 is

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

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

The first terms of the sequence are (OEIS A062200)

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

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

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

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

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

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

After writing out some terms I noticed the pattern

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

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

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

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

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

The OEIS page also gives the following expression for $t_n$:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

matching the values given in the table above.

## June 30, 2015

### The Pakistan heat wave of 2015

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

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

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

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

#### References

Next Page »

The Rubric Theme. Blog at WordPress.com.