Maths Olympiad Prep

Library / /6 of 86

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
A school needs to elect its president. The school has 121 students, each of whom belongs to one of two tribes: Geometers or Algebraists. Two candidates are running for president: one Geometer and one Algebraist. The Geometers vote only for Geometers and the Algebraists only for Algebraists. There are more Algebraists than Geometers, but the Geometers are resourceful. They convince the school that the following two-step procedure is fairer:

a. The school is divided into 11 groups, with 11 students in each group. Each group elects a representative for step 2.

b. The 11 elected representatives elect a president.

Not only do the Geometers manage to have this two-step procedure approved, they also volunteer to assign the students to groups for step 1. What is the minimum number of Geometers in the school that guarantees they can elect a Geometer as president? (In any stage of voting, the majority wins.)

Solution

Solution:
To ultimately win the election in step 2, the Geometers must have 6 seats among the 11 representatives who elect the president.

Moving back to step 1, the Geometers need 6 out of 11 votes in a group to elect a representative from that group. Thus, it takes 6×6=366 \times 6=36 Geometers to elect 6 representatives and thereby win the presidency.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.