# A beautiful problem on the Pigeonhole Principle

I recently solved this beautiful mathematical problem on Pigeonhole Principle from Romania TST 2000.

Let $$S$$ be the set of interior points of a sphere in three-dimensional space and let $$D$$ be the set of interior points of a disc on a plane. For any two points $$X,$$ and $$Y$$ in the space, let $$d(X, Y)$$ denote the distance between them. Determine if there is a function $$f: S\rightarrow D$$ such that $$d(A, B)\leq d(f(A), f(B))$$ for any two points $$A, B\in S.$$

What are you initial thoughts on this problem? Do you think there is such a function or there isn't. I have given my solution to this problem below. You can also post a solution if you have another one :)

We claim that such a function does not exist. To prove this claim, we will assume that there exists such a function $$f$$, and arrive at a contradiction.

Suppose that there exists such a function $$f: S\rightarrow D,$$ then we will consider a cube of side length $$a$$ that is completely in the sphere.

Fix a random positive integer $$n$$, we will partition the cube into exactly $$n^3$$ congruent cubes, such that these identical cubes determine $$n^2$$ identical squares on each face of the larger cube, and $$n$$ identical line segments on each edge of the larger cube.

Now, we consider the $$(n+1)^3$$ points that are the vertices of the $$n^3$$ identical cubes. Let these points be $$S_1, S_2, \cdots, S_{(n+1)^3},$$ we know that the distance between any two of these points is at least $$\frac{a}{n}.$$

Let $$D_1, D_2, \cdots, D_{(n+1)^3}$$ be the points on the disk $$D,$$ that the function $$f$$ maps $$S_1, S_2, \cdots,$$ and $$S_{(n+1)^3}$$ to, more specifically, let $$D_i=f(S_i)$$ for all $$i\in{1,2,\cdots,(n+1)^3}.$$

Since our function $$f$$ has the property that, for any two points $$A, B\in S,$$ $$d(A, B)\leq d(f(A), f(B))$$ holds. Hence, the pairwise distances between the any of the $$D_i$$ are at least $$\frac{a}{n}.$$

This means that we can draw circles around each of those points of radii $$\frac{a}{2n}$$ such that none of the $$(n+1)^3$$ circles intersect. Let the radius of the disk $$D$$ be $$r,$$ we know that each of these circles is contained in the disk concentric with $$D$$ of a radius of $$r+\frac{a}{2n}.$$

All these $$(n+1)^3$$ circles are non-intersecting, and contained in the larger disk. the sum of their areas is lesser than the area of the larger disk. Hence, for all $$n\in\mathbb{N},$$ we have \begin{align*} & \pi\left(\frac{a}{n}\right)^2(n+1)^3\leq\pi\left(r+\frac{a}{n}\right)^2\\ \Rightarrow & \left(\frac{a}{n}\right)^2(n+1)^3\leq\left(r+\frac{a}{n}\right)^2\\ \Rightarrow & \left(\frac{a^2}{n^2}\right)(n+1)^2(n+1)\leq\left(r+\frac{a}{n}\right)^2\\ \Rightarrow & \left(\frac{(n+1)^2}{n^2}\right)(n+1)a^2\leq\left(r+\frac{a}{n}\right)^2\\ \Rightarrow & \left(\frac{n+1}{n}\right)^2(n+1)a^2\leq\left(r+\frac{a}{n}\right)^2\\ \Rightarrow & \left(1+\frac{1}{n}\right)^2(n+1)a^2\leq\left(r+\frac{a}{n}\right)^2. \end{align*}

Now we note that as $$n$$ tends to infinity, the term $$\frac{1}{n}$$ will tend to $$0,$$ and hence, \begin{align*} 1+\frac{1}{n} &\rightarrow 1\\ \left(1+\frac{1}{n}\right)^2 &\rightarrow 1\\ \left(1+\frac{1}{n}\right)^2(n+1)a^2 &\rightarrow\infty. \end{align*} since $$n+1\rightarrow\infty.$$ Hence, the left side of the inequality tends to infinity, implying that since $$\Rightarrow\left(1+\frac{1}{n}\right)^2(n+1)a^2\leq\left(r+\frac{a}{n}\right)^2,$$ the right side will also tend to infinity. But note that as $$n\rightarrow\infty,$$ \begin{align*} \frac{a}{n} &\rightarrow 0\\ \Rightarrow r+\frac{a}{n} &\rightarrow r\\ \Rightarrow \left(r+\frac{a}{n}\right)^2 &\rightarrow r^2. \end{align*} which is finite, hence, we have arrived a contradiction, and such a function $$f$$ does not exist.

• Very nice problem. Thank you for sharing it with everyone, and also posting this amazing solution! Commented May 27, 2022 at 4:41
• Very nice! thanks for posting the question/answer combination together.
– Mike
Commented Jun 6, 2022 at 20:24
• Thanks for your appreciation! This was a wonderful Pigeonhole problem. Commented Jun 7, 2022 at 15:57