How local the property of "being a partition" is? 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!
 A: I think your expression for the number of partitions needs a $k-1$ at the bottom instead of a $k$.
Considering $T(1)$, suppose you have a number of tests indexed by $t$ of the form $x_k=b_t$.
If you are not covering all of the range, you will have a number of partitions missed out by this set of tests.  To cover the remaining partitions with additional tests, if $b_t$ is small the additional tests will look like test for partitions into $k-1$ blocks of $n-c$ for $c$ not equal to any $b_t$.
You will thus either need $o(n)$ tests for $T(1)$ for the given $n$ and $k$, or you will step down
to the situation for $n-c$ and $k-1$.  I leave it to you to figure out how small $c$ can be to prove what you want and still keep $n- c >> k-1$, iterating all the way down of course.  You may be able to get $\Omega(kn^{1- \epsilon})$ at least.
Gerhard "Ask Me About System Design" Paseman, 2011.12.08 
A: Sorry for writing this as an answer. I am new here, 
all "comment" or "edit" buttons somehow disappeared after a short time. 
@Gerhard: I am sorry for a duplicated comment (haven't found any possibility to remove it or at least to excuse). Also, I cannot upvote your answer (too few points). Not a lucky start ...


Concerning the simplest case $r=1$, 
I think that Gerhard's observation  even yields  $T(1)\geq n+1$ by simple induction. 
To parametrize the problem, let $t_p(m)$
denote the smallest number of $1$-tests covering all partitions of $m$ into $p$ parts.
Hence, in my previous notation,
$T(1)=t_k(n)$. We will prove $t_k(n)\geq n+1$ by induction on $n$ and $k$.
Basis case $t_1(n)= n+1$ trivially holds.
For the induction step, fix a smallest set of tests achieving $t_k(n)$, and 
let $c$ be the smallest number not used as a threshold in the $k$-th of these tests.
Then all partitions of $n-c$ into $k-1$ parts must be covered by the remaining tests. 
Since the $k$-th block must already have at least $c$ tests,
induction hypothesis yields the desired lower bound 
$t_k(n)\geq c +t_{k-1}(n-c)\geq c + (n-c)+1=n+1$.
Can something similar work for $r\geq 2$, when we have overlapping supports?
