Results 1 to 2 of 2

Math Help - A 'squareish' question

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    A 'squareish' question

    Hi everyone. So I have a question here. Find the number of squares contained in an n x n square array, where n is larger or equal to 2.

    Ok so my solution: For 1x1 Square array, no of squares=1

    Then keep on doing till a pattern is formed, which is r squared.

    However, when I flipped to the solutions, they proposed an alternative method which I do not understand. They examined 2 x 2 squares and noted that the bottom-left hand corner of each square is unique. If you consider the (n x n) array as (n+1)(n+1) grid (why????) with both x and y coordinates such that x=0,1,2,.....,n-2 (????) repeat for y. The number of points equals (n-1)(n-1) (????)and this the number of 2x2 squares is (n-1)(n-1).

    More generally, number of r x r squares is (n-r+1)(n-r+1).

    Actually I dont really understand the method which the book wrote and had trouble visualizing it. Any helps?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by qazxsw11111 View Post
    Hi everyone. So I have a question here. Find the number of squares contained in an n x n square array, where n is larger or equal to 2.

    Ok so my solution: For 1x1 Square array, no of squares=1

    Then keep on doing till a pattern is formed, which is r squared.

    However, when I flipped to the solutions, they proposed an alternative method which I do not understand. They examined 2 x 2 squares and noted that the bottom-left hand corner of each square is unique. If you consider the (n x n) array as (n+1)(n+1) grid (why????) with both x and y coordinates such that x=0,1,2,.....,n-2 (????) repeat for y. The number of points equals (n-1)(n-1) (????)and this the number of 2x2 squares is (n-1)(n-1).

    More generally, number of r x r squares is (n-r+1)(n-r+1).

    Actually I dont really understand the method which the book wrote and had trouble visualizing it. Any helps?

    Thanks.
    Suppose you know the number of squares N(n) formed on an nxn array now add a border one square wide around the top and right hand edges to give an (n+1)x(n+1) array.

    Every square on the (n+1)x(n+1) array is either a square on the nxn array or has a corner on the border just added. Count these new squares C(n+1) with a corner on the border, and that will give you a recurrence:

    N(n+1)=N(n)+C(n+1)

    which you solve.

    CB
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum