Competition problem — Combinatorics

Library / /14 of 61

Combinatorics Difficulty 5.7 AIME, harder Prove it Belarus

$2n$ girls and $2n$ boys take part in a dancing party. It is known that Bob has a dance with every girl, and Ann has a dance with every boy. Moreover, for any two girls the number of the boys who have a dance with exactly one of these two girls is equal to $n$ .

Prove that

a) any girl, except for Ann, has a dance with exactly $n$ boys;

b) any boy, except for Bob, has a dance with exactly $n$ girls.

Solution

We use the solution of Problem A.8.

a) Let Ann get number $1$ . Each vector $S_i$ , $i \neq 1$ differs from $S_1$ at exactly $n$ positions and all entries of $S_1$ are equal to $1$ . Therefore, $S_i$ have exactly $n$ entries equal to $1$ , which proves the statement.

b) The same proof as in a). We consider the columns instead of the rows.

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.