When to be sure that we have counted all the squares in such problems

Question

My first question: how would one solve such problems (in general)? What should be the general technique?

My second question: When to be sure that we have counted all the squares in such problems?

Answer 1

You need to find some systematic technique. The technique will depend on the problem. Usually there is a regularity to the problem that you can exploit. In this case, I would note that the two squares that are not part of the main $4 \times 4$ do not interact with the lattice, so we can count them separately. For the lattice, work by square size.

You have four choices along each edge for the upper left corner of a $1 \times 1$ square for

$16$ in total.

Similarly there are

$9\ 2 \times 2$ squares, $4\ 3 \times 3$ squares and $1\ 4 \times 4$ for a total of $30$.
You might even know that in an $n \times n$ chessboard there are $\sum_{i=1}^ni^2=\frac 16n(n+1)(2n+1)$ squares.

Each of the stray squares gives us five, for a total

$40$.

Answer 2

Systematic technique is definitely required. I came across this particular puzzle a few years ago on facebook and got into arguments with some people about the answer, with them arguing that there were

41, 42

or even more squares. Eventually I got bored, produced this animation

which shows 40 different squares, and challenged them to show me one that I'd not highlighted.

The general case would be similar - find the recurring pattern, and count them methodically.

As to knowing if you've "found them all", that's just down to being rigorous and methodical in your search. This can get difficult if the puzzle is particularly complex or large, but if the answer is in the realms of "easily countable" as it is in this case then this is easily verified manually.

Answer 3

One potential strategy is as follows:

Call this example an square of dimentions 8x8

1. Start from an extreme corner of the diagram. (example: top left corner)
2. Iterate across the board in such a way as to cover the entire board (example: move down 8 units, right 1 unit, up 8 units, right 1 unit and repeat)
3. Each time you reach previously chosen corner type count the number of possible opposite corners and ensure that they all make a square. (exampe: Each time one sees a "bottom left" corner, draw a line segment of slope 1 towards the top right. Count the number of "top right" corners that this line intersects. Eliminate from this count any corner pairs that have broken sides.)
4. Continue until the entire map is covered and all squares counted.

By this strategy I get:

40 squares

Answer 4

Of course I agree that being systematic is helpful for this sort of puzzle, but I take the original questioner to have been asking also for help with how to be systematic: how to make sure you haven't somehow missed a square. Here is one suggestion, which applies best to cases (like this one) where all the squares have to have the same orientation because of a grid of lines already present in the image.

A square is then determined by its top left corner and its size. So, when you find a square, draw a line on the diagram running from the top left corner to (let's say) somewhere a little down from the top right corner. Now, when you think you have found them all, you can go back and (e.g.) at each available vertex -- each point that could be the top left corner of a square -- check that you have drawn all possible such lines.

Answer 5

Another strategy would be as follows:

1. How many 1x1 squares can we have, ignoring the smaller squares? 4 rows of 4 --> 16
2. How many 2x2 squares can we have, ignoring the smaller squares? 3 rows of 3 --> 9
3. How many 3x3? 2 rows of 2 --> 4
4. How many 4x4? 1 --> 1

This gives us (16+9+4+1)=30 squares.

Now add in the smaller squares:

1. How many 1x1 can we have? 8
2. How many 2x2? 2

This gives us 10 more squares. Add those answers and we get 40.

Answer 6

I believe the 98% get it wrong because of the fact that the question itself is a square. They count the 40 squares created by the green lines, but they miss the pink square. @ClickRick, I believe those that say 42 are correct: the pink area makes 41, the embossed rim would make 42. However, if you wanted to go further, you could note that the background is two different colors; pink and purple, slightly different tones. I count at least 13 purple squares in the background, and at least 2 pink ones. The problem is that the rules are not clearly defined; 40 is correct from a basic standpoint, looking at only the green lines. However, since 98 percent get it wrong, and it is a puzzle after all, I must believe that the squares that exist outside of the line are meant to be counted. My guess is that a large portion of the 98 percent probably say 40. In your simulation, there are only 40. But I believe that there is some reason for the pink background, rather than a plain white one - to complicate things, creating additional inconspicuous squares.

Answer 7

If I have interpreted the question properly, you are asking:

After counting the obvious $40$ squares, how do I convince myself that there are no others?

We can (hopefully) ignore the 'trick' aspects such as the surrounding box - the puzzle might have been hosted on a page containing lots of squares as decoration, and questions that expect this as an answer are misleading.

So we are left with 'how do I know that is it?' My solution is to stare at a puzzle until I become convinced that this is the case. This might take hours, or only minutes. Remove all the squares you have accounted for - what is left? Where might any other squares be? Eventually you can make yourself believe that $40$ is the actual answer, and your search is complete.

Answer 8

Answer to question 1 and 2: Use brute force, that means test all possible combinations.

You will need a definition to check if a point exists and if a line exists.

In Pseudocode that looks something like this:

function get_square_count()
    counter = 0
    for each a in corners:
        for each b in corners:
            //same height level and b right of a
            if a.x=b.x and a.y<b.y:
                if is_square_top_line(a,b):
                    counter++
    return counter

function is_square_top_line(a,b)
    // use square property to add height 
    calculate virtual points c,d
    check if c and d exist
    check if all lines exists a,b b,c c,d, d,a