we-solve (beta)

Math-781-A2 · revision r1 · on Math-781

gpt pro 5.2 attempt on Math-781

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem #361
  2. 1) FORMAL RESTATEMENT
  3. 2) CONTEXT AND DEFINITIONS
  4. 3) QUICK LITERATURE/CONTEXT CHECK
  5. 4) ATTACK PLAN
  6. 5) DETAILED WORK
  7. Consequence for fixed $c>1$.
  8. 6) VERIFICATION AND EDGE CASES
  9. 7) FINAL

Problem #361

1) FORMAL RESTATEMENT

Fix a real constant $c>0$. For each integer $n\ge 1$ let $m=\lfloor cn\rfloor$ and define \[ G_c(n):=\max\left\{|A|:\ A\subseteq\{1,2,\dots,m\}\ \text{and}\ n\notin \Sigma(A)\right\}, \] where $\Sigma(A)=\{\sum_{a\in S} a:\ S\subseteq A\}$ is the set of all subset sums. The problem asks for the size/asymptotics of $G_c(n)$ as $n\to\infty$ and whether $G_c(n)$ depends irregularly on $n$.

2) CONTEXT AND DEFINITIONS

Key observation: if $m\ge n$ and all elements are positive, then elements $>n$ cannot participate in a subset sum equal to $n$. Hence for $m\ge n$ the problem splits: \[ n\notin \Sigma(A)\quad\Longleftrightarrow\quad n\notin \Sigma(A\cap\{1,\dots,n\}). \]

3) QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems forum thread for #361 reports computer checks for $c=3/4$ showing irregular dependence on $n$ (e.g. for $100\le n\le 104$ the maximum sizes are $34,37,32,38,35$), and also notes the "trivial" exact answer when $c\ge 1$.

4) ATTACK PLAN

I will give a complete proof of the exact optimum in the regime $m\ge n$ (in particular, for every fixed $c>1$ and all sufficiently large $n$): \[ G_c(n)=\lfloor cn\rfloor-\left\lceil\frac n2\right\rceil. \] This resolves the "$c\ge 1$" case and shows that in this range the dependence on $n$ is simple (only parity effects via $\lceil n/2\rceil$). For $c<1$ the general problem appears more delicate and (per the forum computations) can be irregular.

5) DETAILED WORK

It suffices to prove the following finite statement.

Theorem 361.1. Let $n,m\in\mathbb{N}$ with $m\ge n$. Then the maximum size of a set $A\subseteq\{1,\dots,m\}$ such that $n\notin\Sigma(A)$ is \[ m-\left\lceil\frac n2\right\rceil. \]

Proof: Let $A\subseteq\{1,\dots,m\}$ and assume $n\notin\Sigma(A)$.

Step 1: reduction to $\{1,\dots,n\}$. Write $A=A_{\le n}\cup A_{>n}$ where $A_{\le n}:=A\cap\{1,\dots,n\}$ and $A_{>n}:=A\cap\{n+1,\dots,m\}$. Any subset sum using an element of $A_{>n}$ is $>n$, hence cannot equal $n$. Therefore $n\notin\Sigma(A)$ iff $n\notin\Sigma(A_{\le n})$. So \[ |A|=|A_{>n}|+|A_{\le n}|\le (m-n)+\max\{|B|:\ B\subseteq\{1,\dots,n\},\ n\notin\Sigma(B)\}. \] Thus it is enough to compute the maximum size in the case $m=n$.

Step 2: the $m=n$ upper bound. Let $B\subseteq\{1,\dots,n\}$ with $n\notin\Sigma(B)$. Then $n\notin B$ (otherwise $\{n\}$ is a subset summing to $n$). Also, for each $x\in\{1,\dots,n-1\}$ we cannot have both $x$ and $n-x$ in $B$, since then $\{x,n-x\}$ sums to $n$. The pairs \[ \{1,n-1\},\ \{2,n-2\},\ \dots,\ \left\{\left\lfloor\frac{n-1}{2}\right\rfloor,\, n-\left\lfloor\frac{n-1}{2}\right\rfloor\right\} \] are disjoint. From each such pair, $B$ can contain at most one element. If $n$ is even, there is one additional unpaired element $n/2$ (since $n-(n/2)=n/2$), which may or may not be in $B$. Hence \[ |B|\le \begin{cases} \frac{n-1}{2}=\left\lfloor\frac n2\right\rfloor, & n\text{ odd},\\[4pt] \frac{n-2}{2}+1=\frac n2=\left\lfloor\frac n2\right\rfloor, & n\text{ even}, \end{cases} \] so in all cases $|B|\le \lfloor n/2\rfloor$.

Step 3: construction (sharpness) for $m=n$. Define \[ B_0 := \{\lceil n/2\rceil,\ \lceil n/2\rceil+1,\ \dots,\ n-1\}\subseteq\{1,\dots,n\}. \] Then $|B_0|=n-\lceil n/2\rceil=\lfloor n/2\rfloor$. We claim $n\notin\Sigma(B_0)$. Indeed, any one-element subset sum is at most $n-1$. Any subset of size at least $2$ has sum at least $\lceil n/2\rceil + (\lceil n/2\rceil+1)>n$. Therefore no subset sum equals $n$.

Thus the maximum over subsets of $\{1,\dots,n\}$ is exactly $\lfloor n/2\rfloor$.

Step 4: conclude for general $m\ge n$. Taking $A:=B_0\cup\{n+1,\dots,m\}$ gives \[ |A|=\lfloor n/2\rfloor+(m-n)=m-\lceil n/2\rceil, \] and $n\notin\Sigma(A)$ by Step 1. This matches the upper bound, so it is optimal. ∎

Consequence for fixed $c>1$.
If $c>1$ is fixed and $m=\lfloor cn\rfloor$, then for all large $n$ one has $m\ge n$, hence \[ G_c(n)=\lfloor cn\rfloor-\left\lceil\frac n2\right\rceil = \left(c-\frac12\right)n + O(1). \] So in this range there is no "irregular" dependence beyond parity.

6) VERIFICATION AND EDGE CASES

  • For $c=1$ this gives $G_1(n)=\lfloor n/2\rfloor$, matching small-$n$ checks.
  • The proof uses only the two-element obstruction $x+(n-x)=n$ and the single-element obstruction $\{n\}$; this is enough to cap the size, while the explicit $B_0$ avoids all subset sums $n$ because its elements are so large that any two already exceed $n$.

7) FINAL

UNRESOLVED (for the full range $c>0$), but with a complete solution for $c\ge 1$.
  • (i) Strongest proved partial result: if $c\ge 1$ and $m=\lfloor cn\rfloor$, then \[ G_c(n)=m-\left\lceil\frac n2\right\rceil = \left(c-\frac12\right)n + O(1), \] with the explicit extremal set $A=\{\lceil n/2\rceil,\dots,n-1\}\cup\{n+1,\dots,m\}$.
  • (ii) First remaining gap: determine $G_c(n)$ (or even its correct order of magnitude) for fixed $0<c<1$; explain/prove the reported irregular dependence on $n$ in that regime.
  • (iii) Next moves: for $c<1$, combine "pairing" constraints with modular constructions (e.g. taking multiples of the smallest prime not dividing $n$) and optimize; try to prove matching upper bounds.
  • (iv) Minimal counterexample search: for fixed $c<1$, compute/estimate $G_c(n)$ across residue classes and prime factorizations of $n$ to identify the correct extremal templates.

COMPLETION: 70%