Exercise 4.1, problems 4, 7, & 18
4. A wheel of fortune has the integers from 1 to 25 placed on it in a random manner. Show that regardless of how the numbers are positioned on the wheel, there are three adjacent numbers whose sum is at least 39.
7. Alumberjack has 4n + 110 logs in a pile consisting of n layers. Each layer has two more logs than the layer directly above it. If the top layer has six logs, how many layers are there?
18. Consider the following four equations:
1) 1 = 1
2) 2 + 3 + 4 = 1 + 8
3) 5 + 6 + 7 + 8 + 9 = 8 + 27
4) 10 + 11 + 12 + 13 + 14 + 15 + 16 = 27 + 64
Conjectures the general formula suggested by these four equations, and prove your conjecture.
Exercise 4.2, problems 16
16. Give a recursive definition for the set of all
a) positive even integers
b) nonnegative even integers
Exercise 4.3, problems 4, 15
4. If a, b, c ∈ Z+ and a|bc, does it follow that a|b or a|c?
15. Write each of the following (base-10) integers in base 2 and base 16.
a) 22 b) 527 c) 1234 d) 6923
Exercise 4.4, problems 1 & 14
problems 1: For each of the following pairs a, b ∈ Z+, determine gcd(a, b) and express it as a linear combination of a, b.
a) 231, 1820 b) 1369, 2597 c) 2689, 4001
14. An executive buys $2490 worth of presents for the children of her employees. For each girl she gets an art kit costing $33; each boy receives a set of tools costing $29. How many presentsof each type did she buy?
Exercise 5.1, problems 8 Logic chips are taken from a container, tested individually, and labeled defective or good. The testing process is continued until either two defective chips are found or five chips are tested in total. Using a tree diagram, exhibit a sample space for this process.
Exercise 5.3, problems 1 & 8
1. Give an example of finite sets A and B with |A|, |B| ≥ 4 and a function f : A→B such that (a) f is neither one-to-one nor onto; (b) f is one-to-one but not onto; (c) f is onto but not one-to-one; (d) f is onto and one-to-one.
8. A chemist who has five assistants is engaged in a research project that calls for nine compounds that must be synthesized. In how many ways can the chemist assign these syntheses to the five assistants so that each is working on at least one synthesis?
Exercise 5.4, problems 13 & 14
Exercise 5.5, problems 2 & 7(a)
2. Show that if eight people are in a room, at least two of them have birthdays that occur on the same day of the week.
7. a) Show that if any 14 integers are selected from the set S = {1, 2, 3, . . . , 25}, there are at least two whose sum is 26.
Ch. 5 of Discrete and Combinatorial Mathematics
Exercise 5.7, problems 1 & 6
1. Use the results of Table 5.11 to determine the best “big-Oh” form for each of the following functions f : Z+ →R.
a) f (n) = 3n + 7
b) f (n) = 3 + sin(1/n)
c) f (n) = n3 − 5n2 + 25n − 165
d) f (n) = 5n2 + 3n log2 n
e) f (n) = n2 + (n − 1)3
f ) f (n) = n(n + 1)(n + 2)
————————
(n + 3)
g) f (n) = 2 + 4 + 6 + ・ ・ ・ + 2n
Exercise 5.8, problems 5 & 6
5. The following pseudocode procedure can be used to evaluate the polynomial 8 − 10x + 7×2 − 2×3 + 3×4 + 12×5, when x is replaced by an arbitrary (but fixed) real number r.
For this particular instance, n = 5 and a0 = 8, a1 = −10,
a2 = 7, a3 = −2, a4 = 3, and a5 = 12.
procedure PolynomialEvaluation1
(n: nonnegative integer;
r,a0,a1,a2,. . .,an: real)
begin
product := 1.0
value := a0
for i := 1 to n do
begin
product := product * r
value := value + ai * product
end
end
a) How many additions take place in the evaluation of the given polynomial? (Do not include the n − 1 additions needed to increment the loop variable i.) How many multiplications?
b) Answer the questions in part (a) for the general polynomial a0 + a1x + a2x2 + a3x3 + ・ ・ ・ + an−1xn−1 + anxn, where a0, a1, a2, a3, . . . , an−1, an are real numbers and n
is a positive integer.
6. We first note how the polynomial in the previous exercise can be written in the nested multiplication method: 8 + x(−10 + x(7 + x(−2 + x(3 + 12x)))).
Using this representation, the following pseudocode procedure (implementing Horner’s method) can be used to evaluate the given polynomial.
procedure PolynomialEvaluation2
(n: nonnegative integer;
r,a0,a1,a2,. . .,an: real)
begin
value := an
for j := n – 1 down to 0 do
value := aj + r * value
end
Answer the questions in parts (a) and (b) of Exercise 5 for the
new procedure given here.
Recent Comments