Twenty Rooms

This problem is from the British Mathematical Olympiad. It is Problem 3 of the 2014 Round 1 paper. The problem states:

A hotel has ten rooms along each side of a corridor. An olympiad team leader wishes to book seven rooms on the corridor so that no two reserved rooms on the same side of the corridor are adjacent. In how many ways can this be done?

Python

A simple approach is to look through all possible combinations of 7 rooms that could be chosen. Start by defining an array to represent the state of the corridor at any moment.

x = [0 for i in range(20)]

Let 0 represent a room that is not chosen. 1 represents a room that is chosen. We ignore the 2 sides of the corridor for now because it makes little difference. Then look through each combination of 7 rooms out of 20.

combinations = []
total = 0

def combination(current_state, length, free_space):
    global total
    if length == 7:
        total += 1
        
        valid = True
        for i in range(9):
            if current_state[i] == current_state[i + 1] == 1:
                valid = False
        for i in range(10, 19):
            if current_state[i] == current_state[i+1] == 1:
                valid = False
        
        if valid:
            combinations.append(current_state.copy())
        return
    else:
        for i in range(free_space, 20):
            current_state[i] = 1
            combination(current_state, length + 1, i +   1)
            current_state[i] = 0

The total variable will allow us to check if the combination function has looked through every single combination. The length paramters tells the function how many rooms have been chosen, and the free_space variable tells the function where to look for the next room that is available to be chosen. Every time the function reaches 7 chosen rooms, it checks if the rooms from 0-9 (side 1), and the rooms from 10-19 (side 2) are adjacent. If the combination is valid, it adds the combination to the array combinations. Now execute:

permute(x, 0, 0)

print(len(combinations))
print(total)

Pass the arguments x (current state), 0 (since no rooms are chosen yet), and 0 (first available room is the room at index 0). len(combinations) correctly returns the output 4352, the answer to the problem. total is the total number of 7 room combinations the function checked through, and returns 77520. This is the number we expect, because 20 Choose 7 (20!/(7!*13!))) = 77520.