Splitting the plane

Firstly, we must examine the values of $A_n$ . Suppose we already have $n$ lines in the plane. Now we add line number $n+1$ , $\ell_{n+1}$ so that our conditions are still satisfied. This means that $\ell_{n+1}$ intersects every line $\ell_1 \ldots \ell_n$ at a different location.

Each time $\ell_{n+1}$ intersects a new line, it enters a new region, which it divides into 2 parts, adding an extra region. Thus, $\ell_{n+1}$ creates $n+1$ new regions: it bisects the uppermost (open) region that it starts in, and then, moving down, it enters $n$ new regions.

So, $A_{n+1} = A_n + (n+1)$ , and $A_0 = 1$

$\therefore A_n = 1+ \sum_{i=1}^n i = T_n+1$ where $T_n \equiv {n\choose 2} = \frac{n(n+1)}{2}$ are the triangular numbers $0,1,3,6,10,15 \ldots$

In order for $A_n$ to be a power of 2,

we must have: $\frac{n(n+1)}{2} + 1 = 2^k \implies n^2 + n = 2^{k+1} -2$ Instead of looking at all possible values of $n$ ,we examine powers of 2.

Note that if $n\le 10^6$ , then $A_n \le \frac{(n+1)^2}{2} < 2^{39}$ .

Further, note that $n^2 < n^2 + n < (n+1)^2$ for positive numbers. This means, if an integer $n$ satisfies the relation, it must be the integer immediately preceding the square root of $2^{k+1} -2$ .

Thus, we can simply go through powers $2^k$ for $k = 0 \ldots 39$ , and take $n = \lfloor 2^{k+1} - 2 \rfloor$ , and check if $n^2 + n = 2^{k+1} - 2$ . For most powers of two, this can even be done by hand.

Doing this up to 39 reveals that for $k = 12, 2^{k+1} - 2 = 8190$ , $n^2+n = 8100 + 90 = 8190$ which means that for $n=90$ $A_n = 2^{12} = 4096$ . So we have $\fbox{n=90, k = 12}$ .

The other solutions are $\fbox{n=1, k=1; n=2, k=2; n=5, k=4}$ . Note that $n=0, k=0$ is a solution, but zero is not positive. Thus there are 4 positive solutions.