How many non-degenerate rectangles are there of the form (a lessthanorequalto x

Question

How many non-degenerate rectangles are there of the form (a lessthanorequalto x lessthanorequalto b) A (c lessthanorequalto y lessthanorequalto d) where a, b, c and d are integers between (and including) 0 and 99? This problem is trickier than it looks (and therefore worth a significant amount of points). You will need to think hard about your solution and very clearly explain your line of reasoning in your submitted solutions. Here are some hints i. Find a formula that's simple but possibly over-counts some rectangles or counts degenerates. ii. Remove the over-counts from the original formula. iii. Remove the degenerates from the what remains. iv. Check your formula for a, b, c, d between 0 to 3 by drawing a picture and counting by hand.

Explanation / Answer

Solution:-

i) There are total 100 values of x (0 to 99) and 100 values of y (0 to 99). So, in total there are 100 * 100 = 10,000 rectangles.

ii) Now, we can simply reject the rectangles with any of the dimnesion 0. So, any rectangle with x = 0 or y = 0 will be degenerate. So, for non-degenerate rectangles, we are left with 99 values of x and 99 values of y.

Ans = 99 * 99 = 9801

iii) Now we can remove duplicate rectangles. Rectangles (1,2) and (2,1) are same. So, we need to remove these duplicates. For x = 1, there are 99 values of y.

For x = 2, there are 98 values of y.

For x = n, there are 100-n values of y.

So, summing up, we get answer = 99 + 98 + 97 + ..... + 1 = 4950

iv) So, applying our formula here, we get 3*(3+1)/2 = 6

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.