Integer Operations & Representation
What is the quotient and remainder when we divide -136 by 21?
q = -7, r = 11
Describe the difference between PMI (principle of mathematical induction) and strong induction. Give an example of a scenario in which you would want to use strong induction over PMI.
For PMI, in our inductive assumption, we assume the statement is true for n=k. For strong induction, in our inductive assumption, we assume the statement is true for i<=k.
How many 6-element DNA sequences… (note: DNA elements can be either A, T, C, or G only)
Do not contain A?
End with CG?
1. 36 = 729
2. 44 = 256
My sock drawer contains 14 pairs of socks. 6 of these pairs are white, 4 pairs are black, and the remaining pairs have cats on them. None of my socks are paired in the drawer.
How many socks do I have to take out to ensure I get at least two cat socks (one pair)?
22
Evaluate the following:
(1011)2 * (1110)2
(1011)2 * (1110)2 = (1001 1010)2
Suppose we want to prove by PMI that 6 divides n3−n whenever n is a nonnegative integer.
Complete the base case and inductive assumption.
Base case: n=1; 13–1 = 0, 6*0 = 0. Thus by definition, 0 is divisible by 6.
Inductive assumption: Assume for n=k there exists an integer a such that k3–k=6a.
How many numbers between 101 and 901 (inclusive of endpoints) are divisible by 6?
900-102/6 + 1= 134
What is the coefficient of x42y9 in (x + y)51?
C(51, 9)
Are 8924 and 272 relatively prime? If not, find their GCD.
gcd(8924, 272) = 4.
Suppose we want to prove by PMI that the following is true for all integers n>0. Complete the inductive assumption and inductive step (skip base case).
31+32+...+3n = (3n+1–3)/2.
Inductive assumption: Assume for n=k that 3+32+...+3k=(3k+1–3)/2 is true.
Inductive step: Show for n=k+1 that 3+32+...+3k+3k+1=(3k+2–3)/2 is true.
3+32+...+3k+3k+1 = (3k+1–3)/2 + 3k+1 = (3k+1–3)/2 + (2 *3k+1)/2 = (3*3k+1–3)/2 = (3k+2–3)/2. Proved by PMI.
How many passwords of only made up of 8 lowercase english alphabet letters either start with "a" or end with "xy" if letters can be repeated.
Do not simplify, just set the problem up!
267 + 266 – 265
What is the smallest number of students that must be enrolled in a given course to guarantee that at least 10 of the students share a birthday month?
109 students.
Convert (3672)8 to decimal.
(1978)10
Prove that for all n>0,
1*1! + 2*2! +...+ n*n! = (n+1)! – 1
BC: n=1: LHS: 1*1! = 1, RHS: (1+1)!–1=2–1=1, LHS=1=RHS.
IA: Assume for n=k that 1*1! + 2*2! +...+ k*k! = (k+1)! – 1 is true.
IS: Show that for n=k+1, 1*1! + 2*2! +...+ k*k! + (k+1)(k+1)! ?= (k+2)! – 1
One hundred tickets, numbered 1, 2, 3, ... , 100, are sold to 100 different people for a drawing. Four different prizes are awarded, including a grand prize. How many ways are there to award the prizes if the person holding ticket 42 wins the grand prize?
C(1, 1) * P(99, 3)
Find the closest big-O bound for f. Prove your solution is correct by finding c and k.
f(x) = (2x3 - x2)(3 + x4)
f(x) is O(x7). Possible solution: c = 8 and k = 1
Find (87 mod 15)4 mod 11.
Use mod theorems & show your work!
5
Prove by strong induction that for all integers n>7, n can be expressed as a sum of 3s and 5s.
Base case: n=8=3+5, n=9=3*3, and n=10=5*2
Inductive assumption: Assume for 8<= i <=k that i can be represented by a sum of 3s and 5s s.t. i=3a+5b where a and b are integers.
Inductive step: show the statement is true for n=k+1.
n = k+1 = k+1+2–2 = (k–2) + 3 = 3a+5b+3 = 3(a+1)+5b. a and b are integers, so a+1 is also an integer.
There are 52 cards in a deck. How many ways can I get a seven-card hand so that I have exactly three kings and exactly two hearts?
You do not need to evaluate, just set the problem up!
C(3, 3) * C(12, 2) * C(36, 2) + C(1, 1) * C(3, 2) * C(12, 1) * C(36, 3).
What is the coefficient of x14 in (5 – 2x2)10?
C(10, 7) * 53 * (-2)7