Skip to content

Erdős problem 350

If A ⊂ ℕ is a finite set of integers all of whose subset sums are distinct then ∑ n ∈ A, 1/n < 2. Proved by Ryavec.

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

350.lean

Retained formal statement4 of 5

If A ⊂ ℕ is a finite set of integers all of whose subset sums are distinct then ∑ n ∈ A, 1/n < 2. Proved by Ryavec.

This was proved by Ryavec, who did not appear to ever publish the proof. Ryavec's proof is reproduced in [BeEr74]. More generally, Ryavec's proof delivers that nA1n221A,\sum_{n\in A}\frac{1}{n}\leq 2-2^{1-\lvert A\rvert}, with equality if and only if A={1,2,,2k}A=\{1,2,\ldots,2^k\}.

This was formalized in Lean by Alexeev using Aristotle.

FormalConjectures/ErdosProblems/350.leanErdos350.erdos_3501 lineExact file
∀ (A : Finset ℕ), Erdos350.DecidableDistinctSubsetSums A → ∑ nA, 1 / ↑n < 2
SolvedProof has a holeformal conjecturesexternal proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page