Another graph theory problem? Consider the lines as vertices, draw an edge between two vertices if their corresponding lines are perpendicular. We want the maximum independent set of this graph. Note that $d(v)\le 1$ for all vertices because we are in the plane, so the graph is essentially a collection of isolated vertices and $p$ pairs of vertices connected by an edge. Therefore $k$ is $n-p$. Note that $p\le \lfloor \frac{n}{2}\rfloor$, so $k\ge \lceil \frac{n}{2}\rceil$ always holds. Equality holds when $p=\lfloor \frac{n}{2}\rfloor$, so $k_{max}=\lceil \frac{n}{2}\rceil$.