從一道很污很污又有趣的推理題說起

有一道網上流傳的趣題：有2男2女，每個人都各自攜帶不同的性病，而且傳染性都很強。如果每個男的和每個女的都發生性關係，但是現在只有2個套套，請問怎樣操作才能讓每個人都不會感染別人的病？

事實上這是一道極為精彩的數學題，這背後的數學結構非常美妙，也非常具有啟發性質。很多看起來很無聊的數學問題，最終都能在計算機、物理學、運籌學等很多學科中有意想不到的應用。比如這道題屬於離散數學分支圖論，在密碼學、計算機通訊與信息安全等領域可能有所應用。

這道題的本意並不是啪啪，比如我可以改為：在只有兩個手套的情況下，兩個醫生分別對兩個病人互相做手術。當然嚴格上這樣改動是有問題的，詳情見文章末尾。因此本文章通篇將會以性交的模式來闡述這個數學問題。

這道題的答案是：

第一步：男一號先戴上套套A，然後外面套上套套B，與女一號啪啪；

第二步：男一號脫掉套套B，與女二號啪啪；

第三步：男二號戴上套套B，與女一號啪啪；

第四步：男二號外面再套上套套A，與女二號啪啪。

這樣無論如何都無法感染性病。

（原題是沒有註解的，我有必要加上五個註解：

①允許套套多層疊加用，但不允許套套翻過來反著用；

②套套可以重複使用；

③陰莖接觸到其他男人的精液也會使得該男子感染其他男人的性病；女性之間同理；

④只能異性之間發生性關係，評論區有人提到男性與男性之間的交配，我們暫時不考慮；

⑤這道題是在理想情況下研究純數學問題，評論區有大量「兩個套套容易破」「性病的防治不止避孕套這種方式」等內容，你們的內容是對的，但並不是本篇文章的核心。

我看到這道題的時候一開始沒想出怎麼做，後來一看答案才嘖嘖稱奇。

我不禁想，如果推廣一下：現在有n對男女，每個人都各自攜帶不同的性病，而且傳染性都很強。如果每個男的對每個女的都發生性關係，最少需要多少個套套，才能使得他們不感染呢？

以下的內容是我的探索過程，講述的是我是如何把下界一步步縮小，從一開始的4*n2，到3n，到2n，到2n-1，到2n-2，到1.5n，到(4/3)n+2，直到目前確定的下界是(4/3)n+2/3個套套（我仍然不知道這是不是最小的下界）。這其中難免走了很多彎路，如果你覺得太長，或者說你覺得沒意義（當然我是覺得有意義的），可以繞到最後看我的最終答案以及解釋。如果中途有答案看不懂也沒關係，因為對於這道題來說，給出的答案越小，思路反而越簡單，這就是數學的魅力。

溫馨提示：如果你想繞到最後看我的最終答案，為了節省你的時間，請認準三行「***********」標誌，該標誌往下即最終答案。如果是一行或者兩行星號標誌的，（雖然不是最終答案）是比較推薦讀者看的內容。

（值得一提的是，我在發出文章的24小時內，不斷有網友提出新思路，下界不斷地刷新，「***********」標誌也不斷地下移）

n=2的情況已經在開始考慮過了。

我們來看一下n=3的情況，有如下六個人：

男1號 女1號

男2號 女2號

男3號 女3號

我花了半小時枚舉，得出3個套套是不夠的，4個套套是可行的。過程如下：

第一步：男一》TB》TA》女一，這表示男一號戴著套套B，然後外面再套上套套A，與女一號啪啪。

剩下的八步也是如此表示：

男一》TB》女二 ；

男三》TC》TA》女一 ；

男三》TC》女三 ；

男二》TA》女一 ；

男一》TB》TC》女三 ；

男二》TA》TB》TC》女三 ；

男三》TD》女二 ；

男二》TA》TD》女二。

我們再來看一下n=4的情況，有如下八個人：

男1 女1

男2 女2

男3 女3

男4 女4

我們可以分為四個步驟：

第一個步驟：

男1 女1

男2 女2

這是兩對男女，我們根據一開始的討論得出，只需要2個套套即可完成互相交配而又不感染性別。

第二個步驟：

男1 女3

男2 女4

第三個步驟：

男3 女1

男4 女2

第四個步驟：

男3 女3

男4 女4

每個步驟需要2個套套，4個步驟需要8個套套。因此，對於4對男女，只需要8個套套。

但是這個結果是很粗糙的，我覺得8個套套太多了。有沒有更好的辦法？我嘗試通過枚舉法來找到比8更小的值，嘗試了一個小時後發現這個過程太艱辛了，就放棄了。不過我的直覺是，對於4對男女的情況，真正的下界應該比8小。

因此目前的結果是：

2對男女，2個套套足夠；

3對男女，4個套套足夠；

4對男女，8個套套足夠。

我可以拓展下：

根據上面的討論，n=4時，我們分了四個組，即四個步驟。同樣的道理：

當n=6時，我們可以像n=4一樣進行兩兩配對，兩對男女為一組，這樣的組數是9組，正好是3的平方。（男1，男2，女1，女2）、（男1、男2、女3、女4）、（男1、男2、女5、女6）、（男3，男4，女1，女2）、（男3、男4、女3、女4）、（男3、男4、女5、女6）、（男5，男6，女1，女2）、（男5、男6、女3、女4）、（男5、男6、女5、女6）。

每個組需要2個套套，這樣一來，全部需要2*32個套套。

繼續拓展：當有2n對男女時，需要的套套數是2*n2。如果是奇數的情況，我沒有想到好的方法，不過如果當做下一個偶數的情況算，至少可以保證滿足的。

比如當有12對男女時，需要72個套套。

另一個拓展思路是，我們能不能換一種分組的方式？

比如n=6時，我們作如下的分組：

（男1、男2、男3、女1、女2、女3）、（男1、男2、男3、女4、女5、女6）、（男4、男5、男6、女1、女2、女3）、（男4、男5、男6、女4、女5、女6）。

一共四組。根據n=3的討論，3對男女需要4個套套，因此四組的情況是，需要16個套套。我們發現按三個分組比按兩個分組更優。

一般化，當有3n對男女時，需要的套套數是4*n2。如果是3n-1或者3n-2的情況，我目前沒有想到好方法，只能按照3n的情況算。

但是這樣的結果還是太差，有沒有更好的下界？

注意：當n>2時，男女交配問題與醫生手套問題不等價。因為不同的醫生戴相同的手套是沒事的，但不同的男性戴相同的套套會發生感染。

我在睡覺前一直在想這個問題，到凌晨三點突然靈光一現，想到了一個新的思路：3n是可行的。（我是在思考「套多層套套的意義是什麼？」這個問題中想到如下解法）

如圖，我們隨機把n個男性與n位女性進行緣分配對，一共配對成為n對「情侶」。每對情侶有三個套套：A、B、C，每個套套的功能是不一樣的，我在下面有說明。

（根據評論區的情況，可能有人沒看懂下面的過程，為了更加形象地說明我的結論，我假定有n個房間，第一對情侶在第一個房間，第二對情侶在第二個房間……等等）

首先，n對情侶可以在自己的房間里啪啪一次。以男一號為例，男一號與女一號在1號房間相處二人世界，男穿上套套B1，與女一號啪啪。同理，其他男性也是穿上各自的套套B，在各自的房間與各自的情侶啪啪。

接下來，當男一號想要和其他女性啪啪時，他首先得在自己的房間里穿上套B1，然後再穿上套A1，再去其他房間敲門。

為什麼要套上A1？這樣的作用是防止套B1的外層受到感染，因為套B1的外層只能有女一號的液體與病毒，不管經過多少次交配，B1的外層只能是女一號的病毒專屬；

去其他房間敲門之後（我們假設他要去第二個房間，即想要和女二號交配），2號房間的門口有一個套套C2，男一號目前已經穿上B1與A1了，他還需要在門口穿上C2，進門後，再穿上B2。這樣套了四個套套，才能和女二號啪啪。C2的作用是防止B2的內部受到感染，因為B2的內層（即B2套套裡面）只能有男二號的液體與病毒，即B2的內層只是男二號專屬。

事實上，每個房間的門口都放有屬於各自的套套C。進門之前得穿上，啪啪完事後出門後得放回門口。

這樣下來，所有情侶的套套B都不會受到感染，且所有的情侶之間都可以互相交配……

我再重複一遍，以男一號為例：套套A1是用來保護套套B1的外層不受其他病毒感染，套套B1的外層只能有女一號的病毒；套套C1是用來保護套套B1的內層不受其他病毒感染，套套B1的內層只能有男一號的病毒。

對於其他的「情侶」，也是類似的過程。套套A是保護套套B的外層，套套C是用來保護套套B的裡面。

所以對於n對男女，3n個套套可以保證互相交配而又不感染性病。

但是直覺告訴我，3n這個下界可能還不夠好。

的確，在我發出回答後的不到四個小時，馬上有評論區的朋友告訴我，2n是可行的：

比如，女二號的專屬套套是A2，男八號的專屬套套是B8，那麼男八號與女二號要啪啪的話，需要男八號先戴上B8，再戴上A2。

還是一樣的情況，每個女性有自身的專屬套套；然後選n-1個男性，每個男性有自己的專屬套套。剩下那個男性先上場，對每一個妹子，使用那個妹子的專屬套套，等到那個男性結束後，他的使命就完成了，可以離開遊戲了。於是n-1個男性帶著各自自己的專屬套套上場。接下來的事情就和上面所說的2n的答案一樣的構造了。

但是，這個結果能不能再小一點呢？

我猜測下界應該是2n-2。

終於，在我發出這篇文章的10小時的時候，我突然迸發了一個嶄新的靈感：2n-2是可行的。

首先還是得先配對：每一個男性i都有自己的專屬套套Bi。比如男1號有專屬套套B1，男2號有專屬套套B2……

第一步:男i號(i∈{2,3,……n})》Bi》B1》女1號。 （n-1）

這代表男i號（第2號男人到第n號男人的其中一個），先戴上套套Bi（即自己的專屬套套），然後再戴上套套B1，接著就能和女1號啪啪了。（n-1）表示在第一步中，發生了n-1次不同的有效的交配，這裡是第2號男人到第n號男人都和女一號啪啪了，所以共有n-1次交配。（注意：n對男女共需要完成n2次不同的有效交配）

第二步：男i號（i∈{1,2,3,……n}）》Bi》女i號。 （n），女1 號over

這代表所有男人分別用自己的專屬套套與對應編號的妹子進行交配，通俗點來說，就是男1號用套套B1與女1號啪啪，男2號用套套B2與女2號啪啪……（n）表示這一步發生了n次有效交配。「女1 號over」表示截止到這一步，女一號已經完成了所有的使命。

第三步：男i號(i∈{1,2,3,……n-1})》Bi》Bn》女n號。 （n-1），女n號 over

第四步：男n號》Ci(i∈{2,3,……n-1})》女i號。 （n-2），男n號 over

註：這裡是C是新的套套，共有n-2個C類套套。加上之前n個B類套套，一共2n-2個套套，即是本題答案。

第五步：男i號(i∈{1,2,3,……n-1})》Bi》Cj(j∈{2,3,……n-1})》女j號。

這一步共有[n-2+(n-3)*(n-2) ]次有效交配。其中男1號只需和n-2個女性交配了，男2號到男n-1號只需和n-3個女性交配了。

所以，所有的交配過程都已經完成了。我們可以相加所有的交配次數，發現正是等於n2。

*********************************

這還沒有完，讓我自愧不如的是，在我給出如上2n-2的答案後，即在我發出文章的16小時後，有評論區的朋友 @team bright 給出更簡單的演算法，雖然還是2n-2的答案，但過程比我上面的方法簡單多了：

一開始還是一樣的思路：前n-1個男性有自己的專屬套套，前n-1個女性有自己的專屬套套。

第一步：這n-1對男女兩兩配對，這樣可以有（n-1）2次有效配對。

第二步：前n-1個男性各自用自己的專屬套套與第n個女性配對，這一步有（n-1）次有效配對。

第三步：前n-1個女性各自用自己的專屬套套與第n個男性配對，這一步有（n-1）次有效配對。

第四步：第n個男性穿上女1號的專屬套套（事實上他可以穿上前n-1個女性的任何一個套套），然後穿上男1號的專屬套套，這樣就可以與第n個女性交配了。這是最後一次配對。

這是目前為止我最滿意的答案。

不過，有沒有比2n-2更小的答案呢？

我認為應該沒有了。因為2對男女至少要2個套套，3對男女至少要4個套套，4對男女至少要6個套套，都是符合2n-2的。

*********************************

*********************************

但是，然而，不過，我又一次被打臉了！

在我發出文章的24小時後，有評論區的朋友 @拒絕咖啡 提出1.5n是可行的下界！

為了方便讀者閱讀，我寫了兩個版本：簡單版本和複雜版本。兩個版本的本質是一樣的，只是描述方式的不同。

下面是簡單版本，如果沒看懂的話可以跳過，去看複雜版本：

男的等分為兩組ab，女的等分為兩組AB。每一組有n/2個人。

每個女的有專屬套套，在a組裡的每個男的有專屬套套。這樣一共就有1.5n個套套了。

第一步：a組男人穿上自己的專屬套套，再分別穿上每個女的專屬套套，和每個女的交配一遍，即a組男性與所有女性自由交配；

第二步：a組男人走人，但是套套留下。注意到，a組的套套外側都是乾淨的，且所有女性的專屬套套的內側都是乾淨的！把A組女性的專屬套套變成b組男性的專屬套套，把a組男性的專屬套套變成A組女性的專屬套套；

第三步：b組男性與所有女性可以自由交配。

這樣全部過程就算完成了。

下面是複雜版本：保證你能看懂。如果你覺得不想看的話可以回去看簡單版本：

假設有n對男女，n是偶數。那我們設n=2m。於是變成了2m對男女。

第1步：給女1、女2、……、女2m 每個女性發一個套套，成為他們的專屬套套B，然後給男1、男2、……、男m每人發一個套，成為他們的專屬套套C（如圖）。那麼這前m個男性 和所有2m個女性可以自由玩耍。

這一步共發生了2m2次交配。然後男1號到男m號的使命都已經完成了，但是他們的套套C的外面還是乾淨的，後面還需要用到。

第2步我們分為m次小步驟來完成：

第2.1步：男（m+1）號》B1》B(m+j) 》女（m+j）號。其中j 取從1到m的m個整數。

比如，男m+1號，先穿著套套B1，再穿上套套B(m+1) ，和女(m+1) 號啪啪。

然後，他脫下套套B(m+1) ，再穿上套套B(m+2) ，和女(m+2) 號啪啪。

這樣，男m+1號可以和女m+1號到女2m號啪啪，這一步共發生了m次交配。

第2.2步，男（m+2）號》B2》B(m+j) 》女（m+j）號。和2.1步類似，這一步是讓男m+2爽一遍，這一步也是發生了m次交配。

這樣的步驟可以持續到第2.m步，第2.m步是：男（m+m）號》Bm》B(m+j) 》女（m+j）號。

因此，整個第2步發生了m2次交配。

第3步：我們注意到，套套C的外面還是乾淨的。

因此：男m+k號》Bk》Cj》女j號。先令j跑遍1到m，然後再令k跑遍1到m。（事實上，第2步也是先令j跑遍1到m，然後再令k跑遍1到m，只不過第2步我分解了，第3步我懶得分解了）

整個第3步發生了m2次交配。

至此為止，所有的交配已經完成，共4m2次交配，也即n2次交配。

整個過程用了3m個套套。摺合成n對男女的話，只需要1.5n個套套即可。

評論區有一位朋友注意到這樣一個事實：在第三步之前，B組女性的專屬套套的內側是乾淨的，事實上，即使B組女性的專屬套套的內側不幹凈，我們也能繼續第三步。

我為什麼要提這樣一個事實？因為在這個1.5n的解法中，感覺並沒有充分榨乾全部信息。如果充分利用全部信息的話，是不是會比1.5n更小？

如果n是奇數怎麼辦？一個很懶的辦法是，我假設加一對虛擬的男女，那麼這樣一共有n+1對男女，是偶數對，那麼1.5（n+1）個套套即可完成。

不過我顯然不滿足這樣的方法，這樣直接浪費了一對名額。我算得，n=2m+1時，只需要3m+2個套套。即n為奇數時，需要的套套數為1.5n+0.5，比上面的情況少1個。

其實思路和n為偶數的情況是一致的。

2m+1個女性各有一個專屬套套C，前m個男性有一個專屬套套B。

第一步：前m個男性戴上專屬套套B1-Bm，與所有女性交配，可以完事；

第二步：前m個男性的專屬套套B1-Bm與前m個女性的專屬套套C1-Cm交換；

第三步：後m個男性分別穿上C1-Cm，各就各位；前m個女性分別準備好B1-Bm，各就各位；

第四步：是不是還漏了一個男性？那個男性穿上最後一個套套，和所有女性交配一遍；

第五步：第三步各就各位的男男女女們可以完成最後一步了。

*********************************

*********************************

*********************************

王炸來了！

在我發出文章的六天後，也就是公元2018年4月25日13點52分，有評論區的朋友 @有限狀態機 提出(4/3)n+2/3是可行的！

（插播一條，在這個「(4/3)n+2/3」答案出現的兩小時前，有朋友 @SmokerX 提出(4/3)n+2的解法。由於時間相隔太近，且工程量巨大，我就不用自己的語言翻譯他的答案，有興趣的朋友可以看他的文章以及評論區：啪啪啪一圖流。這篇文章第一次提出「共享套套」的理念！真是符合目前的共享經濟。而且「(4/3)n+2/3」答案在很大程度上也有這個答案的靈魂在裡面。不過這篇文章有幾個小錯誤，需要結合評論區一起看）

如圖所示：我們把女性分為a、b、c、d四堆人。其中a的人數=b的人數=c的人數=m，d單獨1人。同樣，男性也是這樣的劃分（這樣劃分的前提是n=3m+1）。T是「套套」的簡稱。

首先，我們給abdABD六堆人分發他們的專屬套套，這樣一共發4m+2個套套。事實上這些套套就夠了，4m+2就等於答案(4/3)n+2/3。

第一步：abdABD分別穿上自己的專屬套套，互相交配（如何互相交配，請參照下界是2n的那個答案）。交配完成後，所有女性的專屬套套的內側以及所有男性的專屬套套的外側仍然是乾淨的。

第二步：TA變Tc，即A堆所有男性的專屬套套拿去做c堆所有女性的專屬套套。

第三步：D>TD>Td>Tc>c。（請注意分辨大寫的C與小寫的c）

上面這些符號的意思是：D堆男性（其實就那一個男性）穿著專屬套套D，再穿著d堆女性（其實就那一個女性）的專屬套套d，再穿上c堆女性的專屬套套c，與c堆女性進行交配。注意到這一步進行後，TD的外側以及Td的內側仍然是乾淨的。

第四步：B>TB>Td>Tc>c。注意到這一步進行後，TB的外側以及Td的內側仍然是乾淨的。

第五步：Ta變TC，即a堆所有女性的專屬套套拿去做C堆所有男性的專屬套套。

第六步：C>TC>TD>Tb>b。注意到這一步進行後，TD的外側以及Tb的內側仍然是乾淨的。

第七步：C>TC>Tc>c。

第八步：Td變TD，TD變Td。這句話什麼意思呢？注意到TD的外側以及Tb的內側仍然是乾淨的，因此我們把Td變成D的專屬套套， 把TD變成d的專屬套套。

第九步：TB變Ta，Tb變TA。

進行到現在，我們有兩個事實可以確認：

一：還差A>c，C>a，C>d三個步驟；

二：除了acdACD都有自己的專屬套套。

因此第十步：acdACD戴上自己的專屬套套盡情交配吧！

Over！

那麼問題來了，n=3m以及n=3m+2的情況，下界應該是多少呢？這就交給讀者了，因為n=3m+1的情況解決後，剩下兩個情況就小case了。

關於這個答案的更深入的思考在這篇文章：