help will be really appriciated. The IT department in a hospital is configuring

Question

help will be really appriciated.

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) No all words cannot be distinct. Since we are storing only 4 letter words.
So we can store distinct words : 4! ==> 24 words..
But tape can store 500,000 words. So, all words stored cannot be distinct.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

(ii)
According to pigeon hole princple .. [(n-1) / m ] + 1
where n is total storage and m = items

So m = total items = 4! = 24 (since only 4 letter words are stored)

So 500000 - 1 / 24 + 1
===> 499999/24 + 1 ===> 20833 + 1 ==> 20834

So atleast 20834 non-distinct words has to be stored.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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