Slovenija 2008

The first figure is for $N=12$ and the second is for $N=4$. Let us prove that these are the greatest and the smallest possible values of $N$.



A cube has $8$ vertices. We draw $6$ diagonals, so there are $12$ endpoints altogether. There are $0$, $1$, $2$ or $3$ of the chosen diagonals coming from every vertex of the cube. So, for every vertex we get $0$, $0$, $1$ or $3$ different pairs of diagonals.

Assume that it is possible to get $N\le 3$. If there exists a vertex with $3$ diagonals, then the remaining vertices can have at most one diagonal. This would imply that there are at most $1\cdot 3+7\cdot 1=10$ endpoints, a contradiction.



Thus, no vertex has $3$ chosen diagonals meeting at it and there can be at most $3$ vertices where two of the diagonals meet. Again, every other vertex can be the endpoint of at most one diagonal and there are at most $3\cdot 2+5\cdot 1=11$ endpoints in this case. Once more, a contradiction. We have shown that $N\ge 4$.

There are $\frac{6\cdot 5}{2}=15$ different pairs of diagonals. No two diagonals belonging to the opposite faces of the cube intersect, so there are at most $15-3=12$ different pairs of intersecting diagonals, $N\le 12$.