SCHOOL OF COMPUTER SCIENCE

Puzzle 4: Vacancy Puzzle

The premature retirement of the beloved leader Aldan has left a vacancy on the ruling triumvirate of the Malthusian city of Zocor. There are two political parties, The Meat Lovers Party (MLP)and the Vegetarian Party of the People (VPP). At present each party has one representative in the triumvirate, with the MLP representative Arctan being the most senior.The other ruling member being Arcsin.

The arcane voting rules for replacing Aldan are as follows. There is a large Praesidium with n people in it. At the moment all the members are in the VPP. Each member has an integer valued priority. The selection process will now go in rounds: At the beginning of a round Arcsin will propose some subset S of the remaining candidates C of the Praesidium. (Initially C will be the whole Praesidium). Arctan then has two choices. He can devour S, but then he is forced to decrease the priority value of each member of C \ S by one. Alternatively, he can devour C \ S and decrease the priority values of the members of S by one.

The process continues until one of two things happen: The whole Praesidium has been eaten and then Arctan can choose any member of his party to fill the vacancy. The other possibility is that someone will reach priority zero and then Arcsin can choose any zero priority person to fill the vacancy. Given that the initial priorities are a1, a2, .... an, which party will get to fill the vacancy?

  Solution

< back to the main puzzle page