123-Separable

A set, $S$, of integers is called 123-separable if $S$, $2S$ and $3S$ are disjoint. Here $2S$ and $3S$ are obtained by multiplying all the elements in $S$ by $2$ and $3$ respectively.

Define $F(n)$ to be the maximum number of elements of
$$(S\cup 2S \cup 3S)\cap \{1,2,3,\ldots,n\}$$
where $S$ ranges over all 123-separable sets.

For example, $F(6) = 5$ can be achieved with either $S = \{1,4,5\}$ or $S = \{1,5,6\}$.
You are also given $F(20) = 19$.

Find $F(10^{16})$.

The concept of 123-separability implies that we should allocate the numbers in the set $S$ from smallest to largest. We will always choose $k$ over $2k$ or $3k$, since choosing $k$ prevents us from choosing $2k$ or $3k$, but choosing $2k$ or $3k$ compounds the problem by also restricting another number that could be added to $S$.

Start allocating from 1. We can immediately see a pattern.

For $1 \le n \le 3$, $F(n) = n$.

For $4 \le n < 6$, 4 can't be included anymore due to the restrictions, so we choose 5. For $6 \le n < 8$, 6 can't be included, so $F(6) = F(5) = 5$. For $8 \le n < 12$, 8 can't be included as well, but 9 can, and so the function $F$ attains the value 7 for these $n$. For $n = 12$, $F(12) = 9$. After this, we can see the pattern. For every 3 numbers, 2 can be included in $S$. So, we can generalize this into $F(n) = [\frac{2n}{3}]$, the largest integer less than or equal to $\frac{2n}{3}$. This function represents the "biased allocation". For $F(10^{16})$, simply calculate $[\frac{2 \cdot 10^{16}}{3}]$. Therefore, $F(10^{16}) = \frac{2 \cdot 10^{16}}{3}$ (as 10^16 is a multiple of 3).

More Answers: