Proof: Let $N$ be the number of toothpicks left on the table.
Note that $N \mod 3 = 0$ is equivalent to $N = 3k$ for some $k \in \mathbb{Z}$.
$\rightarrow$ Assume $P_1$ will win if $N = 3k$.
Let $k = 1$, so $N = 3(1) = 3$. We know that if $N = 3$, $P_2$ will win, giving us a contradiction.
So we know that $P_1$ will not win if $N = 3k$.
$\leftarrow$ Assume if $N = 3k$ then $P_1$ will win.
We know that $P_1$ will win if $N = 1$ or $N = 2$ and $P_1$ will not win if $N = 3$.
So $P_1$ will win if $3k = 1$ or $3k = 2$
Since $k \in \mathbb{Z}$, this gives a contradiction.
$\therefore P_1$ will win $\iff N \mod 3 \ne 0$. $\square$
Attempted a proof.
Theorem 1: $P_1$ will win $\iff N \mod 3 \ne 0$
Proof: Let $N$ be the number of toothpicks left on the table.
Note that $N \mod 3 = 0$ is equivalent to $N = 3k$ for some $k \in \mathbb{Z}$.
$\rightarrow$ Assume $P_1$ will win if $N = 3k$.
Let $k = 1$, so $N = 3(1) = 3$. We know that if $N = 3$, $P_2$ will win, giving us a contradiction.
So we know that $P_1$ will not win if $N = 3k$.
$\leftarrow$ Assume if $N = 3k$ then $P_1$ will win.
We know that $P_1$ will win if $N = 1$ or $N = 2$ and $P_1$ will not win if $N = 3$.
So $P_1$ will win if $3k = 1$ or $3k = 2$
Since $k \in \mathbb{Z}$, this gives a contradiction.
$\therefore P_1$ will win $\iff N \mod 3 \ne 0$. $\square$