To satisfy the sticklers, you'll need to use or prove the fact that a square matrix is symmetric and skew-symmetric iff it's a zero matrix, and to show there's exactly one suitable decomposition you must provide it as $A=\frac{A+A^T}{2}+\frac{A-A^T}{2}$.
Another strategy that doesn't require a proof by contradiction is to note symmetric $B$ and skew-symmetric $C$ satisfy $A=B+C$ iff $A=B+C$ and $A^T=B-C$, i.e. iff $B=\frac{A+A^T}{2}$ and $C=\frac{A-A^T}{2}$. This has the advantage that you prove both parts (at most one, at least one) in a single step.
The matrix $M$ is skew symmetric if $M^T=-M$. A general skew symmetric 3x3 matrix has only 3 independent entries.
$$M=\left(
\begin{array}{ccc}
0 & m_{12} & m_{13} \\
-m_{12} & 0 & m_{23} \\
-m_{13} & -m_{23} & 0 \\
\end{array}
\right)
$$
You can use the Rule of Sarrus to make sure $\det(M)=0$.
In a more general setting, the determinant of the skew symmetric $nxn$ matrix is
$$\det(M)=\det(M^T)=\det(-M)=(-1)^n\det(M)$$
where we have used some basic properties of determinants. For odd $n$ this means $\det(M)=-\det(M)$ so $\det(M)=0$. This is sometimes called Jacobi's theorem after Carl Gustav Jacobi.
When $\det(M)=0$ the matrix is singular and the dimension of the column space must be less than $n$.
Further, if the 3x3 matrix $M$ above is $\neq \mathbf{0}$ at least one of $(m_{12},m_{13}, m_{23})$ must be nonzero. But as the entries come in pairs over the diagonal, setting one of them to a nonzero value means at least two columns are linearly independent (convince yourself by setting for example $m_{12}=1$ and notice that column 1 and column 2 are now linearly independent). Armed with this knowledge of 3x3 skew symmetric matrices we are ready to continue our adventure
Since $M$ is an odd dimension skew symmetric matrix the determinant is zero and the dimension of its column space $W$ is at most 2 (Jacobi's theorem). But since $M\neq 0$ and skew symmetric the dimension of $W$ must be at least 2. Hence the dimension of $W$ is exactly 2. This also means that at least two of the columns are $\neq \mathbf{0}$. We say that the columns of $M$, lets call them $(M_1,M_2,M_3)$, spans $W$.
The subgroup of orthogonal matrices with determinant +1 is called the special orthogonal group, denoted SO(3). Every rotation can be represented uniquely by an orthogonal matrix with unit determinant. We are free to pick ANY $A\in \text{SO(3)}$. Let $A$ be a proper $\frac{\pi}{2}$ rotation ($\det\,A=1)$ around a vector in the plane perpendicular to one of the nonzero columns $M_i=v$. The rotated vector $Av$ is clearly not in $W$.
Hence, with our chosen rotation matrix $A$, at least one of the columns of the product $AM=[AM_1\,AM_2\,AM_3]$ has left $W$ completely. It is impossible for $AM$ to equal $cM$ where $c$ is a constant for this specific choice of $A$.
Best Answer
This is known as “Tucker’s theorem”, “Tucker’s existence lemma” or “Tucker’s theorem of alternative” in the literature.
A proof attempt had been made by user “sourisse” on this site before, but the proof is incomplete. Below is a fix.
Let $A$ be an $n\times n$ real skew-symmetric matrix and $i\in\{1,2,\ldots,n\}$. By Farkas’ lemma, either there exist some vectors $v\ge0$ and $w\ge0$ that satisfy $$ \pmatrix{-A&I}\pmatrix{v\\ w}=-e_i $$ or there is some vector $y$ such that $$ y^T\pmatrix{-A&I}\ge0 \quad\text{and}\quad y^T(-e_i)<0. $$ In the former case, we have $Av=w+e_i$. Hence $v\ge0,\,Av\ge0,\,Av+v\ge0$ and $e_1^T(Av+v)>0$.
In the latter case, we have $-y^TA\ge0$ (i.e., $Ay\ge0$ because $A$ is skew-symmetric), $y^T\ge0$ and $y^Te_i>0$. Hence $y\ge0,\,Ay\ge0,\,Ay+y\ge0$ and $e_i^T(Ay+y)>0$.
So, in either case, we have, for each $i$, some vector $x^{(i)}\ge0$ such that $Ax^{(i)}\ge0,\,Ax^{(i)}+x^{(i)}\ge0$ and $e_i^T(Ax^{(i)}+x^{(i)})>0$. Now take $x=\sum_{i=1}^nx^{(i)}$ and we are done.