I tried counting up all the 1 x 1 squares, then all the 2 x 2s and 3 x 3s, but this takes awhile, and eventually I lost count. This method also doesn't lend itself very favorably to a general solution to the question "How many squares in an N x N board?" What if N = 100? How about if N = 1000? We need a more systematic and general approach.My usual opening strategy when I come across a problem like this is to "brute force" a few small instances of the problem and check to see if a pattern emerges. From the pattern I try to see if I can come up with a formula, either by deriving it myself or, more typically, by searching for one online. Let's see if that works here.
For a 0 x 0 board there is a total of 0 squares.
For a 1 x 1 board there is a total of 1 square.
For a 2 x 2 board there is a total of 5 squares.
For a 3 x 3 board there is a total of 14 squares. One large 3 x 3 square, four distinct 2 x 2 squares (pictured below), and nine small squares.
For a 4 x 4 board there is a total of 30 squares, one large 4 x 4 square, four distinct 3 x 3 squares, nine distinct 2 x 2 squares, and sixteen small squares.
I think that's probably enough, because at this point I'm already starting to see a pattern develop. The sequence 0, 1, 5, 14, 30... probably doesn't mean much to most people, and I'll admit it didn't mean much to me either, at first. But when I looked just a little bit deeper, I noticed something familiar. Look at the differences between each of the terms of the sequence.
1 - 0 = 1
5 - 1 = 4
14 - 5 = 9
30 - 14 = 16
...
5 - 1 = 4
14 - 5 = 9
30 - 14 = 16
...
All of the differences are perfect squares, so it looks like all you have to do to find the nth total in the sequence, is add n2 to the previous total. This gives us the following recurrence relation:
f(n) = f(n - 1) + n2
We can use this relation to find out how many squares there are on an 8 x 8 chess board. Continuing on from where we left off:
f(5) = f(4) + 52
f(5) = 30 + 25 = 55
f(6) = f(5) + 62
f(6) = 55 + 36 = 91
f(7) = f(6) + 72
f(7) = 91 + 49 = 140
f(8) = f(7) + 82
f(8) = 140 + 64 = 204
f(5) = 30 + 25 = 55
f(6) = f(5) + 62
f(6) = 55 + 36 = 91
f(7) = f(6) + 72
f(7) = 91 + 49 = 140
f(8) = f(7) + 82
f(8) = 140 + 64 = 204
But how do we confirm that? More importantly, what can you do if you didn't notice a pattern in the sequence in the first place? Searching Google for the sequence 0, 1, 5, 14, 30 gives surprisingly good results in this case, but it normally won't so I want to show you a better place to search. That better place is called the Online Encyclopedia of Integer Sequences. (If you've been spending time at any of the programming puzzle sites that I featured in my last post, you'll want to bookmark OEIS. It's a treasure trove of nerdy goodness.)
Searching OEIS for 0, 1, 5, 14, 30 turns up sequence A000330. That sequence starts out
0, 1, 5, 14, 30, 55, 91, 140, 204...
which definitely seems to confirm the answer we got above.
Scanning through the comments I noticed this one:
Gives number of squares formed from an n X n square...which is exactly what we're looking for. Further down the page you'll find plenty of formulae, and even source code in several different programming languages, for calculating the terms of the sequence. For example, here's a closed form expression for calculating the nth term of the sequence:
f(n) = n * (n + 1) * (2 * n + 1) / 6
Solving for n = 8, we get
f(8) = 8 * (8 + 1) * (2 * 8 + 1) / 6
f(8) = 8 * 9 * 17 / 6
f(8) = 1224 / 6 = 204
f(8) = 8 * 9 * 17 / 6
f(8) = 1224 / 6 = 204
which further confirms the answer we already knew.
If it seems like there are an awful lot of comments, formulae, and references on OEIS, that's because this particular sequence, the sum of the squares from 1 to n, turns up often in many areas of mathematics. Most of the sequences on OEIS won't have this much information to sift through, but you'll very often find something useful.
A Challenge
Now that you know a general strategy for solving puzzles involving integer sequences, why don't you give the following puzzle a try?
How many triangles (of all sizes) do you see in the equilateral triangle below?
Before counting triangles or searching online for the answer, see if you can build a sequence and find a pattern and a formula the way I did with the chess board problem above. Good luck!
40 comments:
Reminded me of this: http://fredrik.liljegren.org/theQuestion.html
Tim,
I had forgotten exactly how that story went, so as I was writing this, I was hoping you'd respond with that link. :)
Interesting problem. I remember discovering the formula for the sum of squares in maths class. Working on the triangles now :-)
John,
Let me know when you get it. I'm debating whether or not to post the full solution here. I don't want to spoil it for anyone. :)
Bill,
ok I got a small way ahead. Basically following the steps of your chess-board solution.
if n is the no. of rows in the triangle figure then the series goes like 0, 1, 5, 11, 19, 29 . . .
Going as previously
1 - 0 = 1 = 2*0
5 - 1 = 4 = 2*2
11 - 5 = 6 = 2*3
19 - 11 = 8 = 2*4
29 - 11 = 10 = 2*5 . . .
Thus for n>1 the recurrence relation should be f(n) = f(n-1) + 2n
But you see the problem. The assumption taken here is f(1)=1. The formula doesn't work for taking f(0)=0 because then f(1)=f(0) + 2*2 = 2!!
I'm trying to work out an n=1 inclusive formula. So please don't post the solution too soon!
Aruni RC,
I won't give the solution to the triangle puzzle just yet, but I do want to give you a couple of hints.
#1) The sequence should start out 0, 1, 5, 13... It looks like you missed the two n(2)-sized triangles (the one that consists of 5 small triangles) in the bottom corners of the n(3) level.
#2) Make sure you keep an eye out for downward-pointing triangles as well.
I'll post the full solution sometime in the first week in August.
Good luck!
thanks for the hints. this sure is more interesting than college assignments (vector analysis) !
okay here's another attempt - half-way though.
If n is the row number of the figure:
Total triangles = Pointing Up + Pointing Down
0 = 0 + 0
1 = 1 + 0
5 = 4 + 1
13 = 10 + 3
27 = 20 + 7
48 = 35 + 13
.........
the Up triangles are: 0, 1, 4, 10, 20, 35 . . .
taking their forward differences we get,
1, 3, 6, 10, 15 . . .
taking fwd diff again,
2, 3, 4, 5, . . .
so the series is reduced to two recursive functions, the base function being natural numbrs from 2.
Predicting the next in the series:
After 5 is 6 in the final series. In the previous series we add this to the last term (15) giving 21.
In the first series we add this to 35 giving 56 - the number of triangles pointing upwards for n=6.
The downward pointing triangles are being quite nasty though (I remember the hint).
No. of downward pointing triangles =
0, 0, 1, 3, 7, 13, . . .
2, 4, 6, . . .
And there's the catch. By this prediction the next no. of dwn triangles should be 21 (8+13). However manually counting it's 22.
Btw, sorry for almost spamming your comments page. ;)
Aruni RC,
One last hint since you are so very close to the general solution: The generating function can change (particularly because of the pattern of downward pointing triangles) based on whether n is even or odd.
I definitely don't consider these comments spam. Having your regular insights as you solve this is helping me decide which steps need illustrations in the explanation I'm writing up. Thank you for sharing them with me.
found the equation
first followed the same way you followed
if it is 0 rows then it is o triangles
it it is 1 rows then it is 1 tri
when it is 2 rows then their is 4 small tris and 1 big
4+1=5 tirs--->2^2+1
case 3 rows
9 small tris, 1 big tri and 2 medium
9+1+2=12 tris--->3^2+(1+2)
case 4 rows
16 small tri, 1 big tri, 2 medium, 3 smaller then med ones
16+(1+2+3)=22--->4^2+(1+2+3)
case 5 rows
25 small tri, 1 very big tri, 2 big,3 medium, 4 smaller than medium
25+(1+2+3+4)=35 tri--->5^2+(1+2+3+4)
here we got a sequence came from the total sum of the triangles 0 1 5 12 22 35
but each number in the sequence is a result from squaring the nth term plus summation from 1 to (n-1)so our function will be
f(n)=n^2+(1+2+3+....(n-2)+(n-1))
the second part of the function is a sequence too but with a missing term which is the last term, the (n)term
in its original form
f(m)=1+2+3+.....(n-2)+(n-1)+n
f(m)= [m*(m+1)]/2
so by removing the n term to meet our sequence it will be
f(m)= ([m*(m+1)]/2)-m
the function of n term recurrence triangles is
f(n)= n^2+[(n*(n+1)/2]-n
and works starting from term 1
have a nice day
M.Kamal,
See my first reply to Aruni RC above, and his subsequent replies. The sequence should start out 0, 1, 5, 13... You said that there are 2 medium sized triangles in case 3, but there are 3, one for each corner of the triangle.
You made the same mistake at the next level, plus there are a few more of the "smaller than medium" triangles (the ones made up of four of the smallest triangles) hiding in the image. Keep looking, and check the other comments for hints. I'll post a full solution in a few more days.
Before offering the solution (or atleast, what seemsto be one), I want to say, this is an excelent blog. I recently stumbled it and I must admit, it's one of the finest I read. Anyway, here's the solution.
Number of small triangles isincreased exponentially (1, 4, 9, 16...). Actual number of triangles differs (1, 5, 13, 27,...).
Difference between actual number, and the number of the small triangles is also an exponential function:
1-1=0
5-4=1
13-9=4
27-16=9
...
So, the solution should be the sum of these two exponential functions:
f(n)=n^2+(n-1)^2 (where n is equal to nuber of rows)
Hope I got it right :)
Ivan,
Your first observation, that the number of small triangles is equal to n^2, is correct. This will be the case for every n. The next part isn't as simple. You made an arithmetic error: 27-16=9, but the correct difference at that step is: 27-16=11. This isn't a perfect square, so the function you derived
f(n)=n^2+(n-1)^2
is also incorrect. If you pick up the trail from where you made this mistake, you'll see that you were on the right track. Keep trying. :)
For upwards tringles:
Size 1 2 3 4
Row 1 1 0 0 0
2 3 1 0 0
3 6 3 1 0
4 10 6 3 1
For the downwards ones just on every second one:
Size 1 2 3 4
Row 1 0 0 0 0
2 1 0 0 0
3 3 0 0 0
4 6 1 0 0
5 10 3 0 0
6 15 6 1 0
The sums for every row gives for the first 6 rows: 1, 5, 13, 27, 48, 78
OEIS identifies: http://www.research.att.com/~njas/sequences/A002717
PS: Note this link, too, found via OEIS bibliography
http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles
CrazyC,
Good job, that's the right sequence. I hadn't seen that second URL either. That's a great resource. Thanks.
I'll still be posting a full solution with illustrations for those who had trouble counting triangles (I had problems keeping track of them myself) and with the formulas I used in the general solution. That should be posted by the end of this coming weekend.
Thanks to everyone who's been commenting on this problem. This has been one of the most fun (for me) posts I've done so far.
Upon the first inspection:
For a triangle with N divisions:
Up Triangles:
Summation of n from 1 to N ( n*(n + 1) / 2 )
Down Triangles:
K = N / 2 or (N - 1) / 2 depending on N being odd or even (When writing code, integer division will solve the problem)
Summation of n from 1 to K ( n*(n + 1) / 2 )
Total:
Sum of these 2. I'll calculate and post.
i started same as you have done in case of chess board....
for size 0:
the no of triangle will be 0,
for size 1:
triangle(1) = Sum(tringle(0)+triangle(1))
= 0+1
= 1
for size 2:
triangle(2) = Sum(triangle(0)+triangle(1)+triangle(2))
= 0+4+1
= 5
for size 3:
triangle(3) = Sum(triangle(0)+triangle(1)+triangle(2)+triangle(3))
= 0+9+3+1
= 13
for size 4:
triangle(4) = Sum(triangle(0)+triangle(1)+triangle(2)+triangle(3)+triangle(4))
= 0+16+7+3+1
= 27
now putting the sequence(0 1 5 13 27) in OLEIS
found that the approximate formula the the sequence is
f(n) = Floor [n*(n+2)*(2n+1)/8]
which also satisfies the initials counted results..........
so for the triange size 5:
f(5) =Floor(5*7*11/8)
=Floor(48.12500)
=48
this should be the correct answer.
Ranjeet,
The way you describe above is almost exactly how I first solved the triangle problem.
I was google searching and your blog came up. I am actually working on this problem for school. I learned some things from reading over your site. I need to show the one to one correspondence yet.
Em,
First, are you talking about the chess board problem, or the triangle problem? Because I have a solution to the latter here.
Second, I'm not sure how rigorous you need to be, but isn't the closed-form function (and its reverse) enough to prove a one-to-one correspondence? I'm a complete math amateur, so I could be wrong about this. :)
Third, thanks a lot for reading and commenting. Helping students (and myself) learn is my main goal for this blog. I hope you'll keep me updated if you find any interesting applications for anything you read here. Good luck in your school work!
I need C or c++ code for finding number of squares on a chess board.
Miki,
You can take the closed form function and create a C or C++ (or any programming language) function from it.
f(n) = n * (n + 1) * (2 * n + 1) / 6
I think the answer is 90
with the chessboard problem, how did you figure out the rule for the problem, if so, what is the working out for the rule, i can't seem to understand how you get it!!
Allie,
Looking at the differences in the number of squares in a 0, 1, 2, 3, 4, etc. sided board, I noticed the pattern 1, 4, 9, 16, ... Those are perfect squares, so all you have to do to find how many squares there are on an n sided board is add n^2 to the number of squares on an n-1 sided board. This gave me the recurrence relation
f(n) = f(n - 1) + n^2.
I found the closed form expression
f(n) = n * (n + 1) * (2 * n + 1) / 6
by cheating and looking it up on OEIS (linked in the article).
is there any explanation for n(n+1)(2n+1)/6 ?
It is sum of squares of up to n..
Easy to identify..
8 by 8 squares = 1 by 1 + 2 by 2 +....+ 8 by 8
= 8^2 + 7^2 +...+ 1^2
Squared becoz length and breadth wise
do you know that sombody cheats people in Finland using your web page address billthelizard.com by sending them SMSes which are payable if they want or not? Can you solve the problem? If not, I assume, it could be you-using your knowledge for such a despicable purpose....
Anonymous,
I don't know anything about the SMSs you mentioned. I can assure you it's not me sending them. Since a URL is public, I don't know if there's anything I can do about it. I'll look into it to see if anything can be done. Thanks for bringing it to my attention.
Thank you in advance and sorry that I'm so suspicious, but yesterday, by my stupid mistake(I thouught it was yet another internet competition) I wrote my mobile's number and I got around 4 SMSes in a row with instruction how to enter the competition, I opened these SMSes sent from number 173311(maybe if I didn't opened it would have been OK...)and it swallowed around 11€ I had on my prepaid-phone.
They ask a question(in Finnish), 'how many triangles can you see?', there's a triangle with many inside, similar to yours and there's your page address(that's how I found it)-otherwise I wouldn't have come across your page as I'm not interested in math.
It's not the first time when somebody cheats people in Finland this way.Btw, these thieves must be very knowledgeable to steal money by sending SMSes to delivered number using a computer.
Anonymous,
Yes, it looks like they're linking to the triangle image. I've heard of a similar scam in an ad on Facebook. I wish there was some way I could switch out the image so they'd stop using it, or just host it themselves.
exactly-this scam I've found on Facebook
your linkage is not working properly please check the urls and edit.
CyberDreamLady,
Thanks a lot for the notification.
@Bill the Lizard. How many rectangles are on a chessboard? That includes squares. Turns out the answer is (((n)(n+1))/2)^2 where n is the number of squares along the side.
There are 354 square on the chess board please re calculate it
I agree, but I think you should add a simplified equality at the end of the equation. Ex:f(n)=f(n-1)+n2=s. In order for this equation to work however, the board must be a square. Correct me if I'm wrong, but I also believe that N=number of squares on one side, to find f, you would have to divide n by s, and s would equal total number of squares. Also, I'm twelve.
Post a Comment