Maths Olympiad Prep

Library / /33 of 224

Algebra Difficulty 5.3 AIME, harder Prove it Belarus

2n2n girls and 2n2n boys take part in a dancing party. It is known that for any two girls the number of the boys who have a dance with exactly one of these two girls is equal to nn.
Prove that for any two boys the number of the girls who have a dance with exactly one of these two boys is equal to nn too.

Solution

Number girls and boys by numbers from 11 to 2n2n. For each ii-th girl we correspond a vector SiS_i with jj-th entry equal to 11 if the ii-th girl has a dance with the jj-th boy, and equal to 1-1 otherwise. Then the condition is equivalent to SiSjT=0S_i \cdot S_j^T = 0 for every iji \neq j, because SiS_i and SjS_j differ at exactly nn positions.

Define the 2n×2n2n \times 2n matrix SS with rows SiS_i, i=1...2ni = 1...2n. Then SST=2nIS \cdot S^T = 2nI, where II is the identity 2n×2n2n \times 2n matrix. This implies, that 12nST=S1\frac{1}{2n}S^T = S^{-1}. Therefore STS=2nIS^T \cdot S = 2nI, which means that every two columns differ at exactly nn positions, which is equivalent to the required statement.

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.