8
$\begingroup$

A room has n empty chairs in a row. You choose a chair and sit it in it. Now someone else comes in and sits as far away as possible from everyone in the room or an arbitrary choice of furthest chair if there is more than one. This happens repeatedly with the rule that no two people can ever sit next to each other. It finishes when there is no more space to sit.

Your goal of course is to choose your chair initially so that as many people as possible can sit in the room.

Say n=2. Wherever we sit we end up with exactly one person sat down.

For n=3. If we sit in the first chair, we get full, empty, full in the end. But if we set the chair bit we get empty, full, empty which is not optimal.

For n=4. Wherever we sit we end up with two chairs with people on them.

For n=5. Sitting in the first chair gives us full, empty, full, empty,full with three people sat down in the end.

For n=7. We need to sit in the third chair it seems.

What is the simplest rule for choosing where to sit which will always give an optimal answer?

$\endgroup$
  • 6
    $\begingroup$ While not exactly an answer, I assume you've seen this? $\endgroup$ – Set Big O Nov 19 '14 at 19:29
  • $\begingroup$ can you assume that those who follow you are also trying to help get the most people seated, or do you have to try to stave off some antisocial strategy from someone who follows you? Someone who sits two seats away from you ensures both those seats stay empty. $\endgroup$ – Kate Gregory Nov 19 '14 at 19:31
  • $\begingroup$ @Geobits isn't that exactly the answer? just reworded? :P $\endgroup$ – stackErr Nov 19 '14 at 19:31
  • 3
    $\begingroup$ Are new people trying to sit as far from you as possible, or from everyone? $\endgroup$ – JonTheMon Nov 19 '14 at 20:00
  • 1
    $\begingroup$ @JonTheMon As far as possible away from everyone. Cleared that up in the question. Thank you. $\endgroup$ – Lembik Nov 19 '14 at 20:01
5
$\begingroup$

The ideal situation is to have ceil(n/2) chairs filled. People and empty chairs will alternate in this situation. Any time there is a gap of just two chairs, it can't be filled, so you want to have gaps of 3 that will eventually fill up leaving gaps of one. For odd number of chairs, you want both ends to be full. For even, you want one of the ends to be full.

Some strategies that don't work well:

  • just sit in the middle. Consider 9: you sit with 4 empty chairs on either side of you. The next person sits at one end, and the next at the other. Now the last two people sit in the centre of each 3-chair gap. Great! But for 11, you have 5 on each side, the ends fill in leaving a pair of 4-gaps, and people sit in those leaving a 1-gap on one side of them and a 2-gap on the other - suboptimal.

  • sit at one end. Second person will sit at the other, third in the middle and we are now in the very same situation as "sit in the middle" is after the third person

  • sit 3 from one end. for 9 you start 001000000 then 001000001 the third person fills the 5-chair gap so 001001001

You win if all the gaps are 1 chair. (Ignore the ends for a moment and imagine you're joining this in progress.) The only way to force all the gaps to be 1 chair is to force them all to be 3 (which someone sits in the middle of) or 1. The only way to make a 3-gap is to have a 7 gap that someone sits in the middle of. The only way to make a 7 gap is a 15 gap that someone sits in the middle of. These are one less than powers of 2.

However the ends mess this up. If you have a 7 gap that stretches to the end, someone will sit at the end, creating a 6 gap which can't be neatly split up like this. So you want to sit so that you put the largest possible power of two between you and one end. Someone will sit at that end creating one of these 2^n-1 gaps and then it will shake out from there. The short end you can't control, you just hope it ends up all 1-gaps but it might not.

For 11, your target gap is 8 You sit: 00100000000. Next person goes to the end: 00100000001. Next person 00100010001. Then you're all set - you will end up 10101010101.

This should work for any number of chairs.

Some things I can prove:

  • if you sit with 2^n chairs to your left, the gap to your right is smaller. Well, if it's not, then it's equal to 2^n + m, where m is positive, meaning you could sit somewhere with 2^n + 2^n chairs to your left and m to your right, meaning there is a way to sit and get 2^(n+1) chairs to your left, so you should have done that. You get the largest power of 2 you can. The not-necessarily-power-of-2 gap on the other side of you must then be smaller. This is what forces the next sitter to sit at the end of your 2^n gap, creating the first (2^n)-1 gap.
  • once you gaps that are (2^n)-1, they will always be split into a pair of (2^(n-1))-1 gaps with a filled chair between them. First, (2^(n-1))-1 + 1 + (2^(n-1))-1 is (2^(n))-1. Second, sitting anywhere in the gap that doesn't result in the same number of empty chairs on either side of the sitter means they are not as far away from others as they could be - they can't get further away than (2^(n-1))-1 and anything else is closer.
$\endgroup$
  • $\begingroup$ This looks very promising. $\endgroup$ – Lembik Nov 20 '14 at 11:30
  • $\begingroup$ The gap you want, is that between you and n or between you and beyond and including n? $\endgroup$ – Raystafarian Nov 20 '14 at 13:15
  • $\begingroup$ gap - empty chairs. When you first sit there are 4, 8, 16, 32 (the largest you can get) empty chairs on one side of you, and some other number that you can't control on the other side, which is smaller than the 4, 8, or whatever. The second person will sit at the end of your power-of-2 gap creating a one-less-than-a-power-of-2-gap which will continue to be split into smaller one-less-than-a-power-of-2 gaps by people who sit in the middle of the gap. $\endgroup$ – Kate Gregory Nov 20 '14 at 13:18
  • $\begingroup$ So n=9 and you sit in position #1, and n=10 you sit in position #2, right? $\endgroup$ – Raystafarian Nov 20 '14 at 13:21
  • $\begingroup$ @Raystafarian yes. It will play out just like the 11 example in the body of the answer, but with 1 or 2 less zeroes before the 1. $\endgroup$ – Kate Gregory Nov 20 '14 at 13:23
4
$\begingroup$

Pick the highest power of 2 that's under the chair limit, add 1, and sit there. (So, if there are 16 chairs, sit at chair 9). This will ensure that the chairs to your left are all filled in a binary fashion. After that, it's just hoping the chairs to the right fill out correctly.

Unfortunately, the means you can only control the chairs to your left. If you had, say, 15 chairs, you can control the first 9, but after that, chair 15 will be taken, then chair 12, leaving 2x 2-space gaps (10-11, 13-14) that you can't control.

$\endgroup$
  • $\begingroup$ Ahhh beat me to it! $\endgroup$ – stackErr Nov 19 '14 at 19:42
  • $\begingroup$ I am not sure I fully understand "This will ensure that the chairs to your left are all filled in a binary fashion". In your example, the next chair to be filled will be 1, then 16, then 5 and so on. $\endgroup$ – Lembik Nov 19 '14 at 19:43
  • $\begingroup$ the why part sounds like it should be on Math SE. $\endgroup$ – stackErr Nov 19 '14 at 19:44
  • $\begingroup$ n=15 you select #9 and follows 1, 15, 3, 13, 5, 11, 7 - is that how your formula works? You don't end up with gaps. $\endgroup$ – Raystafarian Nov 19 '14 at 19:58
  • 2
    $\begingroup$ I imagine it's more like 9, 1, 15, 5, 12, 3, 7. Each person tries to sit as far from each other as possible. $\endgroup$ – JonTheMon Nov 19 '14 at 19:59
0
$\begingroup$

I think the answer is

(n/2) for all even. and for the series n = 3, 7, 11, 15, ... use floor(n/2) while for the series n = 5, 9, 13, 17, ... use ciel(n/2)

n = 4

_ _ _ _

formula says pick chair 2. so you end up with:

0 1 0 2

n = 5

_ _ _ _ _

2 _ 1 _ 3

n = 6

3 _ 1 _ _ 2

n = 7

4 _ 1 _ 3 _ 2

lets skip a few...

n= 10

_ _ _ _ _ _ _ _ _ _

now the formula says sit down in 5.

3 _ 5 _ 1 _ _ 4 _ 2

And the sequence that would follow would be the same as n =4 and n =6:

the left side of 1 is n = 4

the right side is n = 6 including the first person.

similarly by induction all other higher n would break into a subset of n/2 chair arrangements

n = 11

3 _ 6 _ 1 _ 4 _ 5 _ 2

$\endgroup$
  • $\begingroup$ I think you get 5 people sitting down for n = 11 but I can get 6. You seem to get people at chairs 6, 1, 11, 4, 8. But you can get them at 1, 3, 5, 7, 9, 11 by placing myself at 9 to start with. $\endgroup$ – Lembik Nov 19 '14 at 20:29
  • $\begingroup$ your N = 7 example has 8 spaces.... $\endgroup$ – Gorloth Nov 19 '14 at 20:37
  • $\begingroup$ @Gorloth yes and theres the mistake that Lembik is talking about! $\endgroup$ – stackErr Nov 19 '14 at 20:38
  • $\begingroup$ @Lembik edited to address those cases $\endgroup$ – stackErr Nov 19 '14 at 20:43
  • 1
    $\begingroup$ Still doesn't work for larger even numbers. For n=12, this gives 101001001001 (5 occupied) for me, while starting at chair 4 gives 100101010101 (6 occupied). This method is equivalent to choosing an end, since after three steps you end up at the same configuration (both ends and middle occupied). $\endgroup$ – Set Big O Nov 19 '14 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.