The IT department in a hospital is configuring some very small digital back-up t

Question

The IT department in a hospital is configuring some very small digital back-up tape drives. The drives' data is stored in "words" (i.e. non-empty strings of lower-case English letters, whose length is lessthanorequalto 4). Distinct words are separated by blanks. The IT department is told that 500,000 words are stored on each drive. Can it be that all words are distinct ? What is the minimal number of stored words on the tape that will guarantee there are duplicate words? Give a detailed argument using the Pigeon-Hole Principle.

Explanation / Answer

(i) The total number of distinct words with only one letter is 26.

Distinct words with two letters is 26*25 = 650

Distinct words with three letters is 26*25*24 = 15600

Distinct words with four letters is 26*25*24*23 =   358800

The total number of distinct words possible is the sum of all four which is 375076. This number is less than 500,000 so there must be duplicates in the words stored. They are not distinct.

(ii) The minimum number of words to gurantee there are duplicates is 375076 + 1 = 375077.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.