A visitor at a political convention with n delegates
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 &gt; size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.