Varsity Math, Week 16
Coach Newton wants to wish all of the aspiring Varsity Math solvers a Happy New Year!
Gonzi Scheme
The CEO of Topnotch Finances LLC comes home for New Year’s eve and confides, “Dear, 2016 is going to be a terrific year for Topnotch. We’ve found a new investment, codenamed Gonzi. We will open an account with Gonzi at the beginning of next month. At the end of each month, Gonzi adds to the account the same amount that the account was worth at the beginning of the month, and then deducts the month’s expenses from the account. The expenses are terrible, though: $1 million the first month, $4 million the second month, $9 million the third month, each month the square of the next number, in millions. But still, to be able to double the account balance each month before expenses is really attractive.” The CEO’s spouse (and chief advisor) asks, “What happens if your account balance ever goes negative?” “In that case, the account is permanently closed—there is no opportunity to make additional investments.” The spouse concludes, “Then you better make sure you start with a big enough investment so your Gonzi account isn’t closed before you want it to be.” That gives the CEO pause for thought. “You’re right,” he says, “if we only invested $2 million to start with, say, we wouldn’t be able to pay the $9 million expenses in the third month.”
What is the minimum initial investment in Gonzi that will prevent the account from ever being closed as a result of a zero or negative balance?
New Year-amid
If you solved last week’s Boxes not Urns problem, you’ll also know the probability that the two tags Emerson draws are the same color. Write that probability as a fraction P/Q in lowest terms. Ms. Leavenmath has P pupils in her math class. To celebrate the new year, she has her students take a large number of red unit blocks and build a square pyramid. The top level of the pyramid is a single block, and each successive layer is a square of blocks with one more block on each side than the previous layer. Her class builds the third smallest such pyramid with the property that once they are done, the blocks can be divided evenly among the students. She then has one student take his share of the blocks and combine them with an equal number of orange, yellow, green, blue, and purple blocks to demonstrate that with this new collection of blocks he can build a square prism just two units taller than it is wide.
How many blocks are there in the square prism?
Solutions to Week 15
Boxes Nest. If you look at just the heights (or the lengths or the widths) of any sequence of nested boxes, they are an increasing sequence of six whole numbers starting from one and ending at eight. In particular, the middle four can be any four numbers out of the six numbers 2,3,4,5,6,7, so there are `((6),(4)) = 15` possible sequences of heights (or lengths or widths). So why isn’t the answer just 15×15×15, i.e., pick any sequence of heights, lengths, and widths, and use them? The first issue is that the boxes can be rotated on the table. So the lengths are indistinguishable from the widths. Because of the box tops, though, we can always tell which dimension is the heights, and we can use any sequence of heights we want with a given sequence of rectangular length × width “footprints” of the boxes, so the answer will in fact be the number of valid sequences of such footprints times 15.
So shouldn’t the number of sequences of footprints just be the number of sequences in which length and width are always equal, namely 15, plus the number of pairs of two different valid length/width sequences, namely `((15),(2)) = 105`, because with rotation it doesn’t matter which are the lengths and which are the widths, for a total of 120? The problem is that method still double-counts certain sequences of footprints. For example, 2×2 fits in 3×4 fits in 5×6 fits in 7×7, but since each individual box can be rotated, you get that sequence of footprints from the length sequence 2,3,5,7 and width sequence 2,4,6,7, but also from length sequence 2,4,5,7 and width sequence 2,3,6,7. So we need a more careful way of counting valid sequences of four footprints from 2×2 to 7×7.
The Coach wants to show two different ways you could go about this. The first is to find all of the possible footprints one could use, figure out which footprints fit in which other ones, and then use that information to count the sequences of length four that fit together one into the next. There are of course `((6),(2)) + 6 = 21` footprint shapes, i.e. length/width combinations where order doesn’t matter but in which the length and width can be the same or different. However, a 2×7 footprint does not fit in any other footprint nor does any other footprint fit in it, so it cannot be a part of a chain of four nesting footprints. For similar reasons, none of 2×5, 2×6, 3×6, 3×7, or 4×7 can be part of any chain of four nesting footprints. There remain 15 footprints with which we must concern ourselves, and the second column of the table below shows which footprints fit inside a given one.
| Footprint Shape | Fits: | # of 1-seqs | # of 2-seqs | # of 3-seqs | # of 4-seqs |
|---|---|---|---|---|---|
| 2×2 | 1 | 0 | 0 | 0 | |
| 2×3 | 1 | 0 | 0 | 0 | |
| 2×4 | 1 | 0 | 0 | 0 | |
| 3×3 | 2×2 | 1 | 1 | 0 | 0 |
| 3×4 | 2×2, 2×3 | 1 | 2 | 0 | 0 |
| 3×5 | 2×2, 2×3, 2×4 | 1 | 3 | 0 | 0 |
| 4×4 | 2×2, 2×3, 3×3 | 1 | 3 | 1 | 0 |
| 4×5 | 2×2, 2×3, 2×4, 3×3, 3×4 | 1 | 5 | 3 | 0 |
| 5×5 | 2×2, 2×3, 2×4, 3×3, 3×4, 4×4 | 1 | 6 | 6 | 1 |
| 4×6 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5 | 1 | 6 | 6 | 0 |
| 5×6 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5, 4×4, 4×5 | 1 | 8 | 14 | 4 |
| 6×6 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5, 4×4, 4×5, 5×5 | 1 | 9 | 20 | 10 |
| 5×7 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5, 4×4, 4×5, 4×6 | 1 | 9 | 20 | 10 |
| 6×7 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5, 4×4, 4×5, 4×6, 5×5, 5×6 | 1 | 11 | 34 | 30 |
| 7×7 | 2×2, 2×3, 2×4, 3×3, 3×4, 3×5, 4×4, 4×5, 4×6, 5×5, 5×6, 6×6 | 1 | 12 | 43 | 50 |
Now, to count the sequences of four footprints that nest, we begin with sequences of one footprint. Those are easy: as shown in the table, there is exactly one nesting sequence of length one ending at a given footprint, namely that footprint itself. How could we build up a sequence of length two ending at a given footprint? Just add that footprint to any sequence of length one which ends at a footprint which fits inside the given one. In other words, add up the number of sequences of length one for every footprint listed in column two, and that produces the fourth column of the table. But now sequences of length three can be built up from sequences of length two in exactly the same way, and so on to sequences of length four. So each successive column in the table is just the sum of the prior column over all of the footprints listed in the second column.
We now know the number of sequences of four nesting footprints that end at each possible footprint, and we just add them up to get 105 = 50+30+10+10+4+1 possible footprint sequences.
A second approach to finding the number of nesting sequences of footprints may shed additional light. The idea of this approach is to find a “standard” way to rotate each box in any nesting sequence of boxes, and then count the length/width sequences that will arise from the standard orientation. In particular, note that we can rotate every footprint so that its length is at least as large as its width. This means that the length sequence and width sequence will have the property that every entry of the length sequence is greater than or equal to the corresponding entry of the width sequence. Conversely, every one of the 120 possible length/width sequence combinations which can be ordered to have that property will give rise to a distinct valid sequence of nesting footprints. But not all of the length/width sequence combinations can be so ordered. For example, with 2,5,6,7 and 3,4,5,6 in that order, 2 is not bigger than 3, but in the other order, 4 is not bigger than 5. So this combination of sequences does not contribute a valid footprint sequence. We can simply enumerate the sequence combinations which display this obstruction, and subtract them from the overall 120 sequence combinations. It turns out there are 15 bad sequence combinations: 2,5,6,7/3,4,5,6; 2,5,6,7/3,4,5,7; 2,5,6,7/3,4,6,7; 2,4,6,7/3,4,5,6; 2,4,6,7/3,4,5,7; 2,4,5,7/3,4,5,6; 2,3,6,7/3,4,5,6; 2,3,6,7/3,4,5,7; 2,3,5,7/3,4,5,6; 2,3,4,7/3,4,5,6; 2,3,6,7/2,4,5,6; 2,3,6,7/2,4,5,7; 2,3,5,7/2,4,5,6; 2,3,4,7/2,4,5,6; and 2,3,4,7/2,3,5,6. So again, there are 120 − 15 = 105 sequences of nesting footprints.
Counting 105 distinct sequences of four nesting footprints, either way, leads us to conclude that there are 105 × 15 = 1575 different sequences of boxes that Charlie can use to make the nesting boxes toy.
Recent Weeks
Week 15: Boxes not Urns & Boxes Nest, solution to Crooked Clock
Week 13: Try Angles & Great Lengths, solution to Daunting Doorways
Week 12: Daunting Doorways & Slingshot Grid, solution to Design Data
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.
