题干:史密斯先生和他的太太邀请四对夫妻来参加晚会。每个人来的时候,房间里的一些人都要与别的一些人握手。当然,每个人都不会与自己的配偶握手,也不会跟同一个人握手两次。之后,史密斯先生问每个人和别人握了几次手,他们的答案都不一样。那么,问史密斯太太和别人握了几次手呢?
分析已知条件:
1、由史密斯夫妇和四对夫妻可知,总共有10个人。
2、史密斯先生所询问的9个人的握手次数均不相同。
3、约束条件:①每个人均不与配偶握手,当然也不与自己握手。
②相同的两个人最多只握一次手。
因此,每个人握手的次数最多为8次,最少为0次。
所以,问题可以简单的看做将0、1、2、3、4、5、6、7、8九个数字分配给九个人。
解:
1、假设M1握手次数为8,那么除了M1自己和M1的配偶m1外,另外的8个人必定与M1握手一次。因此,握手次数为0的必定是M1的配偶m1。
2、假设M2握手次数为7,由1知7次中必有1次与M1握手,剩下的6次与除M1,m1外的7个人中产生。同样的M2不能和配偶m2握手,不能和自己握手,因此,排除m2,M1,m1外的6个人必定与M2握手一次,握手次数为1的必定是M2的配偶m2(与先前的M1握手一次)。
同理,假设M3握手次数为6,,那么其配偶m3握手次数为2,假设M4握手次数为5,,那么其配偶m4握手次数为3。因此,最终剩下的那位一定就是史密斯先生的妻子,其握手次数为4。
史密斯先生握手问题是由爱丁堡大学的PeterRoss提出来的。个人觉得蛮有趣的,乍一看似乎这题很不简单(可能自己太菜了-_-),但是找到突破口之后问题便很快有了答案!