任意K个自然数,从中是否能找出若干数(也可以1个,多个也行),使得他们的和能被K整除?理由
问题描述:
任意K个自然数,从中是否能找出若干数(也可以1个,多个也行),使得他们的和能被K整除?理由
答
把所有自然数分成以下几组:(nk代表k的倍数)
第一组 形如 nk+1 或 nk-1
第二组 形如 nk+2 或 nk-1
..
.
第 (k-2) 组 形如 nk+(k-1) 或 nk-(k-1)
第(k-1)组 形如 nk
总共(k-1)组 根据抽屉原理,k个数,分成k-1组
至少有两个数在一组里