Beatty Sequence와 Rayleigh's theorem

시험기간인데 포스팅은 하고 싶어서 내뱉는 짧은 주제.

이산수학이 맞는지는 모르겠지만... 이것과 연관된 이산수학 문제가 하나 있으니까 이 카테고리에 포스팅하기로 한다.

---

1. Definition of Beatty Sequence

양의 무리수 \(r\)에 대해서 Beatty Sequence \(\mathcal{B}_r\)을 다음과 같이 정의한다.

$$ \mathcal{B}_r := \{ \lfloor r \rfloor, \lfloor 2r \rfloor, \cdots, \lfloor nr \rfloor \cdots \} $$

2. Rayleigh's theorem

두 양수 무리수 \(r,s\)가 \(\frac{1}{r}+\frac{1}{s} = 1\)을 만족할 때, \(\mathcal{B}_r\)과 \(\mathcal{B}_s\)는 자연수 집합을 분할한다.

귀류법을 이용하여 증명한다.

\(\text{case I : } \mathcal{B}_r \cap \mathcal{B}_s \neq \emptyset \)

즉, \(j = \lfloor kr \rfloor = \lfloor ms \rfloor\)인 \(k,m \in \mathbb{Z}\)이 존재하는 경우이다.

\(j \le kr < j+1 \Rightarrow \frac{j}{r} \le k < \frac{j+1}{r}\)

\(j \le ms < j+1 \Rightarrow \frac{j}{s} \le m < \frac{j+1}{s}\)

양변을 더하면 \(j(\frac{1}{r}+\frac{1}{s}) = j \le k+m \le (j+1)\cdot (\frac{1}{r}+\frac{1}{s}) = j+1\) 이므로, 

\(j < k+m \le j+1\)이 되어 \(k+m\)이 정수라는 가정에 모순.

\(\text{case II : } \mathcal{B}_r \cup \mathcal{B}_s \neq \mathbb{N}\)

이는 두 Beatty Sequence 중 어느 것에도 속하지 않는, 

즉 \( \ kr  < j \ \vee \ j+1 < (k+1)r,  ms  < j \vee j+1< (m+1)s \rfloor\)인 \(j\)가 존재하는 경우이다. 

원래는 \((k+1)r \ge j+1\)로 써야 하지만, \(r\)이 무리수이므로 등호를 제거할 수 있다. (\(s\)도 마찬가지)

case I와 마찬가지로 식을 정리하면 

\(k < j/r \ \vee \ m < j/s \Rightarrow k+m < j(1/r + 1/s) = j\)

\(k+1 > (j+1)/r  \ \vee \ m+1 > (j+1)/s \Rightarrow k+m+2 > j+1\)

\(\therefore k+m < j < k+m+1\)이므로 \(j\)가 정수라는 가정에 모순. \(\blacksquare\)