# Generating a set based on some constraints

Simplified real world problem that came up yesterday.

A new course on my university can be opened if all the attendants can be split into (one or more) groups of n±2 people, where n≥5. So for example if n is 5 and there are 11 attendants, they can be split into groups of 5+0 and 5+1 people (or 5-1 and 5+2). If n is 15 and there are 20 attendants, a course cannot be opened.

I'm looking for a way to generate, for a given n, an infinite list of all possible valid attendant numbers. The trivial approach (try each of the five cardinalities for each group) goes up rapidly and for higher numbers there will be a lot of duplicates. What's a better way?

-

If $n=15$ then with one group you can make any number in $[13,17]$, with two groups any in $[26,34]$, in three any in $[39,51]$, in four any in $[52,68]$, in five any in $[65,85]$ and now the sets are overlapping you can clearly make any higher number. So you can make any number of attendants from $39$ upwards, plus the two smaller sets.

Generalising this, any number of attendants from $k(n-2)$ upwards works if $k(n+2)+1 \ge (k+1)(n-2)$, i.e. if $k \ge \frac{n-3}{4}$, which means that any number of attendants greater than or equal to $(n-2)\lceil{\frac{n-3}{4}}\rceil$ works.

-

If all you care about is the valid numbers of attendants, and not the many possible ways to realize the splitting, you can do it as follows: for each $k$, the number of attendants can be anywhere from $kn-2k=k(n-2)$ through $kn+2k=k(n+2)$. To see this, note that you can achieve $k(n-2)$ by dividing them into $k$ groups of $n-2$ each; you can achieve $k(n-2)+1$ by having one group of $n-1$ and the rest of $n-2$; you can achieve $k(n-2)+2$ by having two groups of $n-1$ and $k-2$ of $n-2$; and so on until you get to $kn-k$, which can be achieved with $k$ groups of $n-1$. Then you can add one person to each group one at a time to cover $kn-k$, $kn-k+1,\ldots,kn$. Then add one person to each group to get an instance for $kn+1$ through $kn+k$; and yet again to get all the ones from $kn+k+1$ through $kn+2k$.

Moreover, if the number of attendants is strictly between $k(n+2)$ and $(k+1)(n - 2)$ for some value of $k$, then achievement is impossible: having at most $k$ groups is insufficient (maximum number of attendants is $kn+2k$), and having $k+1$ groups is too many (minimum number of attendants is $(k+1)(n-2)$). So no number strictly between $k(n+2)$ and $(k+1)(n-2)$ can be achieved.

Now, there comes a point after which $k(n+2)\geq (k+1)(n-2)$; namely, \begin{align*} k(n+2) &\geq (k+1)(n-2)\\ k(n+2) &\geq k(n-2) + n-2\\ k(n-2) + 4k &\geq k(n-2) + n-2\\ 4k &\geq n-2\\ 4k+2 &\geq n. \end{align*} So, if $k$ is the smallest integer such that $4k+2\lt n$ (namely, $k=\lceil \frac{n-2}{4}\rceil$), then there are no unachievable numbers greater than $k(n-2)$, because there will be no "gap" between the case of $k$ groups and the case of $k+1$ groups.

Added. In fact, this can be strengthened a bit, as Henry points out. It's enough for $k(n+2)$ to be exactly one less than $(k+1)(n-2)$ for there to be no unachievable numbers. Solving for that, we have: \begin{align*} k(n+2)+1 &\geq (k+1)(n-2)\\ k(n-2) + 4k+1 &\geq k(n-2) + n-2\\ 4k+1 &\geq n-2\\ 4k+3 &\geq n. \end{align*} So it is enough for $k\geq \frac{n-3}{4}$, or $k=\lceil\frac{n-3}{4}\rceil$ to ensure that there are no gaps after $k(n-2)$.

So if $\ell = \lceil \frac{n-3}{4}\rceil$, then the achievable numbers are:

$n-2$, $n-1$, $n$, $n+1$, $n+2$, $2n-4$, $2n-3$, $2n-2$, $2n-1$, $2n$, $2n+1$, $2n+2$, $2n+3$, $2n+4$, $3n-6,\ldots,3n+6$, $4n-8,\ldots,4n+8,\ldots$, $(\ell -1)(n-2)$, $(\ell-1)(n-2)+1,\ldots,(\ell-1)(n+2)$, and all integers greater than or equal to $\ell(n-2)$.

-
With $n=20$, this would give you $l=4$ so anything from $4\times(20-2)=72$ upwards should be possible. But I don't think $89$ is possible. –  Henry Jun 29 '11 at 7:06
@Henry: Yeah, I'm posting at 2am. I had it right the first time, "corrected it", and now back. You want $\ell=\lceil(n-2)/4\rceil$; with $n=20$, that gives $\ell=5$. –  Arturo Magidin Jun 29 '11 at 7:07
with $n=19$ your revised version gives $l=5$ so anything from $5 \times (19-2) =85$ should be possible. But I think $84 = 21+21+21+21$ is also possible. –  Henry Jun 29 '11 at 7:25
@Henry: I'm did not say that's the smallest number for which there are no gaps larger, only that this number is guaranteed to have no gaps over it. I list 84 as $(\ell-1)(n+2) = (4)(21)$, just before I get to $5(19-2)$. If I find $k$ such that $(k-1)(n+2)+1 = k(n-2)$, instead of $(k-1)(n+2)\geq k(n-2)$, and you get the smallest number after which they all work. –  Arturo Magidin Jun 29 '11 at 7:34
@Henry: In other words, I had not claimed my $\ell$ was optimal... For that matter, neither did Gerry. –  Arturo Magidin Jun 29 '11 at 7:43

Find the smallest integer $k$ such that $k(n-2)\le (k-1)(n+2)$. Then you can open any course with $k(n-2)$ attendants or more. That leaves a finite problem to solve, looking at the classes with fewer than $k(n-2)$ attendants. The value of $k$ is the smallest integer not exceeding $(n+2)/4$.

For example, if $n=20$, then $(n+2)/4=5+$, so take $k=6$. Any class with 108 attendants or more can be opened, now you just have to look at the smaller classes.

-
With $n=20$, I think any class with $90$ attendants or more can be opened. –  Henry Jun 29 '11 at 7:16
@Henry, yes, 89 is the largest class that can't be opened with $n=20$. You can open 18 to 22, 36 to 44, 54 to 66, 72 to 88, and everything from 90 up. –  Gerry Myerson Jun 29 '11 at 13:06