Browse · MathNet
PrintIreland
Ireland counting and probability
Problem
A Dutch hillwalking club with members arranges a series of walks over a number of weekends, according to the following rules. (a) Two walks take place each weekend – one takes place on Saturday, and the other on Sunday. (b) Exactly members of the club participate in each walk. (c) On any weekend, no club member participates in both walks. (d) After all walks are concluded, every pair of club members has participated together in the same number of walks. Prove that after all walks are concluded, every set of three club members has participated together in the same number of walks, and that this number is divisible by .
Solution
Suppose that each pair of club members participates together in walks. The total number of walks organised by the club is then given by since the right-hand side counts the total number of walks by considering all pairs of club members and using rule (d), but counts each walk times. Simplifying, we obtain . Since is relatively prime to and , we must have , i.e. , and so (for some positive integer ). From rules (b) and (c), each club member takes part in exactly walks.
Next, let denote the set of walks in which club member participates, let denote the set of walks in which club members and participate, and let denote the set of walks in which club members , and participate. Then we have for all , and for all . Rules (b) and (c) tell us that for any set of three distinct club members , the number of walks featuring but not or is equal to the number of walks featuring and but not . We may write this as or (rearranging) or . As this formula holds for any set of three distinct club members , the result follows.
Next, let denote the set of walks in which club member participates, let denote the set of walks in which club members and participate, and let denote the set of walks in which club members , and participate. Then we have for all , and for all . Rules (b) and (c) tell us that for any set of three distinct club members , the number of walks featuring but not or is equal to the number of walks featuring and but not . We may write this as or (rearranging) or . As this formula holds for any set of three distinct club members , the result follows.
Techniques
Counting two waysInclusion-exclusionGreatest common divisors (gcd)