How to do this counting problem?

Question

I know that the pigeonhole principle is to be applied here but I can’t see yet how.

On a certain planet in the solar system Tau Cetus, more than half the surface of the planet is dry land. Show that the Tau Cetans can dig a tunnel straight through the centre of the planet, beginning and ending on dry land.

Answer 1

If dry land is always opposite of non dry land, then the area of wet land must be at least equal to area of dry land. But the area of dry land itself is already more than half the area of the planet. If you don't like paraphrasing, check out the following alternative:

Let $S$ be the whole planet, $G$ be all dry land and $G'$ be all land opposite of dry land. Suppose that $G\cap G'=\varnothing$ $$ \begin{align} A(S)&\geq A(G\cup G')\\ &=A(G)+A(G')-A(G\cap G')\\ &=2A(G) \end{align} $$

This contradict $2A(G)>A(S)$

Answer 2

In this case there are uncountably many pigeonholes corresponding to all possible pairs of antipodes of the planet (endpoints of all tunnels) and a pigeon is an infinitesimally small patch of land. Since taking one end of each tunnel covers exactly half the planet's area and more than half the planet's surface is land, there must be a pigeonhole with two pigeons, i.e. suitable endpoints for a land-to-land tunnel.

Answer 3

Proof by contradiction: let's suppose that there was no way to dig a tunnel through the center of the planet starting on dry land which also ends on dry land. This means that for each point on dry land, the point on the opposite side of the planet cannot be dry.

Let's define a function $O(p)$ which acts on the domain of points on the planet which lie on dry land. By our reasoning before, the codomain must consist of entirely wet land. It should be clear that $O$ is injective because each point can only be opposite to exactly one point on the planet.

However, the pigeonhole principle states that there cannot exist an injective function whose domain is larger than its codomain, and the problem tells us that there is more dry land than wet land. Therefore, we have reached a contradiction and there must be some way to dig a tunnel through the center of the planet which starts and ends on dry land.

Hope this helps!

Answer 4

I shall reformulate this into a coloring problem as follows:

Consider a spherical shell $S$ in $\mathbb{R}^3$, the points on whose surface are colored with either one of black $(B)$ or white $(W)$ colors. If more than half of the shell is colored black, show that it is possible to find a line through the center of the shell that joins two black points.

Some notation:

• For a point $p$, I shall denote its diametrically opposite point by $p'$. Note that $(p')' = p$. We shall also call $p'$ as the tunnel-complement of $p$.
• For every point $p\in S$, I will denote its color by $c(p)$. In general, $c(p)\in\{B,W\}$

We shall complete the proof by way of contradiction.
Suppose it is not possible to dig such a tunnel, i.e. there does not exist $p$ such that $c(p) = c(p') = B$.

So, for every $p\in S$ such that $c(p) = B$, we have $c(p') = W$.

Consider the sets:

• $\mathcal{B} = \{p\in S: c(p) = B\}$
• $\mathcal{W} = \{p\in S: c(p) = W\}$
• $\mathcal{B}':= \{p': p\in \mathcal{B}\} $
• $\mathcal{W}':= \{p': p\in \mathcal{W}\} $

We know that $c(p) = W$ for all $p\in \mathcal{B}'$, i.e. all elements diametrically opposite to black elements must be white. It is also clear that $\mathcal{B}\cap\mathcal{W} = \emptyset$ and $\mathcal{B}\cup\mathcal{W} = S$. Also, $|\mathcal{B}| = |\mathcal{B}'|$ and $|\mathcal{W}| = |\mathcal{W}'|$ i.e. the cardinality of a set and its tunnel-complement are the same. This is because there is an obvious bijection between the two, namely $$f:\mathcal{B}\to \mathcal{B}', p\mapsto p'$$ and $$g:\mathcal{W}\to \mathcal{W}', p\mapsto p'$$

We are given that more than half of the shell is colored black, so that $|\mathcal{B}| > |\mathcal{W}|$. Also, $\mathcal{B}' \subset \mathcal{W}$ since all elements opposite to black elements are white. So, $|\mathcal{B}'| \le |\mathcal{W}|$ which gives $|\mathcal{B}| \le |\mathcal{W}|$ from the bijection seen above.

So, we have $|\mathcal{B}| \le |\mathcal{W}|$ and $|\mathcal{B}| > |\mathcal{W}|$ - which is a contradiction. Hence, it is possible to dig the desired tunnel, i.e. we can find a point $p\in S$ such that $p,p'\in\mathcal{B}$.

Answer 5

We can apply the pigeon hole principle by doing something like this:

First, discretize half the surface of the planet into n pigeon holes. Each pigeon hole can accept two items. First, we fill the pigeon holes with dry land. For any pigeon hole with only one item in it, we can now fill it with wet land.

If we have k regions of dry land and k>n, then we'll have to fill an additional (k-n) pigeon holes with a 2nd region of dry land. Now, we have less than n pigeon holes to fill with wet land which corresponds to less than half of the surface being covered with water.

Each pigeon hole containing two areas of dry land corresponds to positions where you can start digging in dry land and reach another area of dry land. This only occurs when k>n or in other words, when more than half of the surface is dry.