设万维读者为首页 广告服务 技术服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:
万维读者网 > 灵机一动 > 帖子
密码锁问题解答
送交者: nanweishui 2006年06月04日13:14:04 于 [灵机一动] 发送悄悄话

Let S(i, j) be the switch at i-th row and j-th column. Let R(i) = 1 if i-th row has odd number of ‘off’s, otherwise R(i) = 0. Similarly define C(i) = 1 if j-th column has odd number of ‘off’s and C(i) = 0 if otherwise.

If N is even, any combination can be opened.
If N is odd, a necessary and sufficient condition for a combination to be opened is:
R(1) = R(2) = … = R(N) = C(1) = C(2) = … = C(N).
(So the example by pistons can not opened because R(1) = 1 and R(2) = 0.)

Proof:
If N is even, switch the status of all switches on i-th row and j-th column will change switch S(i, j) only and keep all other switches the same status. Repeating this process can turn on all switches.

If N is odd, changing any switch will change R(1), R(2), … R(N), C(1), … C(N). Since when the lock is opened, all R(i)s and C(i)s are zeros, a necessary condition is R(1) = R(2) = … = R(N) = C(1) = C(2) = … = C(N).

If this condition is satisfied, then this combination could be opened. It is obvious when N = 1. When N > 1, we can first turn on all switches from 2nd row to N-th row and 2nd column to N-th column (this is a N-1 by N-1 matrix, since N - 1 is even, this can be achieved). We still have R(1) = … = R(N) = C(1) = … = C(N) at this time. If all of them are zeros, then it must be the case that all switches are on. If they equal to 1, then all switches in the 1st row and 1st column are off. We only need change the switch at top-left corner to make all switches on.

0%(0)
0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制
一周点击热帖 更多>>
一周回复热帖