0
$\begingroup$

Say I roll up a square chessboard into a cylinder. How many rectangles, if finite, will it have? Provided that no lateral sides of the rectangle must overlap (so you can't basically go round and round and over and over the same rectangle by completing rotations). i.e. you may start and end a rectangle anywhere, but not overlap it over itself. (Top and bottom of a rectangle may, however, overlap). Can you generalise this for any rectangular grid m×n rolled up into a cylinder?

$\endgroup$
4
  • $\begingroup$ If you know the number of rectangles on the cylinder up to rotation, then you may multiply the result by $n$, to get the total, isn't it? $\endgroup$ – Surb Oct 11 '19 at 9:44
  • $\begingroup$ It is not that simple. Consider all units rectangles, you will count them multiple times if you multiply the number of rectangles up to the number of rotations available. @Surb $\endgroup$ – nicomezi Oct 11 '19 at 9:45
  • $\begingroup$ Let's say you have a rectangle of height one in the direction that doesn't wrap around. It starts at the 4th square on the top row and wraps around to the 3rd square. This occupies the same squares as the rectangle that starts at the top left position and moves around to the top right (if the cylinder is unfurled). Are these counted as 2 rectangles, even though they occupy the same squares? $\endgroup$ – stuart stevenson Oct 11 '19 at 9:56
  • $\begingroup$ Thank you for clarification. $\endgroup$ – nicomezi Oct 11 '19 at 10:50
2
$\begingroup$

I am assuming that rectangles that occupy the same squares are different here.

You can handle the height and length of the rectangles independently.

You can pick any 2 rows (non-wrapped dimension) and have these be the top and bottom of the rectangle. If the top row is the first row of the board, then there are $8$ choices for the bottom row. If the top row is the second, then there are $7$ choices for the bottom. Therefore we get $8 + 7 +...+1 = 36$ choices for those pairs.

For the other dimension, we are not so limited. The start and end of the rectangle can be at any column so there is just $8 \times 8 = 64$ possibilities.

$36 \times 64 = 2304$ rectangles

$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Daniel Fischer Oct 11 '19 at 12:14
  • $\begingroup$ And moderators are here to discuss with people having a bad understanding of the behavior they are expected to have on this site. Not just to remove extended chats in comments. @DanielFischer $\endgroup$ – nicomezi Oct 11 '19 at 13:43
1
$\begingroup$

Let a chessboard of size $M \times N$.

Suppose we roll it as a cylinder so it has a width of $N$. You have $N$ cases from one boundary to the other and $M$ for a whole circle around it.

Consider all the rectangles with width $n$. We count all the possibilities starting from one side of the cylinder. We can chose $M$ unit height rectangle, $m=1$, but $M$ rectangles also for $m \in\{2,\dots,M\}$ (just take one and rotate it around till your reach the first one again). This can be done till we reach the $(N+1-n)$-th line.

Then the number of rectangles with height $n$ is then $$(N+1-n)M^2=(N+1-n)M^2.$$

Then the total number of rectangle is :

$$\sum_{n=1}^N (N+1-n)M^2 = M(M-1)\sum_{n=1}^N (N+1-n)=M^2\frac{(N+1)N}{2}$$

The last formula is due to the fact that $\sum_{n=1}^N (N+1-n)$ is the sum of $n$ terms of an arithmetic sequence.

So the number of rectangles is : $\frac 1 2 M^2(N+1)N$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.