Chapter 6
Solutions for first week’s assignments

Note: These are my approaches to these problems. There are many ways to tackle each.

6.1 Problem Set 1.1

6.1.1 Problem 10

Part a

Following the construction rules for one pass forward:

What remains is to fill in the upper-right corner. The rule is that the 7 below the “?” is the sum of 4 and the missing number “?”. So the final result is

Part b

In this case, no side-by-side numbers are provided. One must start by working on the rule from the apex backward. In the first step, the row above 16 must add to 16, so the missing number is 7. Subtracting 7 from the left and right sides produces the two corner numbers. The final figure is

Part c

Here there is not enough information to progress in either direction. A solution comes from guessing, building a table, or finding relationships. A table would include numbers from 0 to 9 for each of the four open spots.

For finding one solution, note the problem is symmetric. So the numbers along the left side are equal to the numbers along the right. We can use this information to produce a smaller table.

However, symmetry provides sufficient information to work up the figure. The two numbers above the 10 are the same and add to 10, so each is five. Then the corners must be four, and one solution is

Part d

Both parts a and b were formed by applying the rules directly. There was no room for changing any of the values, so these are the only solutions.

For part c, the solution above reduced the problem until there was a unique solution. But the original problem did not require that the numbers down each side stay the same, so we are free to try other patterns. Given the rule for adding adjacent entries in one row to form the next, we know we can shift numbers so long as their sums are the same.

Pushing a one from the left to the right produces a few more examples from the initial solution on the left:

6.1.2 Problem 13

One way to create a table for this problem would be to list all sequences of the numbers 2, 3, 4, 5, and 6. The consider mapping the sequences to the diagrams row-wise; the first three numbers fill the three circles in first row, the next number fills the next circle down, etc.

Filling in the table first by rotating the initial sequence,

This order happens to answer both part a and b almost immediately. In the worst case, however, there are 5! = 120 rows in this table.

So two examples satisfying the relationship are

Answering part c by an exhaustive table requires all 120 rows because the answer is no. This part also indicates how to reduce the table.

The top row of three and the middle column of three add to the same quantity. They also share one number where they intersect. That number does not matter at all. And the order of the remaining numbers within the row or column also does not matter.

So each row of a full table need provide only which number is left out and then two pairs. And note that after picking the number and the first pair, only a single pair remains. So chosing to drop 2 and then picking the pair (3,5) leaves 5 and 6 which forms only one pair. There are five numbers to drop out and six ways to pick a pair from the remaining four numbers, so a complete table was only 30 lines and not 120.

To check the last part, however, we know 3 will be the number left out. This leaves only six lines to check, far fewer than 120.

Examining the sums in the table, note that one always is odd and one always is even. Dropping 3 from the initial sequence leaves 2, 4, 5, and 6. Of those, three are even and only one is odd. The sum of two even numbers is even, and the sum of an even and an odd number is odd. So there is no way to choose two pairs from 2, 4, 5, 6 such that both add to an even or to an odd number. Hence the sums cannot be equal.

Sometimes taking care in reducing a table is more work, but it can make plain relationships you can use in future problems to avoid making any table at all.

6.2 Example like 1.3 with no solution

I apologize for chopping off the hint. It suffered from a cut and paste error and should have pointed you to the even/odd idea.

Guessing and creating small tables of examples are perfectly good approaches. Another is to use a similar even/odd relationship.

The sum of the smaller circles is half the sum of the larger circles. So if the larger circles add to an odd value, there is no way to fill the smaller circles with integers adding to half that odd value.

Fill the outer circles with odd number of odd numbers. The resulting sum is odd.

Without the hint, you may simply fill the larger circles with 1, 1, and 1. Then you need a zero somewhere in the smaller circles, and I disallowed zeros or negative numbers during class. I did not realize that the text allowed non-integers and negative numbers in the problem.

6.3 Problem Set 1.2

6.3.1 Problem 5

Generally, it is far easier to see the rule if the guesses are placed in order, answering a portion of part c. Assume that each of the childrens’ rules are determined by a relatively simple formula of the chosen number.

Part a

Make a table to see if the guesses could satisfy the rule:

So the guesses may have found the rule. If the guesses really are the same, that is more evidence. However, the problem does not provide rules for the initial rules. A student’s rule could be “return a random number.” If the rules are required to be linear, that is of the form ax + b where the chosen number is x, then the five choices above are more than the two required to determine the line. (Two points determine a line, and each guess places a point.)

The two guesses appear the same. Consider the guesses algebraically, so the first guess is 5i - 3 and the second is 5(i - 1) + 2 where i is the chosen number. Expanding the latter, 5i - 5 + 2 = 5i - 3, so the rules really are the same.

Part b

The table of provided data:

The following questions could help guide your guesses,

• Is the sequence formed by a line like ax + b? Such a curve grows slowly.
• The next step up is a quadratic curve like a parabola. Does the data fit some simple formula a{x}^{2} + bx + c?
• The next step is a cubic with {x}^{3}. Do the numbers increase very quickly?

Starting at zero helps; you see the constant term must be one. Subtracting one from the other returned numbers,

So a reasonable guess is {x}^{2} + 1.

Another route to this result:

The curve grows a little more quickly than we would expect from a line. Also, if this were a line, the first two points determine its structure as x + 1, but this does not fit the third point, 3 + 1 = 4≠10.

A quadratic is determined by three points. From the first, (0,1), we see that c = 1. Then the second (1,2) and third (3,10) points set up the equations a + b = 1 and 9a + 3b = 9. We already know this cannot be a line, so a≠0. Assuming a and b are integers, that leaves a = 1 and b = 0. So the rule may be {x}^{2} + 1. That fits the other data.

Part c

The table of provided data:

This grows slowly, so it’s reasonable to guess a linear relationship. The zero term gives a constant 7, and the first term suggests a slope of 3 so 3 ⋅ 1 + 7 = 10. Continuing with the other points confirms that this is a reasonable guess.

Choosing the first few numbers starting from zero definitely helps make the relationship clear. However, it can be useful to pick a few consecutive numbers further away to see how quickly the function grows. In this case, we would expect choosing 10 and 11 to result in two numbers as close together as the results from 0 and 1 if the problem were linear. If the student had returned two numbers much further apart, we could avoid trying to fit the data to a line.

6.3.2 Problem 7

There are many straight-forward ways to build a table here.

One starts by placing all four coins in one denomination, then moves a coin to the right:

There are 15 lines, two of which are shared. So there are 14 different quantities possible.

Another method would write out denominations first and then try to form them with some combination of coins. The smallest possible amount is 20 for using four nickles, and the largest possible is 100 for four quarters. There are (100 - 20)∕5 = 16 possible table entries. But 75 and 90 cannot be formed, leaving 14 different possible quantities.

6.3.3 Problem 8

This is a classical problem used in discrete mathematics and introductory computer science classes, although often starting with a dollar to make tabling less practical.

There are 49 ways.

There are at most two quarters, at most five dimes, at most 10 nickles, and at most 50 pennies per line of a table with the following heading:

To generate the table, start with two quarters and then shift amounts over as in other problems. You used the conserved quantity, the total amount, to guide your next choice.

Another method for solving this problem is to set up recurrence relationships and build a slightly different table.

Consider making change for an amount N. And consider four different ways for making such change:

Say we start at N and the full collection of possible coins. Then either the change contains a quarter or it does not. If it does contain with a quarter, then we change the remaining N - 25 in the same way, possibly with more quarters. If not, then we change N no quarters. So

Similarly,

We can begin constructing a table of values by N starting from the extreme case N = 0. There is only one way of making no change at all, so {A}_{0} = {B}_{0} = {C}_{0} = {D}_{0} = 1. There also is only one way of making change with pennies, so {A}_{N} = 1 for all N. And the relations above show we need only rows where N is a multiple of five and provide formulas for every entry.

6.4 Consider solving Example 1.3 with a table

Note that each of a, b, and c can be at most one less than the smallest number adjacent to them (I ruled out zeros in class). So there are at most 10 possibilities for a, 14 for b, and 10 for c. Listing all would require 10 ⋅ 10 ⋅ 14 = 1400 entries.

But also one variable is completely determined by the other two, so we would need a list of 10 ⋅ 14 = 140 possibilities for a and b (or c and b), or 10 ⋅ 10 = 100 for a and c.

Or we could note that each choice of a immediately determines a possible choice of c. Then we simply verify that some b satisfies the sums. This leaves a total table of 10 lines.

Assume there is a reasonable order for bisection. A worst case sequence of entries we could check would be 1, 10, 5, 7, 8, 9; so 6 entries total. The actual sequence here would be 1, 10, 5, 7, 6; so 5 entries.

6.5 More in Problem Set 1.2

6.5.1 Problem 6: whoops, not assigned

Whoops. I solved this but never assigned it. Keeping the solution here for examples.

There are many approaches. I provide a few overly clever ones below.

The first two parts only require following the rules to fill the triangles.

Part a only requires following the rules to fill the triangle:

Part b is similar, but requires filling in \mathbf{8} = 19 - 11:

The next two fall to the same tabling technique outlined in the solution above with some minor modifications.

For part c, the outer sum is odd, so there is no integer solution. The text apparently allows non-integer solutions. Then the following triangle suffices and can be found by doubling all the entries, solving, and halving all the entries again:

In part d, the negative numbers can be dealt with by adding a sufficiently large number to the vertices of the triangle, solving the problem, and then subtracting half that number from the intermediate nodes.

The first number we add should be even to maintain the even/odd balance (even+even is even, even+odd is odd, so adding an even doesn’t change the number of evens and odds). And adding a number larger than the largest given number will shift all the intermediates above zero. So we chose the smallest even number larger than 11 and hence add 12 across the outer nodes. Solving:

Subtracting half 12 (or 6) from the intermediate notes gives a solution to the original problem:

6.5.2 Problem 13

The area is the product of the length and width. Knowing the lengths are whole numbers, we can write a list of all integers that divide into 120 cleanly. We need only include “half” the entries; the length and width are interchangable.

The perimeter is twice the sum of the length and width. Including the perimeter in the table solves the second part of the problem.

So the shape with the smallest perimeter is the nearly square 10 × 12. This is true in general: The shape with the least perimeter or surface area enclosing the greatest volume is the closest to a circle or sphere. Here, a square is as close to a circle as you can get with four sides, and 10 × 12 is as close as you can get to a square.

6.5.3 Problem 18

Drawing diagrams for smaller problems reveals the sequence in the following table:

The relationship above is that there are four times as many posts as sections, so the final result is 40 posts for 10 sections.

6.5.4 Problem 20

Each square has four edges, and joining two squares along one edge removes one from both but two from their sum. Hence all possible perimeters all are even.

What is the largest number of exposed edges?

Simple counting arguments give an overestimate. Given nine squares, there can be at most 36 edges exposed, or four for each square. But each square must be joined to at least one other. Again, joining reduces the number of exposed edges by one per square. Each square must be joined, so each contributes at most three edges to the total. So there can be at most 27 edges exposed, or 26 taking into account the previous paragraph.

But they squares are all connected. The form hiding the fewest edges occurs when placing all squares in a line. Shifting around squares from this shape only hides more edges, so we know the largest perimeter is 20.

And what is the smallest number? There must be at least four edges exposed, as all the squares are linked and there must be at least four larger edges of at least one edge each.

In general, the most “circle-like” figure has the least exposed surface. In this case, the shape would be square, exposing 12 edges. Shifting any block around a square exposes more edges, so the square is the smallest with a perimeter of 12.

The remaining problem is to take the largest (or smallest) shape and shift blocks around to form all the intermediates. Forming each of 14, 16, and 18 is fairly simple.