Library / All-Soviet-Union Mathematical Olympiad /46 of 185

All-Soviet-Union Mathematical Olympiad

Combinatorics Difficulty 4.7 AIME Prove it Soviet Union

Problem:

A group of 100 people is formed to patrol the local streets. Every evening 3 people are on duty. Prove that you cannot arrange for every pair to meet just once on duty.

Solution

Solution:

Every time a person is on duty he is paired with two other people, so if the arrangement were possible the number of pairs involving a particular person would have to be even. But it is $99$ .

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

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