187 – Midterm 1

Here is the midterm.

Solutions follow.

Problem 1 concerns lists. We are given a collection of 5 objects, and we want to find:

1. The number of lists of length 2 where the entries come from these objects, and repetitions are allowed. We have that for each entry we can use 5 possible objects, for a total of lists.
2. The number of lists of length 2 where the entries come from these objects, and repetitions are required. Now, once we select the first entry (there are 5 possible ways of doing this), the second entry is completely determined. So we only have lists.
3. The number of lists of length 2 where the entries come from these objects, and repetitions are not allowed. There are two ways of counting: Either we simply notice that this is the total number of lists of length 2 (25), except for those that have repetitions (5), for a total of or else we note that whatever first entry we choose (5 possibilities), this eliminates one of the 5 possible objects from being the second entry (so now we only have 4 possibilities for this entry), for a total of

The extra credit problem asked for the number of lists of length 3 whose entries come from and repetitions are required. Again, there are two ways of counting. The easiest way is simply to count of lists of length 3 () and subtract from them those lists that do not have repetitions () for a total of lists. The second way counts the lists directly, but this is a bit more complicated. There are 5 possibilities for the first entry. If the second entry is the same, the third entry is arbitrary (so this gives us lists so far). If the second entry is different (4 possibilities) then the last entry is either the same as the first or the second (2 possibilities), for a total of lists. Hence, the total number of lists we are looking for is

Problem 2 asks us to explain in what sense the statement is equivalent to the statement and to prove that this is the case. 

Two statements are equivalent precisely when they have the same truth values, i.e., they are both true in precisely the same cases and both are false in precisely the same cases. To see that this is the case, the easiest method is to compare the truth tables for both statements and see that they are the same. This is indeed the case: Both statements are true precisely when latex \varphi$ and have the same truth value (be it true or false).

There is another way in which the equivalence can be analyzed. The statement is known to be equivalent to the conjunction Let’s analyze when this conjunction holds, which is the same as saying that both implications must be true. Note that holds if is true. However, if is false, then the implication only holds if is also false. This is to say, This statement is called the contrapositive of and our analysis just showed that the two are equivalent.

In the case that interests us, we see that is equivalent to which is equivalent, considering the contrapositives of both implications, to which is equivalent to which in turn is equivalent to as we wanted to see.

There is yet another way in which one can make sense of two statements and being equivalent, namely, that we can prove from and also prove from A careful study of this sense would lead us to study provability in the context of mathematical logic. 

Problem 3 asks us to show that if are sets and is an element such that and then also

To prove this, recall that If belongs to this symmetric difference, then there are two possibilities: Either or else

1. Assume that and recall that this means that but Then (since we are also given that ) we have that (by definition of ) and (again, by definition of ). But then and therefore (by definition of ), i.e., by definition of
2. Assuming that leads us to the same conclusion by essentially the same argument.

Since in both cases we have reached the desired conclusion, we are done.

Problem 4 asks to show that if and is divisible by then is a factor of

The problem essentially asked us to remember that “ is divisible by ” means the same as and that “ is a factor of .” All three statements mean that are integers and there is an integer such that

We are given that and There are then integers and such that and Then, multiplying the first equation by we get But and it follows that there is an integer (namely, ) such that This is the definition of which is what we needed to prove.

Problem 5 asks us to count the number of positive divisors of  

To find this number, note that and therefore any divisor will have the form where are integers with and

This means that the number of divisors is the same as the number of  lists with as explained. There are 4 possibilities for 3 for 2 for and 2 for for a total of lists, and therefore 48 is the number of positive divisors of

Advertisement