Looking for a problem where one could use a cardinality argument to find a solution. I would like to find an exercise of the type: Find some $x$ in $A\setminus B$. Solution: since $A$ is uncountable and $B$ is countable such $x$ exists... 
 A: The classical result presented by Cantor himself: Prove that there exists a real number that is not algebraic.
Remark: the fact that non-algebraic numbers exist was known before, but Cantor presented the proof of the uncountability of the reals and derived from it a very simple existence proof exactly using what you are asking about, using such a technique for the first time. 
A: Some ideas:

*

*Prove that there exists an irrational number.

*Prove that there exists a sequence of irrational numbers converging to any real number.

*Prove that there exists a subset of the integers which is neither finite nor co-finite.

*Prove that there exists a function $f\colon\Bbb{R\to R}$ which is discontinuous everywhere (replace "countable" with "size continuum" and uncountable with "larger than the continuum").

*There exists a number in the Cantor set which is not the endpoint of an interval disjoint from the Cantor set (the complement of the Cantor set can be written as a countable union of disjoint intervals, so there are only a countable number of endpoints which are elements of the Cantor set).

*There exists a normal number.

*There exists a linear functional on $(\Bbb R[x])^\ast$ which is not an evaluation functional (the dimension of $\Bbb R[x]$ is countable, and therefore the dimension of the evaluation functionals is countable; but $(\Bbb R[x])^{**}$ has an uncountable dimension).

A: One example which I quite like is this:

Show that there are points in the plane which cannot be constructed from unit segment using just compass and straightedge.

The cardinality based proof is simple: We are starting with two points, at each step of construction we can only add finitely many new points and we employ constructions which only have finitely many steps. So the set of all constructible points is countable. The set of all points in the plane has cardinality of continuum, it is uncountable.
The students will probably see in some algebra course1 proofs showing that some particular lengths (such as $\sqrt[3]2$ or $\cos\pi/9$ cannot be constructed). But this proof can be considered simple and it also works for other constructions of similar type. (I.e. constructions with finitely many steps where only finitely many new objects are added in each step.)
1 I would guess that typically cardinalities appear in a curriculum before the course of algebra which includes result needed for proving impossibility of trisecting an angle or doubling a cube. But perhaps somewhere these topics are taught in a different order.
A: *

*There is a function $f : \mathbb{N} \to \mathbb{N}$ not computable by a Turing machine.  (Or there is a real number whose decimal expansion cannot be so computed.)

*There is a non-Borel subset of $\mathbb{R}$.  (Cardinality $\mathfrak{c} = 2^{\aleph_0}$ vs. cardinality $2^{\mathfrak{c}}$.)

