自然数大分家

Wed, 27th November 2019Edit on Githubsequence

自然数分家 - 威佐夫博弈和Beatty定理

PKU-1067是一个石子游戏,这其实是一个威佐夫博弈问题, 英文维基百科 也有详尽描述。
问题的大概描述是: 有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
如果两堆余下物品分别在下面图标中数目时:
wythoff
是接下去先手会输的局面,我们称这种问题中的必败态为奇异局势(ak,bk)(a_k,b_k)
可以看到,a0=b0=0a_0=b_0=0aka_k是未在前面出现过的最小自然数,而bk=ak+kb_k=a_k+k
进一步分析可以发现:
任何自然数都包含在一个且仅有一个奇异局势中,
由于aka_k是未在前面出现过的最小自然数,所以有ak>ak1a_k \gt a_{k−1}
bk=ak+k>ak1+k>ak1+k1=bk1>ak1b_k=a_k+k\gt a_{k−1}+k\gt a_{k−1}+k−1=b_{k−1}\gt a_{k−1}
其中ak=kωa_k=\lfloor k\omega\rfloor, 其中ω2=ω+1\omega^2=\omega+1,即ω=1.618\omega = 1.618\dots即所谓黄金分割数,而bk=kψb_k=\lfloor k\psi\rfloor,其中ψ=ω+1\psi=\omega+1
实际上ana_nbnb_n构成了一个Beatty序列。

Beatty定理

aba,b是正无理数且1a+1b=1\frac1a+\frac1b=1
P={nan为任意的正整数}Q={nbn为任意的正整数}P=\{\lfloor na\rfloor|n为任意的正整数\},Q=\{\lfloor nb\rfloor|n为任意的正整数\}
x\lfloor x\rfloor指的是不好过xx的最大整数)
PPQQZ+Z^{+}的一个划分,即PQP∩Q为空集且PQP∪Q为正整数集合Z+Z^{+}

即对于任意满足条件的无理数a,ba,b, 数列na\lfloor na\rfloornb\lfloor nb\rfloor实现了正整数集的完美分家。

三家分赵

王守恩在2019年10月询问{a(n)}{b(n)}{c(n)}\{a(n)\}\cup\{b(n)\}\cup\{c(n)\}正好构成正整数集吗?为什么? 其中:
{a(n)}={1, 4, 07, 09, 12, 15, 16, 19, 22, 25, 27, 30, 32, 34, 37, 40, 43, 45, 47, 50, 52, 55, 58, 60, 63, 65,...}
{b(n)}={2, 5, 08, 11, 14, 18, 20, 23, 26, 29, 33, 36, 38, 41, 44, 48, 51, 54, 56, 59, 62, 66, 69, 72, 75, 77,...}
{c(n)}={3, 6, 10, 13, 17, 21, 24, 28, 31, 35, 39, 42, 46, 49, 53, 57, 61, 64, 67, 71, 74, 79, 82, 85, 89, 92,...}

a(n)=n+n124+n144a(n)=n+\lfloor n\sqrt[4]{\frac12}\rfloor+\lfloor n\sqrt[4]{\frac14}\rfloor

b(n)=n+n124+n24b(n)=n+\lfloor n\sqrt[4]{\frac12}\rfloor+\lfloor n\sqrt[4]{2}\rfloor

c(n)=n+n44+n24c(n)=n+\lfloor n\sqrt[4]{4}\rfloor+\lfloor n\sqrt[4]{2}\rfloor

lsr314分析发现 , 貌似只要t>0t\gt 0t2,t+1t,t+t2,1t+1t2t^2,t+\frac1t,t+t^2,\frac1t+\frac1{t^2}都是无理数,那么 an=n+nt+nt2,bn=n+nt+nt,cn=n+nt2+nt,a_n=n+\lfloor\frac nt\rfloor+\lfloor\frac n{t^2}\rfloor,b_n=n+\lfloor\frac nt\rfloor+\lfloor nt\rfloor,c_n=n+\lfloor\frac n{t^2}\rfloor+\lfloor nt\rfloor, x\lfloor x\rfloor表示xx的整数部分,那么每个正整数刚好在an,bn,cna_n,b_n,c_n中出现一次。本题中t=214t=2^{\frac14}

群雄逐鹿

王守恩继续问, 还可以有 {a(n)}{b(n)}{c(n)}{d(n)}\{a(n)\}\cup\{b(n)\}\cup\{c(n)\}\cup\{d(n)\}正好构成正整数集吗?

lsr314继续做出解答
如果t1,t2,,tkt_1,t_2,…,t_k都是正数,且任意两个数的比值都是无理数,
ai(n)=j=1ktjtin,i=1,2,k.a_i(n)=\sum_{j=1}^k\lfloor\frac{t_j}{t_i} n\rfloor,i=1,2,…k. 那么每个正整数在数列a1(n),ak(n)a_1(n),…a_k(n)中恰好出现一次。

自然数大分家 - Fibonacci矩阵

mathe在csdn的博客 中, 如下定义一个无限阶矩阵m:
矩阵第0行正好是Fibonacci数列,也就是 m0,0=1,m0,1=2,m0,2=3,m0,3=5,m0,4=8,m_{0,0}=1,m_{0,1}=2,m_{0,2}=3, m_{0,3}=5,m_{0,4}=8,\dots 矩阵第k行中第一个数字是前面k-1行中都没有出现的最小正整数, 所以 m1,0=4,mk,1=2mk,0km_{1,0}=4, 而m_{k,1}=2m_{k,0}-k (这个关系对于第0行也成立), 比如m1,1=2×41=7m_{1,1}=2\times4-1=7
而第k行后面的任意一个数的递推关系同第一行类似,是当前行前面两个数的和。
比如m1,2=m1,0+m1,1=11,m_{1,2}=m_{1,0}+m_{1,1}=11,\dots
于是我们可以得到如下的Fibonacci矩阵

12358132134558914447111829477612319932252161016264268110178288466754915243963102165267432699113112203252841362203565769321508142337609715725441166510761741\begin{matrix} 1&2&3&5&8&13&21&34&55&89&144&\dots\\ 4&7&11&18&29&47&76&123&199&322&521&\dots\\ 6&10&16&26&42&68&110&178&288&466&754&\dots\\ 9&15&24&39&63&102&165&267&432&699&1131&\dots\\ 12&20&32&52&84&136&220&356&576&932&1508&\dots\\ 14&23&37&60&97&157&254&411&665&1076&1741&\dots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{matrix}

我们可以神奇的发现,这个矩阵正好包含了所有的自然数,而且每个自然数只出现一次,它实现了正整数集更大的分家。
链接中还提出了如下一些问题:
问题1)
我们计算所有的mk+1,0mk,0m_{k+1,0}-m_{k,0},我们可以得到如下序列:
32332...
证明或否定:所有的mk+1,0mk,0m_{k+1,0}-m_{k,0}必然是2或者3.
问题2)
我们在一张白纸上先写下
32
两个数
然后从这行数第一个数字开始查看,每看到一个3,在后面添加三个数332;每看到一个2,在后面添加两个数32,
比如第一次操作,由于第一个数是3,添加332,所以数列变成:
32332
第二次操作,由于第二个数是2,添加32,所以数列变成
3233232
第三次操作,由于第三个数是3,添加332,所以数列变成
3233232332
一直这样下去
证明或否定,这样得到的一个序列正好是(1)中由所有mk+1,0mk,0m_{k+1,0}-m_{k,0}顺序排成的序列.
这个方法给出了一种快速构造上面矩阵的方案。

Github