264 CHAPTER 4 Functions
- Construct a sequence of 16 integers that has no increasing or decreasing subsequence
of five elements. - During a month with 30 days, a team will play at least one game a day but no more
than 45 games in all 30 days. Show that there is a stretch of consecutive days during
which the team plays exactly 14 games. (Hint: Let ai be the number of games played
on or before the ith day for 1 < i < 30.) - A widget-maker makes at least one widget every day but not more than 730 widgets
in a year. Given any n, show that the widget-maker makes exactly n widgets in some
set of consecutive days. For some n, it may take more than a single year. - A student has 37 days to prepare for an exam. From past experience, he knows that
he will need no more than 60 hours of study. To keep from forgetting the material,
he wants to study for at least one hour each day. Show that there is a sequence of
successive days during which he will have studied exactly 13 hours. - For any four integers, none of which is even and none of which is a multiple of
5, prove that some consecutive product of these ends in the digit 1. A consecutive
product is one term, two terms in a row, three terms in a row, or all four terms. For
example, for the four integers a, b, c, and d a consecutive product would be a • b but
not a .c. (Hint: Prove that if b c, b- c- d do not end in a 1, and if there is no integer
ending in 1 among a, b, c, and d, then a, a. b, a. b c, and a- b. c- d are all distinct.
Use Theorem 3 in Section 4.6.2). - Select 100 integers from the integers 1, 2 ... , 200 such that no one of the chosen
values is divisible by any other chosen value. Show that if one of the 100 integers
chosen from 1, 2,..., 200 is less than 16, then one of those 100 numbers is divisible
by another.- Prove the assertion in Example 4(c).
22. (a) Find two functions F, G : N - N that are 1-1 but not onto.
(b) Find a function G : N --* N that is onto but not 1-1.
(c) Challenge: Suppose G : N -* N is onto but not 1-1, and suppose G is specified
by an algorithm A. Show that there is an algorithm A' that computes a functionF : N - N, where G o F = IdN. Also, show that F must be 1-1 but not onto. We
have not been precise about what an "algorithm" is; you might choose to interpret
an "algorithm" as being a function written in some programming language. (Hint:
A' can use A as a subprogram.)- Infinite Pigeon-Hole Principle: Suppose X is an infinite set and Y is a finite set. Now,
suppose F : X -* Y. Show there is a y c Y such that for infinitely many x E X such
that F(x) = y.W Countable and Uncountable Sets
In this section, we develop the notion of counting the elements of a set or cardinality more
carefully. The modem notion of cardinality is credited to Georg Cantor (1845-1918, b.
Russia), who found an abstract notion of counting that enabled mathematicians to speak
of the cardinality of an infinite set. The notion also enabled mathematicians to discuss the