1樓:Timosky
來晚惹……@Lunatic 和 @KuriyamaMirai 都給出了很棒的證明。
那麼,就由我來給出「簡單」和「更強」的做法吧!
首先,如果你把所有開關都按一遍(由於每次會連帶旁邊兩個,實際上按了三下),那麼所有燈的狀態都會反轉。記作操作A。
然後,如果只按2號(連帶13)和5號(連帶46),那麼除7號之外的燈的狀態都會反轉。記作操作B。
因此,只要把某盞燈記作7號,再執行操作A和B,就可以只改變該燈狀態而不影響其他燈了。對所有「關」的燈來一遍,燈就全「開」了。完畢。
很簡單有木有!
好,強結論來了:對於n盞燈,每次切換連續的m盞。(n,m)滿足何種條件時,可以經過有限次操作獲得所有狀態呢?
請思考五秒:
五……四……
三……二……
一……噹噹當!答案揭曉!
只要n與m互質且m為奇數就可以啦!
這還是乙個充要條件哦!
下面開始證明:
首先,我們注意到「能通過有限次操作到達任意狀態」等價於「能通過有限次操作改變其中一盞燈的狀態而使其他盞燈狀態不變」。這個很顯然所以用不著證了吧……
——於是m與n就非互質不可了。否則你可以把所有燈按照序號除以r所得餘數(r為n與m的大於1的公約數)分為r組,那麼無論如何操作,任意兩組之間「亮著的燈數的奇偶性」將保持相同或不同,而不會發生相同→不同或不同→相同的改變,自然也就無法做到「只改變一盞燈,不影響其他盞」了。
m也必須是奇數才行,否則「亮著的燈數」的奇偶性也無法改變……
反過來,如果n與m互質且m為奇數,是否必定存在一種方法可以做到「只改變一盞燈」呢?
其實很簡單:連續按就行了。比如對於(47,15),你就第一次按1到15,第二次按16到30,然後是31到45,46到13(繞一圈了!),14到28,29到43……
根據裴蜀定理,n與m互質時,mx+by=1有整數解。用人話說就是:這麼按下去,遲早有一次會按成「34到1」。
這意味著你已經按了k圈燈加乙個燈。結果分兩種:
一:其他燈都被按了偶數次,只有1號被按了奇數次,即整個過程中只有1號狀態變了,成立!
二:與上邊那個相反,只有1號保持不變,其他都反轉了……不過沒關係!因為m為奇數,所以只要把全部燈按一遍(由於連帶,每盞燈被按了m次),就可以把所有燈都反轉了。
至此,本題完結!
啦啦啦……
答主本人目前在被窩裡,手機打字,莫名其妙就得出答案了。還是挺高興滴!
所以,可以請你給我乙個贊麼?蟹蟹~
受 @Lunatic 啟發,給出推廣結論:
對於n盞燈,每次切換連續的m盞,且每盞燈具有k個狀態。則能通過有限次操作得到所有狀態的充要條件是:m與n互質且m與k互質。
必要性:對每盞燈,取狀態值(0,1,2,…,k-1)。若(m,k)=r,則狀態值的總和被r除所得餘數將保持不變。
若(m,n)=R,則將燈盞按照被R除所得餘數分為R組,不同組的狀態值總和被k除所得餘數將保持相同或不同。故要使得經過有限次操作能使恰有一盞燈的狀態發生改變,必須有r=R=1。
充分性:若m與k互質,則總可以進行「全部按一遍」的操作使得所有燈的狀態發生改變,且如此操作(k-1)次,每盞燈都將遍歷k個狀態。若m與n互質,則可進行「連續按」操作使得只有一盞比其餘盞多切換一次。
因此可以經過有限次操作使恰有一盞燈的狀態發生改變。
《原神》遊戲中的「紫立方體」解密基本滿足這一套路。如果在遊玩過程中發現m與n與k的關係不符合結論,或許你就需要尋找被藏起來的其他方塊了。
2樓:KuriyamaMirai
對於這 7 盞燈,因為它們僅有兩種狀態「開」和「關」,不妨用乙個七位二進位制數表示所有燈的狀態(用 0 表示關,用 1 表示開)。
若欲「切換」一盞燈的狀態,將對應位翻轉即可(即,異或 1)。
那麼,每一次操作都可以轉化將當前狀態的二進位制表示異或上 中的乙個。
乙個初始狀態能經過若干次操作變化為全「開」狀態,等價於對應的二進位制數進行若干次「異或上述七個數之一」的操作可以得到 。
根據異或的性質,該命題等價於可以該二進位制數可以表示為 與上述七個整數任選若干個(可以不選)的異或和。
因此,原命題等價於任何乙個七位二進位制數皆可表示為上述七個整數任選若干個(可以不選)的異或和。(注意到 是乙個雙射)
考慮向量空間 ,注意到。
對於其他類似的開關問題,只要對每個單獨的燈涉及的操作皆為「翻轉」,都可以嘗試採用這種方法解決。
由《爐石傳說》想到的數學題,請問該如何解決?
拼勃向上 不斷除以2,當餘數是奇數時減去3,記下次數l,繼續除,直到最後剩餘2,記錄次數n,n l 1就是每次的回合數。你甚至不需要直到生命值這個條件。比如,攻擊力為34,除以2就是17,17是奇數,我們減去3,得到14,同時記下次數1。接著,得到7,減去3,記下次數2,得到4,除以2,得到2,記錄...
如何去思考解決一道數學題?
嘰哩哇啦 今天看見一道題 學生在做一道有四個選項的單項選擇題時,如果他不知道問題的正確答案,就做隨機猜測。現從捲麵上看題是答對了,試在以下情況下求學生確實知道正確答案的概率 1 學生知道正確答案和胡亂猜測的概率都是0.5 2 學生知道正確答案的概率是0.2 我 所以說他到底知不知道正確答案?是我審題...
如何正確刷數學題
大致分三個階段,每個階段有完整的步驟,缺一不可,如果不能嚴格完成到第三階段,請不要使用這種方法 做題 基本題和高階題,標記不會做和做起來感覺有疑點的題目 知道做法但是不知道為什麼的題目 適度複習做過的題 一般只需要花費不長的時間,速覽 或者考試前複習。當積累階段進行了一段時間後 大概是1個月 有了一...