I have encountered this problem: "A circular table has 60 chairs around it. There are N people seated at this table so that the next person seated must sit next to someone. Find the smallest possible value of N". I'm struggling to understand why my solution is wrong, and why the given solution is correct.
My proof is, given N people, if we leave 1 seat to the left of each person blank, then no one has to sit next to each other, however the next person who sits has to sit next to someone. We then proceed to find the number of people this arrangement will need. Since the number of occupied and unoccupied seats must add up to 60, 2N=60. Therefore, N = 30 people can be seated.
However, the solution given is 20. The explanation is "If every third seat is occupied, filling 20 seats, then every unoccupied seat has a person sitting next to it, so N could be 20. To see that N must be at least 20, note that any seating which satisfies the conditions cannot contain a gap of more than 2 unoccupied seats between any occupied seats. If we regard adjacent
occupied seats as having a gap of 0 between them, every seating of N people contains N gaps, all of which must be less than 2. Thus N+2N = 3N is at least as big as the sum of N and all the which is 60, therefore 3N ≥ 60 and N ≥ 20.Note that there are simpler arguments that work when there are 60 seats around the table, but this proof has the advantage of working just as well when the number of seats is not a multiple of 3 (e.g. for 59 seats N must still be at least 20
since 3N ≥ 59, and for 61 seats 3N ≥ 61 implies N ≥ 21)."
I don't understand why my reasoning is false, and why their reasoning is correct. Could someone explain this to me?
Thanks in advance.
Best Answer
I think it is evidently clear how the maximum gap must be less than 3. If the gap exceeds 2, then there will have to be at least one gap of 3 which will allow the next person to sit in the middle.
As we increase the no. of gaps, the value of N will consequently decrease. Thus to find the least value of N for the given conditions to satisfy, we must consider the case where maximum permitted gaps are present.
This is in the case of every third seat being occupied (as this allows a gap of 2 between each person, which is max. permitted gap)
Thus the least value of N turns out to be 20.
The problem with your answer is that, even though it satisfies the given conditions, it's not the best possible arrangement. As in, it isn't the least value of N (which is asked). It is easy to see how increasing the gap will decrease N. So in your case you haven't allocated the maximum gaps, that is the reason your answer came to be incorrect.