Let $a$ and $b$ be sets such that there is a bijection $a\sqcup b\to a\times b$. Show, without assuming the Axiom of Choice, that there is either a surjection $b\to a$ or an injection $b\to a$.
Attempt of solution. Let $f$ be a bijection $a\times b\to a\sqcup b$. If $f(\{(x,y) : y\in b\})\subseteq a$ for some $x\in a$, we are done. Otherwise there is some $z\in f(\{(x,y) : y\in b\})\cap b$ for each $x\in a$. This gives an injection $a\to b$ (does it really?) whence there is a surjection $b\to a$ (is there really?).
Does my solution work? Does it work without AC?
No, your solution does not work because you appealed to the axiom of choice in choosing $z$ in order to define the injection.
Instead, use the fact that $f$ is a bijection to conclude that $f(\{(x,y)\mid y\in b\})\cap b$ creates a partition of $b$ indexed by $a$, and therefore defines a surjection from $b$ onto $a$.