A visitor at a political convention with n delegates

Question

So I have been asked to specifically construct a divide and conquer algorithm for the question:

"You are a visitor at a political convention with n delegates; each delegate is a member of exactly one political party. It is impossible to tell which political party any delegate belongs to; in particular, you will be summarily ejected from the convention if you ask. However,you can determine whether any pair of delegates belong to the same party or not simply by introducing them to each other—members of the same party always greet each other with smiles and friendly handshakes; members of different parties always greet each other with angry stares and insults.

Suppose more than half of the delegates belong to the same political party. Describe an efficient algorithm that identifies all members of this majority party. How many introductions do you need?

So I came up with the pseudocode:

AMajorityPolitician(set of politicians S):

 if |S| == 1 :
  return S
 L = AMajorityPolitician(half of S)
 R = AMajorityPolitician(other half of S)

 if party[first item in L] == party[first item in R]:
  return L U R
 else
  return max(|L|,|R|)

AllMajorityPolititians(set S of n politicians):

 M = AMajorityPolitician(S)

 first = first item of M

 ans = {first}
 for each p in S:
   if first smiles to p:
     ans = ans U {p}

 return ans

But I don't think this works because if I have a list of politicians parties such as: 2,2,1,1,1 and it is split s.t. L=2,2,1 and R=1,1 then majority of L is party 2 of size 2 and majority of R is party 1 of size 2 so algorithm could pick 2 as the majority.

But I don't really know where to go from here to fix it. Do you guys have any suggestions?

Answer 1

You need to make sure what is returned from AMajorityPolitician(set of politicians S) is indeed a politician from the majority in S if there is a majority.

To ensure majority, we need to count the number of politicians who are in the same party as the chosen one. Here is the simple routine.

def number_of_friendly_politicians(person, all_people):
    count = 0
    for p in all_people:
        if smiles_between(person, p):
            count ++;
    return count

Now refactor AMajorityPolitician to the following function, which returns a majority politician in politicians whenever there is a majority.

def a_majority_politician(politicians):
    if size(politician) is 1:
        return that person

    L = a_majority_politician(half of politicians)
    R = a_majority_politician(other half of politicians)

    if number_of_friendly_politicians(L, politicians) * 2 > size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.