TOT 146 1987 Spring Main S3 exchanges of apartments in a city
Source:
April 17, 2020
combinatorics
Problem Statement
In a certain city only simple (pairwise) exchanges of apartments are allowed (if two families exchange fiats , they are not allowed to participate in another exchange on the same day). Prove that any compound exchange may be effected in two days. It is assumed that under any exchange (simple or comp ound) each family occupies one fiat before and after the exchange and the family cannot split up .(A . Shnirelman , N .N . Konstantinov)