How many ways are there to select 5 squares from a 1 0 × 1 0 grid, such that no 2 squares are in the same row or column?
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.
Great explanation. Clearly written and presented.
Right!! Exactly :)
I doubt 100 choice for first. As we do not have a reference point( like in a circular permutation ) for first, so we first place it randomly and then other have choice w.r.t. to it.
Correct me if I'm wrong...
The goal of the solution is to find how many sets of 5 points A ( x 1 , y 1 ) , B ( x 2 , y 2 ) , C ( x 3 , y 3 ) , D ( x 4 , y 4 ) and E ( x 5 , y 5 ) there are, which satisfy x i < x j , y i = y j and 1 ≤ x i , y i ≤ 1 0 for all integers 1 ≤ i < j ≤ 5 .
How many ways to choose x − values are there? It's C 1 0 5 .
And how many ways to choose y − values are there? Careful! It's P 1 0 5 , not C 1 0 5 . 'Cause for y , group ( 1 ; 2 ; 3 ; 4 ; 5 ) is different from group ( 2 ; 3 ; 4 ; 5 ; 1 ) , but for x , it's the same.
Number of ways: C 1 0 5 × P 1 0 5 = 7 6 2 0 4 8 0 .
Note: Generalising, the number of ways to choose k points in a m × n grid such that no 2 squares are in same row or column, and k ≤ min(m,n) is C m k × P n k
Right!! Nice one!!
Ans is 100 * 81 * 64 * 49 * 36 / 5!
I got that it was the product of those 5 squares but why divide by 5?
Log in to reply
Divide by 5 factorial......if your 1st combination is PQRST....it is same as QPRTS,QRTPS,RTQPSetc
Problem Loading...
Note Loading...
Set Loading...
We have five squares to choose:
The first square to choose has 1 0 0 ways.
Now, consider a randomly chosen square. The second one should not belong to first's row and column, so we can neglect from the 1 0 0 ways, 1 9 ways (The shaded squares), Having ( 1 0 0 − 1 9 ) ways for the second.
For the third square to be chosen, we should neglect the shaded rows and columns of each of the two previously chosen squares, but taking into consideration that the shaded areas will meet at 2 squares, thus, leaving us with ( 1 0 0 − 1 9 − 1 9 + 2 ) ways for the third.
The walkthrough now is obvious: The shaded rows and columns of the third chosen square will meet the other shadings in 4 squares, leaving us with ( 1 0 0 − 1 9 − 1 9 + 2 − 1 9 + 4 ) ways for the fourth.
The shadings of the fourth chosen square will meet the other shadings in 6 squares, leaving us with ( 1 0 0 − 1 9 − 1 9 + 2 − 1 9 + 4 − 1 9 + 6 ) ways for the Fifth.
Therefore the number of ways to choose the five squares is: ( 1 0 0 ) ( 8 1 ) ( 6 4 ) ( 4 9 ) ( 3 6 ) = 9 1 4 4 5 7 6 0 0 .
But this number of ways counts repeated possibilities, thus divide by 5 ! to get the correct answer:
9 1 4 4 5 7 6 0 0 / 5 ! = 7 6 2 0 4 8 0