girls and 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 .
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 too.
Solution
Number girls and boys by numbers from to . For each -th girl we correspond a vector with -th entry equal to if the -th girl has a dance with the -th boy, and equal to otherwise. Then the condition is equivalent to for every , because and differ at exactly positions.
Define the matrix with rows , . Then , where is the identity matrix. This implies, that . Therefore , which means that every two columns differ at exactly 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.