Varsity Math, Week 11

momathlogohorizontalWSJLogo

This week, we’re getting ready for the upcoming round of competitions by working on the team uniforms. Also, Coach Newton has decided to switch to a three-week cycle for the relay training, starting with one of today’s problems.
[asciimathsf]

Tee Party

The Varsity math crew is designing team t-shirts. There are seven possible fonts they can use for the caption “MATH TEAM” on the shirts. For an offbeat touch, they’ve decided that each team member will use a different arrangement of fonts. The rules they decide on are that every letter must be in a different font, except that the second occurrence of a particular letter may be, but doesn’t have to be, in the same font as the first.

   How many caption designs are there for the team members to choose among?

Blue_Tshirt_questionmark_thin

Design Data

The region on the t-shirt reserved for the team logo is a rectangle. One of the team members measures the perimeter, and finds it’s 50 centimeters. Another teammate measures the diagonal, which turns out to be `5 sqrt 17` centimeters.

   How much area (i.e., how many square centimeters) do the t-shirt designers have for the logo?

Solutions to Week 10

[asciimathsf]Cross Training. It is possible to get all five team members across in just three boat trips: Send two of the inexperienced teammates across, together with a crew team member (4 minutes). The crew member rows back (1 minute) and then all of the remaining teammates cross (4 minutes), for a total of 9 minutes to get all five to the correct side of the river.

However, it might (and should) concern you that this crossing plan involved two trips with the slower teammates. Is there any plan in which all three of the slower members of the team go at once, and that’s the only trip that involves any of them? Well, either it would have to be the very last trip, or you would need to have a fast teammate already on the other side to bring the boat back to the starting side. But it can’t be the last trip, because how would the boat have gotten back to the starting side with only the three slow teammates on that side? Only by having been rowed there by a slow teammate, making at least two slow trips.

So to try to get it down to a single trip by the slow team members, you need to “plant” a fast rower on the far side. How long does that take? One minute for the two fast rowers to cross, and one minute for one of them to row back, for two minutes. Then four minutes for the slow rowers to cross. At this point you have one fast rower left on the starting side and the other four teammates and the boat on the far side. The fastest possible way to finish up is clearly to send the fast rower on the far side back to fetch the last teammate, a round-trip time of two minutes. Thus, the fastest way to cross the river takes 2 + 4 + 2 = 8 minutes.
 
Windows on the World. Intuitively, to maximize the minimum distance between the windows, Nyman needs to spread them apart as far as possible (imagine the windows all repelling each other as if they were attached to each other with compressed springs that wanted to stretch out as far as possible). To do that, it seems as though the windows will have to end up in a very symmetric configuration, because if they were distributed “unevenly,” Nyman could spread them out wherever they were bunched up and take up a little of the space wherever they were spread more sparsely. Also, we can represent the windows by their centers, since the problem is only looking for the center-to-center distance.

So, what are the highly symmetrical arrangements of eight points on the surface of a sphere? The first one that comes to mind is the vertices of a cube. Since Nyman’s radius is kind of a complicated number, let’s just figure out the separation `s` of two vertices of a cube inscribed in a sphere of radius `r`. Looking at the diagram,WindowsWorldSolnA the body diagonal of the cube will be `2r`. On the other hand, in a cube of edge length `s`, the face diagonal (which is the diagonal of a square with side length `s`) is `sqrt{2}*s`. The body diagonal is therefore the hypotenuse of a right triangle with sides `s` and `sqrt{2}*s`, which is `sqrt{3}*s`. Equating the two expressions for the diagonal, `s = 2 / sqrt{3} r = {2 sqrt{8+2 sqrt 2}}/ sqrt{3}` meters.

This looks a little fishy. Why would the answer come out to be such a strange number? Is there possibly a way to space the windows farther apart on a sphere? Imagine you rotated the top group of four windows with respect to the bottom group, as indicated in the next diagram. WindowsWorldSolnB All of the distances between any top window and any bottom window will grow, with the maximum occurring at a rotation of 45 degrees, so that each top window is precisely between a pair of bottom windows.

So far this has not increased the distance between a pair of top windows or a pair of bottom windows. So now push the top layer and bottom layer toward the “equator” of the sphere. This will allow the top and bottom squares to enlarge, spreading the top and bottom windows farther apart. It will reduce the distance between a top and a bottom window, but we already made that greater than the original edge length of the cube. Thus we still achieve a larger minimum distance by spreading the top and bottom windows while making the top windows nearer the bottom windows. This enlargement of the top and bottom squares continues to help until we have pushed the top windows and bottom windows toward the equator just the right amount so that all pairs of adjacent windows are the same distance apart. At that point, the windows are at the corners of a shape that has a square bottom, and a square top rotated 45 degrees with respect to the bottom, and 8 equilateral triangular faces in a band around the sides. This shape is called a square antiprism, WindowsWorldSolnC and the new One World Trade Center is based on this shape (although that structure is stretched quite a bit vertically!)

If Nyman places his windows at the corners of a square antiprism, how far apart will they be? The key to calculating this distance `t` is to draw the line connecting a top corner `A` with the midpoint `D` of the nearest edge along the bottom. WindowsWorldSolnD The line segment `AD` is the altitude of an equilateral triangle of side `t`, which has length `t sqrt{3} / 2`. Now imagine extending the line from the center `C` of the bottom square face through `D` to a point `B` directly beneath `A`. `CB` is half of the diagonal of a square face of side `t`, so has length `t sqrt{2} / 2`, and `CD = t // 2`, so `DB` is `t(sqrt{2}-1)/2`. Triangle `ABD` is a right triangle, so by the Pythagorean theorem, the height `AB` of the square antiprism is `sqrt{ {3t^2} / 4 – {t^2(sqrt{2}-1)^2}/4} = t/2 sqrt{2 sqrt 2}`.

Finally, the radius `r` of the sphere is also the hypotenuse of a triangle with one leg equal to the half diagonal of a square face `t sqrt{2} / 2`, and other leg equal to half the height, or `t / 4 sqrt{2 sqrt 2}`. WindowsWorldSolnE Therefore, `r = sqrt {t^2 / 2 + {sqrt 2 t^2}/ 8} = t sqrt{ {4 + sqrt 2} / 8}`. Substituting the value of `r` and solving for `t`, we have `{:(t,=,sqrt{ 8/{4 + sqrt 2} (8 + 2 sqrt 2) }  =  sqrt { {8(8 + 2 sqrt 2)(4-sqrt 2)} / {(4+sqrt 2)(4-sqrt 2)}}),( ,=,sqrt{{8*28}/14}  =  4.):}`

In this antiprism configuration, the arrangement seems very constrained; there does not seem to be any way to move the windows farther apart, and we have landed on a very simple answer. Moreover, checking with a calculator, the window separation in the cubical arrangement was only about 3.8 meters, so we really did get the windows farther apart. Hence we conclude that the centers of the windows in Nyman’s building will be 4 meters apart.

On the level from Coach Newton—

Some of you may have had alarm bells go off on that last explanation. The answer should be considered correct because “there doesn’t seem to be” a better way and “it comes out simply”? Sometimes in the heat of doing a problem you’ve got to go with your instinct like that, but if you’re feeling that the given solution is not the entire story, well, you’d be right. So here’s the scoop, if you want to hear all the details of how a great math solver of yesteryear, László Fejes Tóth, figured out conclusively that the corners of a square antiprism form the best-separated arrangement of eight points on a sphere.

Suppose in the optimal configuration the minimum distance between pairs of points is `d`, at least the side length of a square antiprism. Connect all of the pairs of points in this configuration which are at that minimum distance `d` with an arc along the surface of the sphere. These connections create a network, or spherical tiling, all of whose arcs (called edges) have the same length, and with eight junctions (called vertices) where the edges meet, corresponding to the locations of the windows. Now (as you can check), `d` is larger than `text{radius} / sqrt 2 sqrt{5−sqrt 5}`, the side length of the largest regular pentagon which can be inscribed in a sphere. Therefore, every region (called a face) of the network is either a spherical equilateral triangle or a spherical rhombus. Moreover, since there is no way to cover a sphere with equilateral triangles using exactly eight vertices (the only possibilities would be the Platonic solids with triangular faces, which have 4, 6 and 12 vertices respectively), there must be at least one rhombus. In fact, since all of the equilateral triangles must have the same vertex angle between two edges (arcs), and that angle is not 120, 90 or 72 degrees as in the Platonic solids, there must be at least one rhombus at every vertex, in order to make up the full angle sum of 360 degrees at that vertex.

Now we construct a bound on the areas of the faces of any arbitrary network of triangles and rhombuses that has the following properties: there is a rhombus at every vertex; all spherical edge lengths are the same length `u`; no vertices are closer than `u` to each other; and all pairs of vertices not connected by an edge are farther than `u` apart.

Namely, let `T` be the spherical area of each of the triangular faces (which are all identical), and `R` be the minimum area of any of the rhombuses. Note that `R > 2T` because if `R = 2T` then two opposite vertices would be exactly `u` apart, and the rhombus would instead be two triangles in the network, and if `R < 2T` then two opposite vertices would be less than `u` apart. Suppose that overall there are `t` triangles and `r` rhombuses. Then there are `(3t + 4r)//2` edges and some number `n` vertices. By Euler's formula for networks on a plane or sphere, #F - #E + #V = 2, so `t+r -(3t + 4r)//2 + n = 2`. Solving for `r`, `r = n−2−t//2`. The spherical area of all of the faces is less than or equal to `4 pi`, the area of the entire sphere. Therefore, `4 pi >=` area of all of the triangles plus the area of all of the rhombuses `>= tT + rR`. Some algebraic manipulation using the expression for `r` we just derived gives us that
`{:( ,tT + rR,=,tT +r(R−2T+2T)  =  (t+2r)T + r(R-2T)),(,,=,(t + 2(n−2−t//2))T + r(R-2T)  =  (2n−4)T + r(R-2T).):}`

On the other hand, since there is a rhombus at every vertex and a given rhombus touches exactly four vertices, the number of rhombuses must be at least `n//4`. Putting all of these inequalities together, we get `4 pi >= (2n−4)T + (n//4)(R−2T) = (3n//2-4)T + (n//4)R`.

This bound we have derived for the areas of the triangles and rhombuses in such a network in turn bounds the edge length of the network (since the larger the edge length, the larger the areas of the triangles T and rhombuses R would be). Returning to the specific case we are considering, `n = 8`, so `4 pi >= 8T + 2R`, and the largest possible edge length `u` (and hence straight-line distance `d`) would be achieved if equality could be achieved in this relation. But it can, by dividing the sphere into 8 identical spherical triangles and 2 spherical squares (which are a special case of rhombuses)—namely, by arranging for the vertices to be the corners of a square antiprism. Hence, a square antiprism is the optimal arrangement of eight points on a sphere in terms of maximizing the minimum distance between any two points.

 

Geometric Addition. Having solved Windows on the World, we know we are dealing with a four-term geometric sequence `a, a*r, a*r^2, a*r^3`. If the first three formed an arithmetic sequence, then the last three would as well (since they are produced by multiplying the first three terms by `r`) and hence the whole thing would be a four-term arithmetic sequence, which we are told does not occur. Hence, we want either `a*r−a = a*r^3−a*r`, or `a*r^2−a = a*r^3−a*r^2`. We can divide either equation out by `a` (which can’t be zero because otherwise the sequence would not be increasing) to get that either `r−1 = r^3−r` or `r^2−1 = r^3−r^2`. Bringing all of the terms to one side, we want to solve `r^3−2r+1 = 0` or `r^3−2r^2+1 = 0`. Both of these polynomials factor; `r^3−2r+1 = (r−1)(r^2+r−1)` and `r^3−2r^2+1 = (r−1)(r^2−r−1)` But we are told the geometric sequence is increasing, which means that `r != 1`, so we can divide both equations by `r−1` and combine the two equations to get that we need to solve `r^2 +- r−1 = 0`. Using the quadratic equation, we get `r = (+- 1 +- sqrt 5)//2`, which is four solutions since either `+-` could be + or – independently. However, we had better check whether each of these values could be the ratio of an increasing geometric series. In fact, we need to discard both `(+- 1 − sqrt 5)//2` because both of those values are negative, and a geometric series with negative ratio alternates between positive and negative numbers, and so cannot be increasing. That leaves `r = (sqrt 5 +- 1)//2`. Do both of those ratios work? There is certainly an increasing geometric sequence with ratio `(sqrt 5 + 1)//2 > 1`, say starting with 1. What about `(sqrt 5 − 1)//2`, which is between 0 and 1? If you start with a negative number, then each successive term is still negative but closer to 0 and hence greater than the previous one. Hence, we conclude that both solutions work and the answer is that \(\mathbf{r = (\sqrt5 \pm 1)/2}\).

 

Self-sequential Reference. The first thing that we have to do is figure out what

`X = (R^15−(–1//R)^15)// sqrt 5`

is, where `R` is one of the ratios `(sqrt 5 +- 1)//2` from Geometric Addition the prior week. But note two things: `(–1//R)^15 = –1^15//R^15 = –1//R^15`, so the numerator in the expression for `X` is just `(R^15 + 1//R^15)`. Also, `{sqrt 5 + 1}/2 * {sqrt 5 – 1}/2 = {5-1}/4 = 1`, so the two ratios from last time are reciprocals of each other. Since the expression for `X` is unchanged if we replace `R` by `1//R`, it doesn’t matter which one we use to solve this problem. For convenience, let’s use the golden ratio `R=(sqrt 5 + 1)//2`.
There are three possible ways to proceed from this point to find the value of `X`: First, you could just use a calculator. But according to Coach Newton, the ethos of Varsity Math is that there should always be a way to do it without a calculator. So the second method is to try some smaller values of the exponent in the expression for `X` and see what you get. As noted, `1//R` is `(sqrt 5 –1)//2`. So you put in exponent 1 in place of 15 in the expression for `X`, you get `((sqrt 5 + 1)//2 + (sqrt 5 –1)//2) // sqrt 5 = (2 sqrt 5//2) // sqrt 5 = 1`. If you use an exponent of 2, you get `((6+2 sqrt 5)//4 – (6–2 sqrt 5)//4) // sqrt 5 = (2 sqrt 5//2) // sqrt 5 = 1`. An exponent of 3 gives
`((16+8 sqrt 5)//8 + (8 sqrt 5 – 16)//8) // sqrt 5 = (16 sqrt 5//8) // sqrt 5 = 2`. And an exponent of 4 produces
`((56+24 sqrt 5)//16 – (56–24 sqrt 5)//16) // sqrt 5 = (48 sqrt 5//16) // sqrt 5 = 3`. With those four examples: 1, 1, 2 and 3, you could guess that this expression gives you the Fibonacci sequence as the exponent increases. And the third method is, based on that hunch, to add the expression `X_i` (which is just like `X` but with `i` in place of the exponent 15) for two successive exponents:

`{:(X_n + X_{n+1},=,(R^n−(–1//R)^n)//sqrt 5 + (R^{n+1}−(–1//R)^{n+1})//sqrt 5),(,=,(R^n(1+R)−(–1//R)^n(1−1//R))//sqrt 5.):}`

But from the solution to Geometric Addition, we know that `R^2−R−1 = 0`, which means that `1+R = R^2`, and (dividing by `R^2`) that `1−1//R = 1//R^2 = (–1//R)^2`. So

`X_n + X_{n+1} = (R^n(R^2) − (–1//R)^n(–1//R)^2)//sqrt 5 = (R^{n+2} − (–1//R)^{n+2})//sqrt 5 = X_{n+2}`.

Therefore, the sequence of `X_i` is the Fibonacci sequence, so `X` is the 15th Fibonacci number, or 610.

Next, we have to figure out the sequence `L`. It has to start with 2, and then after that we have to use the least possible positive number we can while ensuring that the `k`th term of `L` gives the number of times that `k` appears in the sequence `L`. This is easiest to visualize in the form of a two-row table:

Term Number 1 2 3 4 5 6 7 8
Entry of `L` 2 ? ? ? ? ? ? ?

Trying to fill in the second entry of `L`, we see that we need to have two “1”s somewhere, and we always want to use the smallest number we can, so we need to put a “1” in the second entry of `L`. Similarly, there should be a “1” in the third entry of `L`. So far, that gives us

Term Number 1 2 3 4 5 6 7 8
Entry of `L` 2 1 1 ? ? ? ? ?

For the fourth entry, we can’t use a “1,” and we can’t use a “2” because the sequence tells us there is only one “2” in the sequence, and we’ve already used it up at term one. So we need to use the next smaller number, “3”. That uses up the only “3” we’re allowed to use, so the smallest thing the next term can be is “4,” yielding

Term Number 1 2 3 4 5 6 7 8
Entry of `L` 2 1 1 3 4 ? ? ?

But now we can have three “4”s in a row, before the rule that the `k`th entry of `L` tells you how many times `k` can appear forces us to switch up to “5”:

Term Number 1 2 3 4 5 6 7 8
Entry of `L` 2 1 1 3 4 4 4 5

And now the pattern should be clear: there will be a block of four “5”s starting with the one at term eight, then a block of four “6”s, then a block of four “7”s, then a block of five “8”s, and so on.

But we are still faced with the problem of finding out what the 610th term of `L` will be. We don’t want to have to write out a row of 610 boxes and fill them in one by one. We need a faster way.

There are different possible ways of going about it, but one simple one is to use the structure of the blocks of values of `L` described above as the organizing principle. You can make a table of where in the sequence `L` the blocks of a given length will start, as shown in the table below. The explanation for each entry is color-coded so you can see where the numbers come from in the preceding row. For example, the first block of five consecutive identical entries occurs at position 20, because the blocks of length four started at position 8, and then there were three blocks of size four (since the fourth entry of `L` is three), and 20 = 4×3 + 8.

`n`th entry of `L` `n` 1st block of length `n` starts at position because… The 1st entry of a block of length `n` is because…
2 1 1 (start of sequence) 2 (start of sequence)
1 2 2 there are two “1”s 1 there are two “1”s
1 3 5 there is only one 3 4 that “3” is in pos 4
3 4 8 8 = 3 × 1 + 5 5 5 = 4 + 1
4 5 20 20 = 4 × 3 + 8 8 8 = 5 + 3
4 6 40 40 = 5 × 4 + 20 12 12 = 8 + 4
4 7 64 64 = 6 × 4 + 40 16 16 = 12 + 4
5 8 92 92 = 7 × 4 + 64 20 20 = 16 + 4
5 9 132 132 = 8 × 5 + 92 25 25 = 20 + 5
5 10 177 177 = 9 × 5 + 132 30 30 = 25 + 5
5 11 227 227 = 10 × 5 + 177 35 35 = 30 + 5
6 12 282 282 = 11 × 5 + 227 40 40 = 35 + 5
6 13 354 354 = 12 × 6 + 282 46 46 = 40 + 6
6 14 432 432 = 13 × 6 + 354 52 52 = 46 + 6
6 15 516 516 = 14 × 6 + 432 58 58 = 52 + 6
7 16 606 606 = 15 × 6 + 516 64 64 = 58 + 6
7 17 718 718 = 16 × 7 + 606 71 71 = 64 + 7
7 18 837 837 = 17 × 7 + 718 78 78 = 71 + 7
7 19 963 963 = 18 × 7 + 837 85 85 = 78 + 7
8 20 1096 1096 = 19 × 7 + 963 92 92 = 85 + 7

Now reading off of the table, there is a block of 16 “64”s that starts at position 606. That block clearly covers the 610th entry of `L`, so the 610th entry is 64.

 

Mile High Stretch. Since the shortest distance between any two points is a straight line, we can model the new path of the rope once it reaches a point M one mile above the surface of the Earth as a perfect circle with a small arc deleted, and straight lines connecting the ends A and B of that arc to the point M. In particular, when that rope is stretched taut, those straight lines will be tangent to the circle at A and B, so that there is no bend or kink in the rope. This configuration is shown in the accompanying diagram, MileHighStetchSolnA although the vertical scale is exaggerated so that the point M is visible above the circle.
By the Pythagorean theorem, the length of both segment AM and BM is `sqrt{4001^2 – 4000^2} = sqrt 8001` miles long. But to get the extra rope needed, we have to subtract the length of arc AB from AM+BM. If C is the center of the earth, then angle MCA is `arcsin(sqrt 8001 // 4001)`, so half of the arc AB in miles is `4000 arcsin(sqrt 8001 // 4001)`. Thus, the answer in feet is `5280*2(sqrt 8001 – 4000 arcsin(sqrt 8001 // 4001))`.

There are two ways to complete the problem. The first is to use a calculator. The second is to use the series for arcsin(x) near x=0, which is

`x + 1/2 x^3/3 + 1/2 3/4 x^5/5 + 1/2 3/4 5/6 x^7/7 + …`

In our case, x is `sqrt 8001 // 4001`. The square root of 8001 is between 89 and 90 (as 902 = 8100 and 892 = 902 – 179 = 7921), so x is between 89/4001 and 90/4001, or approximately 0.0225 (90 is 2.25 percent of 4000). Hence, x5 is smaller than 7·10-9, and so the third term and beyond will not change the answer by more than a fraction of a foot. Hence, to within a foot, the answer is
`10560(sqrt 8001 – 4000(sqrt 8001/4001 + {8001 sqrt 8001}/(6*4001^3)))`
  `= (10560/4001^3)sqrt 8001(4001^3 – 4000*4001^2 – 2000·2667)`
  `= (10560/4001^3)sqrt 8001(4001^2 – 5334000)` `= (10560*10674001/4001^3)sqrt 8001`.

We only need the last fraction in parentheses to within one percent, since `sqrt 8001` is under one hundred. So now the computations can be done to three figures, and for that purpose, we can approximate 4001 in the denominator by 4000. 10560/4000 = 2.64, and 10674001 = 8671×1231, with 8671/4000 ≈ 2.17 and 1231/4000 ≈ 0.308. Finally 2.64 × 2.17 × 0.308 × 89.5 ≈ 157.9 feet should be within one foot. (Double-checking with a calculator, the answer to within two thousandths of a foot is 157.4 feet, so any answer within one foot of that would be fine.)
The amazing thing about this answer is that stretching one point of a loop around the Earth to be a mile off the surface of the earth only requires about 158 feet of extra rope, a tiny fraction of the 10,560 feet it would require for a rope to go from a point on the surface, up a mile, and then back down to the surface.

Previous Weeks

Week 10: Mile High Stretch & Self-Sequential Reference, solutions to Week 9
Week 9: Minipixel & Stick Tac Toe, solutions to Week 8
Week 8: Triple Jeopardy & Geometric Addition, solutions to Week 7
Week 7: Hex Truss & Windows on the World, solutions to Week 6
Week 6: Cross Training & Sesquicycle, solutions to Week 5 and Relay 1
Week 5: Laborious Lockup & Prime Event, solutions to Week 4
Week 4: Unsustainable Agriculture & Save the Camel, solutions to Week 3
Week 3: Deranged Assistant & Rush Job, solutions to Week 2
Week 2: Carambola Orchard & Farm Roundup, solutions to Week 1
Week 1: Instant Interrogation & Urn Respect

Come back next week for answers and more puzzles.