When you can’t see the forest for the trees

1. Prologue: simplexes are simple. One day, after having lunch with my friend, we were discussing mathematics while walking back to the university. He told me that after making progress with a difficult problem, an n-dimensional simplex appeared, whose vertices played an important role. Those vertices were defined by a complicated expression deduced from some parameters of a dynamical system. The following conversation unraveled.

“It would be interesting to determine the number of neighbouring vertices for a given vertex of the simplex.”
“Wait, what? Are you kidding me?”
“No, why?”
“Because every pair of vertices are neighbors in a simplex.”

Sometimes it happens that we are so confused amidst the complex relations and convoluted ideas that such a simple pattern eludes us. This post is dedicated to a few problems, where it is easy to get lost in details and miss these obvious (or not so obvious) patterns. Although the solutions are explained, I urge everyone to wander into the forest (and maybe get lost in the woods) before exploring the paths I laid out.

2. Tennis tournaments. The following problem was posed by Paul Halmos in his problem book Problems for mathematicians, young and old.

Problem. Suppose that 1025 tennis players want to play an elimination tournament. This means that they pair up at random for each round, and if the number of players before the round begins is odd, one of them, chosen at random, sits out that round. The winners of each round, and the odd one who sat it out (if there was an odd one), play in the next round, until finally there is only one winner, the champion. What is the total number of matches to be played altogether, in all the rounds of the tournament?

Solution. The answer is quite easy, for in the first round there are 1024 + 1 players playing 512 matches. In the second round the remaining 512 + 1 players play 256 matches and so on, our answer is

512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 + 1 = 1024 .

As Halmos notes, it is rather easy to provide the number of matches given the number of competitors, but it is difficult to see why it is true. The number 1025 = 2^{10} + 1 is rather special. One can see easily that given 2^k + 1 players there are 2^k matches. What if there are 2^k players? In this case, we can see similarly, that there are 2^{k-1} + 2^{k-2} + \dots + 1 = 2^k - 1 matches. Combining the 2^k and the 2^k + 1 case, it follows that when the total number of players are 2^k + 2^l + 1 , then, by splitting them up into groups of 2^k and 2^l + 1 players and have the winners of each group compete for the price, we can see that there are, in total, 2^k - 1 + 2^l + 1 = 2^k + 2^l matches. Following up by induction and using expansion with powers of 2 , we can conclude that when there are n players there are n - 1 matches.

Or we can just notice that each match has a loser and there is only one player who will never lose. This simple line thought immediately implies what we concluded after a more complicated and unnatural induction argument. By looking at the parts of the problem, we have missed the bigger picture. One may say that we couldn’t see the forest for the trees.

3. Trains and eagles.

Problem. A train leaves from city A to city B, which is at a distance of 100 miles. Suppose that the tracks are straight and the train maintains a steady 30 miles per hour at all times. (Perhaps this is a very old train, a steam locomotive.) In the same minute, an eagle takes off from city B to the direction of the train. The eagle flies fast, going at 90 miles per hour. The second it meets with the train, it reverses its direction to city B and flies back. Upon returning to city B, it turns back again to the train and repeats this cycle. The eagle flies back and forth until the train arrives to city B. What is the total distance traveled by the eagle?

Solution. First we shall determine that at which point the train and the eagle meets. If they meet at time t_0 , their initial distance is d = 100 miles and they travel with speeds v_T = 30 mph and v_E = 90 mph, we know that

v_T t_0 = d - v_E t_0,

which gives t_0 = \frac{100}{120} hours. By that time, the train had traveled v_T t_0 = 25 miles. Now the eagle flies back with speed v_E = 90 mph, and by the time it returns to town B, the train had traveled 50 miles, exactly half the distance. We can conclude that when the eagle completes the first cycle, it had traveled 150 miles while the train is only half the way. Using the exact same reasoning, we see that at the end of the second cycle the eagle had traveled 150 + 75 miles while the train just passed the 75 th mile. By induction, it follows that at the end of the k -th cycle, the eagle had traveled

150 + \frac{150}{2} + \dots + \frac{150}{2^{k-1}} = 150 \sum_{l=0}^{k-1} 2^{-l}

miles. Passing to the limit k \to \infty , we obtain that when the train reaches city B, the eagle had traveled exactly 300 miles. If the distances and the speeds are changed, this method still works. In order to obtain the solution, we need to make a simple calculation and evaluate a geometric sum.

Or we can just notice that the eagle spends exactly the same amount of time in the air as it takes the train to reach city B. The train reaches the city in t = \frac{100}{30} hours, therefore the eagle travels a total of t v_E = 300 miles.

4. Teeming ants.

Problem. There are n ants on a steel rod of 1 foot. Each ant is traveling at a 1 foot per minute speed in some direction. When two ants meet, they reverse their direction and continue in that direction. If an ant passes the edge of the rod, it falls off. Prove that after a minute, no ant will remain on the rod.

Solution. Suppose that our rod is simply the interval [0,1] . First let’s study the scenario when there are only two ants. If initally both of them are travelling in the same direction or the opposite direction to each other, they will walk straight off the rod. If they are facing each other, starting from positions x_1 < x_2 , then after t minutes they will be at positions x_1 + t and x_2 - t . It follows that they will meet at time t_0 = \frac{x_2 - x_1}{2} and at position \frac{x_1 + x_2}{2} . They change their directions, and after 1 - t_0 minute had passed since they met, they will be at positions \frac{x_1 + x_2}{2} - 1 + \frac{x_2 - x_1}{2} = x_2 - 1 and \frac{x_1 + x_2}{2} + 1 - t_0 = x_1 + 1 . Or at least they would be, if they would not have fallen off from the edges. To handle the general case when there are n ants, the complexity seems too big to manage. For example, for n = 7 ants, we can make the following picture by plotting the positions against time. The path of one ant is singled out with dashed line.

ants
The position-time plot for seven ants

Wait, what? At this point, we can notice that if we assume that the ants are passing each other upon meeting rather then changing directions, the lines in the picture will remain the same. Individual trajectories may differ, but if we imagine the ants as tiny undistingushable black dots on the interval [0,1] , we see that after a collision the picture is the same no matter they reversed their direction or not. With this observation, it is immediate that every ant falls off from the rod in at most a minute.

5. The problem of the sticky paint.

Problem. Suppose that we have two circles stacked on top of each other. The lower one has radius \sqrt{2} , the upper one has radius 1 . A spot at the top of the smaller circle is painted black, just like in the picture.

painted_disks

The smaller circle starts to roll around the larger one, painting it every time when the spot touches it. But this paint is sticky, which means that when it leaves a mark on one circle, it will paint the other circle back in the next round and so forth. How many black dots will be on the larger circle after the smaller one had gone around it 100 times?

Solution. The difficulty lies in the fact that the painted spots on the larger circle repaint the smaller one which will, in turn, result in more painted spots on the larger one and so on. If there is no repainting then after 100 rounds the total number of black spots in the circle with radius \sqrt{2} will equal to \lfloor 100\sqrt{2} \rfloor . The very first spot (in time, not in distance from the starting point) on the big circle will be put there by the smaller one in the first round. At the next round, this spot will paint the smaller circle back, which, starting from the third round, will paint on the bigger circle \lfloor 98 \sqrt{2} \rfloor times. One can go on with this logic as far as his or her patience allows, but hold on for a minute. Does it mean that after 100 rounds there will be at least \lfloor 100 \sqrt{2} \rfloor + \lfloor 98 \sqrt{2} \rfloor spots? What if on some occasions, a spot on the larger one is “repainted”, that is, what if a spot on the larger circle and a spot the smaller circle touch? If that is the case, the spot on the smaller one will not make any new ones on the larger one, because if there is a spot on the larger one which was made in some previous round, then there will be an another one after it after a distance of 1 on its arc. But wait, what? This means that if a spot is picked up from the larger one by the smaller one, it won’t make any new spots! It follows that no matter how sticky this paint is, there will be \lfloor 100 \sqrt{2} \rfloor spots after 100 rounds, because if a new spot is picked up by the smaller one, it won’t do anything else but paint on the old ones!

6. The unit sphere in four dimensions.

Problem. The unit sphere in n dimensions is defined as

S^{n-1} := \{ (x_1, \dots, x_n) \in \mathbb{R}^{n}: \sqrt{x_1^2 + \dots + x_n^2} = 1 \}.

Show that the four dimensional unit sphere S^3 can be decomposed into the disjoint union of congruent circles!

Solution. It is easy to imagine that the three dimensional sphere S^2 can be decomposed into the union of congruent circles, although they will not be disjoint. One of the problems are that the circles have to be disjoint in our case, but this is the least of our worries. The other problem is that we cannot imagine a four dimensional unit sphere. (Most of us anyway.) Therefore we can try to rely on tools from analytic geometry. The four dimensional sphere

S^3 = \{ (x_1, x_2, x_3, x_4) \in \mathbb{R}^4: \sqrt{x_1^2 + x_2^2 + x_3^2 + x_4^2} = 1 \}

can be parametrized with the so-called hyperspherical coordinates

x_1 = \cos \psi ,
x_2 = \sin \psi \cos \theta ,
x_3 = \sin \psi \sin \theta \cos \phi ,
x_4 = \sin \psi \sin \theta \sin \phi ,

where \psi, \theta, \phi \in [-\pi,\pi) . For example, we can fix \psi and \theta to obtain the circles

\gamma_{\psi, \theta}: t \mapsto (\cos \psi, \sin \psi \cos \theta, \sin \psi \sin \theta \cos t, \sin \psi \sin \theta \sin t),

but these circles are, although congruent, it is not clear whether or not they are disjoint. With some calculations we can work this straight out, but the problem has a one line solution. It reads like “since in the group of unit quaternions the set G = \{ \cos \phi + i \sin \phi: \phi \in [-\pi, \pi) \} is a subgroup, its left cosets are disjoint and congruent.” This simple line of reasoning, along with its beauty, saves us from a lot of calculations. Each point in the four dimensional unit sphere can be represented as a unit quaternion and the subgroup G along with its cosets represents circles, which immediately gives us a partition of S^3 into congruent circles.

7. Epilogue. Truth be told, often there are no forest. I had a teacher who used to say that “when thinking about a problem, a mathematician rather lies in bed for hours than to calculate just five minutes.” I think he was wrong. I think a mathematician lies in bed for hours while thinking when it is the right path and calculates for hours when it is needed. After all, a forest is nothing else than just a collection of trees.

Advertisements

5 thoughts on “When you can’t see the forest for the trees

  1. In the section about the unit sphere in four dimensions, the subgroup G in the group of unit quaternions is not actually a normal subgroup, but the set of left cosets (or right cosets) of G does still partition the 3-sphere into congruent circles.

    Like

  2. 5. The problem of the sticky paint.
    100 times around the big means that the small cirlce should be rotated 100*(root(2) + 1) and not 100*root(2).
    If the same length (the lenght of the big circle) was a straight line, then 100 times would mean 100*root(2). Now, for each one of the 100 times, there is an additional rotation, due to the curve.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s