一百個人能配成 (100·99)/2 對,也就是 4950 對——於是一場人人互握一次的聚會,總共發生 4950 次握手。把除以 2 去掉就得到 9900,它數的是另一樣東西:有序對。在這裡,A 向 B 問好與 B 向 A 問好是兩件事。
凡是隻數相互作用發生了多少次、不數到場有多少人的地方,100·99/2 這個形狀都會重新露面:網路的連線、比較排序、生日問題裡 23 個人給出的 253 對。每多進來一位客人,新增的握手次數正好等於屋裡已有的人數,所以總數就是 1 + 2 + … + 99 這一串——高斯那則軼事加出來的,也是同一個三角形數。
答案
4950
口徑說明
不計順序的那個計數。工作台算 100 × 99 得 9900,是有順序的版本——恰好兩倍。
出處
The number of edges of the complete graph K_n is n(n − 1)/2, the triangular numbers A000217; the party form is the standard counting argument
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進螢幕——答案就是上面那一行,可以自己核對。