Suppose there are n offices for n employees. They are arranged in a circle, so t

Question

Suppose there are n offices for n employees. They are arranged in a circle, so the offices can be numbered from 1 to n so that office i is between office i 1 and office i + 1 (and office n is between office n 1 and office 1). Offices 1, 2, and 3 are larger and nicer than the rest. The employees are meant to be randomly assigned to the offices, but there are three employees (let’s call them employees 1, 2, and 3) who want to have neighboring offices. Design a randomized allocation algorithm that ensures each employee has an equal chance of getting one of the nicer offices, while employees 1, 2, and 3 are guaranteed to get consecutive office assignments

Explanation / Answer

Let the offices are numbered as 01, 02,...0n

They are arranged in circular fashion.

Employees 1,2,3 are to be assigned in neighbouring.

Hence select E1, and assign him any office and next E2 to one of the neighbouring and E3 to neighbouring of E1 or E3

Now remaining employees are n-3. And there are n-3 offices.

Thus now we can assign each to n-3 in (n-3)! ways

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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