IMC 2016 Problem 2

Let $k$ and $n$ be positive integers. A sequence $\left( A_1, \dots , A_k \right)$ of $n\times n$ real matrices is preferred by Ivan the Confessor if $A_i^2\neq 0$ for $1\le i\le k$ , but $A_iA_j=0$ for $1\le i$ , $j\le k$ with $i\neq j$ . Show that $k\le n$ in all preferred sequences, and give an example of a preferred sequence with $k=n$ for each $n$ .

(Proposed by Fedor Petrov, St. Petersburg State University)