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

Pigeon Hole Rule

The Pigeonhole Principle: If n + 1 or more objects are placed in n

boxes, then at least one box contains more than one object.

More generally we can say

If kn + 1 or more objects are placed in n boxes, than at least one box

contains more than k objects.

Now coming to our practical example here

Given :

The Drives data stored in “Words” which are Not empty.

500000 are stored on each drive .

Solution :

In a 27 word English sentence, at least two words start with the same letter that means for every 27th letter in the word string of 500000 has repetitions. To arrive at reverse conclusion we have take a block of all distinct words which has an array size of < 26 .

Minimal set of words : . in our case we have more than 500000 words that means 500000 / 26 = ~ 19230 words are repetitive .

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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