Solution:

b) We prove the following: Given a partition of the set of all powers of $2$ (i.e. two sets $Q$ and $R$ such that each $2^{k}$ is in exactly one of $Q, R$) there exists a unique partition $A, B$ of positive integers with all powers of $2$ prohibited and with $Q \subseteq A, R \subseteq B$. Note that this implies that there are infinitely many partitions of integers with powers of $2$ prohibited, and exactly one such partition with $P \subseteq A$.

First we show that the required partition is unique if it exists. Without loss of generality $1$ is in $A$. Suppose now that we have been able to place all integers up to some $k$ unambiguously, i.e. for any $l < k$ we know whether $l$ is in $A$ or in $B$. If $k$ is a power of $2$ we know where to put it. Otherwise let $2^{i}$ be the smallest power of $2$ strictly greater than $k$. Then $d = 2^{i} - k$ is positive and less than $k$. Therefore we know to which of two sets ($A$ or $B$) the number $d$ belongs. Then we have no choice but to place $k$ in the other set (otherwise $k$ and $d$ would be in the same set, and since $k + d = 2^{i}$ this would contradict $A, B$ being acceptable). So there exists no more than one acceptable partition.

We now show that the desired partition exists. Since we have already defined above a recursive construction producing $A, B$, we just need to check that the resulting partition is in fact acceptable. Suppose not. Then there exist $n < m$ such that $n + m = 2^{i}$ for some $i$ and $m, n$ are in the same set of the partition. Then $m$ is not a power of $2$ (if it were, $n$ would be greater than $m$). Note that $n < m$ implies that $2^{i}$ is the smallest power of $2$ strictly greater than $m$. Then by construction $m$ is in the set different from $n$. Contradiction. So there is no such pair $m, n$. The partition constructed above works. This completes the proof.

a) The proof is similar to that of part b. We will call a partition acceptable if $F$ is prohibited for it. First, we show that there exists no more than one acceptable partition. Since we do not distinguish between $A, B$ we may assume without loss of generality that $1$ is in $A$. Suppose now that we have been able to place all integers up to some $k$ unambiguously, i.e. for any $l < k$ we know whether $l$ is in $A$ or in $B$. Let $f_{i}$ be the smallest Fibonacci number strictly greater than $k$. Then $d = f_{i} - k$ is positive and less than $k$ (to see that, note that if $f_{i} - k > k$ then $2k < f_{i}$, $k < f_{i}/2 \leq f_{i-1}$, contradicting the choice of $f_{i}$).

Therefore we know to which of two sets ($A$ or $B$) the number $d$ belongs. Then we have no choice but to place $k$ in the other set (otherwise $k$ and $d$ would be in the same set, and since $k + d = f_{i}$ this would contradict $A, B$ being acceptable). So there exists no more than one acceptable partition.

We now show that there actually exists an acceptable partition. Since we have already defined above a recursive construction producing $A, B$, we just need to check that the resulting partition is in fact acceptable. Suppose not. Then there exist a smallest $m$ such that $n + m = f_{i}$ for some $n < m$, and $m, n$ are in the same set (by renaming $A$ and $B$ if necessary we may assume $m, n$ are in $A$), i.e. the first $m$ for which there is a problem with the above recursive construction. Then if $f_{j}$ is as before the smallest Fibonacci number bigger than $m$ we have $f_{j-1} \leq m < f_{j}$ which together with $n < m$ gives $f_{j-1} < m + n < 2f_{j} < f_{j+2}$. But $m + n = f_{j}$ is excluded by construction (recall that $m$ is assigned to the set other than that of $f_{j} - m$). So it must be that $m + n = f_{j+1}$. On the other hand for $\hat{m} = f_{j} - m$, $\hat{n} = f_{j} - n$ we have:

1. $\hat{n} > \hat{m} > 0$ and $\hat{n} = f_{j} - n < m$, so the bigger of $\hat{n}, \hat{m}$ is less than the bigger of $m, n$.
2. $\hat{m} + \hat{n} = f_{j} + f_{j} - (m + n) = f_{j} + f_{j} - f_{j+1} = f_{j} - f_{j-1} = f_{j-2}$.
3. $\hat{m}$ is in $B$ by construction.
4. $\hat{n}$ is in $B$, because otherwise $\hat{n}, n$ will be a pair of elements of $A$ adding up to a Fibonacci number with the maximal element in the pair less than $m$, contradicting our choice of $m$.

These observations together mean that $\hat{n}, \hat{m}$ is a pair of elements of $B$ adding up to a Fibonacci number with the maximal element in the pair less than $m$, contradicting our choice of $m$. This contradiction shows that $A, B$ constructed above is indeed an acceptable partition.