Beatty Sequence와 Rayleigh's theorem

2017. 12. 15. 22:46수학 이론/이산수학

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

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


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\)

'수학 이론 > 이산수학' 카테고리의 다른 글

Ore's theorem & Palmer's algorithm  (0) 2019.08.17
Bessel's Correction (Revised)  (1) 2019.03.27
Mirsky's theorem  (3) 2018.11.04
LYM inequality와 Sperner's theorem  (0) 2018.07.23
High Girth & High Chromatic with Probabilistic method  (0) 2017.12.23