Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ respectively.

I would like to know if anyone has ever seen (or knows a proof for) the following result: that any interval of $(a - |A| + 1)(b - |B| + 1)$ consecutive integers contains a number $x$ such that $x$ mod $a$ is in $A$, while $x$ mod $b$ is in $B$.

Actually, I do have a proof of this result, but it's complicated, and I have no proof for the $k$-variate case. To be precise the $k$-variate case is the following: we have $k$ natural numbers $a_1, \ldots, a_k$ that are pairwise coprime, and nonempty sets of residues $A_1, \ldots, A_k$ where $A_i$ is a set of residues mod $a_i$. The question is to show that any interval of at least $$ (a_1 - |A_1| + 1)(a_2 - |A_2| + 1)\cdots (a_k - |A_k| + 1) $$ consecutive integers contains an integer $x$ such that $x$ mod $a_i$ is in $A_i$ for $i = 1, \ldots, k$. The case $k = 1$ is obvious, for the case $k = 2$ I have a proof, and for $k \geq 3$ I only have a partial result, namely that the statement holds as long as the interval length mentioned above is strictly greater than $$ \sum_i \prod_{j\ne i} a_j. $$ Would be grateful if people could tell me what they know about this problem, or their insights. Thanks!