Five friends P, Q, R, S and T went camping. At night, they had to sleep in a row inside the tent. P and Q refused to sleep next to R since he snored loudly. P and S wanted to avoid Q as he usually hugged people in sleep. Assuming everyone was satisfied with the sleeping arrangements, what is the order in which they slept?
A. RSPTQ
B. SQRTP
C. QRSPT
D. QTPSR
GATE 2020 · General Aptitude · Seating Arrangement · medium
Answer: The valid sleeping order is RSPTQ (Answer A)
List all forbidden adjacent pairs: P and Q refuse to sleep next to R: forbidden pairs (P,R) and (Q,R). P and S want to avoid Q: forbidden pairs (Q,P) and (Q,S). Forbidden set: {P-R, Q-R, Q-P, Q-S}.
Identify the most constrained person: Q is forbidden from all neighbours except T. In a 5-person row, Q must be at one end with T as its only neighbour.
Place R using its constraints: Since T is locked next to Q, R must be placed at the other end with S as its neighbour. This gives the partial order: R-S-...-T-Q.