貝亞蒂定理

佇咧數論中，貝亞蒂定理（英文：Beatty sequence）指：若是 $ p , q \ in \ mathbb { R ^ { + } } , p , q \ not \ in \ mathbb { Q } $ 予得 $ { \ frac { 一 } { p } } + { \ frac { 一 } { q } }=一 $。定義集（貝亞蒂列）$ P=\ { \ lfloor np \ rfloor : n \ in \ mathbb { Z } ^ { + } \ } , Q=\ { \ lfloor nq \ rfloor : n \ in \ mathbb { Z } ^ { + } \ } $，著 P 和 Q 構成正整數集的一个分劃：$ P \ cap Q=\ emptyset $，$ P \ cup Q=\ mathbb { Z } ^ { + } $。

就是講：若兩个正無理數的倒算之和是一，則任何正整數攏會拄仔好用一種形式表示無大於其中一个無理數的正整數倍的上大整數。

此定理由 Sam Beatty 佇一九二六年發現。

例

比如講對黃金分割率 $ \ phi $ 來講，會使著 $ r=\ phi $，有 $ s=\ phi + 一={ \ frac { \ phi } { \ phi 影一 } } $（根據黃金分割率的性質），生做兩个序列：

一，三，四，六，八，九，十一，十二，十四，. . .（sequence A 兩百空一 in the OEIS）
二，五，七，十，十三，十五，. . .（sequence A 一千九百五十 in the OEIS）

這被用來構建 Wythoff array，是證明威佐夫博弈的一个關鍵步驟。

Rayleigh 定理

Rayleigh 定理，閣予人號做貝亞蒂定理，定義做：

指定一个無理數 $ r > 一 $，遮有一个數佇咧 $ s > 一 $ 予得貝亞蒂序列 $ B $ 和 $ B'$ 引出的仝名集合將正整數集合劃分：即所有的正整數屬於而且屬於兩个集合中的一个。

頭一種證明

予定 $ r > 一 $，予得 $ s=r / ( r 影一 ) $，必須愛證明任意一个正整數屬於而且干焦屬於序列對應的集合 $ B=\ { \ lfloor nr \ rfloor | n \ in \ mathbb { Z } \ } $ 抑是講 $ B'=\ { \ lfloor ns \ rfloor | n \ in \ mathbb { Z } \ } $ 中的一个。

為著證明伊，會當構建兩个無仝的無交集的集合併排做一个有序列（會當通過序列的序性，使得下標佮值一一對應），通過構造值佮對應下標的一一對應的關係，證明任意一个正整數對應的值屬於而且屬於兩个集合中的一个，咧對應兩个集合的下標集合正正是 $ B $ 和 $ B'$。

需要考慮如下：著正整數 $ j $ 和 $ k $ 來講，有分數 $ j \ over r $ 和 $ k \ over s $ 形成的序列。這兩个序列對應的集合無交集，而且𠢕證明序列本身無重複元素。

無交集會當用反證法，證明兩个數 $ j , \ k \ in \ mathbb { Z } $，有 $ { j \ over r }={ k \ over s } $，遐爾仔滿足：$ { j \ over k }={ r \ over s }=r 影一 $，因為乎 $ r $ 屬於無理數，故 $ r 影一 $ 嘛屬於無理數，袂當予兩个有理數比來進行表示講，矛盾故𪜶形成的集合無交集。

將兩个序列組合做一个序列，需要證明值 $ j \ over r $ 對應的下標就是 $ \ lfloor js \ rfloor $：佇咧 $ i \ over r $ 形成的子序列內底，$ j \ over r $ 的下標為 $ j $；佇咧另外一个子序列，即 $ k \ over s $ 形成的序列內底，$ j \ over r $ 頭前總共有 $ \ lfloor { js \ over r } \ rfloor $ 個數，綜上伊的下標就為 $ j + \ lfloor { js \ over r } \ rfloor=j + \ lfloor { j ( s 影一 ) } \ rfloor=\ lfloor { j + j ( s 影一 ) } \ rfloor=\ lfloor { js } \ rfloor $。同理值 $ k \ over s $ 對應的下標就為 $ \ lfloor kr \ rfloor $。

綜合這兩个無交集的序列合成的序列下標佮值本身是一一對應的，價值本身佮 $ B $ 和 $ B'$ 是相對的，會當證明這是一个劃分。

第二種證明

重複 : 準講，佮定理反倒轉來，有整數 _ j _ > 零和 _ k _ 和 _ m _ 予得

$ j=\ left \ lfloor { k \ cdot r } \ right \ rfloor=\ left \ lfloor { m \ cdot s } \ right \ rfloor \ , . $

這个等價於不等式

$ j \ leq k \ cdot r < j + 一 { \ text { 而且 } } j \ leq m \ cdot s < j + 一 . $

對無空的 _ j _ , 沒有理數 _ r _ 和 _ s _ , 等號無可能成立。所以乎

$ j < k \ cdot r < j + 一 { \ text { 而且 } } j < m \ cdot s < j + 一 $

對而且

$ { j \ over r } < k < { j + 一 \ over r } { \ text { 而且 } } { j \ over s } < m < { j + 一 \ over s } . $

共伊相加並利用條件得，

$ j < k + m < j + 一 $

這無可能 ( 兩个相鄰整數之間無其他的整數 ) . 所以假使無成立 .

落勾 : 準講，佮定理反倒轉來，有整數 _ j _ > 零和 _ k _ 和 _ m _ 予得

$ k \ cdot r < j { \ text { 而且 } } j + 一 \ leq ( k + 一 ) \ cdot r { \ text { 而且 } } m \ cdot s < j { \ text { 而且 } } j + 一 \ leq ( m + 一 ) \ cdot s \ , . $

因為乎 _ j _ + 一非零而且 _ r _ 和 _ s _ 為無理數，等號無可能成立，所以乎

$ k \ cdot r < j { \ text { 而且 } } j + 一 < ( k + 一 ) \ cdot r { \ text { 而且 } } m \ cdot s < j { \ text { 而且 } } j + 一 < ( m + 一 ) \ cdot s . $

所以伊著

$ k < { j \ over r } { \ text { 而且 } } { j + 一 \ over r } < k + 一 { \ text { 而且 } } m < { j \ over s } { \ text { 而且 } } { j + 一 \ over s } < m + 一 $

來共遮的無等式相加甲

$ k + m < j { \ text { 而且 } } j + 一 < k + m + 二 $

$ k + m < j < k + m + 一 $

這無可能。所以假使無成立 .

外部連結

http : / / www . sftw . umac . mo / ~ fstitl / 十 mmo / betty . html