A Combinatorics Question: Why Is My Solution Wrong, And The Given Solution Correct?

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.


If every third seat is occupied, filling 20 seats, then decreasing $N$ any further means there is at least one gap of $4$, so that the person can sit themselves in the middle (seat $2$ of $4$) and not be next to anyone. Hence the minimum value of $N$ is $20$.

Tags:

Combinatorics

Proof Explanation

Related

If $f$ is uniformly continuous on two open sets with a non-empty intersection, then $f$ is uniformly continuous on their union Projection of an interior point of an ellipsoid onto itself A homogeneous cubic polynomial with no non-trivial zero over $\mathbf{F_7}$ Probability - Book with typos problem Which field property enables us to multiply on both sides by the same value, while preserving equality? Manifold that's not $\aleph_1$-separable Regarding evaluation of the limit of the sequence $\Bigl(\frac{1}{n}\Bigr)^n+\Bigl(\frac{2}{n}\Bigr)^n+ \cdots \Bigl(\frac{n}{n}\Bigr)^n$ Prove the following inequality $\sum_{i<j<k}\frac{a_ia_ja_k}{(n-2)(n-1)n}\le \bigg(\sum_{i<j}\frac{a_ia_j}{(n-1)n}\bigg)^2+\frac{1}{12}$ Integral $I(\tau_1,a,b) = \int_{\tau_1}^\infty d\tau_2\ \frac{1}{b^2 + \tau_2^2} \left(\pi - 2 \tan^{-1} \frac{\tau_2}{a} \right)^2$ Is the sequence $x_n=\dfrac{1}{\sqrt{n}}\left(1+\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}}+\ldots+\dfrac{1}{\sqrt{n}}\right)$ monotone? Choosing one of each letter from a string of repeated "ABCD"s such that it is in order of "ABCD" Proof using Fundamental Theorem of Calculus (Showing RHS = LHS)

Recent Posts