Count 'em All 11!

Count the total number of quadrilaterals in the irregular grid above.

Clarifications:

  • Quadrilateral is a polygon that has 4 sides.

This is one part of Quadrilatorics .


The answer is 13746.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Kenneth Tan
Jan 26, 2017

Let's fill in the holes so that it becomes a perfectly rectangular grid.

From this note , we know that the number of quadrilaterals in a 17 × 18 17\times 18 grid is ( 18 2 ) × ( 19 2 ) = 17 × 18 × 18 × 19 4 = 26163 {18\choose2}\times{19\choose2}=\frac{17\times18\times18\times19}{4}=26163

Now we need to remove the quadrilaterals that are not part of the original grid. To do this, let's split it into 3 cases:

Case 1: Quadrilaterals with its top-left corner in region A and its bottom-right corner in region B

This is trivial, all we need to do is first choose the top-left corner in A, there are 5 × 8 = 40 5\times8=40 ways to do so, then we choose the bottom-right corner in B, there are 6 × 3 = 18 6\times3=18 ways to do so.

Hence the number of quadrilaterals with its top-left corner in region A and its bottom-right corner in region B is 40 × 18 = 720 40\times18=720

Case 2: Quadrilaterals with its top-left corner in region A but its bottom-right corner not in region B

Suppose we choose the top-left corner of the quadrilateral i i units away from the left boundary of the whole grid and j j units away from the top boundary of the whole grid.

Then, the number of ways of choosing the bottom-right corner of the quadrilateral (excluding those lying in region B) is ( 17 i ) ( 18 j ) 6 × 3 (17-i)(18-j)-6\times3 .

Thus, the total number of quadrilaterals with its top-left corner in region A but its bottom-right corner not in region B is j = 0 7 i = 0 4 [ ( 17 i ) ( 18 j ) 18 ] = j = 0 7 i = 0 4 [ ( j 18 ) i 17 j + 288 ] = j = 0 7 [ 4 × 5 2 ( j 18 ) 5 ( 17 j 288 ) ] = j = 0 7 ( 10 j 180 85 j + 1440 ) = j = 0 7 ( 1260 75 j ) = 7980 \begin{aligned} &\displaystyle \sum_{j=0}^{7}\sum_{i=0}^{4}[(17-i)(18-j)-18] \\&=\sum_{j=0}^{7}\sum_{i=0}^{4}[(j-18)i-17j+288] \\&=\sum_{j=0}^{7}\left[\frac{4\times5}{2}(j-18)-5(17j-288)\right] \\&=\sum_{j=0}^{7}(10j-180-85j+1440) \\&=\sum_{j=0}^{7}(1260-75j) \\&=7980 \end{aligned}

Case 3: Quadrilaterals with its top-left corner not in region A but its bottom-right corner in region B

Similarly, suppose we choose the bottom-right corner of the quadrilateral i i units away from the right boundary of the whole grid and j j units away from the bottom boundary of the whole grid.

Then, the number of ways of choosing the top-left corner of the quadrilateral (excluding those lying in region A) is ( 17 i ) ( 18 j ) 5 × 8 (17-i)(18-j)-5\times8 .

Thus, the total number of quadrilaterals with its top-left corner not in region A but its bottom-right corner in region B is j = 0 2 i = 0 5 [ ( 17 i ) ( 18 j ) 40 ] = j = 0 2 i = 0 5 [ ( j 18 ) i 17 j + 266 ] = j = 0 2 [ 5 × 6 2 ( j 18 ) 6 ( 17 j 266 ) ] = j = 0 2 ( 15 j 270 102 j + 1596 ) = j = 0 2 ( 1324 87 j ) = 3717 \begin{aligned} &\displaystyle \sum_{j=0}^{2}\sum_{i=0}^{5}[(17-i)(18-j)-40] \\&=\sum_{j=0}^{2}\sum_{i=0}^{5}[(j-18)i-17j+266] \\&=\sum_{j=0}^{2}\left[\frac{5\times6}{2}(j-18)-6(17j-266)\right] \\&=\sum_{j=0}^{2}(15j-270-102j+1596) \\&=\sum_{j=0}^{2}(1324-87j) \\&=3717 \end{aligned}


Therefore, the number of quadrilaterals in the original grid is 26163 720 7980 3717 = 13746 26163-720-7980-3717=13746 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...