Connecting-the-Dots

Learning Objectives

At the end of this sub-unit, students should

• know how to apply connecting-the-dots to problem solving.

Why Connecting-the-Dots

While guess-and-check is the simplest problem solving technique, it is not always be applicable. Take for instance the problem of finding the number of steps it takes for the process based on Collatz conjecture to reach \(n = 1\). To actually perform the check in the guess-and-check, we would have already solved the problem because by continuing the process, we would arrive at \(n = 1\) based on our input.

So clearly, a different problem solving technique is needed. This technique is a precursor to exploration. We will first simplify the process by assuming that there are relationships in the output between consecutive inputs. By looking at this relationships, we can try to derive either a closed-form formula or a what we call as a "connecting formula". Connecting formula will be sufficient to solve the problem without arriving at the closed-form formula. If efficiency is needed, then we can continue the analysis to find the closed-form formula.

But finding the connecting formula might not be easy. We will provide one potential technique at arriving at this connecting formula by playing a puzzle of guess the next number in the sequence¹. This will be like performing guess-and-check but instead of guessing the value, we guess the formula.

Steps

1. Start with series of consecutive inputs.
   • If the input is already given in the problem description, we can use that.
   • Alternatively, we can try to come up with our own series of inputs in the first step.
2. Assume outputs from smaller inputs can be used in the computation of the output for the larger inputs.
   • This is one of the important feature of connecting-the-dots.
3. Find the relationship between outputs from consecutive inputs.
   • The relationship can be simple arithmetic or other more complicated formula based on the operations that can be done on the given data type.
   • We simply have to arrive at the connecting formula that connects the outputs from consecutive inputs.

We will use the following matchstick pattern as our examples.

The input is given at the top for \(n\) from 1 to 3. The pattern is generated by the following procedure.

• Start with a single upright triangle for \(n = 1\) with 3 matchstick.
• If we have created the pattern for \(n - 1\), we can create the pattern for \(n\) by adding \(n\) number of upright triangle (i.e., upright like the case of \(n = 1\), not inverted) at the bottom.

Try to test your understanding by finding the pattern for \(n = 4\).

\(n = 4\)

Number of Small Triangles

Number of Small Triangles

Problem Description

Given the pattern generated above, we can count the number of small triangles as the triangle that is bounded by completely by matchstick without any other matchstick inside. However, we need to count both upright and inverted triangle. So in the case of \(n = 2\), the number of small triangles is 4. This includes 3 upright and 1 inverted. We do not include the large triangle formed from the 4 triangles as part of the small triangle.

Task

Write the function triangles(n) to compute and return the number of small triangles in the pattern for the given value of n.

Assumptions

• n is a positive integer (i.e., n > 0).

To solve this, we first construct a table containing the input and output pair. We know at least the 4 values. Let us leave n = 5 blank for now to check if our solution is actually correct after we found the formula or the connecting formula.

TableSolution

n	matchsticks(n)
1	1
2	4
3	9
4	16
5
\(\vdots\)	\(\vdots\)
n	?

n	matchsticks(n)
1	1
2	4
3	9
4	16
5	25
\(\vdots\)	\(\vdots\)
n	\(n^2\)

Hopefully, the formula is quite obvious once we show it as a table like this. It is simply \(n^2\). We can also check with n = 5 to see that this is correct.

Number of Small Triangles

def triangles(n):
  return n * n

Number of Matchsticks

More interestingly is the case where the closed-form formula is difficult to obtain. We will illustrate that with the following problem.

Number of Small Triangles

Problem Description

Given the pattern generated above, we can count the number of matchstick as the blue lines. Every triangle is enclosed by 3 matchstick but a single matchstick may be part of the enclosure for up to 2 triangles. In the case of \(n = 2\), we have 9 matchsticks.

Task

Write the function matchsticks(n) to compute and return the number of matchsticks in the pattern for the given value of n.

Assumptions

• n is a positive integer (i.e., n > 0).

We will do the same thing as before. Unfortunately, the pattern is not obvious here. So what can we do?

n	matchsticks(n)
1	3
2	9
3	18
4	30
5
\(\vdots\)	\(\vdots\)
n	?

Looking at the pattern, we can see that the top triangle for \(n = 2\) is constructed from the triangle formed by \(n = 1\). This gives us 3 matchsticks + some extra from the bottom row. That extra is 6 matchsticks, which gives us a total of 9 matchsticks as required. So our current hypothesis is (the number of matchstick from \(n - 1\)) + (some extra from the bottom row). Let us see if this hypothesis is correct for the next larger number.

In the case of \(n = 3\), the top two rows are from \(n = 2\), which as we know gave us 9 matchsticks. The extra is the bottom row which gives us another 9 matchsticks. So we have 9 matchsticks + 9 matchsticks = 18 matchsticks. Following this, the case for \(n = 4\) is also the same. We can extend the table to show this pattern more explicitly.

Step 1Updating First Row

n	matchsticks(n)	(n-1) ans + last row
1	3	3
2	9	3 + 6 = 9
3	18	9 + 9 = 18
4	30	18 + 12 = 30
5
\(\vdots\)	\(\vdots\)	\(\vdots\)
n	?

n	matchsticks(n)	(n-1) ans + last row
1	3	0 + 3 = 3
2	9	3 + 6 = 9
3	18	9 + 9 = 18
4	30	18 + 12 = 30
5
\(\vdots\)	\(\vdots\)	\(\vdots\)
n	?

Is the pattern clearer? Let us make it even clearer by making the first row to have the same format. We know the answer is 3 and we know the number of matchstick from the last row is 3. So we want to solve for \(x\) in \(x + 3 = 3\). Clearly, the answer is \(x = 0\).

If the pattern is still unclear, let us extend this further. We have obtained parts of the solution highlighted in yellow. So we are left with the computation of the last row. Extracting the last row into another column produces the following table. The question now is given the leftmost column (i.e., column n), can we produce the rightmost column (i.e., last row). This is what we call as the remaining problem.

Step 2Solution

n	matchsticks(n)	(n-1) ans + last row	last row
1	3	0 + 3 = 3	3
2	9	3 + 6 = 9	6
3	18	9 + 9 = 18	9
4	30	18 + 12 = 30	12
5
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
n	?

n	matchsticks(n)	(n-1) ans + last row	last row
1	3	0 + 3 = 3	3
2	9	3 + 6 = 9	6
3	18	9 + 9 = 18	9
4	30	18 + 12 = 30	12
5
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
n	?		\(3n\)

The pattern becomes simpler. If it is still not as simple, we can further extract some other feature. But hopefully you can see that the formula for the last column is simply \(3n\). What we need to do now is to find the connecting formula. First, note that if we perform the computation in a loop, then we can name the highlighted part as a variable \(p\). If we do so, then the formula for the second rightmost column can be expressed in terms of \(p\).

n	matchsticks(n)	(n-1) ans + last row	last row
1	3	0 + 3 = 3	3
2	9	3 + 6 = 9	6
3	18	9 + 9 = 18	9
4	30	18 + 12 = 30	12
5
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
n	?	\(p + 3n\)	\(3n\)

Since we are using \(p\), we have to ask ourselves, what is the initial value of \(p\)? Looking at the first row, we can see that the highlighted part is 0. This means that we should start the computation with \(p = 0\).

There is another way to think about it. Since our computation is addition, we need to find the additive identity. This is the value \(x\) such that \(x + y\) is equal to \(y\) for any value of \(y\). There is only one answer and that is \(x = 0\), which is the same as our starting value.

So a brief recap, we have found a formula that can be used to compute the value for the next row given the value from the previous row. Let us call the value on the next row as \(q\) and the value from the previous row as \(p\). Then we have \(q = p + 3n\). Now if we look ahead and consider the next next row. Then \(q\) is actually considered as the value from the previous row. This means that \(q\) should actually be named as \(p\).

This is called the connecting formula. It connects the value from the previous row with the value from the previous row. The formula for the current problem can be written as the following code.

p = p + (3 * n)

The next question is how do we utilize this connecting formula? Remember that our basis is always the leftmost column. We want to solve for an arbitrary n. Since all our formula assumes that the value is based on this column, we need to be able to generate all the values from 1 to n inclusive of n. This can be done with the following loop.

i = 1
while i <= n:
  # i is between 1 and n (inclusive)
  i = i + 1

We must then insert the connecting formula, initialize the value of p, and finally return it at the end. This gives us the following code.

Number of Matchsticks

def matchsticks(n):
  p, i = 0, 1
  while i <= n:
    p = p + (3 * i)  # we use i because that's the current row
    i = i + 1
  return p

# quick check
i = 1
while i <= 5:
  print(matchscticks(i))

3
9
18
30
45

Manually check by drawing the pattern for n = 5 and counting. Is it correct for n = 5.

---

1. Unfortunately, for any finite sequence, there is actually an infinite number of formula that can generate the finite sequence. But we will restrict ourselves to a common sense formula. ↩