© Till Hausdorf, MATH+
Author: Clara Stegehuis (Universiteit Twente)
Project: European Women in Mathematics – The Netherlands (EWM-NL)
Challenge
Ada Lovelace was one of the first female computer scientists and is an old friend of Santa. She was also one of the first people to recognize that computers cannot only solve difficult equations and approximate numbers, but can also be used to implement algorithms. Now, Santa needs Ada’s help to develop an algorithm for the following difficult task.
Santa is packaging and sending presents arranged in finite lines in his storage space. Presents can only be sent if they are properly packaged (P). However, for some presents the packaging material has been damaged (D).
When Santa sends out a properly packaged present, the adjacent presents change their status:
- P→D: If the present was properly packaged, then Santa—being the clumsy fella we know and love—manages to damage it.
- D→P: If the present was damaged, then Santa’s little helpers—who are always at his side—repair it so that it is properly packaged afterwards.
The presents are sent one after another. Once a present is sent, it leaves a hole in the line. The presents next to the hole will not be regarded as being adjacent to one another. Yesterday’s first two shippings of Santa’s presents are depicted below:
The initial line in the example consists of seven presents. In the first step, the 4th present (in red) is sent. Hence, the status of two adjacent packages (in blue) is changed from D to P and P to D, respectively. In the second step, the 3rd package (again in red) is sent. It has only one neighbour (again in blue), whose status is then changed from P to D.
Of course, Santa would like to send out all packages of any given line; that is, for a given initial line of presents, he wants the above process to end with an empty line. Although Santa can choose the order in which he sends out the presents, he sometimes gets stuck with only damaged presents (which he cannot send). Santa believes that his friend Ada Lovelace will be able to create an algorithm that solves his shipping problem.
For which initial lines of presents does there exist a shipping algorithm that ends with an empty line?
Possible answers:
- For every initial line of presents that contains at least one properly packaged present.
- For every initial line of presents that contains at least one properly packaged present, and where properly packaged presents are only adjacent to damaged packages.
- For every initial line of presents that contains at least one properly packaged present, and where damaged presents are only adjacent to properly packaged packages.
- For every initial line of presents with an odd number of properly packaged presents.
- For every initial line of presents that contains at least one properly packaged present and with an odd number of damaged presents.
- For every initial line of presents with an odd number of presents that contains at least one properly packaged present.
- For every initial line of presents with an even number of properly packaged presents.
- For every initial line of presents with at least three adjacent properly packaged presents.
- For every initial line of presents with properly packaged presents at both ends of the line.
- For every initial line of presents that contains at least one properly packaged present and with at least three adjacent damaged presents.
Sunday Bonus: For this challenge, you will get a time bonus of 24 hours.
Project reference:
EWM-NL is the national association of women working in the field of mathematics in The Netherlands. Established in 2013, EWM-NL has several hundred members from academia, industry, and society at large. EWM-NL organises several events per year, typically open to all, offers career support grants and maintains a mentor network.