II 5
description:
给定正整数 n≥5 和正整数 a1,a2,…an,如果集合 S={a1,a2,…an} 的任意两个不同的非空子集 A,B 满足: A 中所有数的和不等于 B 中所有数的和。试求 a11+a21+⋯+an1 的最大值。
solution:
首先目测S={1,2,22,…,2n−1} 即为所求的结果,下证其满足“ A 中所有数的和不等于 B 中所有数的和”的条件:
当 S={1,2,22,…,2n−1}时,其中任意两个非空子集元素和显然:
1+2k1+…2kr=2m1+⋯+2mt(1≤ki,mi≤n−1)。
(因为等式两边一奇一偶。
若 2k1+…2kr=2m1+⋯+2mt(1≤ki,mi≤n−1)。
其中 k1<k2<⋯<kr,m1<m2<⋯<mt;
不妨设 k1<m1,等式两边同时除以 2k1,则有:
1+2k2−k1+…2kr−k1=2m1−k1+…2mt−k1。
(还是因为一奇一偶
故得证 S 中元素满足条件。
∴11+21+⋯+2n−11=2−2n−11
下证:对 S={a1,a2,…,an} 满足条件时,有 a11+a21,⋯+an1≤11+21+⋯+2n−11
使用做差法:
11+21+⋯+2n−11−a11+a21,⋯+an1=a1a1−1+2a2a2−2+22a3a3−2a1