CS 23022 Practice Question for Final Eaxm Spring 2007
True/False
Indicate whether the statement is true or false.
____ 1. A proof by the first principle of mathematical induction assumes that the inductive hypothesis is true.
____ 2. To show that is divisible by 3 for every positive integer n, the basis step in an inductive proof would be to show that is divisible by 3 when n equals 1.
____ 3. In the second principle of mathematical induction, to show that proposition P(n) is true for all positive integers n, after showing the basis step for to be true, we assume P(k) is true, where k is an integer , and use it to prove that is true.
____ 4. Let A = {grape, banana, apple} and B = {red, blue, green, yellow}. Let R = {(grape, blue), (banana, yellow), (banana, yellow), (green, apple)}. Then R is a relation from A to B.
____ 5. Let Z be the set of all integers and let R be a relation on defined by . Then it is true that .
____ 6. Let Z be the set of all integers and let R be a relation on defined by . Then it is true that .
____ 7. Let be the set of all positive integers and R be a ternary relation on defined by . Then it is true that .
____ 8. Let . Then the digraph shown above represents the relation .
____ 9. The digraph shown above has a total of four loops.
____ 10. Let R be a relation on set defined by the rule if . Then the range of R, .
____ 11. Let P be the set of people. Then the relation R on , defined by has the domain, D(R): is the set of all people who have money owed to them.
____ 12. Let R be a relation from set X into set Y. The inverse of R , denoted by is the relation from Y to X defined by .
____ 13. Let R be a relation from set A into set B, and let S be a relation from set B into set C. If there exists some such that and , then .
____ 14. Let R be a relation on a nonempty set . Then .
____ 15. In a local election to select one board member, there are 3 Democrats, 5 Republicans, and 2 Independents running for the same office. There are 30 possible outcomes to this election.
____ 16. If task can be performed in ways and task can be performed in ways, then the number of ways of performing tasks and in succession is .
____ 17. A set A contains 5 distinct elements. The number of possible subsets that can be constructed from A is 120.
____ 18. Of 300 patients surveyed, 110 had high blood pressure, 73 had high cholesterol, and 42 suffered from both. The number of patients that had neither high blood pressure nor high cholesterol was 159.
____ 19. On January 3, 100 shoppers were surveyed at the mall. It was determined that 67 came to get a book signed by the author, 42 came to meet friends for lunch, and 26 came to do both. The number in the survey who did not come for the book signing nor to have lunch was 17.
____ 20. The Pigeonhole Principle states that if or more pigeons are put into n holes, at least two pigeons are put in the same hole.
____ 21. Say you have five pairs of mittens, all pairs different colors, jumbled together in a drawer. You go into the room without turning on the light. If you want to be sure to get the red pair, you must draw out 6 individual mittens.
____ 22. The permutation of 7 distinct items, taken 3 at a time, is 343.
____ 23. A list of items implies a permutation whereas a set of items implies a combination.
____ 24. The number of combinations of 5 different objects taken 3 at a time is 10.
____ 25. The number of combinations of 5 different objects taken 5 at a time is equal to 120.
____ 26. A child has 3 pennies, 5 nickels, 2 dimes, and 1 quarter. The number of groups of 3 coins that include none of the dimes is 84.
____ 27. Five candidates for mayor are to participate in a debate. Candidates are lined up on stage behind podiums facing the audience. If two of the candidates refuse to be positioned next to each other, the candidates can be arranged in 60 different ways.
____ 28. The coefficient of in is 15.
____ 29. The coefficient of in the expansion of is 126.
____ 30. In Pascal’s triangle, if rows are labeled and positions (from left to right) in a row are numbered , then the value would be in row 5, position 4.
____ 31. The 6th term of the Fibonacci sequence is 13.
____ 32. The initial conditions for the Fibonacci sequence are and .
Multiple Choice
Identify the choice that best completes the statement or answers the question.
____ 33. To use the first principle of mathematical induction to prove that one can climb a ladder, the inductive hypothesis would be ______.
a. / to show that the first rung of the ladder can be climbedb. / to show that the first k rungs of the ladder can be climbed
c. / to assume that the first k rungs of the ladder () can be climbed
d. / to show that the st rung of the ladder can be climbed given that the first k rungs can be climbed
____ 34. Using the first principle of mathematical induction to prove that for all , the inductive step would be ______.
a. / to show thatb. / to show that , where k is an integer and , implies is true
c. / to show that for all
d. / to show that for all
____ 35. Let be the statement that every positive integer greater than 1 can be factored into primes. Proving this fact using the second principle of mathematical induction, the inductive step would be to show ______.
a. / if is true where n is an integer with , then is trueb. / if is true where n is an integer with , then is true
c. / that is true for some
d. / if all for all are true, then is true
____ 36. Let and . If relation , then which of the following is not correct?
a. / / c. /b. / / d. / Both B and C
____ 37. For a relation R from set A into set B, which of the following is true?
a. / / c. /b. / / d. / Both A and C
____ 38. Let Z be the set of all integers and R a relation on defined by . Which of the following ordered pairs belongs to R?
a. / / c. /b. / / d. / Both A and B
____ 39. Let be the set of all rational numbers and R a relation on defined by . Then which one of the following does not satisfy the relation?
a. / / c. /b. / 1 R 2 / d. /
____ 40. Match the arrow diagram below with the correct binary relation.
a. / / c. /b. / / d. /
____ 41. Which of the relations below matches the following digraph?
a. /b. /
c. /
d. /
____ 42. Let and . Let if and only if . the domain, is ______.
a. / / c. /b. / / d. /
____ 43. Let A be the set of all real numbers and relation R defined on by . Which of the following is true?
a. / Domain of R ,b. / Range of R ,
c. / Domain of R ,
d. / Both A and B
____ 44. Let set . Let R be a relation defined on by . Then is the set ______.
a. /b. /
c. /
d. /
____ 45. Let , and . Let the relations R from and S from be defined as follows:
Then all of the following are true EXCEPT ______.
a. / / c. /b. / / d. /
____ 46. You have 3 trees, 6 bushes, and 5 shrubs to plant. You must decide which item to plant first. If all the plants are unique in some way, how many choices are there?
a. / 14 / c. / 3b. / 90 / d. / 846
____ 47. A binary digit (bit) is either a 0 or a 1. If 8 bits make up a byte, how many different bytes are possible?
a. / 16 / c. / 256b. / 8 / d. / 64
____ 48. A computer password is to consist of 4 digits followed by a letter. The first digit must not be zero. How many passwords can be created?
a. / 26,000 / c. / 21,060b. / 23,400 / d. / 16,848
____ 49. For sets A and B, . Find .
a. / 68 / c. / 22b. / 15 / d. / 8
____ 50. A survey of 500 college students indicated that 320 drank alcohol, 150 smoked, and 70 neither drank nor smoked. The number of students who both drank and smoked was ______.
a. / 30 / c. / 110b. / 40 / d. / 80
____ 51. Count Dracula has five pairs of shoes, all different, jumbled together in his closet. He goes in to get a pair and because vampires don’t dare get in the sunlight, he fumbles in the dark. How many single shoes must he take with him to be certain to have a matching pair among them?
a. / 3 / c. / 5b. / 6 / d. / 10
____ 52. Suppose there are 70 people in a club. Then at least _____ of them must have their birthday in the same month.
a. / 1 / c. / 5b. / 11 / d. / 6
____ 53. Which of the following represents a permutation?
a. / The 5 oldest coins in your collection.b. / The Democrats in congress.
c. / The 5 most recent inductees into the Music Hall of Fame.
d. / An arrangement of paintings on your wall.
____ 54. An algebra class has 30 students. Four students will be selected to go to the board and solve 4 problems. If each student solves only one problem, how many ways can this be done?
a. / 27,405 / c. /b. / 657,720 / d. /
____ 55. Evaluate .
a. / 21 / c. / 504b. / 84 / d. / 720
____ 56. A bag contains three red marbles, three blue ones, five green ones, and two yellow ones. How many sets of four marbles are possible?
a. / 715 / c. / 330b. / 17,160 / d. / 90
____ 57. From a group of 9 children playing soldiers, how many ways can a general, 2 lieutenants, a sergeant, and a corporal be selected?
a. / 7,650 / c. / 181,440b. / 15,120 / d. / 362,880
____ 58. Jason has won a contest that entitled him to select 5 computer games from a list of 12 or 2 reference books from a list of 20. How many ways can he make his selection?
a. / 10 / c. / 782b. / 150,480 / d. / 95,420
____ 59. The coefficient of x in is ______.
a. / 4 / c. / 16b. / 32 / d. / 64
____ 60. The coefficient of in is ______.
a. / 1024 / c. / 4320b. / 5760 / d. / 1620
____ 61. Pascal’s Identity can be stated as follows, where n and r are integers such that ______.
a. / / c. /b. / / d. /
____ 62. Assume rows are numbered starting with 1. The fifth tow of Pascal’s triangle contains the values ______.
a. / 1 3 5 3 1 / c. / 1 5 10 10 5 1b. / 1 4 6 4 1 / d. / 1 2 3 2 1
Problem
63. Prove by induction: For all positive integers n, 5n-1 is divisible by 4.
.
CS 23022 Practice Question for Final Eaxm Spring 2007
Answer Section
TRUE/FALSE
1. ANS: T PTS: 1 REF: 135
2. ANS: T PTS: 1 REF: 136
3. ANS: F PTS: 1 REF: 137
4. ANS: F PTS: 1 REF: 175
5. ANS: F PTS: 1 REF: 175
6. ANS: T PTS: 1 REF: 176
7. ANS: F PTS: 1 REF: 176
8. ANS: F PTS: 1 REF: 177
9. ANS: F PTS: 1 REF: 178