Maths Olympiad Prep

Library / /6 of 16

Combinatorics Difficulty 5.0 AIME, harder Find the answer Italy

Problem:

Around a round table are seated, at constant distance from one to the next, 32 people. In how many ways is it possible to choose 3 of them so that pairwise they are neither adjacent nor diametrically opposite?

Pick one

Solution

Solution:

The answer is (C). Let us select the people one at a time. At the beginning we have no constraints, so we can choose the first person in 32 ways. We can now choose the second person in 28 ways, excluding from the 32 the person already selected, the two adjacent to them, and the one facing them. However, we cannot consider them all together, because depending on how we choose the second person, the third can be chosen in different numbers of ways.

- If we choose the second person among the two seats adjacent to the one diametrically opposite our first choice, this excludes only one seat, in addition to the three already blocked before and the two already taken. Indeed, of the two adjacent seats, one was already blocked (diametrically opposite the first) and only one is now blocked, while the one diametrically opposite it had already been excluded since it is adjacent to the first. So we can choose the third among 32132=2632-1-3-2=26 seats, for a total of 3222632 \cdot 2 \cdot 26 choices for this first case.

- If we choose the second person among the two seats near the two adjacent to our first choice, we exclude the seat just taken, one of the two adjacent seats (the other was already blocked), and the diametrically opposite seat. So we can choose the third among 32133=2532-1-3-3=25 seats, for a total of 3222532 \cdot 2 \cdot 25 combinations.

- If we choose the second person among the 24 remaining seats, once those of the two previous cases have been excluded, this choice excludes 4 seats (the one chosen, the two adjacent, and the opposite one), for a total of 32242432 \cdot 24 \cdot 24 combinations.

In total we then have 32(242+225+226)32\left(24^{2}+2 \cdot 25+2 \cdot 26\right) possible choices, to be divided by 3!=63 !=6 since we have taken into account the order in the choice of the people.

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 translated into English from it; metadata (topic, difficulty) added by this project.