GIAM-solutions Manual
GIAM-solutions Manual
GIAM-solutions Manual
Joseph Fields
1. Each of the quantities indexing the rows of the following table is in one
or more of the sets which index the columns. Place a check mark in a
table entry if the quantity is in the set.
N Z Q R C
17
π
22/7
−6
e0
1+i
√
3
i2
Note that these sets contain one another, so if you determine that a
number is a natural number it is automatically an integer and a rational
number and a real number and a complex number. . .
1
2 CHAPTER 1. INTRODUCTION AND NOTATION
. . . − 3, −2, −1, 0, 1, 2, 3, . . .
(a) 5021.2121212121 . . .
(b) 0.2340000000 . . .
(c) 12.31331133311133331111 . . .
(d) π
(e) 2.987654321987654321987654321 . . .
rat,rat,irr,irr,rat
1.1. BASIC SETS 3
4. The “see and say” sequence is produced by first writing a 1, then it-
erating the following procedure: look at the previous entry and say
how many entries there are of each integer and write down what you
just said. The first several terms of the “see and say” sequence are
1, 11, 21, 1112, 3112, 211213, 312213, 212223, . . .. Comment on the ra-
tionality (or irrationality) of the number whose decimal digits are ob-
tained by concatenating the “see and say” sequence.
0.1112111123112211213...
Experiment!
What would it mean for this number to be rational? If we were to run
into an element of the “see and say” sequence that is its own description,
then from that point onward the sequence would get stuck repeating
the same thing over and over (and the number whose digits are found
by concatenating the elements of the “see and say” sequence will enter
into a repeating pattern.)
7. Consider the process of long division. Does this algorithm give any in-
sight as to why rational numbers have terminating or repeating decimal
expansions? Explain.
You really need to actually sit down and do some long division
problems. When in the process do you suddenly realize that the digits
are going to repeat? Must this decision point always occur? Why?
a c ac
∗ = .
b d bd
How do you know that the result is actually a rational number?
1.1. BASIC SETS 5
(b) (1 + i) + (1 − i)
(c) (1 + i) · (1 − i)
(a) 105
(b) 414
(c) 168
(d) 1612
(e) 9177
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
The primes used in this instance of the sieve are just 2, 3, 5 and 7.
Any number less than 100 that isn’t a multiple of 2, 3, 5 or 7 will not
be crossed off during the sieving process. If you’re still unclear about
the process, try a web search for "Sieve of Eratosthenes" +applet,
1.2. DEFINITIONS: PRIME NUMBERS 7
there are several interactive applets that will help you to understand
how to sieve.
3. What would be the largest prime one would sieve with in order to find
all primes up to 400?
Remember that if a number factors into two multiplicands, the
smaller of them will be less than the square root of the original number.
10. Another famous conjecture, also thought to be true – but as yet un-
proved, is Goldbach’s conjecture. Goldbach’s conjecture states that
every even number greater than 4 is the sum of two odd primes. There
is a function g(n), known as the Goldbach function, defined on the pos-
itive integers, that gives the number of different ways to write a given
number as the sum of two odd primes. For example g(10) = 2 since
10 = 5 + 5 = 7 + 3. Thus another version of Goldbach’s conjecture is
that g(n) is positive whenever n is an even number greater than 4.
Graph g(n) for 6 ≤ n ≤ 20.
If you don’t like making graphs, a table of the values of g(n) would
suffice. Note that we don’t count sums twice that only differ by order.
For example, 16 = 13+3 and 11+5 (and 5+11 and 3+13) but g(16)=2.
10 CHAPTER 1. INTRODUCTION AND NOTATION
1. How many quantifiers (and what sorts) are in the following sentence?
“Everybody has some friend that thinks they know everything about
a sport.”
Four.
3. The sentence “For every pair of (distinct) real numbers there is another
real number between them.” is true. Why?
Think about this: is there any way to (using a formula) find a
number that lies in between two other numbers?
3267 = 466 · 7 + 5
466 = 66 · 7 + 4
7. For conversion between the three bases used most often in Computer
Science we can take binary as the “standard” base and convert using a
table look-up. Each octal digit will correspond to a binary triple, and
each hexadecimal digit will correspond to a 4-tuple of binary numbers.
Complete the following tables. (As a check, the 4-tuple next to A in
the table for hexadecimal should be 1010 – which is nice since A is
really 10 so if you read that as “ten-ten” it is a good aid to memory.)
hexadecimal binary
0 0000
1 0001
2 0010
octal binary 3
0 000 4
1 001 5
2 6
3 7
4 8
5 9
6 A
7 B
C
D
E
F
This is just counting in binary. Remember the sanity check that the
hexadecimal digit A is represented by 1010 in binary. (1010 = A16 =
10102 )
14 CHAPTER 1. INTRODUCTION AND NOTATION
8. Use the tables from the previous problem to make the following con-
versions.
7578 = 1111011112
1001010101102 = 45268
11. Suppose that 340 pounds of sand must be placed into bags having a
50 pound capacity. Write an expression using either floor or ceiling
notation for the number of bags required.
Seven 50 pound bags would hold 350 pounds of sand. They’d also
be able to handle 340 pounds!
jnk lnm
<
d d
for all integers n and d > 0. Support your claim.
You have to try a bunch of examples. You should try to make
sure the examples you try cover all the possibilities. The pairs that
provide counterexamples (i.e. show the statement is false in general)
are relatively sparse, so be systematic.
14. Assuming the symbols n,d,q and r have meanings as in the quotient-
remainder theorem (see page 29 of GIAM). Write expressions for q and
r, in terms of n and d using floor and/or ceiling notation.
I just can’t bring myself to spoil this one for you, you really need to
work this out on your own.
16 CHAPTER 1. INTRODUCTION AND NOTATION
(a) 3 mod 5
(b) 37 mod 7
(c) 1000001 mod 100000
(d) 6 div 6
(e) 7 div 6
(f) 1000001 div 2
3
(a) 0
7
(b) 7
13
(c) 5
13
(d) 8
52
(e) 7
The even numbered ones are 1 and 1287. The TI-84 calculates
binomial coefficients. The symbol used is nCr (which is placed between
the numbers – i.e. it is an infix operator). You get nCr as the 3rd item
in the PRB menu under MATH. In sage the command is binomial(n,k).
17. An ice cream shop sells the following flavors: chocolate, vanilla, straw-
berry, coffee, butter pecan, mint chocolate chip and raspberry. How
many different bowls of ice cream – with three scoops – can they make?
You’re choosing three things out of a set of size seven. . .
1.5. SOME ALGORITHMS 17
r=27
q=0
r=27-5=22
q=0+1=1
r=22-5=17
q=1+1=2
r=17-5=12
q=2+1=3
r=12-5=7
q=3+1=4
r=7-5=2
q=4+1=5
return r is 2 and q is 5.
a b gcd(a, b) lcm(a, b)
110 273
105 42
168 189
For such small numbers you can just find their prime factorizations
and use that, although it might be useful to practice your understanding
18 CHAPTER 1. INTRODUCTION AND NOTATION
What if the lemma wasn’t true? Can you work out what it would
mean if we had a number x such that x2 was even but x itself was odd?
√ √
4. The proof that 2 is irrational can be generalized to show that p is
irrational for every prime number p. What statement would be equiva-
lent to the lemma about the parity of x and x2 in such a generalization?
√
5. Write a proof that 3 is irrational.
√
You can mostly just copy the argument for 2.
1.7. RELATIONS 21
1.7 Relations
Exercises — 1.7
1. Consider the numbers from 1 to 10. Give the set of pairs of these
numbers that corresponds to the divisibility relation.
A pair is “in” the relation when the first number gazinta the second
number. 1 gazinta anything, 2 gazinta the even numbers, 3 gazinta 3,
6 and 9, etc. (Also a number always gazinta itself.)
f = {(0, 0), (1, 1), (2, 4), (3, 2), (4, 2), (5, 4), (6, 1)}
Rng(f ) = {0, 1, 2, 4}
22 CHAPTER 1. INTRODUCTION AND NOTATION
{(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10),
(3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10),
(5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10),
(6, 6), (6, 7), (6, 8), (6, 9), (6, 10),
(7, 7), (7, 8), (7, 9), (7, 10),
(8, 8), (8, 9), (8, 10),
(9, 9), (9, 10),
(10, 10)}
Less-than-or-equal-to
1.7. RELATIONS 23
F G
E B
J H
D C
7. There is a relation known as “has color” which goes from the set
to the set
C = {orange, red, green, yellow}.
Exercises — 2.1
1. Design a digital logic circuit (using and, or & not gates) that imple-
ments an exclusive or.
25
26 CHAPTER 2. LOGIC AND QUANTIFIERS
X Y X ⊕Y
T T ϕ
T ϕ T
ϕ T T
ϕ ϕ ϕ
So it’s true when one, or the other, but not both of its inputs are
true. The upshot of the last sentence is that we can write X ⊕ Y ≡
(X ∨ Y ) ∧ ¬(X ∧ Y ).
The above reformulation should help. . .
2. Consider the sentence “This is a sentence which does not refer to itself.”
which was given in the beginning of this chapter as an example. Is this
sentence a statement? If so, what is its truth value?
The only question in your mind, when deciding whether a sentence
is a statement, should be ”Does this thing have a definite truth value?”
Well?
Isn’t it just plainly false?
4. Complete truth tables for each of the sentences (A∧B)∨C and A∧(B ∨
C). Does it seem that these sentences have the same logical content?
A tiny hint here: since the sentences involve 3 variables you’ll need
truth tables with 8 rows. Here’s a template.
A B C (A ∧ B) ∨ C A ∧ (B ∨ C)
T T T
T T ϕ
T ϕ T
T ϕ ϕ
ϕ T T
ϕ T ϕ
ϕ ϕ T
ϕ ϕ ϕ
28 CHAPTER 2. LOGIC AND QUANTIFIERS
5. There are two other logical connectives that are used somewhat less
commonly than ∨ and ∧. These are the Scheffer stroke and the Peirce
arrow – written | and ↓, respectively — they are also known as NAND
and NOR.
The truth tables for these connectives are:
A B A|B A B A↓B
T T ϕ T T ϕ
T ϕ T and T ϕ ϕ
ϕ T T ϕ T ϕ
ϕ ϕ T ϕ ϕ T
2.2 Implication
Exercises — 2.2
A B A =⇒ B ¬A ∨ B
T T
T ϕ
ϕ T
ϕ ϕ
4. Determine a sentence using the and connector (∧) that gives the nega-
tion of A =⇒ B.
Hmmm. . . This will seem like a strange hint, but if you were to hear
a kid at the playground say “Oh yeah? Well, I did call your mom a
fatty and you still haven’t clobbered me! Owww! OWWW!!! Stop
hitting me!!”
What conditional sentence was he attempting to negate?
5. Rewrite the sentence “Fix the toilet or I won’t pay the rent!” as a
conditional.
The way I see it there are eight possible ways to arrange ”You fix
the toilet” and ”I’ll pay the rent” (or their respective negations) around
an implication arrow. Here they all are. You decide which one sounds
best.
If you fix the toilet, then I’ll pay the rent.
If you fix the toilet, then I won’t pay the rent.
If you don’t fix the toilet, I’ll pay the rent.
If you don’t fix the toilet, then I won’t pay the rent.
If I payed the rent, then you must have fixed the toilet.
If I payed the rent, then you must not have fixed the toilet.
If I didn’t pay the rent, then you must have fixed the toilet.
If I didn’t pay the rent, then you must not have fixed the toilet.
6. Why is it that the sentence “If pigs can fly, I am the king of Mesopotamia.”
true?
Unless we’re talking about some celebrity bringing their pet Viet-
namese pot-bellied pig into first class with them, or possibly a catapult
of some type... The antecedent (the if part) is false, so Yay! I AM the
2.2. IMPLICATION 31
9. What are the converse and inverse of “If you watch my back, I’ll watch
your back.”?
The converse is “If I watch your back, then you’ll watch my back.”
(Sounds a little dopey doesn’t it – likes its sort of a wishful thinking. . . )
The inverse is “If you don’t watch my back, then I won’t watch your
back.” (Sounds less vapid, but it means the same thing. . . )
∞
X Z ∞
f (n) < f (x).
n=1 0
functions, it isn’t too hard to come up with an f that actually has zero
area under it – just make f be identically zero except at the integer
x-values where it will take the same values as the terms of the series.
But wait, the function we just described isn’t “decreasing” – which is
probably why that hypothesis was put in there!
11. On the Island of Knights and Knaves (see page 28) you encounter two
individuals named Locke and Demosthenes.
Locke says, “Demosthenes is a knave.”
Demosthenes says “Locke and I are knights.”
Who is a knight and who a knave?
Could Demosthenes be telling the truth?
34 CHAPTER 2. LOGIC AND QUANTIFIERS
x + (y ∗ z) x + (y z )
+ ∅
= (x + y) ∗ (x + z) = (x + y)(x+z)
x ∗ (y + z)
∗ ∅
= (x ∗ y) + (x ∗ z)
∧
∅
2.3. LOGICAL EQUIVALENCES 35
(a) (A ∧ B) ∨ B ∼
= (A ∨ B) ∧ B
(b) A ∧ (B ∨ ¬A) ∼
= A∧B
(c) (A ∧ ¬B) ∨ (¬A ∧ ¬B) ∼
= (A ∨ ¬B) ∧ (¬A ∨ ¬B)
(d) The absorption laws.
Here’s the pair that shows the negation of an AND is the same as
the OR of the same inputs negated.
(a) (A ∨ B) ⇐⇒ C
(b) (A ∨ B) =⇒ (A ∧ B)
(a) “One should not behave towards others in a way which is disagree-
able to oneself.” Mencius Vii.A.4 (Hinduism)
(b) “None of you [truly] believes until he wishes for his brother what
he wishes for himself.” Number 13 of Imam “Al-Nawawi’s Forty
Hadiths.” (Islam)
(d) “What is hateful to you, do not to your fellow man. This is the law:
all the rest is commentary.” Talmud, Shabbat 31a. (Judaism)
(f) “What you would avoid suffering yourself, seek not to impose on
others.” (the Greek philosopher Epictetus – first century A.D.)
(g) “Do not do unto others as you expect they should do unto you.
Their tastes may not be the same.” (the Irish playwright George
Bernard Shaw – 20th century A.D.)
The ones from Wicca and George Bernard Shaw are just there for
laughs.
For the remainder, you may want to contrast how restrictive they seem.
For example the Christian version is (in my opinion) a lot stronger
than the one from the Talmud – “treat others as you would want to
be treated” restricts your actions both in terms of what you would like
done to you and in terms of what you wouldn’t like done to you; “Don’t
treat your fellows in a way that would be hateful to you.” is leaving
38 CHAPTER 2. LOGIC AND QUANTIFIERS
you a lot more freedom of action, since it only prohibits you from doing
those things you wouldn’t want done to yourself to others. The Hindus,
Epictetus and the Jews (and the Wiccans for that matter) seem to be
expressing roughly the same sentiment – and promoting an ethic that
is rather more easy for humans to conform to!
From a logical perspective it might be nice to define open sentences:
7. You encounter two natives of the land of knights and knaves. Fill in
an explanation for each line of the proofs of their identities.
Q.E.D.
40 CHAPTER 2. LOGIC AND QUANTIFIERS
Q.E.D.
2.4. TWO-COLUMN PROOFS 41
1. A ∨ (A ∧ B) ∼
= A ∧ (A ∨ B)
2. (A ∧ ¬B) ∨ A ∼
= A
3. A ∨ B ∼
= A ∨ (¬A ∧ B)
5. A ∼
= A ∧ ((A ∨ ¬B) ∨ (A ∨ B))
6. (A ∧ ¬B) ∧ (¬A ∨ B) ∼
= c
7. A ∼
= A ∧ (A ∨ (A ∧ (B ∨ C)))
8. ¬(A ∧ B) ∧ ¬(A ∧ C) ∼
= ¬A ∨ (¬B ∧ ¬C)
Proof:
¬(A ∧ B) ∧ ¬(A ∧ C)
DeMorgan’s law (times 2)
≡ (¬A ∨ ¬B) ∧ (¬A ∨ ¬C)
Distributive law
≡ ¬A ∨ (¬B ∧ ¬C)
Q.E.D.
42 CHAPTER 2. LOGIC AND QUANTIFIERS
The exceptions are very small prime numbers. You should be able
to find them easily.
5. Alvin, Betty, and Charlie enter a cafeteria which offers three different
entrees, turkey sandwich, veggie burger, and pizza; four different bev-
erages, soda, water, coffee, and milk; and two types of desserts, pie and
pudding. Alvin takes a turkey sandwich, a soda, and a pie. Betty takes
a veggie burger, a soda, and a pie. Charlie takes a pizza and a soda.
Based on this information, determine whether the following statements
are true or false.
(a) You are either with us, or you’re against us. And you don’t
appear to be with us. So, that means you’re against us!
W ∨A
¬W
∴ A
This is “disjunctive syllogism.”
(b) All those who had cars escaped the flooding. Sandra had a car –
therefore, Sandra escaped the flooding.
Let C(x) be the open sentence “x has a car” and let E(x) be
the open sentence “x escaped the flooding.” This argument is
actually the particular form of universal modus ponens: (See the
final question in the next set of exercises.)
(c) When Johnny goes to the casino, he always gambles ’til he goes
broke. Today, Johnny has money, so Johnny hasn’t been to the
casino recently.
48 CHAPTER 2. LOGIC AND QUANTIFIERS
I’m leaving the last two for you to do. One small hint: both are
valid forms.
2.7. VALIDITY OF ARGUMENTS AND COMMON ERRORS 49
You should note that while the form is valid, there is something
terribly wrong with this argument. Is it really true that everyone
who is guilty of a crime is in prison?
(b) If one eats oranges one will have high levels of vitamin C.
You do have high levels of vitamin C.
Therefore, you must eat oranges.
In the following truth table the predicate variables occupy the first 3
columns, the argument’s premises are in the next three columns and the
conclusion is in the right-most column. The truth values have already
been filled-in. You only need to identify the critical rows and verify
that the conclusion is true in those rows.
2.7. VALIDITY OF ARGUMENTS AND COMMON ERRORS 51
A B C (A ∨ B) ∨ C ¬A ¬B C
T T T T ϕ ϕ T
T T ϕ T ϕ ϕ ϕ
T ϕ T T ϕ T T
T ϕ ϕ T ϕ T ϕ
ϕ T T T T ϕ T
ϕ T ϕ T T ϕ ϕ
ϕ ϕ T T T T T
ϕ ϕ ϕ ϕ T T ϕ
52 CHAPTER 2. LOGIC AND QUANTIFIERS
Reexamine the arguments from problem (1), determine their forms (in-
cluding quantifiers) and whether they are universal or particular.
Hint: All of them except for one are the particular form – number
4 is the exception.
Let F (x) be the open sentence “x is a fish” and let W (x) be the open
sentence “x lives in water.”
5. Read the following proof that the sum of two odd numbers is even.
Discuss the rules of inference used.
x + y = 2k + 1 + 2j + 1 = 2(k + j + 1).
The definition for “odd” only involves the oddness of a single integer,
but the first line of our proof is a conjunction claiming that x and y are
both odd. It seems that two conjunctive simplifications, followed by
applications of the definition, followed by a conjunctive addition have
been used in order to go from the first sentence to the second.
55
56 CHAPTER 3. PROOF TECHNIQUES I
Even
∀n ∈ Z,
n is even ⇐⇒ ∃k ∈ Z, n = 2k
Odd
∀n ∈ Z,
n is odd ⇐⇒ ∃k ∈ Z, n = 2k + 1
Divisibility
∀n ∈ Z, ∀ d > 0 ∈ Z,
d|n ⇐⇒ ∃k ∈ Z, n = kd
Floor
∀x ∈ R,
y = ⌊x⌋ ⇐⇒ y ∈Z ∧ y ≤x<y+1
Ceiling
∀x ∈ R,
y = ⌈x⌉ ⇐⇒ y ∈Z ∧ y−1<x≤y
Quotient-remainder theorem, Div and Mod
∀n, d > 0 ∈ Z,
∃!q, r ∈ Z, n = qd + r ∧ 0 ≤ r < d
n div d = q
n mod d = r
Prime
∀p ∈ Z
p is prime ⇐⇒
(p > 1) ∧ (∀x, y ∈ Z+ , p = xy =⇒ x = 1 ∨ y = 1)
3.1. DIRECT PROOFS OF UNIVERSAL STATEMENTS 57
p is a number, and
p is greater than .
All you have to do to show that some number is odd, is produce the
integer k that the definition of “odd” says has to exist. Hint: the same
number could be used to prove that 128 is even.
You want to argue about the sum of two generic rational numbers.
Maybe call them a/b and c/d. The definition of “rational number”
then tells you that a, b, c and d are integers and that neither b nor d
are zero. You add these generic rational numbers in the usual way –
put them over a common denominator and then add the numerators.
One possible common denominator is bd, so we can express the sum as
(ad + bc)/(bd). You can finish off the argument from here: you need
to show that this expression for the sum satisfies the definition of a
rational number (quotient of integers w/ non-zero denominator). Also,
write it all up a bit more formally. . .
58 CHAPTER 3. PROOF TECHNIQUES I
4. Prove that the sum of an odd number and an even number is odd.
5. Prove that if the sum of two integers is even, then so is their difference.
Hint: If we write x + y for the sum of two integers that is even (so
x + y = 2k for some integer k), then we could subtract
from it in order to obtain x − y. Once you fill in that blank properly
the flow of the argument should become apparent to you.
2 3
6. Prove that for every real number x, 3
<x< 4
=⇒ ⌊12x⌋ = 8.
8. Prove that for all integers a and b, if a is odd and 6 | (a + b), then b is
odd.
evenness(n) = k ⇐⇒ 2k | n ∧ 2k+1 ∤ n
11. Suppose that a, b and c are integers such that a | b and b | c. Prove that
a | c.
This one is pretty straightforward. Be sure to not reuse any vari-
ables. Particularly, the fact that a | b tells us (because of the definition
of divisibility) that there is an integer k such that b = ak. It is not
okay to also use k when converting the statement “b | c.”
ax + b
= 1.
cx + d
Show that x is rational. Where is the hypothesis a ̸= c used?
Cross multiply and solve for x. If you need to divide by an expres-
sion, it had better be non-zero!
13. Show that if two positive integers a and b satisfy a | b and b | a then
they are equal.
From the definition of divisibility, you get two integers j and k, such
that a = jb and b = ka. Substitute one of those into the other and ask
yourself what the resulting equation says about j and k. Can they be
any old integers? Or, are there restrictions on their values?
3.2. MORE DIRECT PROOFS 61
You don’t need all the hypotheses. If a and c have different signs,
then ac is a negative quantity
4. Prove that for all integers a, b, and c, if a|b and a|(b + c), then a|c.
1
5. Show that if x is a positive real number, then x + x
≥ 2.
62 CHAPTER 3. PROOF TECHNIQUES I
If you work backwards from the conclusion on this one, you should
eventually come to the inequality (x − 1)2 ≥ 0. Notice that this in-
equality is always true – all squares are non-negative. When you go
to write-up your proof (writing things in the forward direction), you’ll
want to acknowledge this truth. Start with something like “Regardless
of the value of x, the quantity (x − 1)2 is greater than or equal to zero
as it is a perfect square.”
6. Prove that for all real numbers a, b, and c, if ac < 0, then the quadratic
equation ax2 + bx + c = 0 has two real solutions.
Hint: The quadratic equation ax2 + bx + c = 0 has two real solutions
if and only if b2 − 4ac > 0 and a ̸= 0.
n k n n−r
7. Show that k
· r
= r
· k−r
(for all integers r, k and n with
r ≤ k ≤ n).
d
(f (x) · g(x))
dx
d d
= (f (x)) · g(x) + f (x) · (g(x))
dx dx
Fill in the rest of the proof.
The critical step is to subtract and add the same thing: f (x)g(x+h)
in the numerator of the fraction in the limit which gives the definition
of d (f (x) · g(x)). Also, you’ll need to recall the laws of limits (like
dx
“the limit of a product is the product of the limits – provided both
exist”)
64 CHAPTER 3. PROOF TECHNIQUES I
1. Prove that if the cube of an integer is odd, then that integer is odd.
The best hint for this problem is simply to write down the contra-
positive statement. It is trivial to prove!
2. Prove that whenever a prime p does not divide the square of an integer,
it also doesn’t divide the original integer. (p ∤ x2 =⇒ p ∤ x)
The contrapositive is (p | x) =⇒ (p | x2 ).
∀x, y ∈ Z, x = y =⇒ x + y is even.
∀a, b ∈ R, (a ∈ Q ∧ b ∈ Q) =⇒ ab ∈ Q.
9. Suppose you have 2 pairs of positive real numbers whose products are
1. That is, you have (a, b) and (c, d) in R2 satisfying ab = cd = 1.
Prove that a < c implies that b > d.
3.4 Disproofs
Exercises — 3.4
The intent of the problem is that you find three numbers, a, b and
c, that are all powers of 2 and such that a divides the product bc, but
neither of the factors separately. For instance, if you pick a = 16, then
you would need to choose b and c so that 16 doesn’t divide evenly into
them (they would need to be less than 16. . . ) but so that their product
is divisible by 16.
1! = 1
2! − 1! = 1
3! − 2! + 1! = 5
4! − 3! + 2! − 1! = 19
et cetera
68 CHAPTER 3. PROOF TECHNIQUES I
Of course it turns out that going out to 8 isn’t quite far enough. . .
6. True or false: There are two irrational numbers whose sum is rational.
Prove your answer.
If a number is irrational, isn’t its negative also irrational? That’s
actually a pretty huge hint.
8. True or false: There are two irrational numbers whose product is ra-
tional. Prove your answer.
The two numbers could be equal couldn’t they?
So, essentially one just needs to compute the 4th powers of 1, 3, 5, 7, 9, 11, 13
and 15, and then reduce them modulo 16. An even greater economy is
possible if one notes that (modulo 16) many of those cases are negatives
of one another – so their 4th powers are equal.
2. Prove that every prime number other than 2 and 3 has the form 6q + 1
or 6q + 5 for some integer q. (Hint: this problem involves thinking
about cases as well as contrapositives.)
It is probably obvious that the ”cases” will be the possible remain-
ders mod 6. Numbers of the form 6q+0 will be multiples of 6, so clearly
not prime. The other forms that need to be eliminated are 6q+2, 6q+3,
and 6q+4.
If there are two pebbles on any node we will be able to reach all
the other nodes using pebbling moves (since every pair of nodes is
connected).
5. Find the pebbling number of a graph whose nodes are the corners and
whose edges are the, uhmm, edges of a cube.
9. The trichotomy property of the real numbers simply states that every
real number is either positive or negative or zero. Trichotomy can be
used to prove many statements by looking at the three cases that it
guarantees. Develop a proof (by cases) that the square of any real
number is non-negative.
By trichotomy, x is either zero, negative, or positive. If x is zero, its
square is zero. If x is negative, its square is positive. If x is positive,
its square is also positive.
3.5. BY CASES AND BY EXHAUSTION 73
1. Show that there is a perfect square that is the sum of two perfect
squares.
2. Show that there is a perfect cube that is the sum of three perfect cubes.
3. Show that the WOP doesn’t hold in the integers. (This is an existence
proof, you show that there is a subset of Z that doesn’t have a smallest
element.)
Consider the set {1, 1/2, 1/4, 1/8, . . .}. Does it have a smallest ele-
ment?
Unique existence proofs consist of two parts. First, just show exis-
tence. Then, show that if there were two of the things under consider-
ation that they must in fact be equal.
3.6. EXISTENTIAL STATEMENTS 75
scissors
cuts
paper
smashes
covers
rock
Sets
No more turkey, but I’d like some more of the bread it ate. –Hank Ketcham
1. What is the power set of ∅? Hint: if you got the last exercise in the
chapter you’d know that this power set has 20 = 1 element.
The power set of a set always includes the empty set as well as
the whole set that we are forming the power set of. In this case they
happen to coincide so P(∅) = {∅}. Notice that 20 = 1.
77
78 CHAPTER 4. SETS
7. Find a logical open sentence such that {0, 1, 4, 9, . . .} is its truth set.
Many answers are possible. Perhaps the easiest is ∃y ∈ Z, x = y 2 .
8. How many singleton sets are there in the power set of {a, b, c, d, e}?
“Doubleton” sets?
5, 10
P({a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p})?
16
8
= 12870
10. How many singleton sets are there in the power set of {1, 2, 3, . . . n}?
n
4.2. CONTAINMENT 79
4.2 Containment
Exercises — 4.2
6. Prove that the set of perfect fourth powers is contained in the set of
perfect squares.
It would probably be helpful to have precise definitions of the sets
described in the problem.
The fourth powers are
F = {x ∃y ∈ Z, x = y 4 }.
To show that one set is contained in another, we need to show that the
first set’s membership criterion implies that of the second set.
4.2. CONTAINMENT 81
Intersection Union
version version
Commutative
A∩B =B∩A A∪B =B∪A
laws
Associative A ∩ (B ∩ C) A ∪ (B ∪ C)
laws = (A ∩ B) ∩ C = (A ∪ B) ∪ C
Distributive A ∩ (B ∪ C) = A ∪ (B ∩ C) =
laws (A ∩ B) ∪ (A ∩ C) (A ∪ B) ∩ (A ∪ C)
Double
A = A same
complement
Identity
A∩U =A A∪∅=A
laws
Absorption A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A
82 CHAPTER 4. SETS
1. Let A = {1, 2, {1, 2}, b} and let B = {a, b, {1, 2}}. Find the following:
(a) A ∩ B
{b, {1, 2}}
(b) A ∪ B
{1, 2, a, b, {1, 2}}
(c) A \ B
{1, 2}
(d) B \ A
{a}
(e) A△B
{1, 2, a}
(a) A ∩ ♡
This is just the ace of hearts.
(b) A ∪ ♡
All of the hearts and the other three aces
(c) J ∩ (♠ ∪ ♡)
These two cards are known as the one-eyed jacks.
4.3. SET OPERATIONS 83
(d) K ∩ ♡
The king of hearts, a.k.a. the suicide king.
(e) A ∩ K
∅
(f) A ∪ K
Eight cards: all four kings and all four aces.
84 CHAPTER 4. SETS
(a) A ∩ B = A ∪ B
(b) A ∪ B = A ∪ (A ∩ B)
(c) A△B = (A ∪ B) \ (A ∩ B)
(d) (A ∪ B) \ C = (A \ C) ∪ (B \ C)
Here’s the first one (although I’m omiting justifications for each
step.
x∈A∩B
⇐⇒ ¬(x ∈ A ∩ B)
⇐⇒ ¬(x ∈ A ∧ x ∈ B)
⇐⇒ ¬(x ∈ A) ∨ ¬(x ∈ B)
⇐⇒ x ∈ A ∨ x ∈ B
⇐⇒ x ∈ A ∪ B
In = [−n, 1/n).
Find the union and intersection of all the intervals in this infinite family.
[
In =
n∈N
86 CHAPTER 4. SETS
\
In =
n∈N
To better understand what is going on, first figure out what the first
three or four intervals actually are.
I1 =
I2 =
I3 =
I4 =
6. There is a set X such that, for all sets A, we have X△A = A. What
is X?
One of the answers to the last two questions is ∅ and the other is
U . Decide which is which.
10. Prove the set-theoretic versions of DeMorgan’s laws using the technique
discussed in the previous problems.
Thus x ∈ B.
Now, we will show that B ⊆ A.
Suppose that x ∈ B.
..
.
Thus x ∈ A.
Therefore A ⊆ B ∧ B ⊆ A so we conclude that A = B.
Q.E.D.
Suppose x ∈ A△B.
Then, by definition, x ∈ (A \ B) ∪ (B \ A).
So, x ∈ (A ∩ B) ∪ (B ∩ A).
..
.
4.4. VENN DIAGRAMS 89
1. Let A = {1, 2, 4, 5}, B = {2, 3, 4, 6}, and C = {1, 2, 3, 4}. Place each
of the elements 1, . . . , 6 in the appropriate regions of a three-set Venn
diagram.
2. Prove or disprove:
(A ∩ C ⊆ B ∩ C) =⇒ A ⊆B
3. Venn diagrams are usually made using simple closed curves with no
further restrictions. Try creating Venn diagrams for 3, 4 and 5 sets (in
general position) using rectangular simple closed curves.
I found it easier to experiment by making my drawings on graph
paper. I never did manage to draw the 5 set Venn diagram with just
rectangles. . . probably just a lack of persistence.
Use rectilinear simple closed curves to create a Venn diagram for 5 sets.
Of course, rectangles are rectilinear, so one could use the solution
from the previous problem (if, unlike me, you were persistant enough to
find it). Otherwise, start with the 4 set diagram made with rectangles
and use your 5th (rectilinear) curve to split each region into 2 – don’t
forget to split the region on the outside too.
4.4. VENN DIAGRAMS 91
5. Argue as to why rectilinear curves will suffice to build any Venn dia-
gram.
Fortunately the instructions don’t say to prove that rectilinear curves
will always suffice, so we can be less rigorous. Try to argue as to why it
will alway be possible to add one more rectilinear curve to an existing
Venn diagram and split every region into two.
One might also argue that any continuous curve can be approximated
using rectilinear curves. So if a Venn diagram can be constructed using
continuous curves we can also get the job done with rectilinear curves.
8. The prototypes for the modus ponens and modus tollens argument
forms are the following:
All men are mortal. All men are mortal.
Socrates is a man. Zeus is not mortal.
and
Therefore Socrates is Therefore Zeus is not a
mortal. man.
Illustrate these arguments using Venn diagrams.
The statement “All men are mortal” would be interpreted on a Venn
diagram by showing the set of “All men” as being entirely contained
within the set of “mortal beings.” Socrates is an element of the inner
set. Zeus, on the other hand, lies outside of the outer set.
92 CHAPTER 4. SETS
(A ∩ B) ∪ (C ∩ D) ⊆ (A ∪ C) ∩ (B ∪ D).
10. Use Venn diagrams to show that the following set equivalence is false.
(A ∪ B) ∩ (C ∪ D) = (A ∪ C) ∩ (B ∪ D)
After constructing Venn diagrams for both sets you should be able
to see that there are 4 regions where they differ. One is A ∩ B ∩ C ∩ D.
What are the other three?
4.5. RUSSELL’S PARADOX 93
2. One way out of Russell’s paradox is to declare that the collection of sets
that don’t contain themselves as elements is not a set itself. Explain
how this circumvents the paradox.
If it’s not a set then it doesn’t necessarily have to have the property
that we can be sure whether an element is in it or not.
94 CHAPTER 4. SETS
Chapter 5
Proof techniques II —
Induction
The sum of the first several numbers in this sequence can be expressed
as a polynomial.
n
X
4j + 1 = 2n2 + 3n + 1
j=0
95
96 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
Pn
n 4j + 1
j=0 2n2 + 3n + 1
0 1 1
1 1+5=6 2 · 12 + 3 · 1 + 1 = 6
2 1+5+9= 15 2 · 22 + 3 · 2 + 1 = 15
3 1 + 5 + 9 + 13 = 28 2 · 32 + 3 · 3 + 1 = 28
4
2. What is wrong with the following inductive proof of “all horses are the
same color.”?
Theorem Let H be a set of n horses, all horses in H are the same
color.
Q.E.D.
3. For each of the following theorems, write the statement that must be
proved for the basis – then prove it, if you can!
4. Suppose that the rules of the game for PMI were changed so that one
did the following:
Explain why this would not constitute a valid proof that Pn holds for
all natural numbers n. How could we change the basis in this outline
to obtain a valid proof?
In this modified version, P (0) is not going to imply P (1), and in fact,
none of the odd numbered statements will be proven. If we change the
basis so that we prove both P (0) and P (1), all the even statements will
be implied by P (0) being true and all the odd statements get forced
because P (1) is true.
∀z ∈ Z, Pz ,
1. Write an inductive proof of the formula for the sum of the first n cubes.
Theorem.
n 2
X
3 n(n + 1)
∀n ∈ N, k =
k=1
2
n
X
k3 = 1
k=1
and
2
n(n + 1)
= 1.
2
Inductive step:
Suppose that m > 1 is an integer such that
m 2
X
3 m(m + 1)
k =
k=1
2
m 2
3
X
3 m(m + 1)
(m + 1) + k = + (m + 1)3 .
k=1
2
Thus
100 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
m+1
m2 (m + 1)2 4(m + 1)3
X
3
k = +
k=1
4 4
2
m (m + 1)2 + 4(m + 1)3
=
4
2 2
(m + 1) (m + 4(m + 1))
=
4
(m + 1)2 (m2 + 4m + 4)
=
4
(m + 1) (m + 2)2
2
=
4
2
(m + 1)(m + 2)
=
2
Q.E.D.
n · (n + 1) · (2n + 1) · (3n2 + 3n − 1)
30
3. The sum of the first n natural numbers is sometimes called the n-th
triangular number Tn . Triangular numbers are so-named because one
can represent them with triangular shaped arrangements of dots.
Determine
! a formula for the sum of the first n triangular numbers
Xn
Ti and prove it using PMI.
i=1
n(n+1)(n+2)
The formula is 6
.
1
1 − 4 = −3
1−4+9=6
1 − 4 + 9 − 16 = −10
et cetera
Pn i−1 2
Guess a general formula for i=1 (−1) i, and prove it using PMI.
Theorem.
n
X n(n + 1)
∀n ∈ N, (−1)i−1 i2 = (−1)n−1
i=1
2
n
X
(−1)i−1 i2 = 1
i=1
and also
n(n + 1)
(−1)n−1 = 1.
2
Inductive step:
Suppose that k > 1 is an integer such that
102 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
k
X k(k + 1)
(−1)i−1 i2 = (−1)k−1 .
i=1
2
k+1
X k(k + 1)
(−1)i−1 i2 = (−1)k−1 + (−1)k (k + 1)2
i=1
2
k(k + 1)
= (−1)k−1 − (−1)k−1 (k + 1)2
2
k(k + 1) 2(k + 1)2
k−1
= (−1) −
2 2
2
k 2(k + 1) k(k + 1)
= (−1) −
2 2
(k + 1)(2(k + 1) − k)
= (−1)k
2
(k + 1)(k + 2)
= (−1)k
2
Q.E.D.
n
Y 1 1
1− =
i=2
i n
Notice that the problem statement didn’t specify the domain – but
the smallest value of n that gives a non-empty product on the left-hand
side is n = 2.
5.2. FORMULAS FOR SUMS AND PRODUCTS 103
2
Y 1 1
1− = 1− = 1/2
i=2
i 2
k
Y 1 1
1− = .
i=2
i k
Then,
k+1
Y
1
1−
i=2
i
Y k
1 1
= 1− · 1−
k+1 i=2
i
1 1
= 1− ·
k+1 k
1
= .
k+1
Q.E.D.
The final line skips over a tiny bit of algebraic detail. You may feel
more comfortable if you fill in those steps.
104 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
n
X
6. Prove (4j + 1) = 2n2 + 3n + 1 for all integers n ≥ 0.
j=0
n
X
(4j + 1) = (4 · 0 + 1 = 1
j=0
also, when n = 0,
2n2 + 3n + 1 = 2 · 02 + 3 · 0 + 1 = 1.
Inductive step:
k
X
(4j + 1) = 2k 2 + 3k + 1.
j=0
k+1
X
(We want to show that (4j +1) = 2(k+1)2 +3(k+1)+1.)
j=0
k+1
X
So consider the sum (4j + 1):
j=0
5.2. FORMULAS FOR SUMS AND PRODUCTS 105
k+1
X
(4j + 1)
j=0
k
X
= 4(k + 1) + 1 + (4j + 1)
j=0
= 4(k + 1) + 1 + 2k 2 + 3k + 1
Q.E.D.
Notice that the last line given in the proof is where the inductive hy-
pothesis gets used. The actual last line of the proof is fairly easy to
determine (hint: it is given in the ”We want to show” sentence.) So
now you just have to fill in the gaps. . .
n
X 1 n
7. Prove = for all natural numbers n.
i=1
(2i − 1)(2i + 1) 2n + 1
n
X 1
j=0
(2i − 1)(2i + 1)
n
And, also evaluates to 0 when n = 0.
2n + 1
Inductive step:
By the inductive hypothesis we may write
k
X 1 k
= .
i=1
(2i − 1)(2i + 1) 2k + 1
1
Adding to both side of this gives
(2(k + 1) − 1)(2(k + 1) + 1)
k+1
X 1 k 1
= + .
i=1
(2i − 1)(2i + 1) 2k + 1 (2(k + 1) − 1)(2(k + 1) + 1)
k 1 k+1
+ = .
2k + 1 (2(k + 1) − 1)(2(k + 1) + 1) 2(k + 1) + 1
Note that
k 1
+
2k + 1 (2(k + 1) − 1)(2(k + 1) + 1)
k 1
= +
2k + 1 (2k + 1)(2k + 3)
k(2k + 3) 1
= +
(2k + 1)(2k + 3) (2k + 1)(2k + 3)
k(2k + 3) + 1
=
(2k + 1)(2k + 3)
2k 2 + 3k + 1
=
(2k + 1)(2k + 3)
(2k + 1)(k + 1)
=
(2k + 1)(2k + 3)
k+1 k+1
= =
2k + 3 2(k + 1) + 1
5.2. FORMULAS FOR SUMS AND PRODUCTS 107
as desired.
Q.E.D.
Fn+2 = Fn + Fn+1
The first two Fibonacci numbers (actually the zeroth and the first) are
both 1.
Thus, the first several Fibonacci numbers are
n
X
(Fi )2 = Fn · Fn+1
i=0
n
X
(Fi )2 = 1.
i=0
And, Fn · Fn+1 = F0 · F1 = 1 · 1 = 1.
Inductive step:
108 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
k
X
(Fi )2 = Fk · Fk+1 .
i=0
k+1
X
(Fi )2 = Fk · Fk+1 + (Fk+1 )2 .
i=0
Fk · Fk+1 + (Fk+1 )2
= Fk+1 · (Fk + Fk+1 )
= Fk+1 · Fk+2
So the inductive step has been proved and the result follows
by PMI.
Q.E.D.
5.3. OTHER PROOFS USING PMI 109
1. ∀x ∈ N, 3 | x3 − x
(k + 1)3 − (k + 1)
= (k 3 + 3k 2 + 3k + 1) − (k + 1)
= (k 3 − k) + (3k 2 + 3k).
(k + 1)3 − (k + 1) = 3q + 3k 2 + 3k = 3 · (q + k 2 + k).
110 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
Q.E.D.
2. ∀x ∈ N, 3 | x3 + 5x
3. ∀x ∈ N, 11 | x11 + 10x
4. ∀n ∈ N, 3 | 4n − 1
5. ∀n ∈ N, 6 | (3n2 + 3n − 12)
7. ∀n ∈ N, 4 | (13n + 4n − 1)
8. ∀n ∈ N, 7 | 8n + 6
9. ∀n ∈ N, 6 | 2n3 − 2n − 12
12. ∀n ≥ 3 ∈ N, n3 + 3 > n2 + 3n + 1
13. ∀x ≥ 4 ∈ N, x2 2x ≤ 4x
5.4. THE STRONG FORM OF MATHEMATICAL INDUCTION 111
∀n ∈ N, n ≥ 12 =⇒ ∃x, y ∈ N, n = 3x + 7y.
2. Show that any integer postage of 12 or more can be made using only
4 and 5 stamps.
√
1+ 5
3. The polynomial equation x2 = x + 1 has two solutions, α = 2
and
√
1− 5
β= 2
. Show that the Fibonacci number Fn is less than or equal to
n
α for all n ≥ 0.
112 CHAPTER 5. PROOF TECHNIQUES II — INDUCTION
Chapter 6
6.1 Relations
Exercises — 6.1
113
114 CHAPTER 6. RELATIONS AND FUNCTIONS
4. The “socks and shoes” rule is a very silly little mnemonic for remem-
bering how to invert a composition. If we think of undoing the process
of putting on our socks and shoes (that’s socks first, then shoes) we
have to first remove our shoes, then take off our socks.
The socks and shoes rule is valid for relations as well.
Prove that (S ◦ R)−1 = R−1 ◦ S−1 .
6.2. PROPERTIES OF RELATIONS 115
2. Consider the relation A defined by A = {(x, y) x has the same astrological sign as y}.
Is A symmetric or anti-symmetric? Explain.
3. Explain why both of the relations just described (in problems 1 and 2)
have the transitive property.
4. For each of the five properties, name a relation that has it and a relation
that doesn’t.
6. Prove that “|” is an ordering relation (you must verify that it is reflexive,
anti-symmetric and transitive).
116 CHAPTER 6. RELATIONS AND FUNCTIONS
w1 Aw2 ⇐⇒ w1 is an anagram of w2 .
4. The two diagrams below both show a famous graph known as the Pe-
tersen graph. The picture on the left is the usual representation which
emphasizes its five-fold symmetry. The picture on the right highlights
the fact that the Petersen graph also has a three-fold symmetry. Label
the right-hand diagram using the same letters (A through J) in order
to show that these two representations are truly isomorphic.
6.3. EQUIVALENCE RELATIONS 117
F
E B
J G
I H
D C
5. We will use the symbol Z∗ to refer to the set of all integers except 0.
Define a relation Q on the set of all pairs in Z × Z∗ (pairs of integers
where the second coordinate is non-zero) by (a, b)Q(c, d) ⇐⇒ ad =
bc. Show that Q is an equivalence relation.
6. The relation Q defined in the previous problem partitions the set of all
pairs of integers into an interesting set of equivalence classes. Explain
why
Q = (Z × Z∗ )/Q.
7. Reflect back on the proof in problem 5. Note that we were fairly careful
in assuring that the second coordinate in the ordered pairs is non-zero.
(This was the whole reason for introducing the Z∗ notation.) At what
point in the argument did you use this hypothesis?
118 CHAPTER 6. RELATIONS AND FUNCTIONS
Fox Alligator
Cow
Duck Robin
Goose
Grass Worms
1. An (non-maximal) an-
tichain a. Grass
6.5 Functions
Exercises — 6.5
1. For each of the following functions, give its domain, range and a possible
codomain.
2. Find a bijection from the set of odd squares, {1, 9, 25, 49, . . .}, to the
non-negative integers, Znoneg = {0, 1, 2, 3, . . .}. Prove that the function
you just determined is both injective and surjective. Find the inverse
function of the bijection above.
Z x
1
ln(x) = dt.
t=1 t
From this definition we can deduce that ln(x) is strictly increasing on
its entire domain, (0, ∞). Why is this true?
We can use the above definition with x = 2 to find the value of ln(2) ≈
.693. We will also take as given the following rule (which is valid for
all logarithmic functions).
ln(ab ) = b ln(a)
122 CHAPTER 6. RELATIONS AND FUNCTIONS
Use the above information to show that there is neither an upper bound
nor a lower bound for the values of the natural logarithm. These facts
together with the information that ln is strictly increasing show that
Rng(ln) = R.
0 1 2 3 4 5 6 7 8
1 0/1 1/1 2/1 3/1 4/1 5/1 6/1 7/1 8/1
2. The usual algebraic procedure for inverting T (x) = (x2 +x)/2 fails. Use
your knowledge of the geometry of functions and their inverses to find
a formula for the inverse. (Hint: it may be instructive to first invert
the simpler formula S(x) = x2 /2 — this will get you the right vertical
scaling factor.)
3. What is π2 (W (t))?
10
X 1
· [i is prime].
i=1
i
126 CHAPTER 6. RELATIONS AND FUNCTIONS
Chapter 7
7.1 Counting
1. Determine the number of entries in the following sequences.
2. How many “full houses” are there in Yahtzee? (A full house is a pair
together with a three-of-a-kind.)
127
128 CHAPTER 7. PROOF TECHNIQUES III — COMBINATORICS
6. How many “words” are there of length 4, with distinct letters from the
Cryptographer’s alphabet, in which the letters appear in increasing
order alphabetically? (“Acef” would be one such word, but “cafe”
would not.)
10. How many functions are there from a set of size n to a set of size m?
11. How many relations are there from a set of size n to a set of size m?
7.2. PARITY AND COUNTING ARGUMENTS 129
2. Complete the proof of the fact that “Every graph has an even number
of odd nodes.”
5. The five tetrominoes (familiar to players of the video game Tetris) are
relatives of dominoes made up of four small squares.
1. The statement that there are two non-bald New Yorkers with the same
number of hairs on their heads requires some careful estimates to justify
it. Please justify it.
2. A mathematician, who always rises earlier than her spouse, has de-
veloped a scheme – using the pigeonhole principle – to ensure that
she always has a matching pair of socks. She keeps only blue socks,
green socks and black socks in her sock drawer – 10 of each. So as
not to wake her husband she must select some number of socks from
her drawer in the early morning dark and take them with her to the
adjacent bathroom where she dresses. What number of socks does she
choose?
4. Given any set of 53 integers, show that there are two of them having
the property that either their sum or their difference is evenly divisible
by 103.
5. Prove that if 10 points are placed inside a square of side length 3, there
√
will be 2 points within 2 of one another.
3. Find (x2 + y 2 )6 .
1 1
1
2 1
1
2
2 1
3 1
3
1 3
6
3 3
3 1
combinatorially.
n
n
X n
∀n ∈ N, ∀x, y ∈ R, (x + y) = xn−k y k
k=0
k
136 CHAPTER 7. PROOF TECHNIQUES III — COMBINATORICS
Chapter 8
Cardinality
137
138 CHAPTER 8. CARDINALITY
3. Prove that any two circles are equinumerous (as sets of points).
6. Verify that the final deduction in the proof of Cantor’s theorem, “(y ∈
S =⇒ y ∈
/ S) ∧ (y ∈
/ S =⇒ y ∈ S),” is truly a contradiction.
8.4. DOMINANCE 141
8.4 Dominance
Exercises — 8.4
c c c
b⋆⋆ a⋆ b⋆ a⋆⋆
c⋆ c⋆
b ⋆ a⋆
c⋆⋆ b
a
a b
a b
143
144 CHAPTER 9. PROOF TECHNIQUES IV — MAGIC
1. Do the algebra (and show all your work!) to prove that invariant de-
fined in this section actually has the value 1 for the set of all the men
occupying the x-axis and the lower half-plane.
1. There is a scenario where the proof we have sketched for Monge’s circle
theorem doesn’t really work. Can you envision it? Hint: consider two
relatively large spheres and one that is quite small.