Four players are playing a game involving choosing $1\times1$ squares on a grid of size $3 \times 8$ . Each player chooses a random square on the grid, then all players reveal their choices and a token is placed in the center of each of these squares. The probability that the tokens form the vertices of a non-degenerate rectangle can be expressed as $\frac{a}{b}$ where $a$ and $b$ are coprime positive integers. What is the value of $a + b?$
Details and assumptions
Players are allowed to have selected the same squares. There is no restriction on their choices.
A
degenerate
rectangle has 0 area.
Squares are rectangles.
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.
Do you understand where there are ${8 \choose 2} \times {3 \choose 2}$ 'upright' rectangles in the grid?
Most students missed out the 'slanted unit squares', since they are used to the problem being only involving 'upright' rectangles. This version gets much harder as you increase the dimensions of the board.
The cardinality of the sample space is $24^4$ , since there are 24 squares and the players choose squares independently. Now we find the number of non-degenerate rectangles.
Firstly, we count the number of non-degenerate rectangles such that their sides parallel with the grid. Each rectangle is defined by 3 squares : top left, top right and bottom left. Since the rectangle is non-degenerate, the top left square takes place in the first 7 columns and the first 2 rows. Now we consider 2 small cases :
The top left square takes place in the first column : If it lies in the $i$ -th column ( $i=\overline{1,7}$ ), then the top right square can be choosed in one of the next $8-i$ squares of the same row. On the other hand, the bottom left square can be choose in one of the last two rows of the same column with the top left square. Therefore, there are $2 \times (7+6+\cdots+1)=56$ cases.
The top left square takes place in the second column. By similar arguments as above, we have $28$ cases possible.
If the side of the rectangle are not parallel to the sides of the grid, it can only be formed by choosing 4 squares forming a cross, for example, the squares with coordinates : $(1,2), (2,1), (2,3), (3,2)$ . There are 6 rectangles at all.
Therefore, there are totally 90 non-degenerate rectangles. We must count the permutation of 4 vertices. Hence, the probability that the tokens form the vertices of a non-degenerate rectangle is $\frac{90 \times 4!}{24^4} = \frac{5}{768}$ . Then the answer is $5+768=773$ .
Considering that the vertices of the rectangle are the tokens, precisely we can use the center of the token to avoid confusion. Since the target rectangle must not be degenerate then the smallest grid size for the rectangle is the $2 \times 2$ grid, while the largest one would be the whole $3 \times 8$ grid.
There are 14 $2 \times 2$ grid. There are 7 $3 \times 2$ grid. There are 12 $2 \times 3$ grid. There are 6 $3 \times 3$ grid. There are 10 $2 \times 4$ grid. There are 5 $3 \times 4$ grid. There are 8 $2 \times 5$ grid. There are 4 $3 \times 5$ grid. There are 6 $2 \times 6$ grid. There are 3 $3 \times 6$ grid. There are 4 $2 \times 7$ grid. There are 2 $3 \times 7$ grid. There are 2 $2 \times 8$ grid. There are 1 $3 \times 8$ grid.
Thus there are $84$ possible rectangles whose sides are parallel to the grid lines.
Now, we consider those rectangle whose sides are not parallel to the grid lines.
Connecting the tokens' center with lines parallel to the original grid lines, we form a new $2 \times 7$ grid.
With careful analysis of the new grid, we can see that the only possible slope for the oblique rectangle(with respect to the grid lines) is $1$ and $-1$ . Specifically we can form 6 other rectangles for this size.
All in all we have $90$ rectangles using the tokens as the vertices. We also get another factor which is $24 = 4!$ for the choice of 4 persons of the vertices of the rectangle.
For the universal set of choice of the square we got $24 ^ 4$ .
Thus the that the tokens form the vertices of a non-degenerate rectangle $= \frac{ expected events }{ total number of events} = \frac{90 \times 24}{24 \times 24 \times 24 \times 24} = \frac{90}{24 \times 24 \times 24} = \frac{5}{3 \times 2^8}$
Thus $a = 5$ and $b = 768$ and $a + b = 5 + 768 =773$
We first calculate the total number of possible choices by the $4$ players. There are $24$ total squares to choose from, and so we find that there are $24^4$ possible choices for the placement of the $4$ tokens. However, the tokens are indistinguishable, so we must divide out $4! = 24$ and get that there are $24^4$ valid positions.
We now calculate the number of ways to create a rectangle using the four tokens. If the rectangle's sides are parallel to the edges of the grid, then there are $\binom{3}{2} = 3$ ways to pick the two rows that will contain two tokens each and $\binom{8}{2} = 28$ for the two columns which contains two tokens each. Thus, there are $3 \cdot 28 = 84$ such rectangles. If the sides are not parallel to the edges, we have very limited options. In fact, the rectangle must be a square with its diagonals parallel to the edges of the grid. There are clearly only $8$ such rectangles. This gives us a total of $90$ rectangles.
Finally, we calculate the desired probability: $\frac{90}{24^3} = \frac{5}{768} \to a + b = \fbox{773}$ .
I think it would make more sense to say there's $90 \cdot 4!$ ways that they'll make a rectangle, and then divide that by $24^4$ .
Sorry, typo in the last sentence of the first paragraph. It should say " $24^3$ valid positions."
i think there are only 6 rectangles whose sides aren't parallel to the edges. typo?
Log in to reply
Yes, thanks for catching that.
there are 7 rectangles
Can you explain why a rectangle with sides not parallel to the grid must be a square?
Log in to reply
Simply consider the "slopes" of the edges of the rectangle. Unless the edge goes vertically or horizontally, it must have a slope of either $1$ or $-1$ . This is easy to check but much harder to explain rigorously. Essentially, any other slope will lead to vertices that are outside the grid, since all angles must be right.
Oops, I missed the case when sides are not parallel to the edges.
u directly divided by 4! , but that would not be true cause , in case of 2 tokens in same box and other 2 in different u have to divide by 3!, and similarly different for different cases
The first step is to count the possible rectangles. Starting with rectangles with sides parallel to the sides of the board and one unit "tall", there are 14 of the smallest rectangles (1x1), 12 of 1x2, 10 of 1x3, 8 of 1x4, 6 of 1x5, 4 of 1x6, and 2 of 1x7. Next, counting the rectangles two units tall, there are 7 of 2x1, 6 of 2x2, 5 of 2x3, 4 of 2x4, 3 of 2x5, 2 of 2x6, and 1 of 2x7. Lastly, there are 6 squares at a 45^\circ angle to the sides of the board. That's 90 total. There are 24 ways each of these rectangles can be created (4 players, each with their token). There are a total of 90 \cdot 24 ways to make a rectangle.
Since each player can place their token anywhere, there are 24^4 ways to place all four tokens on the board. \frac{90 \cdot 24}{24^4} reduces to \frac{5}{768}. 5 + 768 = 773
Probability is the number of desirable outcomes divided by the total number of outcomes possible. The desirable outcomes are rectangles, which consist of two pairs of parallel sides. If you equate a column or row of the grid to a side, you can find the total number of rectangles with sides parallel to the grid rows by choosing 2 rows out of 3= ${6 \choose 3}$ . You multiply this by the number of pairs of columns you can choose out of 8 columns= ${8 \choose 3}$ . This gives you 84 rectangles with sides parallel to the grid, but you also have to consider those rotated rectangles. You will quickly find that the only rectangle that will fit is the square with sides $\sqrt{2}$ (because the rest of the quadrilaterals will not have sides that are perpendicular). There are 6 such rectangles. 84+6=90 total rectangles disregarding which player picked which point. Since there are 4 players, the points can be arranged in 4! ways resulting in a total of 2160 nondegenerate rectangles with 4 distinct points(representing the 4 players). Now, the number of total possible ways the 4 points were chosen is $24^{4}$ , since there are 24 choices for each of the 4 players. The final probability would then be $\frac{90\times4!}{24^4}$ , which reduces to $\frac{5}{768}=\frac{a}{b}$ , so $a + b=773$ .
Calvin L is my fake name....problem??? :)
Problem Loading...
Note Loading...
Set Loading...
in finding the number of non-degenerate rectangle in a $3 \times 8$ grid, the formula is $C(8,2)*C(3,2)$ for rectangles which are parallel to the sides of the grid while there is $6$ squares which are not parallel to the sides of the grid but still they are non-degenerate rectangle so we add it together
so we will have a formula of $C(8,2)*C(3,2) + 6$ but there are four players so we must multiply the whole formula by $4!$
so in finding the probability, we divide the whole formula by the ways the 4 player can pick a square in the grid, or $24 \times 24 \times 24 \times 24 = 24^4$ so the Probability is $\frac{(C(8,2)*C(3,2) + 6)*4!}{24^4} = \frac{5}{768} = \frac{a}{b}$ so $a+b = 5 + 768 = 773$