Complex Counting Problems

Q. In a version of the computer language BASIC, the name of a variable is a string of one or two alphanumeric characters, where uppercase and lowercase letters are not distinguished. (An alphanumeric character is either one of the 26 English letters or one of the 10 digits.) Moreover, a variable name must begin with a letter and must be different from the five strings of two characters that are reserved for programming use. How many different variable names are there in this version of BASIC?

Q. Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there?

The Subtraction Rule (Inclusion–Exclusion for Two Sets)

Q. How many bit strings of length eight either start with a 1 bit or end with the two bits 00?

Q. A computer company receives 350 applications from computer graduates for a job planning a line of newWeb servers. Suppose that 220 of these applicants majored in computer science, 147 majored in business, and 51 majored both in computer science and in business. How many of these applicants majored neither in computer science nor in business?

The Division Rule

Q. How many different ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left neighbor and the same right neighbor?

The Pigeonhole Principle

Q. Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion

Q. What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?

Q. a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit (hearts, diamonds, spades, or clubs) are chosen. b) How many must be selected to guarantee that at least three hearts are selected?

Q. What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10-digit telephone numbers? (Assume that telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit from 2 to 9 inclusive, and X represents any digit.)

THEOREM derived from Pigeonhole Principle

Previous Next