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$