Question

в городе 2001 телефон, и каждый соединен с некоторыми другими. может ли случиться, что каждый телефон связан ровно с 15-ю другими

Answer 1

Построим граф, где вершинами будут телефоны, а рёбрами - возможность позвонить c телефона на телефон. Если допустить, что такой граф существует, то получим, что в нашем графе 2001 нечетных вершин, а этого быть не может.

Answer 2

Да, такое возможно.

Для того чтобы каждый телефон был связан ровно с 15-ю другими телефонами, всего должно быть 2001 телефон и общее количество соединений равно:

2001 телефон * 15 соединений на каждый телефон = 30015 соединений.

Однако, каждое соединение соединяет два телефона, поэтому общее количество соединений должно быть четным числом. В данном случае, 30015 является нечетным числом, а значит, невозможно установить ровно 15 соединений для каждого из 2001 телефона.