집합 U를 1부터 1000까지의 모든 자연수의 집합으로 정의합니다. 그 다음 1000보다 작은 홀수 k에 대해 집합 A_k를 {k*(2^n)|n은 0 이상의 정수, k*(2^n)<=1000}으로 정의합니다.
그렇게 하면, 집합 U는 A_1, A_3, A_5, ... , A_999 500개의 집합으로 분할됩니다.
U에서 501개의 원소를 뽑을 때, 비둘기집 원리에 의해 어떤 (1000보다 작은) 홀수 i가 존재하여, A_i에서 두 개 이상의 원소가 뽑히게 됩니다. 또, A_i에서 두 개의 원소를 뽑았을 때 두 수는 반드시 약수와 배수 관계입니다. (자세한 설명 생략)
따라서 1부터 1000까지의 자연수에서 서로 다른 501개를 뽑으면 어느 하나가 다른 하나를 나누는 서로 다른 두 자연수가 존재하게 됩니다.