روش های جایگزین
- زمان مطالعه 8 دقیقه
- سطح خیلی سخت
دانلود اپلیکیشن «زوم»
این درس را میتوانید به بهترین شکل و با امکانات عالی در اپلیکیشن «زوم» بخوانید
متن انگلیسی درس
Alternative methods in counting. So I’ll begin by saying counting is an area of math that sometimes requires some significant out-of-the-box thinking. It’s not really a formula of math where you can just rely on formulas or rely on the same method every single problem. Each problem requires something different and this is especially true on the test.
They specialize in writing problems that require a different approach than other problems. So in particular sometimes a very straightforward calculation is not the most efficient and sometimes it is even prohibitively long. In this video I will discuss a couple creative approaches that can simply some counting problems.
The first involves shifting the focus on what is asked. Suppose we have n total items. Of course, the total number of orders we could put the n items in is n factorial. Suppose a restriction is given and we want the number of arrangements that meet that restriction. We have already talked about the way to count arrangements obeying many simple restrictions.
Think of it this way, every arrangement of the total n factorial must either obey the restriction or not obey the restriction. So let’s say that n factorial that’s the total number of arrangements, let’s just say that R is the number of arrangements that obey the restriction, and Q is the number of arrangements that do not obey the restriction. Well obviously, R + Q has to equal n!.
Because all of the arrangements, every single arrangement, either does, or doesn’t, obey the restriction. So together, they have to add up to the total number of arrangements. But think about this equation. If we subtract R from both side. If we subtract Q from both sides, we get R = n!-Q.
And this is an alternate way to get the number of arrangements that obey the restriction. We can subtract, we can count all the ones that don’t obey the restriction and then subtract that from the whole. And this is a really important idea. This can be a powerful shortcut in a number of cases.
So here’s a practice problem. Think about this for a moment, and then we’ll talk about it. Six children will sit in a row of six chairs but Jackie and Marilyn cannot be seated next to each other. How many arrangements are possible? Well, first let’s try to count this directly.
First of all, there’s no formula we can used. There’s no formula that we can just plug in and automatically get the answer. We have to think about cases. So, let’s start with Marilyn in the first chair on the left. Well then, Jacqueline could be in any of the four chairs on the right. So, she can’t be in that one right next to Marilyn but she could be in the other four.
Now put Marilyn in the second chair. Well then, Jacqueline could be in any of the three chairs to the right. So the number of chairs that Jacqueline could be in is not the same for each time. And notice, as we keep moving Marilyn over, then there’s gonna be some chairs on the left and some chairs on the right where Jacqueline could be. So this is starting to get hard.
Counting all the arrangements that meet this restriction is hard and time-consuming. Now if you’re good at counting and you’re well organized, you might be able to do it relatively quickly. But what I’m gonna show is something even quicker. So first of all, we know that the total, of course, is 6 factorial which is 720, and those are all the arrangements that includes all the ones where Jackie and Marilyn are seated next to each other, and all the ones where they’re not seated next to each other.
So let’s count the arrangements that don’t meet this restriction, that is all the arrangements where Jackie and Marilyn do sit next to each other. So if they’re sitting next to each other, how many possible arrangements? Well, this turns out to be relatively easy to count. Because they could be right next to each other in those first seats on the left and of course, they could be in either order.
Or we could move them one seat over, or one seat over, or one seat over, or one seat over. And so those are ten possible ways that we could configure Jackie and Marilyn on these chairs with them right next to each other. With any of these ten arrangements, the four empty seats could be filled by any arrangements of the remaining four children.
So that would be 4 factorial or 24. So, it would be these 10 arrangements and anyone of them, times 24. So 10 times 24, 240, this is the total number of arrangements that are not allowed and, of course, the total number of arrangements period is 720. So the allowed must be 720 minus 240 which is 480. And so that turns out to be, by far, the most efficient way to count the number of arrangements in this particular case.
Note that the prompt question contained a restriction involving the word, not. That can be a very important clue that thinking about this alternative way might be easier. The other strategy takes advantage of a kind of symmetry. We will begin with an example question. So here’s a practice question.
Think about this, and then we’ll talk about it. Six children will give presentations, one after the other. Luke’s presentation makes a reference to something mentioned in Ruth’s, so Ruth’s presentation must come before Luke’s, and not necessarily immediately before. How many orders are possible? Well, Ruth’s presentation must come some time, any time, before Luke’s.
We could list all the ways that Ruth could occupy a slot before Luke, but that would take some time. Instead, think about it this way. For every order in which Ruth comes before Luke. So here’s a random order, and it just happens that R comes before L. There’s a corresponding order in which L comes before R.
In other words, we’ve just swapped the position of L and R, and everyone else stays in the same place. And so these two correspond to each other. They’re identical except that L and R are in opposite orders. So these are the same two. But notice that we picked another one.
Another one where R comes before L. Again we could swap R and L. And we get a corresponding one. Again another one where R comes before L. Swap them so L comes before R. And we could do this time and time again.
For each order that happens to have R before L. We can find a matching order that has L before R. In other words, we can match these two groups in a one to one matching pattern, this is a really big idea. Think about this pattern of one to one matching, this means that for every arrangement in which R comes before L there is exactly one arrangement in which L comes before R.
Therefore, in exactly half L comes first, and in the other half, R comes first. So, whatever the total number of arrangements there are in exactly half of them R comes first, R comes before L. And in the other half L comes before R. To count the number of arrangement in which R comes first, in which R comes before L.
We simply divide the total number by 2. So, 6 factorial divided by 2, 720 divided by 2, is 360. And that’s the answer. Both of these approaches can profoundly reduce calculations. If you notice that one is relevant to a problem. It’s important to review this approaches enough and practice them when they are relevant so that they are on your radar when you analyze a new problem.
In summary, if you were asked to count how many arrangements obey a restriction, it may be easier to count the ones that do not, and subtract them from the total. In any question that is asking about two terms to be in one order and not another, think about whether these two groups, the ones that obey the restriction and the ones that do not obey the restriction, whether those two groups are related by a kind of symmetry.
مشارکت کنندگان در این صفحه
تا کنون فردی در بازسازی این صفحه مشارکت نداشته است.
🖊 شما نیز میتوانید برای مشارکت در ترجمهی این صفحه یا اصلاح متن انگلیسی، به این لینک مراجعه بفرمایید.