0
$\begingroup$

Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline A$ and the coverage has no excess points in $(-\infty; N]$.

Am I right assuming that this problem can be reduced to the set cover problem? I couldn't come up with a strict proof for some reason yet.

$\endgroup$
5
  • 1
    $\begingroup$ The question is unclear. Isn't $1,2,\dots,N$ an integer arithmetical progression that covers $[1,N]$ all by itself? What is an "excess point"? $\endgroup$ Apr 5, 2014 at 10:49
  • $\begingroup$ Sorry, I meant that every point in given set is in range $[1, N]$. Excess point is a number which is covered but does not belong to the given set. $\endgroup$
    – Paul
    Apr 5, 2014 at 12:45
  • $\begingroup$ OK, I mostly understand now, though I'm not sure I understand the switch between $[1;N]$ and $(-\infty;N]$. $\endgroup$ Apr 6, 2014 at 6:24
  • $\begingroup$ The idea behind using $-\infty$ is that progressions have to start in $[1;N]$. This is probably unnecessary condition though. Obviously an intersection of progressions gives another progression and any combination can be presented as unions of intersections of progressions or their negations, but I can't make a step further. $\endgroup$
    – Paul
    Apr 6, 2014 at 17:46
  • $\begingroup$ What if you take a set with no 3-term APs? There are known examples when such a set is fairly big. $\endgroup$
    – DmitryZ
    Apr 9, 2014 at 22:50

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.