…, -2, 0, 2, 4, 6, 8, 10, … (짝수)
…, -3, 0, 3, 6, 9, 12, 15, … (3의 배수)
…, -3, 1, 5, 9, 13, 17, … (4의 배수+1)
…, -5, 3, 11, 19, 27, 35, … (8의 배수+3)
…, -5, 7, 19, 31, 43, … (12의 배수+7)
…, -1, 23, 45, 68, … (24의 배수+23)

어떤 수 $n$을 24로 나눈 나머지를 생각해보면 모든 정수는 위 등차수열 중 적어도 하나에는 반드시 포함됨을 알 수 있다. 유명한 수학자 에르되시( Erdős)는 1950년 논문에서 임의의 $N$에 대해, 공차가 $N$ 이상인 등차수열만 써도 이런 식으로 모든 정수 집합을 덮을 수 있지 않겠냐고 적었다. 하지만 이 문제는 지난 수십년 간 풀리지 않았었고, 에르되시는 1980년 논문에서 본인이 1934년에 이 문제를 생각했다며 증명이나 반증에 $500을 준다고 했다. 에르되시는 1913년 태어났으니 1934년이면 21살일 때가 되겠다.

예를 들어 N=3인 경우 아래처럼 등차수열들을 구성하면 공차는 서로 다르면서 전체 정수 집합을 덮을 수 있다.

3의 배수, 4의 배수, 5의 배수, 6의 배수+1, 8의 배수+1, 10의 배수+2, 12의 배수+11, 15의 배수+1, 20의 배수+14, 24의 배수+5, 30의 배수+8, 40의 배수+6, 60의 배수+58, 120의 배수+26.

1968년엔 Churchhouse가 N=9인 방법을 찾고, 1971년에는 Krukenberg가 박사논문에서 N=18인 방법을 기술했으며, S. L. G. Choi가 1971년에 N=20인 방법을 찾았다. 1981년 Morikawa는 N=24까지 올리고 2009년엔 Gibson은 대규모 컴퓨터 계산을 통해 N=25인 방법을 찾았으며, 같은 해 Nielson이 N=40인 방법에 대한 논문을 출판했다. 이 문제에 대한 Nielson의 설명을 아래 동영상에서 볼 수 있다.

2013년  옥스포드대학의 Bob Hough 박사는 에르되시의 위 추측은 거짓이고, 만일 공차가 서로 다른 등차수열로 정수 집합을 덮을 수 있다면 그 중 적어도 하나의 등차수열의 공차는 $10^{18}$보다 클 수 없음을 증명하였다. 이로써 무려 63년만에 에르되시의 미해결 문제 하나가 해결된 셈이다. 증명은 확률론적 방법을 쓰는데, Lovasz Local Lemma를 응용한다고 한다. (arxiv에 올라온 논문)

(이 분야 논문이 있는 캐나다 밴쿠버의 British Columbia 대학 교수로 70년대 주로 활동한 S.L.G. Choi라는 분이 한국인일까요? 아닐 것 같긴 합니다만.)