數學中有許多問題，要求在各種約束之下，使某個量最大化或最小化，這些問題稱為

極值問題

。和計數問題一樣（

數學不好，你連“簡單”的計數都不會，計數問題為什麼能這麼難？

），有一些極值問題可以實際地算出精確解來，而更多的則是，雖然精確解是談不上的，但仍然可以找到有趣的估計。這兩類問題，下面各有一些例子。

（1）令n為一正整數，而X為一含有n個元素的集合。問可以找出X的多少個子集合，使得沒有一個會含於另一個子集合之內。

可以做出的一個簡單觀察是∶如果兩個不同子集合大小相同，則沒有一個會包含於另一個之內。所以滿足問題的約束的方法之一是選取所有的子集合具有同樣大小 k。X的大小為k的子集合一共有

n!/k!（n-k）!

個，這個數通常記為

而不難證明當k=n/2（若n是偶數）或者k=（n±1）/2（若n是奇數）時，它取最大值。為簡單計，我們集中於n為偶數的情況。剛才證明了∶在n元素的集合中，可以做出

個 n/2元素的子集合，其中沒有一個會包含任意另一個。也就是說，

是這個問題的一個下界。一個稱為

Sperner 定理

的結果指出，它也是一個上界。就是說，如果取多於

個子集合，不論怎樣取，其中必有一個包含於另一個之內。

（2）設有一條有重量的鏈子，兩端掛在天花板的兩個鉤子上，而除此以外鏈子再沒有其他支撐點。這個掛著的鏈子將是什麼形狀？

初看起來，這並不像是一個極大極小問題，但它很快就是了。這是因為物理學的一個一般原理告訴我們，鏈子將會靜止在一個使得位能為最小的形狀上。 這樣我們就面臨一個新問題∶令A，B是（位於同一水平高度而）相距的距離為d 的兩點，c為長度為l以A，B為兩端的曲線的集合，問哪一條曲線C∈c具有最小位能？這裡設任意曲線段的質量正比於其長度。這條曲線的位能是mgh，m是曲線的質量，g是引力常數，而h為曲線的重心的高度。因為m和g不會改變，這個問題就有了一個新的陳述∶哪一條曲線C∈c具有最小的平均高度？

這個問題可以用一種稱為

變分法

的技術來解決。粗略地說，它的思想是∶有了一個集合c，又有了一個定義在c上的函式h，即平均高度，此函式把每一個C∈c 映為其平均高度。我們試著來使h最小化，而處理這個問題的一個自然的途徑是設法定義某種導數，然後再去找一條曲線C∈c，使得這個導數為0。注意，“導數”一詞在這裡並不是沿著曲線運動時高度的變率，而是指曲線的平均高度（以線性方式）對於整個曲線的微小攝動的響應。利用這一類的導數來求最小值，比求定義在R上的函式的駐點要複雜一點，因為c是一個無限維的集合。然而這個途徑還是能起作用的，解也是知道的，是一種稱為

懸鏈線

的曲線。這是又一個能夠準確回答的最小化問題。

變分法的典型問題都是求一條曲線、一個曲面或者更一般種類的函式，使得某一個量達到最大或最小值。

如果這個最大或者最小存在（對於一個無限維集合，它們絕非自動存在的），則使得最大或最小達到的物件，會滿足一組偏微分方程，稱為

尤拉-拉格朗日方程

。

（3）在1和n之間可以找到多少個數，使得其中不會有3個構成等差數列？如果n=9，答案是5。因為在1，2，4，8，9這五個數中，找不到3個成為等差數列。所以，在1到9之間有五個數，其中沒有等差數列。那麼，在1 到9之間能否找到6個數使其中不會有3個數的等差數列呢？這也不會。原因如下∶

如果這6個數中已經包含了5，那麼必須捨去4或6。否則，4，5，6就是3個數的等差數列。類似地，必須捨去3與7之一，2與8之一，1與9之一。總之要捨去4個數，而只剩下5個，與題設的6個數發生矛盾。總之，這6個數中不能有5在。

我們又必須捨去1，2，3中的一個數，如果一個都不捨，則又出現了等差數列1，2，3，同理也必須捨去7，8，9中的一個。但是，我們已經不允許取5，所以4和6都必須保留。但是那樣一來，就不能保留2或8。也必須捨去1，4，7之一，總之必須捨去至少4個數，而不可能留下6個數。

當n=9時，這種笨拙的逐個情況逐一論證的辦法還算行得通，n 稍微大一點，就無法逐一考慮了。對於這個問題，似乎沒有一個乾淨利落的答案准確地告訴我們，在1到n之間最大的不包含長度為3的等差數列的集合是什麼，所以我們代之以尋求這個集合的大小的上下界。為了證明一個下界，必須找到一個好的構造、一個不包含任意等差數列大集合的方法；而為了證明一個上界，就必須證明∶任意的有一定大小的集合，必定含有一個等差數列。

至今為止，離最佳的界還很遠呢。1947年，Behrend找到了一個大小為

其中沒有等差數列，而在1999年Jean Bourgain又證明了每一個大小為

都含有一個等差數列。當n=10^100 時，

（4）理論計算機科學是許多最小化問題的來源∶當人們編制一個計算機程式以完成一項任務時，他就會希望在儘可能短的時間裡完成它。下面是一個聽起來很初等的例子∶如果想把兩個n位數相乘，需要多少步？

即使對於什麼叫做一“步”並不太清楚，也能看到通常的乘法，即長乘法，至少需要n^2步。這是因為在計算過程中，第一個數的每一位都會被第二位數的每一位去乘。 人們可能心想，這是必不可少的，但是事實上，有聰明的方法把問題變換一下，就能極大地減少計算機完成這類乘法所需的時間。最快的方法是用

快速傅立葉變換

來把計算的步數從n^2減少到

因為一個數的對數遠小於這個數本身。

另一個實質上類似的問題是∶矩陣乘法有沒有快速演算法？要想用經典的方法把兩個n×n矩陣乘起來，需要對矩陣裡面的數作n^3次單個的乘法。這個問題上的突破主要來自 Strassen，他的思想是把這兩個 n × n 矩陣的每一個都“平分”成 4 個

初看起來只不過是把原來矩陣的乘法化為8對小矩陣的乘法，但是這些乘法實際上是互有關聯的，Strassen做了7個乘法，而8個乘法就可以由此匯出了。然後就可以利用遞迴，就是把同樣的思想用於加速這7個小矩陣的乘法，並仿此以往。

Strassen 的演算法把矩陣乘法的步數的數量級從 n^3 降為

所以這已經是顯著的改進，不過要當n很大時才是。他的基本的分而治之的策略後來又得到改進，最近又有了新的突破（

最近，人工智慧推進了數學研究的程序，揭示了矩陣乘法的新可能性

）。

關於更多的這一類問題，可見計算複雜性和演算法設計的數學還有一類更加微妙的最大化和最小化問題。例如，假設我們想要理解相繼的素數之差的性質。這種差最小為1（2和3之差），不難證明差沒有最大的，所以關於這些差似乎不會有有趣的最大化和最小化問題。

然而事實是，如果先作適當的規範化，就可以提出很吸引人的問題。素數定理指出，接近於n的素數，密度是大約1/logn，所以n附近的兩個素數間平均的空隙長約為logn。如果p，q是兩個相繼的素數，就可以定義它們的規範化的空隙長為（q一p）/logp。這個規範化空隙長的平均值為1，但是會不會有時小得多，有時又大得多？

Westzynthius 在1931年就指出，甚至規範化空隙長也可能任意長，廣泛的信念則是它也可以任意接近於0（由著名的孿生素數猜想立刻可以推出這件事），然而一直到2005年，才由Goldston，Pintz和Yildirim 證明了這一點。