2
$\begingroup$

This is problem which came up in the process of designing a game. Thus, I don't know any previous work relevant to the problem.

Fix a small set $D$ of a natural numbers. For example, $D=\{1,2,3\}$. Also fix natural number $k$, e.g., $k=5$.

We wish to consider a hitting set of all $k$-length arithmetic sequences $\{a, a+d, a+2d,...a+(k-1)d\}$ where $d \in D$ and $a > 0$.

Such a hitting set is a subset of the natural numbers $H$ such that for any $d \in D$ and $a > 0$, at least one of $a, a+d, ..., a+(k-1)d$ is contained in $H$

If the limit $\lim_{n \to \infty} |H \cap \{1,...,n\}|/n = \delta$ exists, then we say that $\delta$ is the density of the hitting set $H$. For any given set $D$ and number $k$, there exists an infimal density $\delta_0$ of all such hitting sets. I would like to estimate the infimal density $\delta_0$ for an arbitrary set $D$ and number $k$.

I give some concrete examples.

Let $D=\{1\}$. Then the optimal hitting set is $C=\{k,2k,...\}$ with a density of $1/k$.

Let $D$ be a singleton $D=\{d\}$. Then the optimal hitting set is $C=\{d(k-1)+1,d(k-1)+2,..,d(k-1)+d,2d(k-1)+d+1,...,2d(k-1)+2d,...\}$ with a density of $1/k$.

Let $D=\{1,2\}$ and $k=2$. Then an example of a hitting set is $C=\{n: n \mod 3 \in \{1,2\}\} = \{1,2,4,5,7,8,...\}$ with a density of 2/3. However, I don't know whether a hitting set with a lower density exists. (EDIT: The answer is no, see comment by domotorp)

EDIT:

A visualization of the problem. The top figure depicts the $k$-length arithmetic sequences for $k=6$ and $D=\{1,2,3\}$. hit by an element $n$, the red dot. The black pixels in the first row are the values $a$ for which the $d=1$ sequences are hit by $n$. The black pixels in the second row are the values $a$ for which the $d=2$ sequences are hit by $n$. Analogously for the third row. The figure on the bottom depicts a hitting set for the problem $k=6, D=\{1,2,3\}$ with a density $3/8$.

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ For D={1,2} and k=2 no thinner hitting set can exist, as you need 2 numbers from any 3 consecutive numbers. $\endgroup$
    – domotorp
    Aug 25, 2014 at 18:44
  • $\begingroup$ Conjecture: the optimal hitting set takes the form {m(k-1)+1,m(k-1)+2,...,m(k-1)+M,...} where m = min(D) and M = max(D), so the density is M/(m(k-1)+M) $\endgroup$ Aug 25, 2014 at 19:50
  • 1
    $\begingroup$ The conjecture is false, as if $k\ge 2$ and D is any set of odd numbers, then the density is $\le \frac 12$. $\endgroup$
    – domotorp
    Aug 26, 2014 at 8:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.