Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Fill the vacancy

Question

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?

Share this post


Link to post
Share on other sites

3 answers to this question

  • 0

I don't have a full solution, but this might help get things started.

Spoiler

 

Describe the Praesidium as a vector (n1, n2, n3, …) where nm is the number of people in the Praesidium of priority m. So a Praesidium of (2, 5, 0, 1) would have eight people: 2 of priority one, 5 of priority two, and 1 of priority four.

First note that Arcsin can win if there are at least 2m people of priority m for any value of m. Just put 2m-1 people in S so there are also at least 2m-1 people in not(S), and Arctan will have to leave at least 2m-1 of them who will be priority m-1 in the next round. Keep repeating that, and you'll get 21 people of priority 1 and one of them will get through the next round to reach priority zero. Conversely, if the Praesidium is filled only with people of one priority level (call it m) and there are fewer than 2m people, then Arctan can just keep eating whichever of S or not(S) has the most people and will eat them all before any reach priority zero.

The interesting stuff happens when there are people at multiple different priority levels, but there are fewer than 2m people at any given priority level. As a simple example of that, consider the Praesidium (0, 2, 5). If Arcsin just split people into S and not(S) evenly [like making (0, 1, 2) and (0, 1, 3)] then Arctan would just eat the larger one and the next round would be (1, 2), then Arctan would eat whichever of S or not(S) holds the priority one person to make it (1) in the next round, and then Arctan would win. But instead if Arcsin started off by making S and not(S) be (0, 2, 0) and (0, 0, 5), then the next round would either be (2) or (0, 5), and either of those situations would be an easy win for Arcsin because they have nm > 2m.

Let's try to generalize that. Suppose there is some priority level m with at least 2m-1 people. Then Arcsin could make one group S with 2m-1 people of priority m and the other group not(S) containing the rest of the Praesidium; Arctan would have to eat S or else he would be in a losing situation, and proceeding to the next round would have converted everyone in not(S) to one lower priority level. So if there are two priority levels with nm at least 2m-1 (call them ma and mb) then Arcsin can win: put 2ma-1 priority ma people in S and pub 2mb-1 priority mb people in not(S). Or if there's a priority level m with at least 2m-1 people and two different priority levels mc and md with 2mc-2 and 2md-2 people, then Arcsin could make S be 2m-1 people of priority m so Arctan has to eat them with everyone else in not(S) and then could with because mc-1 and md-1 now both hold 2m-1 people. In general terms, you can calculate the vector where each term is given by (m - log2 nm), and if there is any series of terms with at least one value less than or equal to 1, at least one value less than or equal to 2, at least one value less than or equal to 3, etc eventually reaching some point where there are two or more values less than or equal to that number, then Arcsin could win.

That vector can come in handy, so I'll define it as a term for the next paragraph. Since using "l" or "o" from "log" could get confusing: gm = m – log2 nm, and call gm undefined if nm = 0 and omit such terms from the vector.

Now consider cases where there's not a series of gm terms going 1, 2, 3, …, x, x to give Arcsin a win with that approach. Suppose the gm vector looks like (3, 2, 3, 2, 3, 3). Arcsin could put everyone from both priority levels with gm = 2 into S and put everyone from the four priority levels with gm = 3 into not(S). If Arctan doesn't eat S, then there would be two priority levels with gm = 1 in the next round so Arctan would lose, so Arctan must eat S. Then the next round would have four priority levels with gm = 2. Arcsin could put everyone from two priority levels in S and everyone from two other priority levels in not(S), so no matter what Arctan does there will be two priority levels with gm = 1 in the next round and Arcsin could win.

Stated in more general terms, you can take the gm vector and calculate a new vector ngm which is a count of all gm terms over the range (m-1 to m] (excluding m-1 but including m), and if ngm is at least m, or if there is a series of terms ngm – m incrementing from 1 upward until there are two terms of the same value, then Arcsin could win.

 

After that point, it gets too abstract for me to continue comprehending.

Share this post


Link to post
Share on other sites
  • 0
On 12/13/2018 at 2:16 PM, CaptainEd said:

Plasmid, In what sense is this not a total solution?

Well, I've shown a lot of ways where Arcsin could win, but I don't actually prove that Arctan can win in cases that aren't covered in the above ramblings. An ideal solution would be along the lines of: "If the composition of the Praesidium meets these criteria then Arcsin has a strategy that's guaranteed to win, and if it doesn't fit those criteria then Arctan has a strategy that's guaranteed to win."

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×