Problem 5, 2004

A merchant has to ferry seven goods across a river: a piece of cheese, a mouse, a rat, a cat, a dog, a wolf and a bear. His boat has room for only \(k\) of the seven at a time. If they are left without him:

the mouse eats the cheese; the rat eats the mouse or the cheese; the cat eats the rat or the mouse; the dog kills the rat or the cat; the wolf kills the dog or the cat; the bear kills the dog or the wolf.

While the merchant is present none of this happens. Determine the smallest \(k\) for which he can be certain of getting all seven goods safely to the other bank.