1.舞会
A先生和他的太太参加了一场共有n对夫妻的舞会，已知夫妻之间不能握手，而且A先生之外的所有人握手次数都不相同。求A先生太太握几次手？
解析：一共有2n个人，而除去A先生共有2n-1个人。注意到一个人不能和自己和配偶握手，最多握手次数是2n-2，所以本题隐藏了一个条件即有一个人握手次数是0，并且A先生的握手次数等于2n-1个人中的某个人。
这时又注意到，握手2n-2次的人只没握过其配偶的手，若握手次数为0的人不是他的配偶，那么一定会与他握手，与前提矛盾，所以，握手次数为0的人一定和握手2n-2次的人是夫妻。
接下来，假设握手0、2n-2次的人不存在，那么原本握手1次的人变为握手0次，可以推出原本握手2n-3次的人一定是握手1次的人的配偶。
（从另一个角度看，握手1次的人一定握的是2n-2次的人，如果一次人不是握手2n-3次的人的配偶，那么2n-3次的人没握手的只有0次人和其配偶，也就是说一定握了1次的人，而一次人只与2n-2次人握手，所以，前提矛盾。）
接下来，一次次推导，
2n-2~0
2n-3~1
2n-4~2
...
发现每个人和他配偶握手次数相加为2n-2。结合A先生与2n-1个人中某人握手次数相同，容易发现他们的握手次数都是n-1次。
2.男女队员
一个长度为4n的队列，有2n男、2n女。问此序列中存在长度为2n的区间使得其中有n男n女的概率，并证明。
通过取4的例子发现，对于特定的n，存在这样的区间概率为100%。鉴于题意中没有区分n的大小，可以认为该结论对任意n都成立，接下来考虑如何证明。
显然序列中长度为2n的区间有2n+1个，一种简单的想法是证明它们中至少有一个满足条件。这样，这2n+1个区间就作为一个集合，既然需要证明其中的某一个是特殊的，就可以知道证明过程中需要所有这些区间的一部分信息。考虑最左侧区间，表征其信息显然可以使用男性数量。设为x。考虑关联元素，即其右侧相邻区间，容易知道x或增加1或减少1或不变。则可以知道区间的变化在整数集内是连续的。注意到最右侧区间男性数量必定为2n-x，由连续性可知，从最左侧到最右侧，男性数量连续地从x变化为2n-x。又知道x和2n-x中一定有一个男性数量大于等于n，一个小于等于n，由连续性知其中必定有一个男性数量为n，证毕。
3.赛马问题
现有64匹赛马和一个八跑道赛场。问最少赛多少场才能测出最快的4匹马。
一个明显的陷阱是赛九场，8场选出每场最快的4匹，一场选出顺序。错误原因在于，最快的四匹马需要所有64匹的信息，然而每一场比赛选择的马匹都是随机的，也就是说每场比赛的信息是孤立的，这样选出的4匹可能不是最快的4匹。例如，假如一场比赛的前四是64匹马的前四，那么赛九场自然是错误的。
所以，我们必须顾及64匹马。显然赛8场不会改变，因为我们需要全部信息，但是之后我们需要把每一场的所有马的信息关联起来，所以我们使八场的冠军比赛，以冠军速度顺序排列八场共64匹马为一个序列（不改变每一场内部顺序）。由于每一场的马匹速度是单调的，而所有排头速度是单调的，可以知道每场排头比之后的排头快，每场排头比同场的马快，可以知道排头必定比它后面所有的马都快，但无法确定它前面的非排头马速度大小。所以，从前往后每场比赛必定至少产生一名包括排头的入选者，因为如果没选该场比赛排头，之后所有马都比该排头慢，不符合越快越好的规则，所以每场必定先选排头。此时也可以得出，序列中只有前三场和第四场排头有机会，因为选到第四场排头时至少有四名入选者了。
由于第一名已经确定，所以7+1一场最好可以选出剩余3名，最坏可以选出剩余1名。如果选出的小于三名，则再选7+1一场即可选出剩余全部三名。
所以，最坏情况11场，最好情况10场。
标签：排头,思维,次数,握手,几道,配偶,每场,2n From： https://www.cnblogs.com/dudujerry/p/17686093.html