Consider the following problem:
You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can be in a different order). Using balance scales (the outcomes are $>$, $=$ or $<$) at most $k$ times, determine whether the labels are correct.
I'm not exactly interested in how to solve the problem: the original problem was for $n=6$ and $k=2$, and I know solutions. What I'm interested in is the following: when I heard the problem, I first tried to determine whether a solution even exists from the information-theoretic standpoint. I.e. is the amount of information revealed by $k$ weighings even potentially enough? I don't know how to approach it.
For example, for $n=6$ and $k=2$ there exist $2$ solutions:
compare $1,2,3$ with $6$ and then compare $3,5$ with $1,6$
compare $1,3$ with $5$ and then compare $1,2,5$ with $3,6$
But if we estimate the amount of information naively, then we conclude that with $2$ weighings we can only distinguish $3^k=9$ permutations, which is much less than required $6!$.