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

“arrange” for short. Now, I talked about this

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

have to add an additional three options for the

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

your problem solution, but sometimes it’s helpful to

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

and get your answer. So we have to place

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,

because we don’t normally ask you to think about different

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.