1989年、テキサス大学オースティン校のRobert Holte氏たちは、ある実務上の困りごとを数学の問題として定式化した。複数の人工衛星がそれぞれ決まった間隔でデータを送信してくる。地上局のアンテナは一度に一つの衛星しか受信できない。各衛星について「連続する日間に必ず1回は受信する」という条件を満たしつつ、無限に続く受信スケジュールを組めるか。この問いが輪番割当問題(pinwheel scheduling problem)の始まりだった。
問題の構造は単純だ。$k$個の仕事があり、仕事$i$は日ごとに必ず1回実行しなければならない。1日に実行できる仕事はちょうど1つ。スケジュールが存在するか否かを判定したい。
密度という量がこの問題の核心を握る。各仕事の「1日あたりの実行頻度」の合計であり、これが1を超えれば物理的にスケジュール不可能である。1日に1つしか仕事をこなせないのに、要求される総仕事量が1日あたり1を超えるのだから当然だ。
ところが密度1以下という条件は、スケジュール可能性を保証しない。最も有名な反例は$(2, 3, m)$()である。密度はであり、$m$を大きくすれば1にいくらでも近づけられるが、この組はどんな$m$を選んでもスケジュール不可能だ。2日周期の仕事と3日周期の仕事が互いに干渉し、3番目の仕事を割り込む隙間が永遠に残らない。