First of all note that we have $ (q + 1)^q - 1$ possible nonzero vectors $ (x_1,\cdots,x_q)$ such that $ 0\leq x_i\leq q$ are integers. But $ a_{j1}x_1 + \cdots + a_{jq}x_q$ can only assume $ q^2 + 1$ different values, because if it is maximized/minimized by $ (M_1,M_2,\cdots,M_q)/(m_1,m_2,\cdots,m_q)$, we have that $ \sum_{i = 1}^{q}a_{ji}(M_i - m_i)\leq q\times q = q^2$ (if $ a_{ji} = 0$, it doesn't affect the sum, if it is $ 1$, $ M_i = q,m_i = 0$, and if it is $ - 1$, $ M_i = 0,m_i = q$). From this we conclude that there are at most $ (q^2 + 1)^p = (q^2 + 1)^{q/2}$ possible values for the vector $ (a_{11}x_{1} + \ldots + a_{1q}x_{q},\cdots,a_{p1}x_{1} + \ldots + a_{pq}x_{q})$. But we have that: $ (q + 1)^q - 1 = (q^2 + 1 + 2q)^{q/2} - 1 =$ $ = (q^2 + 1)^{q/2} + \left( - 1 + \sum_{j = 1}^{q/2}{{q/2}\choose j}(q^2 + 1)^{q/2 - j}(2q)^j\right) > (q^2 + 1)^{q/2}$ We conclude that by the pigeonhole principle there are two distinct vectors being mapped to the same vector. Taking their difference we have a vector with the desired properties.