2
$\begingroup$

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?

3 Answers 3

1

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.

  • 0
    @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.2011-06-29
2

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)$.

  • 0
    @Henry: In other words, I had not claimed my $\ell$ was optimal... For that matter, neither did Gerry.2011-06-29
2

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.