There is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjacent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others.
So where should the first customer sit?
Check your answer:-Click here to See Solution
*here for illustration -> bold one is occupied
Let’s take a few easy examples first
3 seats in the bar:
best possible arrangement 1, 2, 3 -> he asks first person to sit on 1st or 3rd
5 seats in the bar:
best arrangement 1,2,3,4,5 -> pretty clear he will ask first person to sit on 1st, 3rd or 5th
7 seats in the bar:
best arrangement 1,2,3,4,5,6,7 -> he will ask first person to sit on 3rd or 5th, not on 1st or 7th else the 3rd person will sit on 4th (1,2,3,4,5,6,7) and which will not be best possible arrangement
now, lets see 25 seats
best arrangement 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
we will have to find if it is possible to get this arrangement if yes how, we can try to discard the seats one by one
lets say first person sits on 13th (middle)
order of sitting -> 13, 1, 25, 19, 7, 22
here we can see that 22 is not in the optimal solution, so this does not give the best possible arrangement.
we can actually also discard 1, 25, 19 (as otherwise next person will sit on 22nd), similarly 7th (as otherwise next person will sit on 4th)
also notice this is symmetrical so just try one side of 13 and you will have one more answer exactly opposite. (lets try right side as we are already discussing about it).
19 can’t be the answer either as otherwise a person will sit on 22nd.
if we make first person sit on 23rd
order of sitting 23, 1, 12 (which will not be optimal)
let’s try 21
order of sitting 21, 1, 11, 16 (which is not optimal)
lets try 19
order of sitting 19, 1, 10 (not optimal)
lets try 17
order of sitting 17, 1, 25, 9, 13, 21, 5,23,19,15,11,7,3
hurray we got the best arrangement if we make first person sit at 17th, from the symmetry it will work for 9 as well, so it will either be 9 or 17.
there is another way of solving it, is like how you can get this, with gap of 3 so that next person has no other choice but to sit on optimal place.
which reduces hit & trial 🙂
Hour glass problem