Erdős Problem 361 #
Reference: erdosproblems.com/361
theorem
Erdos361.erdos_361.bigO
(c : ℝ)
(hc : 0 < c)
(A : ℕ → ℕ)
(hA : ∀ (c n : ℕ), A n = {B ∈ (Finset.Icc 1 ⌊c * n⌋₊).powerset | n ≠ ∑ a ∈ B, a}.sup Finset.card)
:
Let $c > 0$ and $n$ be some large integer. What is the size of the largest set $A \subseteq \{1, \ldots, \lfloor c n \rfloor\}$ such that $n$ is not a sum of a subset of $A$? Does this depend on $n$ in an irregular way?
theorem
Erdos361.erdos_361.bigTheta
(c : ℝ)
(hc : 0 < c)
(A : ℕ → ℕ)
(hA : ∀ (c n : ℕ), A n = {B ∈ (Finset.Icc 1 ⌊c * n⌋₊).powerset | n ≠ ∑ a ∈ B, a}.sup Finset.card)
:
Let $c > 0$ and $n$ be some large integer. What is the size of the largest set $A \subseteq \{1, \ldots, \lfloor c n \rfloor\}$ such that $n$ is not a sum of a subset of $A$? Does this depend on $n$ in an irregular way?
theorem
Erdos361.erdos_361.smallO
(c : ℝ)
(hc : 0 < c)
(A : ℕ → ℕ)
(hA : ∀ (c n : ℕ), A n = {B ∈ (Finset.Icc 1 ⌊c * n⌋₊).powerset | n ≠ ∑ a ∈ B, a}.sup Finset.card)
:
Let $c > 0$ and $n$ be some large integer. What is the size of the largest set $A \subseteq \{1, \ldots, \lfloor c n \rfloor\}$ such that $n$ is not a sum of a subset of $A$? Does this depend on $n$ in an irregular way?