MPMP17 - Cats and Dogs

cats-and-dogs.md

This is the seventeenth puzzle in Matt Parker's Matt Parker's Maths Puzzles puzzle series

Cats and Dogs

As the owner of a pet hotel, you have ten kennels in a row that you can put either a cat, or a dog into each night. Cats, being as they are, are not happy when placed adjacent to other cats. Dogs do not mind who they are next to though.

How many different ways are there to put cats and dogs into the ten kennels, such that no two adjacent kennels both contain cats?

Solution

My first intuition is that this feels like a highly recursive problem. Perhaps we can calculate the answer for ten kennels if we knew the answer for nine, or something like that. Lets define some notation:

• C_n will be the number of ways to fill the first n kennels such that there is a cat in the nth kennel.
• D_n will be the number of ways to fill the first n kennels such that there is a dog in the nth kennel.

Now we can notice a recurrence relation between these C_n and D_n.

This is because a cat can only be next to a dog, and a dog can be next to either a cat or a dog.

We also have an obvious base case: There is only one way to put a cat or a dog in the first kennel. So C₁ = D₁ = 1.

Now the total number of ways to fill ten kennels will be the sum of C₁₀ and D₁₀; 144 ways.

Here is some python code!

def possiblePetHotels(numKennels):
    """
    Counts the number of ways to allocate either a cat or a dog to a number of
    kennels in a row such that no two adjacent kennels both contain a cat.
    """
    # How many ways to fill the first n kennels with a cat in the nth kennel.
    C_n = 1
    # How many ways to fill the first n kennels with a dog in the nth kennel.
    D_n = 1

    for _ in range(numKennels - 1):
        # A cat can only be next to a dog.
        # A dog can be next to a cat or a dog.
        C_n, D_n = D_n, C_n + D_n

    return C_n + D_n

This recurrence relation is the same as the fibonacci numbers.