Problem 963

Let $f(n)$ be the maximal $k$ such that in any set $A\subset \mathbb{R}$ of size $n$ there is a subset $B\subseteq A$ of size $\lvert B\rvert\geq k$ which is dissociated that is, the sums $\sum_{b\in S}b$ are distinct for all $S\subseteq B$ . Estimate $f(n)$ - in particular, is it true that

f(n)\geq \lfloor \log_2 n\rfloor?

Source: erdosproblems.com/963

Number theory

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN, with its note that no finite computation can settle it (page last edited 23 January 2026).

Er65: Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math. VIII, Amer. Math. Soc. (1965), 181--189. Printed p. 188: the bound $k\ge\lfloor\log n/\log3\rfloor$ , called not difficult and given without proof, the question whether $\lfloor\log n/\log2\rfloor$ is attainable, and the example $a_i=i$ . Library home: Erdos 1965.
Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999); the site cites item 1.22.

Problem 963

Status

Proof claims

Discussion