text: 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.
metadata: {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}