MathLabs

第6题

一个国际协会的成员来自六个不同国家。成员名单有 19781978 人，编号为 1,2,…,19781,2,\ldots,1978。证明至少有一名成员，其编号是本国两名成员编号之和，或是本国一名成员编号的两倍。
第 3/6 步：重复差的递降
上一步下一步
通俗地说

每次递降要么证明结论，要么减少可用国家数。

⌈3295⌉=66,⌈654⌉=17\left\lceil\frac{329}{5}\right\rceil=66,\quad\left\lceil\frac{65}{4}\right\rceil=17
详细分析

至少有 6666 个差属于同一国家。以其中最小者为基准取 6565 个差；若某差落入已用国家，则利用嵌套差的表示得到所需同国和。否则至少有 1717 个差属于一个新国家。