(For problems 1, 2 and 5, use the general approach to proving existence-
and-uniqueness theorems, as in the proof of the unique factorization theorem,
for example)
1. (advice: do problem 2 before this one!) (a) Prove that every positive
integer n can be written as
n = at 10t +:::+a1 10 +a0;
where the ai’s are integers such that 0 ai 1. How does your proof break down in the case q = 0? What about the
case q = 1?
2. Prove that for each number n, there is a unique integer r and unique
integers a1;:::;ar such that 0 ai i, ar is non-zero, and
n = r! ar + (r 1)! ar 1 +:::+ 1! a1:
3. Let x and y be positive real numbers and consider the binomial ex-
pansion (x + y)n = Pk nk xkyn k. For what k is nk xkyn k the largest?
This k depends on x, y and n: write k = k(x;y;n). Compute the limit of
k(x;y;n)=n as n tends to in nity. (Imagine that n is very large (like 100),
and illustrate term k with a black dot at k=n in the interval [0;1]. The limit
you computed is the location of the largest term!)
4. Let q, w and N be positive integers such that q 0, f(k)(x) = x.)
Hint: Do an example rst. Pick a small n, and any function f on
f1;2;:::;ng. Illustrate the situation by drawing n dots labelled i for i =
1;:::;n, and an arrow from the dot labelled i to the dot labelled f(i) for
each i. Which i belong to cycles of your f? What does the algorithm do in
the picture?
16(*). Let m and n be positive integers. Consider all functions from
f1;:::;mg to f1;:::;ng.
(a) How many such functions are there in total?
(b) How many of these functions are injective?
(Give your answers as functions of m;n, and prove that they are correct.)
3
17(*). [Exercise 2.3.11 in the book] Show that the set P(X) of subsets
of a nite set X has size jP(X)j= 2jXj.
18(*). How many numbers inf1;:::;10000gare divisible by at least one
of 2;3 and 5?
19. In this exercise we consider automata over the alphabet f0;1g.
Show that there is no automaton whose set of accepted sequences is fs :
s has at least as many ones as zerosg.
(Hint: Argue by contradiction: suppose M is such an automaton. Show
that the state reached by M with input 0:::0|{z}
r
has to be distinct for all
r. Prove this again by contradiction: suppose the state reached with input
0:::0|{z}
r
and the state reached with input 0:::0|{z}
s
are the same, and r0 ! R be given by f(x) = 1=x and g(x) =
1 x. How many di erent functions can you get by composing f and g
repeatedly? (Equivalently, how many distinct functions are there among
f;g;fg;gf;fgf;ffg;fggf;:::?)
24(*). Suppose R is a partial order on the set X, and de ne a new
relation S on X by letting aSb if aRb and bRa. Show that S is an equivalence
relation.
25(*). Let X be the set of subsets of f1;2;3;4;5g and consider the
function f : X ! X, de ned by f(x) = xc4f1;4g. (Recall that for sets
A;B, we de ne the symmetric di erence by A4B = (AnB)[(BnA). We
denote the complement of a set x by xc.) Find the inverse f 1 of f.
4
26(*). De ne a relation R on the set of positive integers N, as follows.
For x;y 2 N, we say that xRy if for every nonzero binary digit in x, the
corresponding binary digit in y is nonzero. Show that R is a partial order.
27. How many permutations of [n] are such that 1 and 2 are in the same
cycle? (Hint: write the permutation in the disjoint cycle representation.)
28. Show that every permutation of [n] can be written as a product of (12)
and (12:::n) in some order (allowing repetitions). (Hint: rst show that
every permutation can be written as a product of adjacent transpositions
(ii + 1). Then show that each adjacent transposition can be written as a
product of the two cycles above (in some order, allowing repetitions).)
29. Suppose u = (12:::n). Which cycles v of [n] are such that v(x)6= x
for all x2[n] and uv = vu?
30. Let = 1::: n be a permutation and 0 = n::: 1 its reverse
permutation. Show that sgn( 0) = sgn( ) or sgn( ) if n2 is odd or n2 is
even respectively.
31. For what n is n2 even? Prove your claim.
32. What values of o( ) (the order of ) are possible for a permutation
of length 6?
33. Let G = (R3; ) where is the vector cross product. Is G a
group? (For vectors (a;b;c) and (d;e;f), the vector cross product is de ned
by (a;b;c) (d;e;f) = (bf ce;cd af;ae bd).)
34. Given a nonnegative integer n, let G be (a) the set of even permuta-
tions of [n], or (b) the set of odd permutations of [n]. In both cases let the
group operation be given by composition of functions. Is G a group?
35. Let R be a ring such that x2 = x for all x2R. Show that 2x = 0
for all x2R. (By 2x we mean x+x.)
36. [Exercise 4.3.4 in the book] Let G be a group and c2G. De ne by
letting a b = ac 1b. Show that the set G with the operation is a group.