(7 votes, average: 4.29 out of 5)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
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
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)
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
let’s try 21
order of sitting 21, 1, 11, 16 (which is not optimal)
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
lets try 19
order of sitting 19, 1, 10 (not optimal)
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
lets try 17
order of sitting 17, 1, 25, 9, 13, 21, 5,23,19,15,11,7,3
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
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.
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
which reduces hit & trial 🙂
The best possible scenario would be that every odd seat is occupied(total of 13 seats). The gap bw any two customers needs to be divided repeatedly in halves so at any time the gap must be in the powers of 2. Therefore the first seat will either be 9 or 17
seat #13
Seat #7 may be better
I’d need as many odd numbers as possible to reach 25. Five 5s would reach 25, so my final answer would be Seat #5
I think 9th or 17th is better
If we choose 9th then the order will be
3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2
(There are other possibility too)
where 13 customer can sit.same if we choose 17th.
But if we choose 13th then only 9 customer can sit. like this
2 _ _ 6 _ _ 4 _ _ 7 _ _ 1 _ _ 8 _ _ 5 _ _ 9 _ _ 3
I am pretty sure 9 or 17 is correct! 🙂