x1,x2,…,x9 是依次排列的九盏灯，只有当 x(i-1) 开灯时才能开关 xi，问一些有关问题

wintex

請問計數問題
有一种不太成熟的想法：1、不管什么状态下一步都只有两种或一种可变状态，且统计上平均，故可得结论每种状态下可变状态为3/2种是嗎？；
2、若有N盏灯，每盏灯两种状态，共2^N种状态；3、若最少变换，不会经过重复状态。
结论：N盏灯从任一状态变到其他状态最多经过2/3*2^N种，考虑到可能不能整除，再取整。

請問為什麼？謝謝老師。

luyuanhong

题  x1,x2,…,x9 是从左到右依次排列的九盏灯，x1 在任何情况下都可以开关，

对 i=2,3,…,9 ，xi 必须在它的左边只有 x(i-1) 一盏灯开灯时，才能开关。

（1）如果所有灯都处于开灯状态，要将 x4 关闭，至少需要几次开关操作？

（2）如果除 x6 以外，所有灯处于开灯状态，要将所有灯都打开，至少需要几次

    开关操作？

解  下面用 O 表示开灯状态，用 X 表示关灯状态。

（1）至少要操作 3 次，具体操作步骤如下：

     x1  x2  x3  x4  x5  x6  x7  x8  x9

     O   O   O   O   O   O   O   O   O

1.   O   X   O   O   O   O   O   O   O

2.   X   X   O   O   O   O   O   O   O

3.   X   X   O   X   O   O   O   O   O

（2）至少要操作 21 次，具体操作步骤如下：

     x1  x2  x3  x4  x5  x6  x7  x8  x9

     O   O   O   O   O   X   O   O   O

1.   O   X   O   O   O   X   O   O   O

2.   X   X   O   O   O   X   O   O   O

3.   X   X   O   X   O   X   O   O   O

4.   O   X   O   X   O   X   O   O   O

5.   O   O   O   X   O   X   O   O   O

6.   X   O   O   X   O   X   O   O   O

7.   X   O   X   X   O   X   O   O   O

8.   O   O   X   X   O   X   O   O   O

9.   O   X   X   X   O   X   O   O   O

10.  X   X   X   X   O   X   O   O   O

11.  X   X   X   X   O   O   O   O   O

12.  O   X   X   X   O   O   O   O   O

13.  O   O   X   X   O   O   O   O   O

14.  X   O   X   X   O   O   O   O   O

15.  X   O   O   X   O   O   O   O   O

16.  O   O   O   X   O   O   O   O   O

17.  O   X   O   X   O   O   O   O   O

18.  X   X   O   X   O   O   O   O   O

19.  X   X   O   O   O   O   O   O   O

20.  O   X   O   O   O   O   O   O   O

21.  O   O   O   O   O   O   O   O   O

王守恩

luyuanhong 发表于 2020-1-23 23:58
题  x1,x2,…,x9 是从左到右依次排列的九盏灯，x1 在任何情况下都可以开关，

对 i=2,3,…,9 ，xi 必须在 ...

题  x1,x2,…,xn 是从左到右依次排列的n盏灯，x1 在任何情况下都可以开关，
对 i=2,3,…,n ，xn 必须在它的左边只有 x(n-1) 一盏灯开灯时，才能开关。
如果所有灯都处于开灯状态，要将 xn关闭，至少需要几次开关操作？

先从简单说起。
要将 x1 关闭，至少需要 1 次开关操作
要将 x2 关闭，至少需要 1 次开关操作
要将 x3 关闭，至少需要 2 次开关操作
要将 x4 关闭，至少需要 3 次开关操作
要将 x5 关闭，至少需要 6 次开关操作
要将 x6 关闭，至少需要 11 次开关操作
要将 x7 关闭，至少需要 22 次开关操作
要将 x8 关闭，至少需要 43 次开关操作
要将 x9 关闭，至少需要 86 次开关操作

Table[Ceiling[2^n/3], {n, 0, 14}]
xn={1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462}

Table[(2^n + 2 - Mod[n, 2])/3, {n, 0, 14}]
xn={1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462}

Table[(2^n + 3 - Cos[n*\[Pi]])/6, {n, 1, 15}]
xn={1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462}

LinearRecurrence[{2, 1, -2}, {1, 1, 2}, 15]
xn={1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462}

永远

luyuanhong 发表于 2020-1-23 23:58
题  x1,x2,…,x9 是从左到右依次排列的九盏灯，x1 在任何情况下都可以开关，

对 i=2,3,…,9 ，xi 必须在 ...

陆老师好，新年快乐！鼠年大吉。

王守恩

luyuanhong 发表于 2020-1-23 23:58
题  x1,x2,…,x9 是从左到右依次排列的九盏灯，x1 在任何情况下都可以开关，

对 i=2,3,…,9 ，xi 必须在 ...

题  x1,x2,…,xn 是从左到右依次排列的n盏灯，x1 在任何情况下都可以开关，
对 i=2,3,…,n ，xn 必须在它的左边只有 x(n-1) 一盏灯开灯时，才能开关。
如果所有灯都处于开灯状态，要将 xn关闭，至少需要几次开关操作？
操作 0 次，a(00)=0
操作 1 次，a(01)=1
操作 2 次，a(02)=11
操作 3 次，a(03)=01
操作 4 次，a(04)=011
操作 5 次，a(05)=111
操作 6 次，a(06)=101
操作 7 次，a(07)=001
操作 8 次，a(08)=0011
操作 9 次，a(09)=1011
操作10次，a(10)=1111
操作11次，a(11)=0111
操作12次，a(12)=0101
操作13次，a(13)=1101
操作14次，a(14)=1001
操作15次，a(15)=0001
操作16次，a(16)=00011
操作17次，a(17)=10011
操作18次，a(18)=11011
操作19次，a(19)=01011
操作20次，a(20)=01111
操作21次，a(21)=11111
操作22次，a(22)=10111
操作23次，a(23)=00111
操作24次，a(24)=00101
操作25次，a(25)=10101
操作26次，a(26)=11101
操作27次，a(27)=01101
操作28次，a(28)=01001
操作29次，a(29)=11001
操作30次，a(30)=10001
操作31次，a(31)=00001
操作32次，a(32)=000011
操作33次，a(33)=100011
操作34次，a(34)=110011
操作35次，a(35)=010011
操作36次，a(36)=011011
操作37次，a(37)=111011
操作38次，a(38)=101011
操作39次，a(39)=001011
操作40次，a(40)=001111
操作41次，a(41)=101111
操作42次，a(42)=111111
操作43次，a(43)=011111
操作44次，a(44)=010111
操作45次，a(45)=110111
操作46次，a(46)=100111
操作47次，a(47)=000111
操作48次，a(48)=000101
操作49次，a(49)=100101
操作50次，a(50)=110101
操作51次，a(51)=010101
操作52次，a(52)=011101
操作53次，a(53)=111101
操作54次，a(54)=101101
操作55次，a(55)=001101
操作56次，a(56)=001001
操作57次，a(57)=101001
操作58次，a(58)=111001
操作59次，a(59)=011001
操作60次，a(60)=010001
操作61次，a(61)=110001
操作62次，a(62)=100001
操作63次，a(63)=000001
操作64次，a(64)=0000001
操作65次，a(65)=1000001
操作66次，a(66)=1100001
操作67次，a(67)=0100001
操作68次，a(68)=0110001
操作69次，a(69)=1110001
操作70次，a(70)=1010001
.............
问：操作 n 次，a(n)的通项公式可以有吗？