Tutorial: Decision algorithms: The addition and multiplication principles
Adaptive game version
(This topic is also in Section 6.3 in Finite Mathematics or Section 7.3 in Finite Mathematics and Applied Calculus) I don't like this new tutorial. Take me back to the old version of this tutorial!
Addition and multiplication principles
Let's start with a simple scenario:%%A Because there are 3 sci-fi movies and 5 horror movies, you have $3 + 5 = 8$ to choose from. This scenario illustrates the following general principle:
Addition principle
When choosing among $r$ alternatives whose outcomes are all different, if:
When choosing among $r$ alternatives whose outcomes are all different, if:
-
Alternative 1 has $n_1$ possible outcomes,
Alternative 2 has $n_2$ possible outcomes,
...
Alternative $r$ has $n_r$ possible outcomes,
%%Example
In the scenario above, our decision on which movie to see is based on the following two alternatives:
In the scenario above, our decision on which movie to see is based on the following two alternatives:
-
Alternative 1 Choose a sci-fi movie : 3 outcomes,
Alternative 2 Choose a horror movie : 5 outcomes.
%%Q What does this have to do with sets?
%%A Good question! When we talk about the number of possible outcomes resulting from making decisions, we are really talking about the number of elements in the resulting set of outcomes; in other words, the cardinality of the resulting set of outcomes. %%Q In the %%prevsectut there are lots of rules for calculating cardinality. Is the addition principle some kind of new rule we should add to the list?
%%A No. Think about the addition principle in terms of cardinalities: If the set of outcomes of the first alternative is $A$ and set of outcomes of the second alternative is $B$, then the combined set of outcomes from both alternatives is their union $A \cup B$. As we are insisting that no two alternatives have any outcomes in common, we are really insisting that here, $A$ and $B$ are disjoint, and so, by the rule for the cardinality of a union in the %%prevsectut,
%%A Good question! When we talk about the number of possible outcomes resulting from making decisions, we are really talking about the number of elements in the resulting set of outcomes; in other words, the cardinality of the resulting set of outcomes. %%Q In the %%prevsectut there are lots of rules for calculating cardinality. Is the addition principle some kind of new rule we should add to the list?
%%A No. Think about the addition principle in terms of cardinalities: If the set of outcomes of the first alternative is $A$ and set of outcomes of the second alternative is $B$, then the combined set of outcomes from both alternatives is their union $A \cup B$. As we are insisting that no two alternatives have any outcomes in common, we are really insisting that here, $A$ and $B$ are disjoint, and so, by the rule for the cardinality of a union in the %%prevsectut,
$n(A \cup B) = n(A) + n(B) \qquad$ \t Just add the cardinalities if the sets are disjoint.
%%Q Now how many different options do you have?
%%AFor each of the three 3 sci-fi movies, there are two times, giving 6 possibilities, and for each of these six choices, there are two auditoriums, giving a total of 12 possibilities. Notice that this time, we needed to make a sequence of three decisions: First decide on a movie, then a time, and finally a type of auditorium. This scenario illustrates the following general principle.
Multiplication principle
When making a sequence of choices with $r$ steps, if:
When making a sequence of choices with $r$ steps, if:
- #[Step 1 has $n_1$ possible outcomes,][Paso 1 tiene $n_1$ resultados posibles,]#
#[Step 2 has $n_2$ possible outcomes,][Paso 2 tiene $n_2$ resultados posibles,]#
...
#[Step $r$ has $n_r$ possible outcomes][Paso $r$ tiene $n_r$ resultados posibles,]#
%%Example
Gift pen sets come in three presentations: fancy, semi-fancy, and plain. Each presentation includes either a fountain pen or a ballpoint pen, and comes in four colors. To decide on a pen set for an acquantiance, you make a sequence of three decisions:
Gift pen sets come in three presentations: fancy, semi-fancy, and plain. Each presentation includes either a fountain pen or a ballpoint pen, and comes in four colors. To decide on a pen set for an acquantiance, you make a sequence of three decisions:
-
Step 1: Choose a presentation: 3 possible outcomes
Step 2: Choose a type of pen: 2 possible outcomes
Step 3: Choose a color: 4 possible outcomes
%%Q What does this tule have to do with sets?
%%A As we said above, we are calculating the cardinality of the resulting set of outcomes. %%Q For the addition principle we used the rule for the cardinality of a (disjoint) union. Which rule do we need here and why?
%%A If the set of outcomes of the first step is $A$ and set of outcomes of the second step is $B$, then the set of outcomes resulting from both steps in succession is a choice of an element $a$ of $A$ followed by a choice of an element $b$ of $B$; so we are really choosing a pair of elements $(a, b)$ with $a \in A$ and $b \in B;$ in other word, an element of the Cartesian product $A \times B$, and so, by the rule for the cardinality of a Cartesian product in the %%prevsectut,
%%A As we said above, we are calculating the cardinality of the resulting set of outcomes. %%Q For the addition principle we used the rule for the cardinality of a (disjoint) union. Which rule do we need here and why?
%%A If the set of outcomes of the first step is $A$ and set of outcomes of the second step is $B$, then the set of outcomes resulting from both steps in succession is a choice of an element $a$ of $A$ followed by a choice of an element $b$ of $B$; so we are really choosing a pair of elements $(a, b)$ with $a \in A$ and $b \in B;$ in other word, an element of the Cartesian product $A \times B$, and so, by the rule for the cardinality of a Cartesian product in the %%prevsectut,
$n(A \times B) = n(A)n(B) \qquad$ \t Multiply the cardinalities.
Combining the addition and multiplication principles
Now let's look at a situation that calls for combining both principles. The following is similar to Example 1 in Finite Mathematics:
We can think of each of the examples we have looked at so far as determining the number of outcomes of some activity, like deciding on a pen set, choosing an entree, filling out a multile-choice answer sheet, or ordering refreshements. In each case, we needed to make a sequence of decisions in order to determine the outcome, and the sequence of decisions we wrote down in each case is called a decision algorithm.
Decision algorithms
Decision algorithm
A decision algorithm is a systematic list of decisions we need to make in order to completely determine an outcome of some activity. We can use a decision algorithm to determine the number of possible outcomes by applying the addition and multiplcation principles to the decision algorithm.
In short:
%%A What it means for a decision algorithm to be valid is that making different choices must always result in a different outcome. For instance, if you look at the decision algorithm we wrote down to decide on a gift pen set, making different decisions in any of the three steps would result in a different gift.
A decision algorithm is a systematic list of decisions we need to make in order to completely determine an outcome of some activity. We can use a decision algorithm to determine the number of possible outcomes by applying the addition and multiplcation principles to the decision algorithm.
In short:
To count the number of possible outcomes of some activity, come up with a valid* decision algorithm to determine the outome by systematically listing the decisions to be made at each stage, and then apply the addition and multiplication principles.
%%Q Wait a minute! what is all this about a "valid" decision algorithm? %%A What it means for a decision algorithm to be valid is that making different choices must always result in a different outcome. For instance, if you look at the decision algorithm we wrote down to decide on a gift pen set, making different decisions in any of the three steps would result in a different gift.
%%Examples
1. You are the coach of the Enormous State U Blastball team. Your team is to have four players: a striker, two blasters, and a blocker. You have five possible players to choose from to make up the team. Following are two decision algorithms; one are valid and one is invalid. In the first algorithm, you pick players for the five positions on-by-one to form the team. In the second, you instead fill the three positions one-by-one:
1. You are the coach of the Enormous State U Blastball team. Your team is to have four players: a striker, two blasters, and a blocker. You have five possible players to choose from to make up the team. Following are two decision algorithms; one are valid and one is invalid. In the first algorithm, you pick players for the five positions on-by-one to form the team. In the second, you instead fill the three positions one-by-one:
\t
Step 2: Pick the first blaster: 4 choices
Step 3: Pick the second blaster: 3 choices
Step 4: Pick the blocker: 2 choices
Total: 5×4×3×2 = 120 possible teams
\t
Step 2: Pick the blocker: 4 choices
Step 3: Pick two of the remaining three to be the blasters: 3 choices
(Choose which of the three to leave out.)
Total: 5×4×3 = 60 possible teams
Although each of these algorithms leads to a blastball team, Algorithm 1 is not valid for counting the number of possible teams you can make. Why? Suppose that Joaquim and Matilda are two players. Then, if you choose Joaquim in Step 2 and Matilda in Step 3, you end up wit the same two blasters as you would by choosing Matilda in Step 2 and Joaquim in Step 3. Thus switching your decisions in Steps 2 and 3 results in the same outcome (the same team), and so the Algorithm 1 is not valid.On the other hand, if you make changes any of your decisions in Algorithm 2, the resulting team will be different (think about why). Thus, Algorithm 2 is valid.
Decision algorithm 1
Step 1: Pick the striker: 5 choices Step 2: Pick the first blaster: 4 choices
Step 3: Pick the second blaster: 3 choices
Step 4: Pick the blocker: 2 choices
Total: 5×4×3×2 = 120 possible teams
Decision algorithm 2
Step 1: Pick the striker: 5 choices Step 2: Pick the blocker: 4 choices
Step 3: Pick two of the remaining three to be the blasters: 3 choices
(Choose which of the three to leave out.)
Total: 5×4×3 = 60 possible teams
2. You have four cards spread in front of you; each with a single digit printed on it: Two of them have a "1", one has a "2", and one has a "3". You want to know how many different 4-digit sequences you can make by arranging the cards in different orders.Following are three decision algorithms; two are valid and one is invalid. In the first algorithm, we pick the four cards one-by-one to form the sequence. In the second and third, we instead think of placing the four cards in four empty slots in order to obtain the sequence:
\t
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4-digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 1][Algoritmo de decisión 1]#
#[Step 1: Pick the first card: 4 choices][Paso 1: Escoje la primera carta: 4 opciones]#
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 2][Algoritmo de decisión 2]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para el "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 3][Algoritmo de decisión 3]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para la "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Although each of these algorithms leads to a 4-digit sequence, Algorithm 1 is not valid for counting the number of possible 4-digit sequences. Why? Because, for instance, we can use Algorithm 1 get the same sequence "3121" by making different decisions as follows:][Aunque cada uno de estos algoritmos conduce a una secuencia de 4 dígitos, el Algoritmo 1 no es válido para contar el número de posibles secuencias de 4 dígitos. ¿Por qué? Porque, por ejemplo, podemos usar el Algoritmo 1 para obtener la misma secuencia "3121" al hacer diferentes decisiones como sigue:]#
\t
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
\t #[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
Now try some of the exercises in Section 6.3 in Finite Mathematics or Section 7.3 in Finite Mathematics and Applied Calculus.
Last Updated: July 2023
Copyright © 2022 Stefan Waner and Steven R. Costenoble
Copyright © 2022 Stefan Waner and Steven R. Costenoble