抽屉原理问题

以下是引用seaverr在2003-9-9 9:47:00的发言：
抽屉原理


     抽屉原理又叫狄里克雷原理，是指：把n+1个元素，任意放入n个抽屉，则其中必有一个抽屉里至少有2个元素.（证明略）应用抽屉原理来解一些数学题目，往往会起到较好的效果.
    抽屉原理较简单的一个应用如：在任意3名同学中，至少有2名同学的性别相同.我们不妨将男、女性别视为两个抽屉，3名同学视为3个元素，依据抽屉原理，其中必有一个抽屉里至少有2个元素，即至少有2名同学的性别相同.
    抽屉原理的更为一般的表达形式是：把多于n个元素，任意放入n个抽屉里，则有一个抽屉里放进了两个或更多的元素.
    应用抽屉原理解题，关键是构造合适的抽屉.
    其具体应用为：

例1：证明任意7个不同的整数中，必有两个数，它们的和或差是10的倍数.

证明：∵任意整数除以10的余数，只能是0，1，2，3，4，5，6，7，8，9这十个数中的一个.
    ∴不妨从余数角度出发，考虑构造合适的抽屉.（由题目分析，要求我们构造六个抽屉，并且抽屉中的余数和或差只能是0）
    由这10个余数，构造6个抽屉：
    {0}，{5}
     {1，9}，{2，8}，{3，7}，{4，6}
    则任意7个不同整数除以10后所得余数（即7个元素），任意放入这6个抽屉，其中必有一个抽屉包含有其中2个不同整数除以10后所得的2个余数.
    若这两个余数同属于抽屉{0}或抽屉{5}，则此二余数差是0，即这两个余数对应的整数之差可以被10整除.
    若这两个余数同属于{1，9}，{2，8}，{3，7}，{4，6}这四个抽屉中的任意一个，则这两个余数和是10，即这两个余数所对应整数之和是10的倍数.
    可见，任意7个不同的整数中，必有两个数的和或差是10的倍数.

例2：对于任意的五个自然数，证明其中必有3个数的和能被3整除.

证明：第一步：构造合适的抽屉
     ∵任何数除以3所得余数只能是0，1，2，不妨分别构造为3个抽屉：
     {0}，{1}，{2}
     若这五个自然数除以3后所得余数分别分布在这3个抽屉中，我们从这三个抽屉中各取1个，其和必能被3整除.
     若这5个余数分布在其中的两个抽屉中，则其中一个抽屉，包含有3个余数（抽屉原理），而这三个余数之和或为0，或为3，或为6，故所对应的3个自然数之和是3的倍数.
     若这5个余数分布在其中的一个抽屉中，很显然，必有3个自然数之和能被3整除.

例2′：对于任意的11个整数，证明其中一定有6个数，它们的和能被6整数.

证明：设这11个整数为：a1，a2，a3……a11
    ∵6=2×3
    先考虑被3整除的情形
    由例2知，在11个任意整数中，必存在：
    3|a1+a2+a3
    不妨设a1+a2+a3=b1；
    同理，剩下的8个任意整数中，由例2，必存在：3 | a4+a5+a6.
    不妨设a4+a5+a6=b2；
    同理，其余的5个任意整数中，
    有：3|a7+a8+a9
    设：a7+a8+a9=b3
    再考虑b1、b2、b3被2整除.
    依据抽屉原理，b1、b2、b3这三个整数中，至少有两个是同奇或同偶，这两个同奇（或同偶）的整数之和必为偶数.不妨设2|b1+b2
    则：6|b1+b2
    即：6|a1+a2+a3+a4+a5+a6
    ∴任意11个整数，其中必有6个数的和是6的倍数.

思考题：

     n名同学每人至少与别人握一次手，但不能重复.证明其中至少有2名同学握手次数相同.

——可参看《北京数学奥林匹克初中教材》

解题新思路：

     鸡兔四十九
     百条腿地里走
     问：鸡、兔各几何
     分析：此题实际是简单的二元一次方程组
     设：鸡为x只，兔为y只，则
     
     解此方程组即可得
     另法：假设鸡、兔都为两条腿，则四十九只鸡、兔共98条腿，比100还差两条，此两条恰为兔少的两条腿，所以应该有一只兔，四十八只鸡.