設萬維讀者為首頁 廣告服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:
萬維讀者網 > 靈機一動 > 帖子
密碼鎖問題解答
送交者: 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 | 全球最佳航空公司出爐:海航獲五星
海外華人福利!在線看陳建斌《三叉戟》熱血歸回 豪情築夢 高清免費看 無地區限制
一周點擊熱帖 更多>>
一周回復熱帖