Maths Olympiad Prep

Library / /24 of 30

Combinatorics Difficulty 6.6 National olympiad Prove it Ireland

A Dutch hillwalking club with 4n4n 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 2n2n 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 tt of walks, and that this number tt is divisible by n1n-1.

Solution

Suppose that each pair of club members participates together in rr walks. The total number mm of walks organised by the club is then given by
m(2n2)=r(4n2), m\binom{2n}{2} = r\binom{4n}{2},
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 (2n2)\binom{2n}{2} times. Simplifying, we obtain 2r(4n1)=m(2n1)2r(4n-1) = m(2n-1). Since 2n12n-1 is relatively prime to 22 and 4n14n-1, we must have 2n1r2n-1 \mid r, i.e. r=(2n1)pr = (2n-1)p, and so m=2(4n1)pm = 2(4n-1)p (for some positive integer pp). From rules (b) and (c), each club member takes part in exactly m/2=(4n1)pm/2 = (4n-1)p walks.

Next, let SiS_i denote the set of walks in which club member ii participates, let Si,jS_{i,j} denote the set of walks in which club members ii and jj participate, and let Si,j,kS_{i,j,k} denote the set of walks in which club members ii, jj and kk participate. Then we have Si=(4n1)p|S_i| = (4n-1)p for all ii, and Si,j=r=(2n1)p|S_{i,j}| = r = (2n-1)p for all i,ji, j. Rules (b) and (c) tell us that for any set of three distinct club members {i,j,k}\{i, j, k\}, the number of walks featuring ii but not jj or kk is equal to the number of walks featuring jj and kk but not ii. We may write this as
SiSi,jSi,k+Si,j,k=Sj,kSi,j,k |S_i| - |S_{i,j}| - |S_{i,k}| + |S_{i,j,k}| = |S_{j,k}| - |S_{i,j,k}|
or (rearranging)
2Si,j,k=Si,j+Si,k+Sj,kSi=3(2n1)p(4n1)p=2(n1)p \begin{aligned} 2|S_{i,j,k}| &= |S_{i,j}| + |S_{i,k}| + |S_{j,k}| - |S_i| \\ &= 3(2n-1)p - (4n-1)p \\ &= 2(n-1)p \end{aligned}
or Si,j,k=(n1)p|S_{i,j,k}| = (n-1)p. As this formula holds for any set of three distinct club members {i,j,k}\{i, j, k\}, the result follows.

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 and solution reproduced as published; topic and difficulty added by this site.