Math Is Fun Forum

Catone

Guest

combinatorial analysis problem

hello everyone

i have a test on this subject soon and i just can't figure out this excercise:

"How many rectangles can be formed out of the field lines of a 8x8 field chess board?"

The answer is 1296 but I have no idea how to get there.

Thank you in advance!

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: combinatorial analysis problem

Hint: Every rectangle is uniquely determined by choosing 2 row lines and 2 column lines.

Catone

Guest

Re: combinatorial analysis problem

ugh! you're killing me! i really am at my wits end...

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: combinatorial analysis problem

Consider the vertical/horizontal lines that separate the colums/rows. There are 9 vertical lines and 9 horizontal lines. In order to form a rectangle, you need to choose 2 vertical lines and 2 horizontal lines. How many ways are there of choosing 2 lines from 9? How can you therefore find the number of unique rectangles?

Catone

Guest

Re: combinatorial analysis problem

heureka!

is this way of doing it correct?:

we have 36 possibilites to choose two lines per direction (horizontal/vertical) -> since there are two directions we multiply 36 x 36 and get 1296?

please elaborate!

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: combinatorial analysis problem

Yes, that's right

There are 36 ways of choosing a pair of vertical lines, and 36 ways of choosing a pair of horizontal lines. Each pair of vertical lines can be matched with each pair of horizontal lines: the first pair of vertical lines can match with 36 pairs of horizontal lines, the second pair of vertical lines can match with 36 pairs of horizontal lines... the 36th pair of vertical lines can match with 36 pairs of horizontal lines, which gives a total of 36*36 matchings.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: combinatorial analysis problem

My way is to count the number of

rectangles (including squares) on the board for each

, where

is the number of rows and

the number of coliumns making up the rectangle.

If you put the

rectangle on the top-left corner of the board, you can shift it downwards

times and rightwards

times. Hence the number of

rectangles on the board is

.

Thus the total number of rectangles is

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: combinatorial analysis problem

For the related problem with squares instead of rectangles, it turns out that the number of squares visible on an n×n square grid is

For a 3×3 grid in particular, the answer is 14. This actually came up in the final of University Challenge 2009–10, shown on Easter Monday. One idiot contestant actually buzzed with the ridiculous answer 6. I hate idiots!!