Skip to content

Erdős problem 1

If A⊆{1,...,N}A\subseteq\{1, ..., N\} with ∣A∣=n|A| = n is such that the subset sums ∑a∈Sa\sum_{a\in S}a are distinct for all S⊆AS\subseteq A then N≫2n. N \gg 2 ^ n.

Sources

The source's own material, retained exactly.

8 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1.lean

Retained formal statement7 of 8

A generalisation of the problem to sets A⊆(0,N]A \subseteq (0, N] of real numbers, such that the subset sums all differ by at least 11 is proposed in [Er73] and [ErGr80].

[Er73] Erdős, P., _Problems and results on combinatorial number theory_. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.

[ErGr80] Erdős, P. and Graham, R., _Old and new problems and results in combinatorial number theory_. Monographies de L'Enseignement Mathematique (1980).

FormalConjectures/ErdosProblems/1.leanErdos1.erdos_1.variants.real1 lineExact file
∃ C > 0, ∀ (N : ℕ) (A : Finset ℝ), Erdos1.IsSumDistinctRealSet A N → N ≠ 0 → C * 2 ^ A.card < ↑N
OpenStatement only, no proof