I got this problem and its solution from Rustan Leino, who got this problem many years ago, likely from Jan van de Snepscheut.

You're given a 3x3x3 cube of cheese and a knife. Your goal is to divide the cheese into 27 1x1x1 cubes, using as few straight cuts as possible. You may not modify any piece of cheese's shape other than with a cut, and you may not move the cheese during a cut.

It's possible to do this with six cuts. Prove that it's not possible with fewer.

When you're done, one of the 27 cubes is the original center of the 3x3x3 cube. None of this center cube's sides existed in the original block, so all of them must have been created by cuts. There are six such sides, and no pair of them are coplanar, so you must have needed six cuts.