贝亚蒂定理

在数论中，贝亚蒂定理（英语：Beatty's theorem），又称瑞利定理（英语：Rayleigh's theorem）指：若 <math> p,q \in \mathbb{R^+} ,p,q \not\in \mathbb{Q} </math> 使得 <math>\frac{1}{p} + \frac{1}{q} = 1</math>，它们所生成的贝亚蒂数列（英语：Beatty sequence）<math>P = \{\lfloor np \rfloor : n \in\mathbb Z^+ \}, Q=\{\lfloor nq \rfloor : n \in\mathbb Z^+\}</math>，构成正整数集的一个划分：<math> P \cap Q = \emptyset</math>，<math>P \cup Q =\mathbb Z^+</math>。

即是说：若两个正无理数的倒数之和是1，则任何正整数都可刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

此定理由Sam Beatty在1926年发现。

例子

比如说对于黄金分割率 <math>\phi</math> 而言，可以令 <math>r = \phi</math>，有 <math>s = \phi + 1 = \frac{\phi}{\phi - 1}</math>（根据黄金分割率的性质），生成两个序列：

• 1，3，4，6，8，9，11，12，14，...（sequence A000201 in the OEIS）
• 2，5，7，10，13，15，...（sequence A001950 in the OEIS）

这被用来构建 Wythoff array，是证明威佐夫博弈的一个关键步骤。

Rayleigh 定理

Rayleigh 定理，又被称为贝亚蒂定理，定义为：

指定一个无理数 <math>r > 1</math> ，这里存在着一个数 <math>s > 1</math> 使得贝亚蒂序列 <math>B</math> 和 <math>B'</math> 引出的同名集合将正整数集合划分：即所有的正整数属于且仅属于两个集合中的一个。

第一种证明

给定 <math>r > 1</math>，使得 <math>s = r / (r-1)</math>，必须要证明任意一个正整数属于且仅属于序列对应的集合 <math>B = \{\lfloor nr \rfloor | n \in \mathbb{Z}\}</math> 或者 <math>B' = \{\lfloor ns \rfloor | n \in \mathbb{Z}\}</math> 中的一个。

为了证明它，可以构建两个不同的没有交集的集合并排成一个有序序列（可以通过有序序列的有序性，使得下标和值一一对应），通过构造值和对应下标的一一对应的关系，证明任意一个正整数对应的值属于且仅属于两个集合中的一个，而对应两个集合的下标集合正是 <math>B</math> 和 <math>B'</math>。

需要考虑如下：对于正整数 <math>j</math> 和 <math>k</math> 而言，有分数 <math>j \over r</math> 和 <math>k \over s</math> 形成的序列。这两个序列对应的的集合没有交集，且容易证明序列本身没有重复元素。

没有交集可以利用反证法，证明两个数 <math>j,\ k \in \mathbb{Z}</math>，有 <math>{j \over r} = {k \over s}</math>，那么满足：<math>{j \over k} = {r \over s} = r - 1</math>，因为 <math>r</math> 属于无理数，故 <math>r - 1</math> 也属于无理数，不能被两个有理数的比来进行表示，矛盾故它们形成的集合没有交集。

将两个序列组合成一个序列，需要证明值 <math>j \over r</math> 对应的下标就是 <math>\lfloor js\rfloor</math>：在 <math>i \over r</math> 形成的子序列中，<math>j \over r</math> 的下标为 <math>j</math>；而在另一个子序列，即 <math>k \over s</math> 形成的序列中，<math>j \over r</math> 前面一共有 <math>\lfloor{js \over r}\rfloor</math> 个数，综上它的下标就为 <math>j + \lfloor{js \over r}\rfloor =j + \lfloor{ j(s - 1)}\rfloor = \lfloor{j + j(s - 1)}\rfloor = \lfloor{js}\rfloor</math>。同理值 <math>k \over s</math> 对应的下标就为 <math>\lfloor kr\rfloor</math>。

综上这两个没有交集的序列合成的序列下标和值本身是一一对应的，值本身和 <math>B</math> 和 <math>B'</math> 是对应的，可以证明这是一个划分。

第二种证明

重复: 假设, 与定理相反地, 有整数 j > 0 和 k 和 m 使得

<math>j = \left\lfloor {k \cdot r} \right\rfloor = \left\lfloor {m \cdot s} \right\rfloor \,.</math>

这等价于不等式

<math>j \le k \cdot r < j + 1 \text{ 且 } j \le m \cdot s < j + 1. </math>

对于非零的 j, 无理数r 和 s, 等号不可能成立. 所以

<math>j < k \cdot r < j + 1 \text{ 且 } j < m \cdot s < j + 1 </math>

从而

<math>{j \over r} < k < {j + 1 \over r} \text{ 且 } {j \over s} < m < {j + 1 \over s}. </math>

将它们相加并利用条件得,

<math>j < k + m < j + 1 </math>

这是不可能的 (两个相邻整数之间没有其他的整数). 所以假设不成立.

遗漏: 假设, 与定理相反地, 有整数 j > 0 和 k 和 m 使得

<math>k \cdot r < j \text{ 且 } j + 1 \le (k + 1) \cdot r \text{ 且 } m \cdot s < j \text{ 且 } j + 1 \le (m + 1) \cdot s \,.</math>

因为 j + 1 非零且 r 和 s 为无理数, 等号不可能成立, 所以

<math>k \cdot r < j \text{ 且 } j + 1 < (k + 1) \cdot r \text{ 且 } m \cdot s < j \text{ 且 } j + 1 < (m + 1) \cdot s. </math>

于是得

<math>k < {j \over r} \text{ 且 } {j + 1 \over r} < k + 1 \text{ 且 } m < {j \over s} \text{ 且 } {j + 1 \over s} < m + 1 </math>

将这些不等式相加得

<math>k + m < j \text{ 且 } j + 1 < k + m + 2 </math>

<math>k + m < j < k + m + 1 </math>

这是不可能的. 所以假设不成立.

外部链接

• http://www.sftw.umac.mo/~fstitl/10mmo/betty.html （页面存档备份，存于互联网档案馆）