0. Book problems:
Section 6.1: 2, 4, 16, 28. 6.3: 8,
12, 14, 28, 32. 7.2: 8, 24,
28. 8.5: 2, 4, 6.
Discrete Math I for Computer Science
Due: Before the final exam.
- Given ten points in the plane with no three collinear,
- How many different segments joining two points are there?
- How many ways are there to choose a directed path of length
two through three distinct points?
- How many different triangles are there?
- How many ways are there to choose 4 segments?
- If you choose 4 segments at random, what are the chances
that some three form a triangle?
- Forty equally skilled teams play a tournament in which every
team plays every other team exactly once, and there are no ties.
- How many different games were played?
- How many different possible outcomes for these games are
- How many different ways are there for each team to win a
different number of games?
- Let C(n, k) be the number of ways to choose k
objects from a set of n. Prove by a combinatorial
- C(n,0) + C(n, 1) + … + C(n,
n) = 2n.
- C(n,m)C(m,k) = C(n,k)C(n-k,
- C(n, n-k) = C(n, k).
- C2(n,0) + C2(n,
1) + … + C2(n, n) = C(2n,
n). (Hint: Use c).
- Prove the following combinatorial identities by formula.
- C(n+1, k+1) = C(n, k+1)
+ C(n, k).
- C(r, r) + C(r+1, r) +
C(r+2, r) + … + C(n, r) = C(n+1,
r+1). Hint: Use (a), and notice that
C(r, r) + C(r+1, r) = C(r+2,
r+1). The series telescopes.
- Using the identity in 4b above, derive a formula for the sum
(1)(2)(3) + (2)(3)(4) + … + (n-2)(n-1)(n).
Hint: Set r = 3.
- If you have 2n socks in a drawer, n white and
n black, and you reach in to choose 2 socks at random,
- How many ways are there to choose?
- How many of these ways result in getting a pair of the same
- Write a simple closed form formula in terms of n for
the chance choosing a matching pair of socks from a drawer
with n white and n black socks.
- A few short problems:
- How many ways are there to choose a president, vice
president, secretary and treasurer from 9 people?
- How many ways can 13 identical balls be distributed into 3
- How many numbers greater than 3,000,000 can be formed from
permutations of 1,2,2,4,6,6,6?
- How many nine-digit numbers with twice as many odd digits as
even digits? (leading zeros are allowed, and zeros are
- How many passwords can be created in the form [A-Z][a-z]9[0,1]6?
(That is, a capital letter followed by 9 lowercase letters
followed by 6 bits).
- How many different 7-card Poker hands are there?
- How many 7-card poker hands are a flush (all one suit)?
- Let A and B be n-bit numbers, each
representing a subset of n elements. How many
total pairs are there? In how many of these pairs is A a
subset of B? What are the chances given two randomly
chosen n-bit numbers, that the second is a subset of the
- How many ways are there to distribute eight balls into six
distinct boxes with at least one ball in each box if:
- The balls are identical?
- The balls are distinct? Hint: Separate into
- How many ways are there to distribute eight balls into
six distinct boxes with at most four balls combined in the
first two boxes if:
- The balls are identical? Hint: Separate into
- The balls are distinct? Hint: Separate into
- Fibonacci in Pascal’s Triangle.
Prove by induction that the nth Fibonacci number Fn
equals C(n, 0) + C(n-1, 1) + C(n-2,
2) + … + C( ceiling(n/2), floor (n/2)).
You should assume that F0 = F1 =
- There’s a new screen saver that displays a random rectangular
piece of an n by n checkerboard.
- How many rectangles are there in a checkerboard of size 1?
2? 3? 4?
- How many squares are there in a checkerboard of size 1? 2?
- Guess a general formula for the number of squares and
rectangles. Put each in closed form in terms of n.
- Prove your formulas are true.
- What’s the chance that the rectangle displayed is a square?
Give a simplified closed form in terms of n.
- Although the number of squares and rectangles increase
without bound as n increases, what happens to the
ratio of squares to rectangles?
- A password is created with eight characters each of which is
between the letters a and z inclusive. How many different
passwords are possible?
- If no duplicate letters are allowed, then how many passwords
- In each case, if 2,000,000 random attempts are made by a
hacker to guess the password, what’s the chance that he cracks
- If it is known that the password is one of the 3,300,000
entries in a list of words and proper names, and again the
hacker tries 2,000,000 random attempts to crack it. What’s the
chance of his success?
- Assume one person out of 10,000 is infected with HIV, and
there is a test in which 2.5% of all people test positive for
the virus although they do not really have it. If you test
negative on this test, then you definitely do not have HIV.
What is the chance of having HIV, assuming you test positive
- A round-robin tournament is one where each player plays each
of the other players exactly once. Prove that if no person loses
all his games, then there must be two players with the same
number of wins.
- Each of two disks has one megabyte of bits around its
perimeter, half of which are ones and half of which are zeros.
Prove that no matter how the bits are arranged, the disks can be
placed on top of each other, so that half a megabyte of bits
match up. (Hint: Count the total matches as you rotate the top
disk around the bottom, and make a pigeonhole argument).
- How many different collections of six integers are there
(duplicates allowed), where each integer is between 2 and 5,
inclusive, and the sum equals 20? (Use
- Three computer tasks A, B, C each with 5 ordered parts:
A1 through A5, B1 through B5, and C1 through C5, are being
multi-tasked by my PC. Each task must execute its parts in order
one through five. Thus A1 B1 B2 C1 C2 C3 C4 B3
A2 etc. is an acceptable order. Assume, that the
choice of which task to work on next is chosen randomly, and
that the next part of that task is then executed. What is
the probability that after all 15 parts are complete, five parts
of at least one task were executed consecutively? (Use
- A password requires that you use a sequence of upper-case
characters, lower-case characters and digits. A valid password
must be at least 10 characters long, and it must contain at
least one character from each of the three sets of characters.
If you generate 10 random characters from the union of the three
sets of characters, what is the probability that you will get a
valid password? (Use Inclusion/Exclusion).
- What are the chances that a randomly dealt 13-card hand has at
least one of every suit? (Use Inclusion/Exclusion).