Checkboard Trilogy #3
And now, the final question in Bobo The Bear’s Checkboard Trilogy:
How many ways are there to arrange 4 checkers on the spaces of a standard 8×8 checkerboard so that they form the corners of a square (This includes squares that are “tilted” with respect to the edges of the board)?
Answers can be submitted below; will reveal sometime next week
This version of the puzzle is very very cool!!!! but very very hard also…
Here is my shot at it:
With 4 checekers you have the 204 aligned squares minus the individual squares (64)
—> 140
I found the “tilted” squares folowing this weird pattern:
1X1=0 (can get 4 checkers in it)
2X2=0 –> number of tilted squares in 1X1 + square(0)= 0
3X3=1 –> number of tilted squares in 2X2 + square (1)= 0 + 1= 1
4X4=5 –> number of tilted squares in 3X3 + square (2) = 1 + 4= 5
5X5=14–> number of tilted squares in 4X4 + square (3)= 5 + 9= 14
6X6=30–> ……………………. in 5X5 + square(4)= 14 + 16 = 30
and so on………..
its like you lose 2 dimensions….. so the formula for an 8X8 square will be:
square(1)+square(2)+square(3) +square(4)+square(5)+square(6)=1+4+9+16+25+36 = 91 tilted squares
so the total number position of checkers without importance in the order between checkers, like checkers 1,2,3,4… because they are identical is 231, I think, cool!!!….
Answer = 336.
With some hit and trial, I got following formula to calculate the number of ways to arrange 4 checkers:
Number of ways = [ N * N * { ( N * N ) - 1 } ] / 12, where N = number of rows in a checker board (it is assumed to be a square board).
Putting N = 8, we get number of ways = [ 8 * 8 * { ( 8 * 8 ) - 1 } ] / 12
= [ 64 * { 64 - 1 } ] / 12
= [ 64 * 63 ] / 12
= 4032 / 12
= 336
Either this one was more difficult than I anticipated, or that many of you were “checkerboarded out” by the end.
I, too, came up with 336 arrangements for an 8×8 checkerboard, and I agree with the formula that munna posted for the general NxN board (My hat goes off to you – well done). Here’s how I came up with my results:
Each square, tilted or not, can be considered “bounded” by a regular, untilted square. For example, the arrangement in the diagram is bounded by the 6×6 square in the upper left hand corner of the board. Each regular square (larger than 1×1) bounds itself, and possibly other tilted squares.
There are 49 different 2×2 squares, and each one bounds exactly 1 square (itself).
There are 36 different 3×3 squares, and each one bounds exactly 2 squares (itself, and one tilted at 45 degrees).
There are 25 different 4×4 squares, and each one bounds exactly 3 squares (itself and two different tilted squares).
In general, the number of QxQ squares is (9-Q)^2 (or (N+1-Q)^2 in the general case). Each QxQ square bounds itself and exactly Q-2 tilted squares. The tilted squares correspond one-to-one with the unit squares in the top row of the QxQ square, excluding the corner squares.
Putting this to work for an 8×8 checkerboard, we have:
(7^2)*1 + (6^2)*2 + (5^2)*3 + (4^2)*4 + (3^2)*5 + (2^2)*6 + (1^2)*7 = 336.
For a general NxN, it’s
sum(i*(N-i)^2) for i=1 to N-1
And I confirmed that the formula (N^2 * (N^2)-1)/12 does calculate this sum correctly.
Thanks to everyone who participated and, hopefully, enjoyed the series.
I saw my mistake, man I never complete accurately what I do, thats a problem, a hat to both of you who found it in a formula man, incredibly, my approach was more visual and I failed to pass it to a decent mathematical version however I found my error:
My approach is a lot different to yours, however it yields the same solution:
Taking from my last explanation:
Normal Squares that can fit 4 checkers: 140… that was easy.
Tilted Squares :
the error in my explanation was that I did not acummulate the tilted squares that were different, I was counting the different tilted squares in each dimension so it was accumulative, man sooooo dumb … wow …
so: 1X1=0, 2X2=0, 3X3=1, 4X4= 5, 5X5= tilted squares in 4X4 + square(3)=14
6X6= tilted squares in 5X5 + square(4)=30, 7X7= tilted squares in 6X6 + square(5)= 55
8X8= tilted squares in 7X7 + square(6)= 91
now all tilted squares in the 8X8 are: 0+0+1+5+14+30+55+91= 196 tilted squares
TOTAL SQUARES: 140 + 196= 336
Now I would have post it again if I was not complety sure that this method was completely different to the one used, with that being said…
@BobotheBear: please give your feedback to my solution, do you found it valid or faulty, in less words do I have your blessing in my solution… cool man.. very nice puzzle by the way.
This was a very nice series and I am glad to be a part of this Checkboard Trilogy. I frequently look for puzzles in this website and I have noticed that puzzles from Bobo The Bear are really hard to solve (especially The Involuting Goat).
My approach was little different. What I did was to find out all possible (and unique) ways to place first two points (A & B) of a square ABCD on the board, so that the square ABCD remains within the 8 * 8 Checkerboard.
Following this approach I found that there are:
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 squares when both points A & B are in row 1
6 + 5 + 4 + 3 + 2 + 1 = 21 squares when point A is in row 2 and point B is in row 1
6 + 6 + 5 + 4 + 3 + 2 + 1 = 27 squares when both points A & B are in row 2
5 + 4 + 3 + 2 + 1 = 15 squares when point A is in row 3 and point B is in row 1
5 + 5 + 4 + 3 + 2 + 1 = 20 squares when point A is in row 3 and point B is in row 2
5 + 5 + 5 + 4 + 3 + 2 + 1 = 25 squares when both points A & B are in row 3
and so on…
I found a patter in this series for general N x N board. Solving the patter I found that the total number of ways to arrange 4 checkers is:
Sum of [(N – i) * N * i] / 2 for i = 1 to N – 1
Solving above summation, I found the following formula that I posted in my first post:
Number of ways = [N^2 * (N^2 – 1)] / 12
Taking this a little further, I found a general formula for a rectangular Checker board:
Number of ways = [C * (2R – C) * (C^2 – 1)] / 12 provided R >= C
Here R = Number of rows; and C = Number of columns
Putting R = C = N, you will get general formula for square N x N board mentioned above.
I hope I was able to explain my approach. This was a great series, I enjoyed it and look forward for more.
The Involuting Goat puzzle was posted by Bilbao. Please ignore the part in my last post where I mentioned Bobo The Bear instead of Bilbao.
@suineg and @munna: It’s great to see multiple valid approaches that all converge to provide the same resolution to a problem. I think you both did a great job in seeing and solving the problem in your individual ways. And thank you both for your words of encouragement – it’s always good to hear when one’s contributions are sincerely appreciated. Thank you!
I noticed that I erred in my order of operations when I (incorrectly) presented Munna’s formula as (N^2 * (N^2)-1)/12. He’s correct that it should be [N^2 * (N^2 – 1)]/12 instead. And very well done with extending the soluiton to rectangular boards as well. Wow!