3
$\begingroup$

Disclaimer: This is not homework, it is not for a class, and it is not for any kind of test.

I'm trying to improve my skills with creating algorithms to solve word problems.

I've been banging my head on this one and in the spirit of learning I would like help with a solution.

Please explain your thought process in coming up with a solution. I would like to discover what thoughts I am NOT having so that I can hopefully use that observation to improve my thought process.

Problem:

  1. The side of each square is one.
  2. The area of each square is one.
  3. Come up with a formula where given n, find the area of a polygon
  4. n can be any integer

Picture of the polygons.

n area thoughts about the formula
1 1 each side is one, area is one
2 5 n -1 = 1. 1 square = 4 sides, each can attach a square, 4 squares, area = 4 + 1
3 13 n-1 = 2, 2 squares = 8 sides, each can attach a square, 8 new squares + 5 old squares, area = 13
4 25 n-1 = 3, 3 squares = 12 sides, each can attach a square, 12 new squares + 13 old squares, area = 25

The part that is driving me nuts is how given just n, to come up with the number of preexisting squares to add to the area generated by (n-1) x 4.

My intuition is that I may not be supposed to do that, but I can't think of how else to get the area of each progressively larger polygon given just n.

Any clues would be greatly appreciated.

$\endgroup$
3
  • 1
    $\begingroup$ There are two schools of thought you can follow. One, you can keep track of two running variables instead of just one: the area and the perimeter. The area of the next is just the sum of the area and the perimeter of the previous, and the perimeter of the next is some function of the area of the next. The other school of thought is, the $n$ represents some sort of radius, so the area clearly scales as $O(n^2)$. So take any three points in your progression and fit it to a parabola $an^2+bn+c$ $\endgroup$
    – Ninad Munshi
    Oct 31, 2022 at 20:24
  • 2
    $\begingroup$ Another approach is coloring the squares like in a checkerboard, then count black (or white) squares and sum the white (black) squares. It is easy to see that we obtain $n^2+(n-1)^2$. Still another approach is starting counting squares from a corner and noticing they are the sum of odd integers from $1$ to $2n-1$ and $1$ to $2n-3$ which gives again $n^2+(n-1)^2$. $\endgroup$
    – Fabius Wiesner
    Oct 31, 2022 at 21:07
  • 1
    $\begingroup$ These are called centered square numbers and there is more information than you will probably want at oeis.org/A001844 $\endgroup$
    – Narlin
    Oct 31, 2022 at 21:14

2 Answers 2

Reset to default
3
$\begingroup$

The area of the shape where n=4, for example, is $(1+3+5+7) + (1+3+5)$. This means that for any n, we can write the area as $(1+3+\dots+2n-1) + (1+3+\dots+2n-3)$. Using the formula for the sum of the first $n$ odd numbers, we find that this, quite eloquently, is equal to $n^2 + (n-1)^2$.

$\endgroup$
2
$\begingroup$

Since you figured out the difference is $4(n-1)$, try computing 1/4 of the area.

$$\begin{array} {r|l} n & \text{area}/4 \\ \hline 1 & \frac 14 \\ 2 & \frac 14 + 1 \\ 3 & \frac 14 + 1 + 2 \\ 4 & \frac 14 + 1 + 2 + 3 \\ \end{array}$$

Can you finish?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .