Question

Problem 1 (40 pts). The Stellar Federation consists of n + 1 planets. The Federal Government is on the planet Alpha. It provides services for all planets sending identical spaceships to them. Each spaceship has a schedule that says for each day of the Federal Month, which of the planet it is currently visiting or whether it is in the outer space. The Federal Month has m days and m > n. Each spaceship visits each planet exactly one day during the Federal Month with the restriction (*) no two spaceships can be at the same planet on the same day. The Federal Government decided to change its spaceships to more advanced ones. The Planet Governments asked to give old spaceships to them where each will be put in the Space Museum. The Federal Government consented to their request. The Technical Department of the Federal Government decided to do this by truncation each spaceship’s schedule in the following way: for each spaceship, there will be some day when it arrives at the scheduled planet and remains there for the museum without visiting the remaining planets in its schedule.

(1) Show that it is possible to do this satisfying the restriction (*).

(2) Give an algorithm for doing this.

Answer 1