Question

请教一题证明题

请教一题证明题请教怎么用鸽巢原理来证明

Answer 1

此题用鸽巢原理很难构造鸽巢。例如n=5,可构造鸽巢：
{6,2},{7,1},{8,4},{9,3},{10,5};
n=6,可构造鸽巢：
{7,1},{8.4,2},{9,3},{10,5},{11},{12,6}.
但对于任意的n,就难以表达。
但可以用别的证法。例如，在1至2n的整数中，取n+1,n+2,……,2n这n个数，都不存在一个数能被另一个数整除。如果增加一个不大于n的正整数，那么上述n个数中至少要去掉一个能被它整除的数，所以命题成立。