**Note:** The problem is solved! See * EDIT* below.

The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the Knapsack problem?

Let $n,k$ be natural numbers, $n\gg k$.
By a **partition** (of $n$ into $k$ parts) I mean a vector $x=(x_1,\ldots,x_k)$
of non-negative integers
such that $x_1+\cdots+x_k=n$. Since order here matters,
we have $\tbinom{n+k-1}{k-1}=\tbinom{n+k-1}{n}$ partitions.
By an $r$-**test** I mean a pair $(S,b)$ where $S\subseteq \{1,\ldots,k\}$, $|S|=r$
and $0\leq b\leq n$ is an integer.
Say that a partition $x$ **passes** such a test if $\sum_{i\in S}x_i=b$.
Let us call $S$ the *support*, and $b$ the *threshold* of the test $(S,b)$.
Finally, let $T(r)=T_{n,k}(r)$ denote the smallest number of $r$-tests such that **every**
partition passes at least one of these tests. It is easy to see that:

- $T(k)=1$: every partition passes the test $(\{1,\ldots,k\},n)$.
- $T(k-r)=T(r)$ for all $r=1,\ldots,k-1$: a partition passes a test $(S,b)$ if and only if it passes the test $(\overline{S},n-b)$.
- $T(r)\leq n+1$: just take all tests $(S,b)$ with $S=\{1,\ldots,r\}$ and $b=0,1,\ldots,n$.

Form (3) we have that $T(1)+T(2)+\cdots+T(k)\leq O(kn)$.

Does $T(1)+T(2)+\cdots+T(k)\geq \Omega(kn)$?

I am only interested in a *rough* bound holding for infinitely many numbers $n$ and $k$.
The difficulty here is that the supports $S$
of different tests $(S,b)$ may be different, and may even overlap.
If, say, all test must have the same support, say $S=\{1,\ldots,r\}$, then
$T(r)\geq n+1$ thresholds $b$ are necessary for every $r=1,\ldots,n-1$:
if some threshold $b$ is missing, then the vector
$x=(b,0,\ldots,0,n-b)$ is a partition but it passes none of the tests.
If, however, we had an additional test $(S',0)$ with $S'=\{2,\ldots,r+1\}$, then
$x$ would already pass this test.

In general, even the case $r=1$ is not quite clear (at least to me).

Does $T(1)\geq \Omega(n)$?

Take a minimal set of $1$-tests, and let $B_i$ be the set of thresholds $b$ used by the $i$-th tests $(\{i\},b)$. Hence, we have to lower-bound $T(1)=\sum_{i=1}^k|B_i|$. We only know that $\overline{B}_1\times \overline{B}_2\times \cdots\times \overline{B_k}$ must avoid any partition. Simplest possibilities are to take $B_1=\{0,1,\ldots,n\}$ and $B_2=\ldots=B_k=\emptyset$, or to take all the $B_i$ equal to $\{0,1,\ldots,n/k\}$. Both possibilities use about $n$ tests. But how to argue that there are no better possibilities?

Has anybody seen anything related being considered?

* EDIT:* When properly used, Gerhard's "missing threshold" hint for the case $r=1$
leads to a tight

**answer**$T(r)=n+1$ for all $1\leq r\leq k-1$.

In fact, we always need $\geq n+1$ tests, as long as supports are strictly smaller than $k$.

**Proof:**
Argue by induction on $n$ and on the number $m$ of supports in the collection.
If $m=1$, then we need $n+1$ tests, by the argument above. For general $m$,
fix one support $S$ containing no other support (from our collection of tests)
as a proper subset. Then take the *smallest* number $c$ which does not appear
as a threshold $b$ in any of our tests of the form $(S,b)$.
Thus, we must already have
at least $c$ tests with support $S$. The remaining tests $(T,b)$ with $T\not\subseteq S$ can be modified
in such a way that they cover all partitions of $n-c$ into $k-|S|$ parts.
Namely, fix a string of numbers $(a_i:i\in S)$ summing up to $c$, and concentrate
on partitions of $n$ containing this string. If some test $(T,b)$
participates in covering any of such partitions, and if $T\cap S\neq \emptyset$,
then replace $(T,b)$ by the
test $(T\setminus S,b')$ where $b'=b-\sum_{i\in S\cap T}a_i$.
By induction hypothesis, there must be at least $n-c+1$ such tests, giving
a lower bound $n+1$ on the total number of tests. $\Box$

Thanks, Gerhard, for a useful hint!