b******r
发帖数: 1 | 1 如果每盏灯的开关不止开，关两种状态，而是有四档：关，亮度1，亮度2,亮度3。
每次小明动开关只能动其中k个开关，每个开关只能调一档。(0裆可以到1裆,但不能直
接到2裆,3裆；3当也不能到0裆。)
如果小明每次动k个开关，一共动了4^n次使得n盏灯遍历了所有的亮度状态组合并且回
到最初始的状态，那么(n,k) 就是好的。
这种情况下好的(n,k) 有哪些？ |
T*******x
发帖数: 8565 | 2 你这个的问题不允许灯档位0123循环，应该增大了很多难度。组合问题很难找出通解，
尤其是限制条件不那么对称的情况下。
经你提醒我又想了一下原问题，灯档位只有01的。我又看了一下你和另外一位的证法，
似乎都有gap。
比如你说直接跳k位，最后还是个loop，这没问题。但是怎么保证k位的和0位之间差k个
灯的变化？
另外一位用Z2 feild vector space证明的，似乎也有gap。包含k个1的向量中可以选出
一组基和标准基e1,e2,…一一对应，这没问题，well，这应该没问题。但是怎么保证以
这种对应走出的路径不重复经过点呢？
【在 b******r 的大作中提到】
: 如果每盏灯的开关不止开，关两种状态，而是有四档：关，亮度1，亮度2,亮度3。
: 每次小明动开关只能动其中k个开关，每个开关只能调一档。(0裆可以到1裆,但不能直
: 接到2裆,3裆；3当也不能到0裆。)
: 如果小明每次动k个开关，一共动了4^n次使得n盏灯遍历了所有的亮度状态组合并且回
: 到最初始的状态，那么(n,k) 就是好的。
: 这种情况下好的(n,k) 有哪些？
|
b******r
发帖数: 1 | 3 i和i加1位之间差的一次开关的操作，i和i加k之间当然差的就是k次开关操作。
线性代数的办法没仔细看，但本质上应该都是一样。
不过光有基不行，基的顺序也一样重要。
【在 T*******x 的大作中提到】
: 你这个的问题不允许灯档位0123循环，应该增大了很多难度。组合问题很难找出通解，
: 尤其是限制条件不那么对称的情况下。
: 经你提醒我又想了一下原问题，灯档位只有01的。我又看了一下你和另外一位的证法，
: 似乎都有gap。
: 比如你说直接跳k位，最后还是个loop，这没问题。但是怎么保证k位的和0位之间差k个
: 灯的变化？
: 另外一位用Z2 feild vector space证明的，似乎也有gap。包含k个1的向量中可以选出
: 一组基和标准基e1,e2,…一一对应，这没问题，well，这应该没问题。但是怎么保证以
: 这种对应走出的路径不重复经过点呢？
|
T*******x
发帖数: 8565 | 4 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有gap。gap
存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
我一会儿再把这个证明展开一下，变成一个算法。
【在 T*******x 的大作中提到】
: 你这个的问题不允许灯档位0123循环，应该增大了很多难度。组合问题很难找出通解，
: 尤其是限制条件不那么对称的情况下。
: 经你提醒我又想了一下原问题，灯档位只有01的。我又看了一下你和另外一位的证法，
: 似乎都有gap。
: 比如你说直接跳k位，最后还是个loop，这没问题。但是怎么保证k位的和0位之间差k个
: 灯的变化？
: 另外一位用Z2 feild vector space证明的，似乎也有gap。包含k个1的向量中可以选出
: 一组基和标准基e1,e2,…一一对应，这没问题，well，这应该没问题。但是怎么保证以
: 这种对应走出的路径不重复经过点呢？
|
T*******x
发帖数: 8565 | 5 不对。i和i加k之间差的是k次开关操作，但不一定是在k盏灯上，可以比如在3盏灯上做
k=5次开关操作。
【在 b******r 的大作中提到】
: i和i加1位之间差的一次开关的操作，i和i加k之间当然差的就是k次开关操作。
: 线性代数的办法没仔细看，但本质上应该都是一样。
: 不过光有基不行，基的顺序也一样重要。
|
T*******x
发帖数: 8565 | 6 对于原问题，灯只有开关两种状态，lowai的方法是可以的。如果说有gap的话，这个
gap很可能是在我的理解之中。就是找基那个地方。我相信肯定是没问题的。
所以我给一个有算法的证法，这样就不存在找基的问题了。
1. (n,1) 肯定走得通。surprisingly，并不是特别容易。因为这也是一个一笔画的问
题，能不能走通，看configuration。还是需要证明的。
2. k是偶数的时候，这个容易说明 - 不改变灯总体奇偶性，不可能走通。
3. 如果(n,k)是“好的”，那么(n+1,k)是好的。这个和1一样，都需要同一个算法说明。
4. 对于任意偶数n，余一盏是走得通的，也就是k=n-1。这个可以用到lowai的方法，但
是很直观。
1234加在一起就可以证明任意奇数k，n>k，(n,k)是“好的”。
(1)和(3)的算法是数学归纳法，考虑k=1，假设n成立，那么n+1成立。为此把n+1个灯的
开关状态想象成2^{n+1}的多维正方体的顶点，并把它拆为2个2^n个多维正方体a，b，
第一个编号，a1,a2,a...2^n，第二个对应编号b1,b2,b...2^n，两个ab同编号顶点之间
相差的就是最后那一维。如果a能走通，走到最后一步的时候，不回到原点，调到相应b
点上，然后按a的方法反着走，会走到a起始点对应的b点，最后一步回到a起始点。(3)
的证明方法一样。
(4)的证明方法，因为k=n-1，那么按照开关一盏的顺序，每次开关余一盏，也就是剩下
的那些。这个相当于找基，但是比较直观，这叫canonical。不存在重复走过一点的问
题，这是我糊涂了，因为这两组基是逐点一一映射，线性。
gap
【在 T*******x 的大作中提到】
: 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有gap。gap
: 存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
: 我一会儿再把这个证明展开一下，变成一个算法。
|
S**********A
发帖数: 1 | 7 简单画了一下
先考虑k = 1，对于n=2是哈密顿图，并且对于n > 2也是一样的
可以写成一个4层(多次嵌套)的哈密顿图（radix = 4的格雷码）
只要有一个回路，k = 1成立，则1 + 2k都成立，按照同一回路traverse
【在 b******r 的大作中提到】
: 如果每盏灯的开关不止开，关两种状态，而是有四档：关，亮度1，亮度2,亮度3。
: 每次小明动开关只能动其中k个开关，每个开关只能调一档。(0裆可以到1裆,但不能直
: 接到2裆,3裆；3当也不能到0裆。)
: 如果小明每次动k个开关，一共动了4^n次使得n盏灯遍历了所有的亮度状态组合并且回
: 到最初始的状态，那么(n,k) 就是好的。
: 这种情况下好的(n,k) 有哪些？
|
S**********A
发帖数: 1 | 8 可以这么解:
由于n-ary 格雷码一定存在，所以这个图必然是作为(4,n）-gray code的一个哈密顿图
那么就一定存在一个k=1的路径
按照下文同样的办法可以证明
https://www.mitbbs.com/article/Military/64783715_0.html
奇数step size都有解
【在 S**********A 的大作中提到】
: 简单画了一下
: 先考虑k = 1，对于n=2是哈密顿图，并且对于n > 2也是一样的
: 可以写成一个4层(多次嵌套)的哈密顿图（radix = 4的格雷码）
: 只要有一个回路，k = 1成立，则1 + 2k都成立，按照同一回路traverse
|
b******r
发帖数: 1 | 9 我理解错了，以为是开关 k次。
如果开关 k 盏灯会复杂些。。。。
k=1时候没有区别。
k>1的时候。注意到两件事：
1.如果(n,k) 是好的，不难证明,(n加1,k) 也是好的。(可以直接构造出来)
2.如果(n,k) 是好的，且 n 为偶数，(n, n-k) 也是好的。(每一步操作都取对偶)
所以综上所述，对于所有的 k
: 不对。i和i加k之间差的是k次开关操作，但不一定是在k盏灯上，可以比如在3盏
灯上做
: k=5次开关操作。
【在 T*******x 的大作中提到】
: 对于原问题，灯只有开关两种状态，lowai的方法是可以的。如果说有gap的话，这个
: gap很可能是在我的理解之中。就是找基那个地方。我相信肯定是没问题的。
: 所以我给一个有算法的证法，这样就不存在找基的问题了。
: 1. (n,1) 肯定走得通。surprisingly，并不是特别容易。因为这也是一个一笔画的问
: 题，能不能走通，看configuration。还是需要证明的。
: 2. k是偶数的时候，这个容易说明 - 不改变灯总体奇偶性，不可能走通。
: 3. 如果(n,k)是“好的”，那么(n+1,k)是好的。这个和1一样，都需要同一个算法说明。
: 4. 对于任意偶数n，余一盏是走得通的，也就是k=n-1。这个可以用到lowai的方法，但
: 是很直观。
: 1234加在一起就可以证明任意奇数k，n>k，(n,k)是“好的”。
|
T*******x
发帖数: 8565 | 10 嗯，对，和我思路差不多。
在k盏灯上，可以比如在3盏
【在 b******r 的大作中提到】
: 我理解错了，以为是开关 k次。
: 如果开关 k 盏灯会复杂些。。。。
: k=1时候没有区别。
: k>1的时候。注意到两件事：
: 1.如果(n,k) 是好的，不难证明,(n加1,k) 也是好的。(可以直接构造出来)
: 2.如果(n,k) 是好的，且 n 为偶数，(n, n-k) 也是好的。(每一步操作都取对偶)
: 所以综上所述，对于所有的 k:
:
: 不对。i和i加k之间差的是k次开关操作，但不一定是在k盏灯上，可以比如在3盏
: 灯上做
|
b******r
发帖数: 1 | 11 嘿嘿，n=1,k=1时候不成立。但n>1,k=1时候是成立的(如果我没想错的话)。
我出这个题就是觉得一般人试了n=1不成立就被吓住，不会往下试了。
: 简单画了一下
: 先考虑k = 1，对于n=2是哈密顿图，并且对于n
【在 S**********A 的大作中提到】
: 可以这么解:
: 由于n-ary 格雷码一定存在，所以这个图必然是作为(4,n）-gray code的一个哈密顿图
: 那么就一定存在一个k=1的路径
: 按照下文同样的办法可以证明
: https://www.mitbbs.com/article/Military/64783715_0.html
: 奇数step size都有解
|
b******r
发帖数: 1 | 12 刚看到你的解法，英雄所见略同。。
: 嗯，对，和我思路差不多。
: 在k盏灯上，可以比如在3盏
【在 T*******x 的大作中提到】
: 嗯，对，和我思路差不多。
:
: 在k盏灯上，可以比如在3盏
|
c********s
发帖数: 1 | 13 类似香蕉要不要吃皮的题目 一簇香蕉吃的每根顺序
【在 T*******x 的大作中提到】
: 你这个的问题不允许灯档位0123循环，应该增大了很多难度。组合问题很难找出通解，
: 尤其是限制条件不那么对称的情况下。
: 经你提醒我又想了一下原问题，灯档位只有01的。我又看了一下你和另外一位的证法，
: 似乎都有gap。
: 比如你说直接跳k位，最后还是个loop，这没问题。但是怎么保证k位的和0位之间差k个
: 灯的变化？
: 另外一位用Z2 feild vector space证明的，似乎也有gap。包含k个1的向量中可以选出
: 一组基和标准基e1,e2,…一一对应，这没问题，well，这应该没问题。但是怎么保证以
: 这种对应走出的路径不重复经过点呢？
|
b******r
发帖数: 1 | 14 你这解法跟我之前的犯的是同样的错误。。。
: 可以这么解:
: 由于n-ary 格雷码一定存在，所以这个图必然是作为(4,n）-gray code的一个哈
密顿图
: 那么就一定存在一个k=1的路径
: 按照下文同样的办法可以证明
: https://www.mitbbs.com/article/Military/64783715_0.html
: 奇数step size都有解
【在 S**********A 的大作中提到】
: 可以这么解:
: 由于n-ary 格雷码一定存在，所以这个图必然是作为(4,n）-gray code的一个哈密顿图
: 那么就一定存在一个k=1的路径
: 按照下文同样的办法可以证明
: https://www.mitbbs.com/article/Military/64783715_0.html
: 奇数step size都有解
|
c********s
发帖数: 1 | 15 香蕉和一袋开心果的选择题目
gap
【在 T*******x 的大作中提到】
: 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有gap。gap
: 存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
: 我一会儿再把这个证明展开一下，变成一个算法。
|
S**********A
发帖数: 1 | 16 修正一下,2m-ary的格雷码是循环的，一定可以有k=1的解，所以4(6, 8, 10, etc.)状
态的灯一定可以解
你指的错误是什么？
【在 b******r 的大作中提到】
: 你这解法跟我之前的犯的是同样的错误。。。
:
:
: 可以这么解:
:
: 由于n-ary 格雷码一定存在，所以这个图必然是作为(4,n）-gray code的一个哈
: 密顿图
:
: 那么就一定存在一个k=1的路径
:
: 按照下文同样的办法可以证明
:
: https://www.mitbbs.com/article/Military/64783715_0.html
:
: 奇数step size都有解
:
|
T*******x
发帖数: 8565 | 17 嗯对。你这个在n=2，k=1的时候，是4X4格子上的一笔画loop。n=1的时候走不通。但是
n=2可以。但是n=3好像又不行了。
【在 b******r 的大作中提到】
: 嘿嘿，n=1,k=1时候不成立。但n>1,k=1时候是成立的(如果我没想错的话)。
: 我出这个题就是觉得一般人试了n=1不成立就被吓住，不会往下试了。
:
:
: 简单画了一下
:
: 先考虑k = 1，对于n=2是哈密顿图，并且对于n
|
T*******x
发帖数: 8565 | 18 0123的状态要允许循环，3循环回到0，这就可以了，任意(n,1)都可以，n>1。这是那位
说的2m-ary Gray code.
【在 T*******x 的大作中提到】
: 嗯对。你这个在n=2，k=1的时候，是4X4格子上的一笔画loop。n=1的时候走不通。但是
: n=2可以。但是n=3好像又不行了。
|
T*******x
发帖数: 8565 | 19 哦，允许循环的话，状态数不需要偶数，任意数大于等于2都可以。m-ary, 不需要2m-
ary。
【在 T*******x 的大作中提到】
: 0123的状态要允许循环，3循环回到0，这就可以了，任意(n,1)都可以，n>1。这是那位
: 说的2m-ary Gray code.
|
T*******x
发帖数: 8565 | 20 不对。还是要2m-ary。
【在 T*******x 的大作中提到】
: 哦，允许循环的话，状态数不需要偶数，任意数大于等于2都可以。m-ary, 不需要2m-
: ary。
|
T*******x
发帖数: 8565 | 21 但是k>1可能就不行了，奇数也不行。这里看来那个Z2 field vector space的确起作用
了。2m个状态，它不构成finite field，找基的argument就不再成立了。
【在 T*******x 的大作中提到】
: 0123的状态要允许循环，3循环回到0，这就可以了，任意(n,1)都可以，n>1。这是那位
: 说的2m-ary Gray code.
|
S**********A
发帖数: 1 | 22 k is odd,只需要证明任意 1 + i k 不等于1 + jk mod 4^n (aka无重复)
假设有重复,(i -j)k = 0 mod 4^n, or (i - j)k = 4^n * r, for some r
k是奇数所以4^n | (i-j), 这是不可能的，因为0 <= i, j <= 4^n - 1，
所以随便一个奇数k都成立
【在 T*******x 的大作中提到】
: 但是k>1可能就不行了，奇数也不行。这里看来那个Z2 field vector space的确起作用
: 了。2m个状态，它不构成finite field，找基的argument就不再成立了。
|
T*******x
发帖数: 8565 | 23 你这个我没看懂。我再想想。
【在 S**********A 的大作中提到】
: k is odd,只需要证明任意 1 + i k 不等于1 + jk mod 4^n (aka无重复)
: 假设有重复,(i -j)k = 0 mod 4^n, or (i - j)k = 4^n * r, for some r
: k是奇数所以4^n | (i-j), 这是不可能的，因为0 <= i, j <= 4^n - 1，
: 所以随便一个奇数k都成立
|
S**********A
发帖数: 1 | 24 step size 1的时候，就是2m-ary cyclic gray code，理解成一条长度为4^n的循环
linked list
从1（or any starting point）开始，step size改成奇数k,连跳4^n - 1步后要证明这
4^n步每一个都在不相同节点，则遍历了所有4^n个节点
上面过程是反证，1 + ik = 1 + jk mod 4^n不可能，即跳4^n - 1步的过程中无重复
【在 T*******x 的大作中提到】
: 你这个我没看懂。我再想想。
|
T*******x
发帖数: 8565 | 25 哦我明白了，bookacar说你和他之前犯的是同一个错误。你这个是在step size 为1的
路径上跳k步。不会重复走过的节点，这没问题。但是每一次跳k个节点不满足要求，要
求是要改变k个灯的状态。比如k=5，要求是每一次同时改变5个灯的状态，而你这个只
是5次改变灯的状态，这5可以是只作用在3个灯上。
【在 S**********A 的大作中提到】
: step size 1的时候，就是2m-ary cyclic gray code，理解成一条长度为4^n的循环
: linked list
: 从1（or any starting point）开始，step size改成奇数k,连跳4^n - 1步后要证明这
: 4^n步每一个都在不相同节点，则遍历了所有4^n个节点
: 上面过程是反证，1 + ik = 1 + jk mod 4^n不可能，即跳4^n - 1步的过程中无重复
|
S**********A
发帖数: 1 | 26 这就尴尬了
【在 T*******x 的大作中提到】
: 哦我明白了，bookacar说你和他之前犯的是同一个错误。你这个是在step size 为1的
: 路径上跳k步。不会重复走过的节点，这没问题。但是每一次跳k个节点不满足要求，要
: 求是要改变k个灯的状态。比如k=5，要求是每一次同时改变5个灯的状态，而你这个只
: 是5次改变灯的状态，这5可以是只作用在3个灯上。
|
b******r
发帖数: 1 | 27 我也看了下线性代数的法子。
如果a1,a2, ..., am张成整个空间，一般情况下不一定可以取到若干ai 构成基。
不过这里是 F_2，貌似就可以。有意思。。。
: 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有
gap。gap
: 存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
: 我一会儿再把这个证明展开一下，变成一个算法。
【在 T*******x 的大作中提到】
: 哦我明白了，bookacar说你和他之前犯的是同一个错误。你这个是在step size 为1的
: 路径上跳k步。不会重复走过的节点，这没问题。但是每一次跳k个节点不满足要求，要
: 求是要改变k个灯的状态。比如k=5，要求是每一次同时改变5个灯的状态，而你这个只
: 是5次改变灯的状态，这5可以是只作用在3个灯上。
|
b******r
发帖数: 1 | 28 马的，这个对任意的线性代数都成立。。
我想成模了，还以为发现什么新大陆了。。。
: 我也看了下线性代数的法子。
: 如果a1,a2, ..., am张成整个空间，一般情况下不一定可以取到若干ai 构成基。
: 不过这里是 F_2，貌似就可以。有意思。。。
: gap。gap
【在 b******r 的大作中提到】
: 我也看了下线性代数的法子。
: 如果a1,a2, ..., am张成整个空间，一般情况下不一定可以取到若干ai 构成基。
: 不过这里是 F_2，貌似就可以。有意思。。。
:
:
: 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有
: gap。gap
:
: 存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
:
: 我一会儿再把这个证明展开一下，变成一个算法。
:
|
T*******x
发帖数: 8565 | 29 找基那个地方也不是完全的trivial。即使是余一法，里面也还是有点东西的。
假设有n盏灯，每盏灯只有01开关状态，n盏灯的总状态构成{0,1}^n=(Z_2)^n的vector
space，令e_i为开关第i盏灯其它不动，那么e1,e2,...,en为标准基。令(ei)为第i盏灯
不动其它动，那么我们要证明(e1),(e2),...,(en)也构成一组基。
这个用构造性的证法并不容易，比如用(e1),(e2),...,(en)构造出e1来，我试了一下，
没有完全试出来。但是把e_i->(e_i)这个基变换写成矩阵，这是一个除了对角线为0之
外全1的矩阵，记为A。可以验证当n为偶数时，A^2=I，n为奇数时，A^2=0，这是在Z2
field下。所以A的determinant也是n为偶数时等于1，n为奇数时等于0。也就是说n为偶
数时，余一法构成一组基，n为奇数时还不行。
这个小玩意能抠出不少东西啊。
【在 b******r 的大作中提到】
: 我也看了下线性代数的法子。
: 如果a1,a2, ..., am张成整个空间，一般情况下不一定可以取到若干ai 构成基。
: 不过这里是 F_2，貌似就可以。有意思。。。
:
:
: 我又想了一下原问题。Z2 field vector space那个方法（lowai的方法）没有
: gap。gap
:
: 存在于我的理解当中。:) 重复经过点的问题也不存在，这个是我糊涂了。
:
: 我一会儿再把这个证明展开一下，变成一个算法。
:
|
b******r
发帖数: 1 | 30 要写成一个通式会比较麻烦。但试个例子会很容易。每次开关k个灯，最后只让第一个
灯亮，有很大自由度，容易做到。
其实也不必证明 span，只需找出n 个线性独立的向量来就行。
比如(1..100..),(01..1100..)一直出现连续的 k个1.
所以这个办法可以得到一个更强的结论：k 为奇数的时候。可以每次开关相邻(假设n
盏灯围成一个圈)的 k 盏灯，最后再回到初始状态。
如果灯有4个状态(假设3可以循环到0)这个办法就有点问题了。这时仍然可以找到 n 个
线性独立的向量(仍然可以像上面一样找包含所有相邻的k 个1的向量)，但现在是在 Z_
4里。线性独立没法保证是基了。。。
直觉上应该仍然是基，不过需要额外的论证了。
: 找基那个地方也不是完全的trivial。即使是余一法，里面也还是有点东西的。
: 假设有n盏灯，每盏灯只有01开关状态，n盏灯的总状态构成{0,1}^n=(Z_2)^n的
vector
: space，令e_i为开关第i盏灯其它不动，那么e1,e2,...,en为标准基。令(ei)为
第i盏灯
: 不动其它动，那么我们要证明(e1),(e2),...,(en)也构成一组基。
: 这个用构造性的证法并不容易，比如用(e1),(e2),...,(en)构造出e1来，我试了
一下，
: 没有完全试出来。但是把e_i-
【在 T*******x 的大作中提到】
: 找基那个地方也不是完全的trivial。即使是余一法，里面也还是有点东西的。
: 假设有n盏灯，每盏灯只有01开关状态，n盏灯的总状态构成{0,1}^n=(Z_2)^n的vector
: space，令e_i为开关第i盏灯其它不动，那么e1,e2,...,en为标准基。令(ei)为第i盏灯
: 不动其它动，那么我们要证明(e1),(e2),...,(en)也构成一组基。
: 这个用构造性的证法并不容易，比如用(e1),(e2),...,(en)构造出e1来，我试了一下，
: 没有完全试出来。但是把e_i->(e_i)这个基变换写成矩阵，这是一个除了对角线为0之
: 外全1的矩阵，记为A。可以验证当n为偶数时，A^2=I，n为奇数时，A^2=0，这是在Z2
: field下。所以A的determinant也是n为偶数时等于1，n为奇数时等于0。也就是说n为偶
: 数时，余一法构成一组基，n为奇数时还不行。
: 这个小玩意能抠出不少东西啊。
|
T*******x
发帖数: 8565 | 31 嗯，对。n盏灯排成一圈，连续的k个1这样的，总共n个，证明它们它们线性独立。看起
来几乎不需要证明了。不过要证的话也还是写成矩阵行列式证明非零。good
discussion.
Z_
【在 b******r 的大作中提到】
: 要写成一个通式会比较麻烦。但试个例子会很容易。每次开关k个灯，最后只让第一个
: 灯亮，有很大自由度，容易做到。
: 其实也不必证明 span，只需找出n 个线性独立的向量来就行。
: 比如(1..100..),(01..1100..)一直出现连续的 k个1.
: 所以这个办法可以得到一个更强的结论：k 为奇数的时候。可以每次开关相邻(假设n
: 盏灯围成一个圈)的 k 盏灯，最后再回到初始状态。
: 如果灯有4个状态(假设3可以循环到0)这个办法就有点问题了。这时仍然可以找到 n 个
: 线性独立的向量(仍然可以像上面一样找包含所有相邻的k 个1的向量)，但现在是在 Z_
: 4里。线性独立没法保证是基了。。。
: 直觉上应该仍然是基，不过需要额外的论证了。
|
n**e
发帖数: 1296 | 32 提供个答案给你们：
（1，1）和（n, k) (k为奇数且k
【在 b******r 的大作中提到】
: 如果每盏灯的开关不止开，关两种状态，而是有四档：关，亮度1，亮度2,亮度3。
: 每次小明动开关只能动其中k个开关，每个开关只能调一档。(0裆可以到1裆,但不能直
: 接到2裆,3裆；3当也不能到0裆。)
: 如果小明每次动k个开关，一共动了4^n次使得n盏灯遍历了所有的亮度状态组合并且回
: 到最初始的状态，那么(n,k) 就是好的。
: 这种情况下好的(n,k) 有哪些？
|
