Chaitanya's Random Pages

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

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.

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.

Create a free website or blog at WordPress.com.