A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Have We Met Before?」.

Have We Met Before? #

Problem #

Show me that if there are 6 people at a party, then either at least 3 people met each other before the party, or at least 3 people were strangers before the party.

Solution 1 #

本题是一道经典的组合问题, 是著名的拉姆齐二染色定理的一种特殊情况 $R(3,3) = 6$ . 由抽屉原理, 对于 $A$ , 另外五个人中要么至少有三个人和他相识, 要么至少有三个人和他不相识. 不妨设至少有三个人和 $A$ 相识, 如果这三个人里有两个互相认识, 那么这两个人和 $A$ 组成了互相认识的三个人; 如果这三个人两两都不认识, 那么这三个人就组成了互相不认识的三个人.