数学奥赛题,哥哥姐姐们帮帮忙啊已知S={1,2,3,4……1997},A={a1,a2,a3……aR}且A是S的子集.A中任意2个不同元素之和不能被117整除,试确定R的最大值.速度不需要太快,关键是过程,

数学奥赛题,哥哥姐姐们帮帮忙啊已知S={1,2,3,4……1997},A={a1,a2,a3……aR}且A是S的子集.A中任意2个不同元素之和不能被117整除,试确定R的最大值.速度不需要太快,关键是过程,
数学奥赛题,哥哥姐姐们帮帮忙啊
已知S={1,2,3,4……1997},A={a1,a2,a3……aR}且A是S的子集.
A中任意2个不同元素之和不能被117整除,试确定R的最大值.
速度不需要太快,关键是过程,

数学奥赛题,哥哥姐姐们帮帮忙啊已知S={1,2,3,4……1997},A={a1,a2,a3……aR}且A是S的子集.A中任意2个不同元素之和不能被117整除,试确定R的最大值.速度不需要太快,关键是过程,
一个数x能被117整除,表示 x mod 117 ≡ 0
这样,在A中,我们只需要不同时选取mod 117的值的和为117的两个数即可.
比如 58 mod 117 ≡ 58,59 mod 117 ≡ 59,我们不同时选取就可以了.
而 117 mod 117 ≡ 0,所以在1到117中,我们最多只能选取58个数（比如选1到58）
后面,我们只需要选择 117a + 前面选的58个数 （a为任意自然数）,就可以满足要求了.
1997 = 8 + 117 × 17
所以我们最多可以选择 58 × 17 + 8 = 994个数（前提是前58个数必须选取1到8）.
所以R的最大值为994.
（举个例子,A = { 1,2,3,4,5,6,7,8,.,57,58,
117 + 1,117 + 2,.,117 + 57,117 + 58,
.,
117 * 16 + 1,117 * 16 + 2,.117 * 16 + 57,117 * 16 + 58,
117 * 17 + 1,117 * 17 + 2,117 * 17 + 3,117 * 17 + 4,117 * 17 + 5,117 * 17 + 6,117 * 17 + 7,117 * 17 + 8 }
一共 994个数）

一个数x能被117整除，表示 x mod 117 ≡ 0
这样，在A中，我们只需要不同时选取mod 117的值的和为117的两个数即可。
比如 58 mod 117 ≡ 58， 59 mod 117 ≡ 59，我们不同时选取就可以了。
而 117 mod 117 ≡ 0，所以在1到117中，我们最多只能选取58个数（比如选1到58）
后面，我们只需要选择 1...

全部展开

一个数x能被117整除，表示 x mod 117 ≡ 0
这样，在A中，我们只需要不同时选取mod 117的值的和为117的两个数即可。
比如 58 mod 117 ≡ 58， 59 mod 117 ≡ 59，我们不同时选取就可以了。
而 117 mod 117 ≡ 0，所以在1到117中，我们最多只能选取58个数（比如选1到58）
后面，我们只需要选择 117a + 前面选的58个数 （a为任意自然数），就可以满足要求了。
1997 = 8 + 117 × 17
所以我们最多可以选择 58 × 17 + 8 = 994个数（前提是前58个数必须选取1到8）。
所以R的最大值为994。

收起

把1,2,3,...,1997这1997个数分为118组,具体分组这样进行,
用这些数去除118,所得余数从0,1,2,..,117刚好118组.
而这些组中刚好有这样的情况,要是取了余数为0的,就不能再取余数为117的,否则不能满足要求.
所以只能取一半的.有118/2=59组.而1997/118=16余109,也就是说
余数为1,2,...109的...

全部展开

把1,2,3,...,1997这1997个数分为118组,具体分组这样进行,
用这些数去除118,所得余数从0,1,2,..,117刚好118组.
而这些组中刚好有这样的情况,要是取了余数为0的,就不能再取余数为117的,否则不能满足要求.
所以只能取一半的.有118/2=59组.而1997/118=16余109,也就是说
余数为1,2,...109的这109组有17个数,而余数为109,110,...,117,0的这些组只有16个.要使R最大,取较多元素的组.所以R=17*59=1003.不知对否.

收起