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?
Let V equal the number of different variable names in this version of BASIC. Let V1 be the number of these that are one character long and V2 be the number of these that are two characters long.
Then by the sum rule, V = V1 + V2 but V1 = 26, because a one-character variable name must be a letter.
Furthermore, by the product rule there are 26 · 36 strings of length two that begin with a letter and end with an alphanumeric character.
However, five of these are excluded, so V2 = 26 · 36 − 5 = 931. Hence, there are V = V1 + V2 = 26 + 931 = 957 different names for variables 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?
Let P be the total number of possible passwords, and let P6, P7 and P8 denote the number of possible passwords of length 6, 7, and 8, respectively. By the sum rule, P = P6 + P7 + P8.
To find P6 it is easier to find the number of strings of uppercase letters and digits that are six characters long, including those with no digits, and subtract from this the number of strings with no digits. By the product rule, the number of strings of six characters is 366 , and the number of strings with no digits is 266.
Therefore, P6 = 366 - 266 = 1,867,866,560
Similarly, P7 = 367 - 267 = 70,332,353,920
Similarly, P8 = 368 - 268 = 2,612,282,842,880.
P = P6 + P7 + P8 = 2,684,483,063,360.
If a task can be done in either n1 ways or n2 ways, then the number of ways to do the task is n1 + n2 minus the number of ways to do the task that are common to the two different ways.
We thus get the formula: |A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|
Q. How many bit strings of length eight either start with a 1 bit or end with the two bits 00?
We can construct a bit string of length eight that begins with a "1" in 27 = 128 ways
This follows by the product rule, because the first bit can be chosen in only one way and each of the other seven bits can be chosen in two ways. Similarly, we can construct a bit string of length eight ending with the two bits 00, in 26 = 64 ways.
This follows by the product rule, because each of the first six bits can be chosen in two ways and the last two bits can be chosen in only one way.
However, there are 25 = 32 ways of constructing strings that start with "1" and end with "00".
These have been included twice and need to be subtracted.
So finally we get, 128 + 64 − 32 = 160.
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?
To find the number of these applicants who majored neither in computer science nor in business, we can subtract the number of students who majored either in computer science or in business (or both) from the total number of applicants. Let A1 be the set of students who majored in computer science and A2 the set of students who majored in business.
|A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|
= 220 + 147 − 51 = 316.
We conclude that 350 − 316 = 34 of the applicants majored neither in computer science nor in business.
The Division Rule
THE DIVISION RULE There are n/d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w.
This means that “If the finite set A is the union of n pairwise disjoint subsets each with d elements, then n =|A|/d.”
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?
We arbitrarily select a seat at the table and label it seat 1. We number the rest of the seats in numerical order, proceeding clockwise around the table. Note that are four ways to select the person for seat 1, three ways to select the person for seat 2, two ways to select the person for seat 3, and one way to select the person for seat 4.
Thus, there are 4!=24 ways to order the given four people for these seats. However, each of the four choices for seat 1 leads to the same arrangement, as we distinguish two arrangements only when one of the people has a different immediate left or immediate right neighbor.
Because there are four ways to choose the person for seat 1, by the division rule there are 24/4 = 6 different seating arrangements of four people around the circular table.
Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it
THE PIGEONHOLE PRINCIPLE : If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.
Examples :
Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays.
In any group of 27 English words, there must be at least two that begin with the same letter, because there are 26 letters in the English alphabet
A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.
THE GENERALIZED PIGEONHOLE PRINCIPLE : If N objects are placed into k boxes, then there is at least one box containing at least ⌈ N/k ⌉ objects.
Among 100 people there are at least ⌈ 100/12 ⌉ = 9 who were born in the same month.
Q. Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion
Let n be a positive integer. Consider the n + 1 integers 1, 11, 111,...,11 ...1 (where the last integer in this list is the integer with n + 1 1s in its decimal expansion). Note that there are n possible remainders when an integer is divided by n.
Because there are n + 1 integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by n.
The larger of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0s and 1s.
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?
The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer N such that ⌈ N / 5 ⌉ = 6.
The smallest such integer is N = 5 · 5 + 1 = 26. If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade.
Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade.
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?
a) Suppose there are four boxes, one for each suit, and as cards are selected they are placed in the box reserved for cards of that suit. Using the generalized pigeonhole principle, we see that if N cards are selected, there is at least one box containing at least ⌈ N / 4 ⌉ cards.
Consequently, we know that at least three cards of one suit are selected if ⌈ N / 4 ⌉ ≥ 3. The smallest integer N such that ⌈ N / 4 ⌉ ≥ 3 is N = 2 · 4 + 1 = 9, so nine cards suffice.
For part b) We do not use the generalized pigeonhole principle to answer this question, because we want to make sure that there are three hearts, not just three cards of one suit. Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three hearts.
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.)
There are eight million different phone numbers of the form NXX-XXXX
Hence, by the generalized pigeonhole principle, among 25 million telephones, at least ⌈ 25,000,000 / 8,000,000 ⌉ = 4 of them must have identical phone numbers.
Hence, at least four area codes are required to ensure that all 10-digit numbers are different.
THEOREM derived from Pigeonhole Principle
Every sequence of n2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.
The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10 = 32 + 1. There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5