CSC 201 - Discrete Math for
Professor Shai Simonson
Due: Monday, October 2.
Section 4.2: Problems: 2a-c,
4a-d, 26, 40. Section 4.3: Problems 33c-d.
Section 4.4: Problems 2, 4, 9, 12, 37
Section 4.6: 24.
Section 5.1: Problems 6, 7, 11, 16, 18, 32, 49, 51.
- Prove by induction that 2n>n2 for all integers n larger than 4.
- Take any integer n,
and partition it in two parts each greater than zero. For
example 16 might be partitioned into 3 and 13. Calculate
the product of the two numbers, in this case 39. Repeat
this process with each of the two numbers, until you are down to
1, keeping track of the sum of all the products. For
example, if you start with 7, then you could get 3 and 4.
Three becomes 1 and 2. Four becomes 2 and 2. The
two's all become 1 and 1. This gives: 12 + 2 + 4 + 1
+ 1 + 1 = 21. Make a conjecture about the relationship of
this sum to n. Prove
your conjecture by induction.
- Prove that the square root of 3 is irrational using
Aristotle/Hipassus’ techniques. Make sure to prove the
- Compute by hand, the smallest positive integers x, y,
v such that ax-by
= bu-av = gcd(a,b)
for each pair a, b below. Use
the Euclidean algorithm and back tracking. (i) 99,
101 (ii). 36, 42
- Prime Numbers: How many distinct divisors are there for
pa, where p is a prime?
Prove your conjecture by induction on a. How
many distinct divisors are there for an arbitrary number m? Hint: Factor m into its prime factors so that m
, and prove your answer by induction on n,
the number of distinct prime factors. Use the first part of this
question as your base case.
- RSA encryption. Let p=13
and q=11. Calculate an appropriate public code,
and private code for doing RSA encrypting.
Assuming that each character in a message is represented by its
ASCII value (an assigned table of integers from 0 to 127, can be
found in many texts), encode the message “Too much work!” by
encoding each ASCII value one at a time.
- If I want to send you something securely so that you know it
came from me and I know that only you received it, I can
put it in a box and lock the box keeping the only key in my
pocket. When you receive the box, you add your own lock to
it and send it back to me. I then remove my lock and
return the box once again to you, at which point you open your
own lock to get at the contents. Explain how to get this
effect electronically using RSA. Recall that RSA can be used for
encryption or authorization.
- Guess the number of different ways for n people to
arrange themselves in a straight line, and prove your guess is
correct by induction.
- Euclid proved that there is an infinite number of primes, by
assuming that n is the highest prime, and exhibiting a
number that he proved must either be prime itself, or else have
a prime factor greater than n. Find the smallest n
for which Euclid’s proof does not provide an actual
prime number. (You can write a program to find it if you like).
- In Stonehill-ball, you can score 11 points for a goal, and 7
for a near miss. Prove by induction that you can achieve any
score greater than or equal to 60. Hint:
Try to add one point to your score by adding/subtracting
multiples of a and b. We did this in class
with 2 cent and 3 cent coins. Extra
Credit: Prove that in general that if a and
b are relatively prime, you can get any score greater
than or equal to (a-1)(b-1) where a and b are the two point values
(in our example a = 7
and b =11).
- Guess a formula (or just look around the internet) for the sum
below, and prove you are right by induction.
1(2) + 2(3) + 3(4) + … + n(n+1)