Bariz - Problem

Source: XII Rioplatense Mathematical Olympaid (2003), Level 3

Tags: arithmetic sequence, algebra unsolved, algebra

Shu

09.08.2011 04:40

Let $n$ and $k$ be positive integers. Consider $n$ infinite arithmetic progressions of nonnegative integers with the property that among any $k$ consecutive nonnegative integers, at least one of $k$ integers belongs to one of the $n$ arithmetic progressions. Let $d_1,d_2,\ldots,d_n$ denote the differences of the arithmetic progressions, and let $d=\min\{d_1,d_2,\ldots,d_n\}$. In terms of $n$ and $k$, what is the maximum possible value of $d$?

$nk$ is good enough. Just consider the following residue classes modulo $nk$: $[0],[k],[2k]..,[(n-1)k]$ Now we show that we can't get anything larger. Take any list of $d$ consecutive integers with the first(smallest) being in an arithmetic progression of length $d$. Then there is only at most one integer from each progression in this list. Let's call these integers $b_1<b_2<...<b_m$ Now consider the intervals $[b_1,b_2),[b_2,b_3)...,[b_m,b_1+d)$. Thus sum of their lengths is $d$ thus there is one with length at least $d/m \geq d/n$. Hence $k\geq d/n$.