Rooks on a Chessboard

Today, we’re going to do a fun
problem called rooks on a chessboard. And rooks on a chessboard is a
problem that’s going to test your ability on counting. So hopefully by now in class,
you’ve learned a few tricks to approach counting problems. You’ve learned about
permutations, you’ve learned about k-permutations, you’ve
learned about combinations, and you’ve learned
about partitions. And historically for students
that we’ve taught in the past and many people, counting
can be a tricky topic. So this is just one drill
problem to help you get those skills under your belt. So what does the rooks on a
chessboard problem ask you? Well, you’re given an 8-by-8
chessboard, which I’ve tried to draw here. It’s not very symmetrical. Sorry about that. And you’re told that you
have eight rooks. I’m sure most of you guys
are familiar with chess. But if any of you aren’t,
chess is a sophisticated board game. And one of the types of pieces
you have in this game is called a rook. And in this particular problem, there are eight rooks. And your job is to place all
eight rooks onto this 8-by-8 chessboard. Now, you’re told in the problem
statement that all placements of rooks are
equally likely. And you are tasked with finding
the probability that you get a safe arrangement. So that is to say, you place
your eight rooks on the board. What is the probability
that the way you placed them is safe? So what do I mean by “safe”? Well, if you’re familiar with
the way chess works, so if you place a rook here, it can move
vertically or it can move horizontally. Those are the only two
legal positions. So if you place a rook here
and you have another piece here, then this is not a safe
arrangement, because the rook can move this way
and kill you. Similarly, if you have a rook
here and another piece here, the rook can move horizontally
and kill you that way. So two rooks on this board are
only safe from each other if they are neither in the same
column nor in the same row. And that’s going to be key for
us to solve this problem. So let’s see– where
did my marker go? I’ve been talking a lot,
and I haven’t really been writing anything. So our job is again, to find the
probability that you get a safe arrangement. So I’m just going to do
previously, and you guys have heard it in lecture. Hopefully you remember something
called the discrete uniform law. So the discrete uniform law is
applicable when your sample space is discrete and all
outcomes are equally likely. So let’s do a quick
check here. What is our sample space
for this problem? Well, a logical choice would
be that the set of all possible outcomes is the set
of all possible spatial arrangements of rooks. And hopefully it’s clear to
you that that is discrete. And the problem statement
furthermore gives us that they’re equally likely. So the discrete uniform
law is in fact applicable in our setting. So I’m going to go ahead and
write what this means. So when your sample space is
discrete and all outcomes are equally likely, then you can
compute the probability of any event, A, simply by counting
the number of outcomes in A and then dividing it by the
total number of outcomes in your sample space. So here we just have to find
the number of total safe arrangements and then divide
it by the total number of arrangements. So again, as you’ve seen in
other problems, the discrete uniform law is really nice,
because you reduce the problem of computing probabilities to
the problem of counting. And so here’s where we’re
going to exercise those counting skills, as I
promised earlier. Now, I would like to start
with computing the denominator, or the total
number of arrangements, because I think it’s a slightly
easier computation. So we don’t care about the
arrangements being safe. We just care about
how many possible arrangements are there. Now, again, we have eight rooks,
and we need to place all of them. And we have this 8-by-8 board. So pretty quickly, you guys
could probably tell me that the total number of square
is 64, because this is just 8 times 8. Now, I like to approach
problems sequentially. That sort of really helps me
think clearly about them. So I want you to imagine a
sequential process during which we place each rook
one at a time. So pick a rook. The chessboard is
currently empty. So how many squares can you
place that rook in? Well, nobody’s on the board. You can place it in 64 spots. So for the first rook that you
pick, there are 64 spots. Now, once you place this rook,
you need to place the second rook, because again, we’re
not done until all eight are placed. So how many possible
spots are left. Well, I claim that there are 63,
because one rule of chess is that if you put a piece in
a particular square, you can no longer put anything
else on that square. You can’t put two
or more things. So the first rook is occupying
one spot, so there’s only 63 spots left. So the second rook has 63 spots
that it could go in. Similarly, the third
rook has 62 spots. Hopefully you see the pattern. You can continue this down. And remember, we have to
place all eight rooks. So you could do it out
yourself or just do the simple math. You’ll figure out that the
eighth rook only has 57 spots that it could be in. So this is a good start. We’ve sort of figured out if
we sequentially place each rook, how many options
do we have. But we haven’t combined these
numbers in any useful way yet. We haven’t counted the number
of total arrangements. And this may already be obvious
to some, but it wasn’t obvious to me when I was first
learning this material, so I want to go through
this slowly. You have probably heard in
lecture by now about the counting principle. And what the counting principle
tells you is that whenever you have a process that
is done in stages and in each stage, you have a
particular number of choices, to get the total number of
choices available at the end of the process, you simply
multiply the number of choices at each stage. This might be clear to you,
again, simply from the statement, for some of you. But for others, it might
still not be clear. So let’s just take
a simple example. Forget about the rook problem
for a second. Let’s say you’re at
a deli, and you want to make a sandwich. And to make a sandwich, you need
a choice of bread and you need a choice of meat. So we have a sandwich-building
process, and there’s two stages. First, you have to pick the
bread, and then you have to pick the meat. So let’s say for the choice
of bread, you can choose wheat or rye. So again, you can always use
a little decision tree– wheat or rye. And then let’s say that
for the meats, you have three options. You have ham, turkey,
and salami. So you can have ham,
turkey, or salami– ham, turkey, or salami. How many total possible
sandwiches can you make? Well, six. And I got to that
by 2 times 3. And hopefully this makes sense
for you, because there’s two options in the first stage. Freeze an option. Given this choice, there’s
three options at the second stage. But you have to also realize
that for every other option you have at the first stage, you
second stage. And this is the definition
of multiplication. If you add three two times,
you know that’s 3 times 2. So if you extrapolate this
example to a larger, more general picture, you will have
derived for yourself the counting principle. And we’re going to use the
counting principle here to determine what the total number
of arrangements are. So we have a sequential process,
because we’re placing the first rook and then the
second rook, et cetera. So at the first stage,
we have 64 choices. At the second stage,
we have 63 choices. At the third stage, we have
62 choices, et cetera. And so I’m just multiplying
these numbers together, because the counting principle
says I can do this. So my claim is that this product
is equal to the total number of arrangements. And we could stop here, but I’m
going to actually write this in a more useful way. You guys should have
been introduced to the factorial function. So you can express this
equivalently as 64 factorial divided by 56 factorial. And this is not necessary for
express these types of products in factorials,
because you can see cancellations more easily. So if it’s OK with everybody,
I’m going to erase this work to give myself more room. So we’ll just put our answer for
the denominator up here, and then we’re going to get
started on the numerator. So for the numerator, thanks to
the discrete uniform law, we only need to count the number
of safe arrangements. But this is a little bit more
tricky, because now, we have to apply our definition
of what “safe” means. But we’re going to use the same
higher-level strategy, which is realizing that we can
place rooks sequentially. So we can think of it as
a sequential process. And then if we figure out how
many choices you have in each stage that sort of maintain the
“safeness” of the setup, then you can use the counting
principle to multiply all those numbers together
eight rooks. Starting the same way we did
last time, how many spots are there for the first rook
that are safe? Nobody is on the board yet, so
nobody can harm the first rook we put down. So I claim that it’s just
our total of 64. Now, let’s see what happens. Let’s pick a random
square in here. Let’s say we put our
first rook here. Now, I claim a bunch of spots
get invalidated because of the rules of chess. So before, I told you a rook can
kill anything in the same column or in the same row. So you can’t put a rook here,
because they’ll kill each other, and you can’t
put a rook here. So by extension, you can see
that everything in the column and the row that I’m
highlighting in blue, it’s no longer an option. You can’t place a
rook in there. Otherwise, we will
have violated our “safety” principle. So where can our
second rook go? Well, our second rook can go in
any of the blank spots, any of the spots that are not
highlighted by blue. And let’s stare at this
a little bit. Imagine that you were to take
scissors to your chessboard and cut along this line
and this line and this line and this line. So you essentially sawed off
this cross that we created. Then you would have four
free-floating chessboard pieces– this one, this one,
this one, and this one. So this is a 3-by-4 piece,
this is 3-by-3, this is 4-by-3, and this is 4-by-4. Well, because you cut this part
out, you can now slide those pieces back together. And hopefully you can convince
yourself that that would leave you with a 7-by-7 chessboard. And you can see that the
dimensions match up here. So essentially, the second rook
can be placed anywhere in the remaining 7-by-7
chessboard. And of course, there are 49
spots in a 7-by-7 chessboard. So you get 49. So let’s do this experiment
again. Let me rewrite the reduced
7-by-7 chessboard. You’re going to have to forgive
me if the lines are not perfect– one, two, three, four, five,
six, seven; one, two, three, four, five, six, seven. Yep, I did that right. And then we have one, two,
three, four, five, six, seven. That’s not too bad for
my first attempt. So again, how did I get this
chessboard from this one? Well, I took scissors and I cut
off of the blue strips, and then I just merged the
remaining four pieces. So now, I’m placing
my second rook. So I know that I can place my
second rook in any of these squares, and it’ll be
safe from this rook. Of course, in reality, you
wouldn’t really cut up your chessboard. I’m just using this as a visual
aid to help you guys see why there are 49 spots. Another way you could see 49
spots is literally just by counting all the white squares,
but I think it takes time to count 49 squares. And this is a faster
way of seeing it. So you can put your second
rook anywhere here. Let’s actually put in the
corner, because the corner is a nice case. If you put your rook in the
corner, immediately, all the spots in here and all the spots
in here become invalid for the third rook, because
otherwise, the rooks can hurt each other. So again, you’ll see that if you
take scissors and cut off the blue part, you will have
reduced the dimension of the chessboard again. And you can see pretty quickly
that what you’re left with is a 6-by-6 chessboard. So for the third rook, you get a
6-by-6 chessboard, which has 36 free spots. And I’m not going to insult
your intelligence. You guys can see the pattern– 64, 49, 36. These are just perfect
squares decreasing. So you know that the fourth
rook will have 25 spots. I’m going to come over here
because I’m out of room. The fifth rook will
have 16 spots. The sixth rook will
have nine spots. The seventh rook will
have four spots. And the eighth rook will
just have one spot. And now, here we’re going
to invoke the counting principle again. Remember the thing that I just
defined to you by talking about sandwiches. And we’ll see that to get
the total number of safe arrangements, we can
just multiply these numbers together. So I’m going to go ahead
and put that up here. You get 64 times 49 times
36 times 25 times 16 times 9 times 4. And in fact, this
is our answer. So we’re all done. So I really like this problem,
spatial arrangements. So it’s a nice exercise, because
it lets you practice your counting skills in a
new and creative way. And in particular, the thing
that we’ve been using for a while now is the discrete
uniform law. But now, I also introduced
the counting principle. And we used the counting
principle twice– once to compute the numerator
and once to compute the denominator. Counting can take a long time
for you to absorb it. So if you still don’t totally
buy the counting principle, that’s OK. I just recommend you do some
more examples and try to convince yourself that it’s
really counting the right number of things. So counting principle is
the second takeaway. And then the other thing that
is just worth mentioning is, you guys should get really
comfortable with these factorials, because they will
just show up again and again. So that’s the end of the
problem, and I’ll see you next time.