Draw traces along two identical papers arbitrarily so that each one is divided into $k$ parts of the same size. Place $k$ pins through them with their boundaries coincided. Show that there exists a certain placement of the pins so that when the papers break apart along the traces drawn on them, each fragment has at least one pin through it.
I hope the question is clear enough with this picture.
I thought that since I have no idea how the paper was divided, I'd better consider it as a graph-theory problem instead of a combinatoric geometry problem.
So I construct graph with $2k$ vertices $a_1,\ldots,a_k;b_1,\ldots,b_k$ representing the fragments. Construct sides between fragments which have common area. If this can be proven:
There exists a one-one mapping between $\{a_1,\ldots,a_k\}$ and $\{b_1,\ldots,b_k\}$ so that each mapped pair are connected.
The problem would be solved.
Consider the bipartite graph $G$ on $k+k$ vertices where each vertex represents a fragment and each edge connects two overlapping fragments (one in each sheet). Since all fragments are the same size, given any subset $S$ of fragments in sheet $1$ with cardinality $n$, at least $n$ fragments in sheet $2$ are needed to completely overlap $S$.
Hall's marriage theorem and the symmetric argument with respect to swapping sheets together guarantee a perfect matching in $G$. For each edge in such a matching you push a pin; after splitting the fragments, all of them are guaranteed to have been pierced by a pin as required.