Question

В группе из трёх мальчиков и трёх девочек каждый мальчик знаком только с двумя девочками и каждая девочка знакома только с двумя мальчиками.
Докажите возможность составления таких трёх пар, чтобы попавшие в одну пару мальчик и девочка были знакомы между собой.

Answer 1

М-1, М-2, М-3 - мальчики

Д-1, Д-2, Д-3 - девочки.

Допустим, М-1 знаком с Д-1 и Д-2, М-2 также знаком с Д-1 и Д-2. Выходит, что у Д-1 и Д-2 уже есть по 2 знакомых мальчика. Значит, М-3 может быть знаком только Д-3, а Д-3 - только с М-3, что противоречит условиям задачи. Значит никакие 2 мальчика не знакомы с одними и теми же двумя девочками и наоборот - никакие 2 девочки не знакомы с одними и теми же двумя мальчиками.

Но при этом, из любых двух мальчиков оба знают одну и ту же девочку и наоборот - из любых двух девочек обе знают одного и того же мальчика.

Значит, составление таких трёх пар, чтобы попавшие в одну пару мальчик и девочка были знакомы между собой, возможно.