Assignment 1
MA 375 Homework 1 Solutions
Section 4.1:
50: The claim is true if n=1 because if you pick 2 numbers from the
set {1,2} then it is easy to see that there are 2 chosen
numbers that divide each other. (Generally, if 2 equal numbers
are chosen this is true trivially, and if you choose 2 distinct
ones an easy check shows that the claim is ok.)
Now assume the claim is true for n+1 numbers chosen from
{1,2,...,2n} and let's try to show it stays true if we pick n+2
numbers from {1,...,2n+2}.
Again, if there are 2 equal numbers there is nothing to prove
really, so let's suppose all the chosen numbers are distinct. If
all, or just n+1 of the n+2 chosen numbers are in the smaller set
{1,2,...,2n} then the inductive hypothesis helps us out to
conclude that there are 2 chosen ones that divide each other. So
let's consider the case where 2n+1, 2n+2 and n of the numbers
{1,2,...,2n} are chosen.
Clearly, if in this situation n+1 is also a chosen number we are
done because n+1 divides 2n+2. So assume that n+1 is not chosen.
Let C be the chosen numbers that are less than 2n+1; there are n
of these. Consider the set D which is C together with the number
n+1. D contains n+1 distinct numbers, and they are all in
{1,2,...,2n}. By the inductive hypothesis, D contains 2 numbers A
and B which divide each other. If neither A nor B are equal to
n+1, then C contains both A and B and so A and B are both chosen
numbers and we are done.
Finally, we inspect the case where either A or B is n+1. The
other number is then either a divisor or a multiple of n+1. It
can't be a multiple because the smallest multiple would be 2(n+1)
which is bigger than 2n+1 and hence not in C. It follows that C
contains a divisor of n+1. Of course, n+1 is not a chosen number,
so that this divisor does not seem to be helpful. However,
2*(n+1)=2n+2 IS a chosen number, and a divisor of n+1 is also a
divisor of 2n+2. So even in this worst of all cases there are 2
chosen numbers that divide each other.
This completes the inductive step and the proof.
64: If there are 2 people you can find out with 2 questions whether
there is a celebrity and 2 is no more than 3(2-1)=3. Suppose now
there are n+1 people. Fist ask "does A know B?" with arbitrary A,
B. If "yes" then A is not a celebrity, if "no" then B is not. In
either case, one person (let's call him E) has been eliminated
from being one. Now by induction one can find out with at most
3(n-1) questions if there is a celebrity among the remaining n
people. If there is none, there isn't one in the big set
either. If there _is_ one between the n people (let's call him C),
in order to confirm C as celebrity between all n+1 people, you
still have to check that E knows C and that C does not know
E. This uses at mot 1+3(n-1)+2=3(n+1-1) questions.
54: The proof breaks down at the point where they write
a^(k+1) = a^k*a^k/a^(k-1).
The equation is true, but k-1 is not necessarily a nonnegative
integer, even if k is a nonnegative integer. (Specifically, if
k=0, which is a nonnegative integer, then k-1=-1 is not
nonnegative!) Therefore we cannot use the inductive hypothesis on
-1. And so the proof fails.
8: Note that 2-2*7+2*7^2-...+2*(-7)^n = sum 2*(-7)^i
i=0
Let P(n) be the statement
" 2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4 ".
Armed with this we see that the base case n=0 is true:
(1-(-7)^1)/4 = (1+7)/4 =2.
Now assume that P(n) is true. Then
2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4
and hence
2-2*7+2*7^2-...+2*(-7)^n +2*(-7)^(n+1)=(1-(-7)^(n+1))/4+2*(-7)^(n+1).
=[(1-(-7)^(n+1))+8*(-7)^(n+1)]/4
=[1+(-7)^(n+1)*(-1+8)]/4
=[1+(-7)^(n+1)*(7)]/4
=[1-(-7)^(n+1)*(-7)]/4
=[1-(-7)^(n+2)]/4
which is exactly what we had to show: P(n+1) is true.
6: Let P(n) be "1*1! + 2*2! + ...+ n*n! = (n+1)! -1".
The base case is easy.
Assume P(n). Then
1*1! + 2*2! + ...+ n*n! + (n+1)*(n+1)! = (n+1)! -1 +(n+1)*(n+1)!
by the inductive hypothesis
= (n+1)! *[1+n+1] -1
= (n+2)! -1.
This is precisely what P(n+1) says.
20: Let P(n)= " 3^n < n! for all n>6.
The base case is n=7, the first number bigger than 6.
There we have 3^7= 2187 and 7!=5040. So, ok.
No assume P(n). Then
3^(n+1) = 3^n * 3
< n! * 3 (by inductive hypothesis)
< n! * 4
< n! * 5
...
< n! *(n+1)
= (n+1)!.
That is what P(n+1) says.
32: Base case n=0 is true. 3 divides 0.
(n+1)^3 +2*(n+1) = n^3 + 3*n^2 + 3*n + 1 + 2*n + 2
= n^3 + 2*n + 3*(n^2+n+1)
By inductive hypothesis, n^3+2*n is a multiple of 3. Obviously,
3*(n^2+n+1) is also a multiple of 3. Hence their sum is a multiple
of 3. TRhis sum equals (n+1)^3 +2*(n+1), hence P(n+1) holds.
49: The problem is that even though x and y are positive integers, the
numbers x-1 and y-1 may not be. That means, that we cannot use the
inductive hypothesis on x-1 and y-1.
To see an explicit example how the proof fails, note first that
the base case is ok: if you have 2 positive numbers x, y and their
maximum is equal to 1, then they are both equal, x=y=1.
If now we look at the next case, k=2, we could have x=1 and
y=2. Their max is 2, and yet they are not equal. So with this
choice of x and y the proof must fail. It does the moment that you
try to use the "fact" that since x-1 and y-1 have max equal to 1
then they must be equal. This is an attempt of using the inductive
hypothesis in the wrong way: since x=1, x-1 is NOT positive. So
the base case (which only considers positive numbers) does not
apply.
And indeed, x-1=0 and y-1=1 are not equal.
7.5:
6: a) 10000 since adding A1 and A2 to A3 does not give anything that
was not already in A3.
b) 11100 since there is no overlap of the sets.
c) If we just add them altogether, we get 11100. However, there are
two elements in A1 intersection A2 that we counted twice, once for
A1 and once for A2. So we should subtract them from
11100. Similarly we double counted the 2 elements common to A1 and
A3, and the two elements common to A2 and A3.
So the corrected count is 11100 - 6.
Now however we made another mistake: there is one element that was
in A1 and A2 and A3. This was counted 3 times in the sum 11100, and
then taken out 3 times as one of the two elements in the corrected
sum. So in the mumber 11100-6 it is not counted at all! Let's put
it back in, then we get 11095.
The general formula is written down on top of page 454. It comes
from the double counting considerations we just went through.
12: There are 1000 integers not exceeding 1000. Of these, the squares
of 1,2,...,31 are squares. Also, there are the 10 cubes
1,2^3,...,10^3.
There are 3 numbers that are simultaneously squares and cubes: 1, 64
and 729. 1=1^2=1^3, 64=4^3=8^2, 729=27^2=9^3.
Let A2 be the set of all squares, it has 31 elements. Let A3 be
the set of all cubes, it has 10 elements. There are 3 in both, so
the union of A2 and A3 has 31+10-3 = 38 elements.
20: 10000+10000+10000+10000+10000
-1000-1000-1000-1000-1000-1000-1000-1000-1000-1000
+100+100+100+100+100+100+100+100+100+100
-10-10-10-10-10
+1
(there are 5 sets, 10 2-fold intersections, 10 3-fold
intersections, 5 4-fold intersections and 1 5-fold interesection)
28: The interesection of all pairs of events is empty. So the union of
all n events has exactly as many elements as the sum of all the
separate events. So the probability of the union of the n events
is the sum of the n probabilities -- no fudge terms are required
since there is no overcounting.