新一期的最強大腦林建東那個挑戰項目沒有看懂啊，後來的坐標和前邊的數字牆有啥關係？求詳解?

01-25

2015.01.12 13:17pm第2次修改答案。

感謝 @Alen SUN的指正，第一次的時候 @Alen SUN 提的問題我理解錯了… 這次應該對了，再次求審閱，表示感謝~

感謝 @林劭秋的問題，並感謝@知乎以及 @趙惠民的指正。不過，斜著正交是否容易構造，這個問題細緻理解的話真不是那麼容易的，我添加在答案的最後面。

===============================

2015.01.11 1:35am第1次修改答案。

非常感謝 @tof lx 以及 @FAN IMAX 的提問以及指正。確實，如果冷靜思考的話，8質數情況要比7質數情況簡單。我後面會給出可能的原因，來解釋為何挑戰者反而花費了更長時間，而非更短時間給出答案。此版修改了答案，請審閱。

非常感謝 @Alen SUN 的指正。的確，編碼規則有些出入，你的結果是正確的，答案已修改，請審閱。

說句題外話，現在知乎上胡亂噴人的情況確實有，我認為知乎這個平台是大家交流的平台，提問和回答本身就是一個互相質疑互相提高的過程。所以， @FAN IMAX 同學的指正非常有助於我修改答案，給各位知乎er們一個更全面，更完美的結果，在此再次感謝~ 至少我回答的所有問題，歡迎大家討論、指正。

===============================

謝邀。今天跑步跑的有點多，正不想幹活呢，看到這麼一道題，就來認真回答一下。如果有不正確的地方，還請大家指正。

===============================

其實我是沒看過《最強大腦》的，就聽說第二季《最強大腦》有奶茶，這也沒引起我什麼興趣。看到題主的問題，再看到標籤列到了密碼學中，興趣就來了！馬上補了一下這一期的《最強大腦》。當然，我是用土豆補的，網址是：最強大腦 150109(上)_土豆。

===============================

看完以後，大失所望… 倒不是因為他挑戰的不精彩，而是因為這題目的描述太坑了。我們來看一下這個題目描述：「國家寶藏」。其中，我把不嚴謹的描述進行了加粗處理。

精準的虛擬地球，現場任選一處作為藏寶地點。此點地理坐標隨機轉換成五位數，藏入數字矩陣。在他藏入的同時，矩陣會自動生成一個質數密碼，對其加密。此質數密碼又七個質數組成。七個質數兩兩連線，有且僅有兩條連線垂直相交。這兩條垂直相交線的交點處，就是藏寶地點地理坐標對應的五位數。

那麼，這個挑戰實際上是什麼意思呢？具體過程如下。

現場在虛擬地圖上面任選一處，這一處地點位置以經度和緯度表示。
將經度和緯度寫為一個五位數（在此，我們將五位數表示為P(osition)）。
將這個五位數P放在數字矩陣中。
系統根據數字放置的位置，產生7個五位質數，放置在數字矩陣中。數字矩陣的其它點用合數填充。這7個五位質數位置進行兩兩連線。這些連線中有且只有兩條線垂直相交。相交位置就是五位數P的位置。

選手需要進行的步驟如下。

選手首先要找到7個五位質數。
在不藉助任何工具的情況下，將這7個五位質數兩兩連線。
找到這所有連線中那兩條垂直相交的線，標出交點。
交點所在的位置，就是五位數P。

我用圖例來說明一下選手需要進行的步驟。以下是一個用Excel截圖產生的15*23的方格。假設我們已經找到7個質數。

將這7個質數所在的點進行兩兩連線，如圖。

舉例來說，C6所在點與其他點的連線用紅色標註。

在所有線中，找到那兩個嚴格垂直相交的線，在此用紅色標註。

這兩個線的交點，就是需要尋找的五位數P。

最後，選手根據這個五位數P，恢復出坐標，並在虛擬地圖上進行標註。

注意，實際挑戰中數字矩陣的大小為30列*46行。因此，數字矩陣中一共有1380個數字。

===============================

這個題目中有一些沒有描述清楚的地方，我們一一說明。1. 如何將地理經緯度轉換成五位數？

根據後面挑戰的過程，轉換方法是這樣的：

前3位表示經度，後2位表示緯度。經度是E還是W，緯度是N還是S，由顏色進行區分。

在此引用 @Alen SUN 的評論：

通過顏色來區分E和W、N和S，就是這樣而已。因為經度的範圍是0~180，緯度的範圍是0~90，經度+緯度就是五位數。然後可以看到加上顏色之後5位數的前3位和後兩位是不同顏色的，就是說用4種顏色來標記E、W、N、S。

2. 為何判斷是這種轉換方法？

為了挑戰真實性，我們應該要求數字矩陣中任何一個點都可能是給定點。因此，數字矩陣中出現的全部數字，都應該滿足編碼規則。如果仔細看數字的話，會發現如下規律：

所有數字中，前三位小於等於180；
後兩位出現了大於90的數。

@Alen SUN的方法是正確的。不過，確實有出現後面兩位大於90的數。所以我估計給出數字矩陣中，除了目標點P和7個五位質數外，其他點直接從(00000,18100)之間的點選取，才造成了這種情況。而且，可能並不是依照平均分布取點，而是用其他方法（比如正態分布取點），使得不正常的點儘可能少，以迷惑挑戰者。

3. 選手是否知道這個轉換規則？

答案應該是肯定的，選手知道。否則，選手找到五位數P後，難道還需要猜想如何恢復到經緯度嗎？我們注意，挑戰的本質是展示挑戰者對數字的敏感性。而且，如果是因為轉換規則猜錯了而導致標註錯誤的話，那前面一堆工作在幹什麼…

4. 兩兩相交的直線一定是水平和豎直相交嗎？有沒有可能是斜著相交？

我認為系統設定是只能水平豎直相交，但是挑戰者不知道這個規則。首先明確，斜著相交，會因為數字矩陣長寬比的變化而變化。為什麼呢？我們在後面進行證明。

挑戰者不知道規則有下述原因：

如果挑戰者知道只能是水平豎直相交，其挑戰難度大大降低：一旦找到一個質數，則分別尋找所在行和所在列的質數，如果都存在，就找到位置了。
在真正挑戰過程中，挑戰者17分鐘就找到了所有的質數。但是其確定了三遍才肯定只有豎直水平相交的兩條直線是嚴格垂直，並且交點在一個數字的正中間。如果其知道只能水平豎直相交，沒有必要花費那麼長時間確定。

系統設定是只能水平豎直相交，有兩個原因：

是否斜著相交，與方格的長寬有關係，所以如果想用程序構造出斜著相交，首先需要知道屏幕上每一個數字所佔方格的長和寬。我覺得組委會應該不會考慮到這個細節。
是否斜著相交，方格的長和寬也需要滿足一定條件，否則不可能找到這樣的點。為什麼？在後面進行證明。

===============================

題主的問題解答完畢，下面是一些細節問題。

1. 挑戰過程中，給定結果08867也是一個質數，這對挑戰帶來了多大的影響？

影響有，但是沒有想像的那麼大。7個質數，會標註出7個點。7個點兩兩連線，最多有21個線（之所以最多，有可能會出現3個或以上數量的點在一條直線上的情況，這時候3個線重合，可認定為1個線），需要從21個線裡面找兩條互相垂直的線。8個質數，會標註出8個點。8個點兩兩連線，最多有28個線，需要從28個線裡面找兩條互相垂直的線。但是，實際上由於出現第8個質數的唯一可能是相交點也為質數，而這個質數會重複地與那4個點有連線。因此，最多只會有24個線。

這裡，@tof lx 以及 @FAN IMAX 給出了他們的指正，我認為是正確的，在此分別用他們的評論。

@tof lx 的具體指正：

二是藏寶位置碰巧也是一個質數時，我認為難度應該降低了，不知對不對？
因為無論藏寶位置是不是質數，解題的第一不都是找出這個數字陣列中的質數，
這第一步的難度不會因為多了1個質數提高太多。如果發現是8個質數時，應該會意識到坐標一定在多出的這個質數中了，也就是說坐標就在這8個質數中了。雖然
說從數學角度講，多了一個質數意味著兩兩連線會多出不少種組合，但對於這道題來講，選手是站在屏幕牆前，腦中虛擬對這8個質數兩兩連線，首先可以排除外圍
的幾個質數，更容易找出處於特殊的正交位置上的這個質數（08867）。

@FAN IMAX 的具體指正：

挑戰者現在大屏幕中找出7個質數，結果找出了8個。那麼應該有一種判斷是這多出來的一個質數就是要找的目標。那麼是哪一個呢？最投機的方法就是這8個數中
必定有5個數字構成兩條線垂直，而分別又每3個構成一條直線。所以，我智商比較低的想法是難點應該是找出那些所有的5位數的質數。所以要是7個質數的話會
不會更難？

我對此有自己的理解，在此選擇性地給出我自己回復給 @tof lx 的私信：

我不知道您是否有過極度緊張的時刻。我第一次主持節目時候有這種體會。這種上電視的節目，相信挑戰者也是極度緊張。這種時候，首先挑戰者找到8個質數，第一個反應肯定是「我是不是有一個想錯了？」所以他才驗證了好多遍。然後，他會思考為什麼多一個質數。這也需要一定時間，畢竟這種情況是意料之外的。再三確定後，後面就快了。

2. 在數字矩陣中找質數是否容易？

快速判斷一個數是否為質數，是一個數學問題。數學上怎麼判斷我就不提了，有興趣的朋友可以查詢相關的百科。挑戰者可能通過如下方法進行判斷：

給定一個數，心算是否是質數。如果是這樣，那麼挑戰者還是挺厲害的…畢竟是一個五位數判斷質數問題，並非想像的那麼容易。
背誦所有五位數中的質數，快速挑選，有點類似查找表法。

如果是第二個方法，我們就要考察一共需要背誦多少個質數了。我們知道，挑戰題目匯總，五位數的範圍是從00001到18099。這其中一共有多少個質數呢？我們用程序計數，源代碼如下：

import java.math.BigInteger;


public class NumberOfPrimers {

	private final String startNum;

	private final BigInteger stopInteger;

	private final int certainty;
	public NumberOfPrimers(String startNum, String stopNum, int certainty){

		this.startNum = startNum;

		stopInteger = new BigInteger(stopNum);

		this.certainty = certainty;

	}
	public int countNumberOfPrimers(){

		BigInteger tempInteger = new BigInteger(this.startNum);

		int numberOfPrimes = 0;

		while (tempInteger.compareTo(stopInteger) != 1){

			if (tempInteger.isProbablePrime(certainty)){

				numberOfPrimes++;

			}

			tempInteger = tempInteger.add(BigInteger.ONE);

		}

		return numberOfPrimes;

	}

public static void main(String[] args){ NumberOfPrimers numberOfPrimes = new NumberOfPrimers("1", "18099", 50); System.out.println(numberOfPrimes.countNumberOfPrimers()); } }

運行結果為2074。2074 / 18099 * 100% = 11.46%。也就是說，挑戰者需要背誦範圍內11.46%的數，這也不容易。

===============================

回顧題目描述。

精準的虛擬地球，現場任選一處作為藏寶地點。此點地理坐標隨機轉換成五位數，藏入數字矩陣。在他藏入的同時，矩陣會自動生成一個質數密碼，對其加密。此質數密碼又七個質數組成。七個質數兩兩連線，有且僅有兩條連線垂直相交。這兩條垂直相交線的交點處，就是藏寶地點地理坐標對應的五位數。

題目描述中坑爹的地方有兩點。

地理坐標的轉換並不是隨機的，而是確定的。
所謂質數密碼加密，並非是加密，而是通過質數來標註目標點的位置。

===============================

有關是否可以構造斜著垂直相交的證明。

前方高能預警，非戰鬥人員迅速撤離！這個地方的回答比（sang）較（xin）理（bing）論（kuang）！

我們要回答兩個問題：

斜著相交，是否會根據方格的長寬的變化而變化？如果是的話，那麼如果想構造斜著垂直相交，節目組寫程序的時候需要首先測量屏幕上每一個顯示數字所佔的長和寬，並把這個值作為程序的輸入。但這個事情實在是有點…麻煩…
是否一定能找到斜著垂直相交的四個點？直觀地看，似乎並不容易。如果點是連續的還好，但恰好是離散的…

這個地方怎麼證明呢？這個真需要用到有關密碼學的知識了。屏幕中所有數字的中心位置可以按照如圖所示表示：

如果把每個點與方格一起看，這個圖是不是特別像一個規律排列的方格子？對了！這個東西在數學上是有定義的，就叫做格（Lattice），而且這個東西現在在密碼學中是有非常廣泛的應用哦！在數學上，Lattice（Full-rank Lattice）的定義為：給定n個線性無關的向量b_1, b_2, ......, b_n，由這n個向量生成的Lattice為

$mathcal{L}(b_1, b_2, cdots, b_n) = left{sum {x_i b_i} | x_i in mathbb{Z} ight}$

我們稱b_1, b_2, ......, b_n為Lattice的Basis。如果我們定義B為一個n*n的矩陣，其列向量分別為b_1, b_2, ......, b_n，那麼由B生成的Lattice為

$mathcal{L}(B) = mathcal{L}(b_1, b_2, cdots, b_n) = {Bx | x in mathbb{Z}^n}$

在上面的圖中，我們可以把方格的長（設為a）所對應的列向量(a, 0)以及方格的寬（設為b）所對應的列向量(0,b)作為Basis。那麼，上圖的Lattice表示為

$[left{ {left( {egin{array}{*{20}{c}} a0 \ 0b end{array}} ight)x|x in {mathbb{Z}^n}} ight}]$

其中x是一個2維向量，代表這個點在第幾行第幾列。這樣一來，方格上的坐標都可以用Lattice定義了，只不過Lattice的表示是方格上每個點的坐標向左下方平移了(a/2, b/2)得來，這並不影響垂直關係。

我們在整數中中任取兩個點，作成一個向量。再任取兩個點，作成一個向量。這4個點所對應的2個向量表示為

$vec{v}_1 = (v_1, w_1), vec{v}_2 = (v_2, w_2)$

這兩個向量在Lattice中為

$Bvec{v}_1, Bvec{v}_2$

我們現在的目的是，讓這兩個向量垂直，這代表了在方格中選擇任意4個點，其連線垂直。我們看看如果垂直，需要滿足什麼條件。兩個向量垂直的條件是一個向量的轉置點積另一個向量的結果為零，即：

$(Bvec{v}_1)^{ ext{T}} cdot (Bvec{v}_2) = 0$

由線性代數知識，乘積的轉置等於轉置後再乘積，而且行列式不為零的矩陣是不可交換群，向量是scalar product可交換群。因此我們有

$[0 = {(B{vec v_1})^{ ext{T}}}cdot(B{vec v_2}) = {vec v_1}^{ ext{T}}{B^{ ext{T}}}B{vec v_2}]$

似乎沒法再化簡了… 我們把B和兩個向量的坐標代入，有

$[{vec v_1}^{ ext{T}}{B^{ ext{T}}}B{vec v_2} = left( {egin{array}{*{20}{c}} {{v_1}}{{w_1}} end{array}} ight)left( {egin{array}{*{20}{c}} a0 \ 0b end{array}} ight)left( {egin{array}{*{20}{c}} a0 \ 0b end{array}} ight)left( {egin{array}{*{20}{c}} {{v_2}} \ {{w_2}} end{array}} ight) = {a^2}{v_1}{v_2} + {b^2}{w_1}{w_2} = 0]$

其中v1,v2,w1,w2都為整數。如果向量v_1和v_2本身就是豎直水平的，上式嚴格為0，沒問題。但是，如果向量v_1和v_2本身並不是豎直水平的，那就有點麻煩了。後面的結論我直接給出，證明略。

${a^2}{v_1}{v_2} + {b^2}{w_1}{w_2} = 0$

這個式子我們暫且稱為垂直等式。注意到這個等式是與a，b有關的。所以節目組如果嚴謹，必須要測量數字矩陣每個方格的長和寬。另外，這個垂直等式是可能找到解的，並且給定交點的話，有演算法可以計算出4個點，使得4個點的連線垂直相交，且交於給定交點。設給定點用Lattice表示為X = B(v, w)，演算法如下：

在Lattice中任取一點，其可以表示為P = B(v_1, w_1)。
連接PX，延長線上至少有一個點也在Lattice上，即B(v_1+v, w_1+w)。如果還有其他點也沒問題。在延長線上，任意取一個在Lattice上的點Q(v_2, w_2)。
以(v_2-v_1, w_2-w_1)作為輸入，根據垂直等式，計算與之垂直的向量V。注意由於垂直等式有兩個未知量，所以找到的是一個一次式。
以X為原點，做向量V，則P+V一定在Lattice上，為R。
連接RX，延長線上至少有一個點也在Lattice上。如果還有其他點也沒問題。在延長線上，任意取一個在Lattice上的點T(v_2, w_2)。
P,Q,R,T為滿足條件的四個點。

注意，由於題目中屏幕上數字一共有30列46行，所以必須滿足P,Q,R,T橫坐標小於30，縱坐標小於46。我覺得，節目組不會：喪心病狂的嚴格測量每個數所佔方格的長和寬。

如果節目組真這麼做了，我只能說：牛逼！！

===============================

如果題主還有問題，歡迎留言。

以上。

我覺得他是靠記憶背下那2000多一點的質數的。根據以下幾點：

假設他是靠算的，樓上說一秒要進行6-7次4位數除以2位數的運算我覺得人類不可能達到。這麼多期的最強大腦也沒有一個人展現出接近這種能力。試想一下分解4321，普通人1秒鐘只能想到這個數不能被2，3，5 整除。但選手能在1秒內知道 4321不是質數(4321 = 29*149)，也就是說他在一秒內要試4321 被 7,11,13,17,19,23,29 除，這計算能力有點太扯了。

他後來加試的反應告訴我他絕對不是算的。Doctor魏在加試中問的數是8771 = 7 * 7 * 179。智商夠的人都會先排除2，3，5，然後開始算7。選手用了10秒鐘算出了8771能被7整除，這和他之前挑戰時的計算速度差了( 6次計算/ 1秒）/ （1次計算/10秒）= 60倍。。還不考慮這一次計算除的只是個7。試想你如果能算出1234 + 56 =？然後你突然在 3+4 =？卡住了這科學么。Doctor魏出的題也明顯太簡單，2，3，5 再往上就是7了，說明他自己也知道選手不是很強。外加選手聽到加試時驚訝的表情，不用再多說了。

從他誇張的表達中可以知道這個人喜歡吹牛。「全香港最聰明的人」，「給我一個問題我可以給你一萬種答案」，「提前兩個星期來南京，每天睡20個小時」。這些無據可查的大話讓人覺得他華而不實。反觀蜂巢迷宮的鮑橒VCR里介紹的都是蜂巢迷宮，個人基本沒有介紹，實力不是吹出來的。

所以我覺得他的分數水分很大，至少他的計算能力不是那麼強。不可否認他挑戰的這個項目不是一般人能完成的，就算不用計算，記住2000多個質數也很難。但他非要把自己的能力誇大或者說編造，這就是他的不對了。

看了師兄的回答我把計算過程再說一遍。

假設採用最惡意（巧妙/作弊）的方法進行大概十分鐘就能得出結論。

如果是使用快速方法，即知道是垂直相交。那麼只要找到任意兩個在同一行和同一列的質數後焦點即為所求。（這個方法也需要把表裡面的所有數字計算一遍是否是質數，這個也是為了解決兩兩連線的問題。）

垂直問題：

比如如圖所示，我用EXCEL都是長寬45像素的格子分別選取之後故意畫歪的。這個是不是絕對垂直是看不明白的。

質數問題：

數字是從2到18099以內的質數。回答排名第一的同學已經算出來了，2074個。

最惡意（作弊）的方法做這個題目肯定是要把這2074個質數都記住的。

然後不用計算是否一個數字是質數。

在比賽過程中選手平均0.7秒一個把所有點都過濾了一遍，並且記憶8個點。

再之後兩兩連線，找到交點所在並比較。

八個點兩兩連線實際結果是28個點。其中一個點在這28個點之中。實際上現在兩輪記憶了35個點的位置。

PS:我是不可能清楚的記住這麼多點的。本人記憶力很差。同時連線也很不容易，如開始的圖。

比賽到此為止。目前除了兩兩連線不需要數學能力。只需要記憶力就能給出答案。所以就出現了加試。

關於加試：

DR.魏給出的題目數是一個四位數。四位數的分解的除了1以外的最小因子肯定是在100以內的。

因為100^2=10000(「若自然數N不能被不大於(根號)√N的任何素數整除，則N是一個素數」。見（代數學辭典[上海教育出版社]1985年。屜部貞世朗編。259頁）見質數表第五節括弧3).質數表_互動百科

假設選手是背出來的按照上面的結果2074個質數都記得。所以幾乎能很快確定是否是質數。

那麼就需要看選手能否在很快時間內對數字進行分解。用2、3、5以外的質數進行試除。

8771=7*7*179。雖然這裡只用計算一下（大概10秒）就能得出結論。這個選手還是有較強的計算能力的。

關於質數分解問題：

有知友表達觀點是在1380個數字組成的矩陣中拋去偶數，結尾是5,3的倍數之後的數字集合中答題者應該是算出來的。

在快速計算中2,3,5,11的倍數這樣的數幾乎能一眼看出來，7的倍數快速計算也是一次縮減一位，不如直接除來得方便。那麼假設1380個數字是均勻分布，剩下的不能被2、3、5、整除的數字有大約1380*(1/2)*(4/5)*(2*3)*（10/11）約等於335個。對其進行進行質性檢測。

質數分解問題：

質數是如何算出來的？

比如一個數字是901是質數還是合數？

首先明顯不是2,3,5，這樣的倍數。然後開始試除，

7、11幾乎也能快速確定不是其倍數

901/13發現除不盡。901/17發現901/17=53

結果出來了。這個計算過程有

第一步：2、3、5不對

第二步：7、11不對

第三步：13不對

第四步：17.

如果17不對就是第五步23，第六步29、第七步31。。。

質數檢測是全世界公認的難題。90年代以前的方法中最快的方法也只能這麼干。即用小質數依次試除。

那麼問題來了。這340個左右的數字是算出來的還是背出來的？

17分鐘340個數字，認出來計算複雜度是O(340)

質數測試的方法是一個數字比如901

質數測試是O(340*(質數數量(√18100)/2))=O{340*(32個質數-card{2,3,5,11})/2}=O{340*14}=O(4760)

答題者用了17分鐘約17*60=1020算了4760次除法，大約一秒鐘計算5次除法，前面應該是計算6到7次一秒的4位數除以兩位數。後面效率下降也應該有3秒一次。這個計算速度是很恐怖的。

分析結束：

到此為止假設是全部按照記憶力這個測試也能過。就是要很快記住兩千多個質數然後開始玩。

正常方法

一秒鐘計算6次以上的四位數除以兩位數才能玩。約17分鐘搞定。

如果選手是全部計算出來的那麼這個就太恐怖了。9分當之無愧。但是後期的10秒和前面的速度不符。也可能是長時間計算後腦力降低（人發木了）。

作弊的方法是被輸18100以內的質數就能玩。約10分鐘就搞定全部。

大約前期17分鐘能縮減至5分鐘，選數字能縮減到2分鐘（發現了同行有質數並且同列有質數）。然後在加試過程中挨個試除也能在20秒內解決。

看了節目，遊戲規則說了半天，後來才知道是找出屏幕中所有的質數然後連線。我的第一反應就是：如果那哥們把所有的質數都背下來咋辦？

Doctor魏說要加試，給出了一個數字，那麼只要在自己所背的質數中過濾一遍。如果Doctor魏再給個質數，他背出來也沒什麼意義，不能說明什麼問題。所以Doctor魏給了個合數，那就一個一個除唄。之前17分鐘1020秒對1380個數是不是質數進行了計算，現在算一個數要10秒，時間上差距有點大啊。雖然要計算出因數，但是8771能被7除，應該是比較好計算的。

他計算屏幕上的數字時，速度那麼快。

但是，魏教授臨時給他一個數字計算時，他就變慢了。

我覺得，這個問題很奇怪。

每個人都把他當計算器，算出來的數都是肯定正確的，但是忽略了他連續正確分解了1296個數的能力。