I volunteered at the Julia Robinson Math Festival held at a nearby school last Saturday. It was a great event for kids in 4th to 9th grade in the area, featuring a room full of mathematical activity tables and raffle tickets to be given out as rewards for a good idea or explanation.
The table I was working at featured a number of problems about a “mad veterinarian”. He had a machine that you can feed two cats to and get a dog out. You can also feed it two dogs to get one dog out, and if you feed it a cat and a dog, you get out a cat. The veterinarian wants to end up with only one cat, and no other animals. Can he do this starting with three cats and one dog? How about four cats and two dogs?
After playing around with this a bit, one realizes that a simple parity argument shows which starting positions he can get just one cat from. But here’s a harder question:
He built a new machine that now can only accept two different types of animals, and returns either a dog, a cat, or a mouse, as follows. If you feed it a cat and a dog, you get out a mouse. If you feed it a dog and a mouse, you get out a cat. If you feed it a mouse and a cat, you get out a dog. Now, for which starting numbers of cats, dogs, and mice can he end up with exactly one cat in the end (and no other animals)?
Needless to say, it was a fun morning of mathematics. 🙂
Nice question! A fun thing to spot is that the mad veterinarian’s machines are just multiplication in the groups {cat, 1=dog} and {1, cat, dog, cat*dog=mouse}, which gives the parity relations immediately. (The restriction that the second machine only allows different animals to be ‘multiplied’ turns out not to be much of a restriction at all: a pair of animals of the same species can still be ‘cancelled’ (as they have order 2 in the group), but you need to go via an animal of another species – any one will do. So cancel off your cats in pairs, leaving just one, and then cancel off your dogs and mice in pairs. This is always doable as long as you don’t start off with lots of cats and no dogs or mice.)
Ah, that is a nice way of looking at it! So basically it’s Z_2 and the Klein four group – I didn’t realize that.
Yeah – these reminded me a lot of the symmetries of games like the 15-puzzle, nim and peg solitaire. The idea seems to be to choose a clever group G such that (1) we can label board positions / game states with an element of G in a natural way and (2) this element is invariant under legal moves of the game. I guess it was partly luck that the mad veterinarian’s machines corresponded to groups at all, but perhaps heuristically you’d only expect to get a nice answer if there are underlying symmetries. Not sure. Fun, anyway. 🙂
To be honest, I didn’t think of parity arguments, but instantly of type 1 formal grammar.
In between I thought, that it were even type 2, but then I noticed, that you need the rules to swap two animals.
But a really nice puzzle. I will suggest to put it on a CompSci example sheet. 🙂